http://download1.csdn.net/down3/20070522/22002507287.pdf 原文下载
应用粒子群最优化的文件聚类
崔晓慧，Thomas E. Potok，Paul Palathingal
应用软件工程学研究小组
计算科学与工程学部
橡树岭国家实验室
橡树岭，TN 37831-6085
cuix, potokte, palathingalp@ornl.gov
概要
快速与高质量的文件聚类在有效地导航，总结和组织信息方面起着重要的作用。最近的一些研究已经表明分割聚类算法更适合用来聚类大量的数据。然而，在分割算法中应用的最普遍的K均值算法，只能产生局部最优的解决方案。在这篇文章中我们提出了一种粒子群（PSO）文件聚类算法。与K均值算法的局部搜索相反，PSO聚类算法在整个解决空间中完成一次全局的搜索。在我们进行的实验中，我们分别在四组不同的文本文件数据集中应用了PSO,K均值和改进的PSO聚类算法。数据集中文件的数目覆盖了从204到大于800的范围，群的数目覆盖了从大于5000到大于7000的范围。结果表明，改进的PSO聚类算法与K均值算法相比能产生更紧凑的聚类结果。
绪论
文件聚类作为一种基本的操作被广泛应用于无人管理的文件组织，自动主体获取和信息恢复等领域。聚类涉及到将一系列的样本划分为指定的群数。聚类一系列数据的动机是寻找数据固有的结构并揭露这种结构作为一系列的种群。每个种群中的数据样本应该具有很大程度的相似性，而这种相似性与其他种群相比有应该最小[3，9，23，25]。目前有两种主流的聚类技术：“分割法”和“分等级法”[9]。大部分的文件聚类算法可归为这两类。分等级的方法产生一个分割的聚类序列，而且在这个序列的顶部有一个单独的、包含所有样本点的种群，底部有个别的点。分隔聚类方法寻找一种将文件归为不重叠类的分割，依此作为聚类的最小估计值。虽然分等级的聚类方法经常被描述为一种较高质量的聚类方法，但是这种技术不能包括样本分类的任一种约束条件，这样就可能会在文本分析的较早阶段得到较差的分类结果[9]。此外，这种方法的时间复杂度是二次的[23]。
近些年来，由于分割聚类技术只需要较低的计算要求，人们已经认识到分割数据技术更适合聚类较大量的文件数据集[23，25]。分隔聚类算法的时间复杂度是线性的，这使得它得到广泛的应用。最有名的分割聚类算法是K均值聚类算法和它的变种算法[11]。这种算法简单易懂而且基于稳定的变异分析基础。除了K均值聚类算法，其他一些算法，比如遗传算法（GA）[10，18]和自组织映射聚类算法（SOM）[14]也已经用于文件聚类。粒子群优化（PSO）[13]是另一种已经被应用到图像聚类和其他低空间维数的数据集中的智能算法[15，16]。然而，限于作者的认识，PSO聚类算法一直没有被应用到文本文件聚类领域中。在这篇论文中，一种基于PSO的文件聚类算法被提出。这篇文章剩余的组织结构如下：第2章介绍了用具类算法描述文件以及比较文件间相同点的方法。第3章介绍了K均值聚类算法和PSO聚类算法的概况。PSO聚类算法在第4章被详细描述。第5章介绍了详细的实验步骤和PSO算法与K均值算法的性能对比结果。同时给出了对于实验结果的分析讨论。结论在第6章给出。
2、基本知识
2.1、文件表示法
在大多数的聚类算法中，要聚类的数据集被描述为一系列的向量X={x1,x2….xn}，这里的向量xi相当于一个样本，可以称其为特征向量。特征向量应当具有合适的属性来描述这个样本。文本文件样本可以用向量空间模型（VSM）来描述[8]。在这个模型中，一个文件的内容被形式化为多维空间中的一个点，被标记为向量d，例如d={w1，w2，…，wn}这里的wi（i=1，2，…，n）是一个文件中组ti的条件权重。在一个文件中，条件权重值对于这个条件来说是很重要的。为了计算条件权重，我们必须考虑在一个文件和一系列文件中条件的出现频率。最常用的加权方案结合了条件频率与逆文件频率（TF-IDF）[8，19]。在文件j中，条件i的权重按下式计算：
w ji = tf ji ´ idf ji = tf ji ´ log2 (n / df ji ) (1)
这里的tfji是文件j中条件i的出现次数，dfji指出了文件归类过程中的条件频率，n是归类文件的总数。这种加权方案是低识别损耗与高频率词的折衷。
2.2、相似度度量
两个文件之间的相似度需要用聚类分析来计算。很多年来，有两种方法被用来计算文件mp和文件mj之间的相似度。第一种是基于Minkowski距离的方法，如下：
(2)
设n=2，我们获得了欧几里得距离。为了应用相等的开端距离，假设依据维数距离范围非常大，那么在向量空间中，大多数算法用格式化的欧几里得距离作为两个文件mp和mj之间的相似度度量。距离公式的计算如3所示：
(3)
这里的mp和mj是两个文件向量；dm表示向量空间的维数；mpk和mjk表示在第k维上文件mp和文件mj的权重值。另一种在文件聚类中常用的相似度计算方法是余弦相关方法[19，20]，如下：
(4)
这里的***是这两个文件向量的点积。|.|表示向量的长度。这两种相似度度量的方法在文本文件聚类文章中用都用的较为广泛。
3、背景
3.1、K均值聚类算法
K均值聚类算法简单易懂，而且基于变异分析的稳定基础。它将一组数据向量聚类为预先确定的群数。它从随机的初始聚类中心开始，依据数据样本和聚类中心的相似性，不断的分配数据集中的数据样本给聚类中心。再分配过程直到条件满足才结束（例如，最大的迭代次数或经过一定的迭代次数后聚类结果不再改变）。K均值算法可描述为：
（1） 随机选择聚类中心向量作为初始的集合划分。
（2） 将每个文件向量划分到离他最近的聚类中心的所在群中。
（3） 按式5重新计算聚类中心。
(5)
这里的dj是属于分类sj的文件向量；表示聚类中心向量；nj是属于分类sj的文件向量个数。
（4） 重复第2步和第3步直到达到收敛。
K均值算法的主要缺点是结果很大程度受初始聚类中心选择的影响，而且可能会落入局部最优[21]。因此，初始聚类中心的选择影响了K均值算法的主要处理，同时也影响了数据集的划分结果。K均值的处理过程是在临近的初始分类中寻找局部最优分类并优化划分结果。在一个数据集中相同的初始聚类中心总是产生相同的聚类结果。然而，如果能用其他技术获得较好的初始聚类中心，K均值算法在优化初始聚类中心得到最优聚类中心方面就能发挥较好的作用。
3.2、PSO算法
PSO算法是由艾伯哈特和肯尼迪于1995年提出的[13]，它来源于对鸟群社会行为的模拟。在PSO算法中，一只鸟群中的鸟被形象地比喻为一个粒子。这些粒子可以被想象为在一个问题空间中简单地飞行。在多维问题空间中一个粒子的位置表示问题的一个解。当一个粒子移动到一个新的位置，就会产生一个不同的问题解。这个解由一个适当的方程来评估，这个方程提供了解的效用的一些值。每个粒子在问题空间中沿每维运动的速度和方向将会随着每一代的运动改变。综合粒子本身的经验pid和其他粒子的经验pgd影响着每一个粒子在问题空间中的移动。随机值rand1和rand2用于处理的完整性，即确保粒子在收敛到最优解周围时能搜索一个较大的空间范围。c1和c2为调节pid和pgd相对重要性的参数以决定粒子的下一次移动速度。在每一代，粒子的新位置通过当前位置xid与粒子的当前速度vid相加来获得。在数学上由于多维空间的存在，第i个粒子按照如下方程来改变自己的速度和位置[13]：
vid = w´