发布时间 : 星期五 文章基于划分的聚类算法更新完毕开始阅读470d1ce32e60ddccda38376baf1ffc4fff47e24c
.
关，而与数据对象的数目无关.
1.2.5模型的方法(model-based methods)
基于模型的方法就是先给每一个聚类假定一个模型，再去寻找能较好的满足该模型的数据的集合。此模型也许是数据点在空间中的密度分布的函数，也许是其它.其潜在的假定为: 一系列概率的分布决定该目标数据的集合. 统计方案、神经网络方案通常是其研究的两种方向。
2 基于划分的聚类算法
给定一个数据集D，其包含有n个数据对象，用一个划分方法来构建数据的k个划分， 每一个划分表示一个类，且k≤n。根据D 的属性，使得同一类中的数据对象之间尽可能的“接近”，而不同的类中的数据对象之间尽可能的“远离”。
2.1 K-均值聚类算法
2.1.1K均值聚类算法[4]基本原理
随机选k个点作为初始的聚类的中心点，根据每个样本到聚类的中心之间的距离，把样本归类到相距它距离最近的聚类中心代表的类中，再计算样本均值.如若相邻的两个聚类中心无变化，调整立即结束，如若不然，该过程不断重复进行。其特点是:在每次迭代的时候，均要检查每一个样本分类，看该分类是否正确，不正确的话，就要在全部的样本中进行调整，调整好后，对聚类的中心进行修改，再进行下一次迭代；如若分类正确，聚类的中心就不再调整了，标准测度函数也就收敛了，算法也就结束了。
2.1.2K均值聚类算法步骤
输入项为:簇的数目k及包含有n个对象的数据的集合。输出项为:k个簇。具体的方法: 1）在数据的对象的集合中，任选k个对象作为初始的簇的中心； 2）依据簇中的对象的平均值，为每一个对象重新予以最相似的簇； 3）更新簇的平均值（即计算每一个簇中的对象的平均值）； 4）重复2）3）两个步骤； 5）一直到不再发生变化为止。
Word 资料
.
图 1 K-means算法过程示意图
Fig 1 K-means algorithm process diagram
2.1.3K均值聚类算法性能分析
优点:该算法的运算速度非常快，而且其结构也很简洁；其类簇之间的区别也很明显；最重要的是其时间复杂度为O（nkt），所以，在处理大型数据集时，它具有可伸缩性和高效性.其中，n是样本的数目，k是类簇的数目，t是迭代的次数，通常k≤n 且t≤n。缺点:该算法需要事先给定簇类的数目k；它不适合非凸形状的簇，也不适合存在大小差别很大的簇的数据的集合；其对数据集合内的噪声和离群点的敏感较高，因为此类数据也许会对均值造成一定的影响；因为其对初始中心的选择的依赖性较强，所以，产生局部的最优解发生的概率非常大。
2.2 K-中心点聚类算法
2.2.1K中心点聚类算法[5]基本原理
首先，针对每个类，先为其随机的选择一个实际样本，将其作为初始的中心点，而数据集内剩余的其他样本则依据其与中心点样本的相似度，将其分配到最相似的中心点所在的簇类内，然后，再选择新的中心点对象将原来的中心点对象替换掉，以此达到提高聚类质量（聚类质量是由数据集内的各个样本与所属簇的中心点间的平均相异度来度量的。）的目的，如此反复的选择，一直到聚类质量不再提高为止.用接近聚类中心的一个数据对象来表示K中心点聚类算法的簇，而在K均值聚类算法中，用该簇中数据对象的平均值来表示每个簇。
2.2.2最早提出的K中心点聚类算法
PAM[6]（Partioning around Medoid）是最早提出的K 中心点聚类算法.其原理为:先为每个类任选一个代表对象，而剩下的数据对象则根据其与代表对象的距离远近而相应的加入到最近的类中，再尝试着用非代表数据对象将代表数据对替换掉，如此反复尝试，直至收敛。
Word 资料
.
图 2 对象i被对象h替换的4种情况示意图
Fig 2 diagram of 4 cases of object I replaced by object h
为了判定一个非代表对象Oh是否是当前一个代表对象Oi的好的替代，对于每一个非中心点对象Oj，下面的四种情况被考虑：
? 第一种情况：假设Oi被Oh代替作为新的中心点，Oj当前隶属于中心点对象Oi。如果Oj离这个新的中心点Oh最近，那么Oj被分配给Oh。
? 第二种情况：假设Oi被Oh代替作为新的中心点，但是Oj当前隶属于另一个中心点对象Ot，t≠i。如果Oj依然离Ot最近，那么对象的隶属不发生变化。
? 第三种情况：假设Oi被Oh代替作为新的中心点，Oj当前隶属于中心点对象Oi。如果Oj离某个中心点Ot最近，i≠t，那么Oj被重新分配给Ot。
? 第四种情况：假设Oi被Oh代替作为新的中心点，但是Oj当前隶属于另一个中心点对象Ot，t≠i。如果Oj离这个新的中心点Oh最近，那么Oi被重新分配给Oh。
2.2.3 PAM算法步骤
输入项为:簇的数目k及包含有n个对象的数据的集合。输出项为:k个簇。具体的方法: 1）在数据的对象的集合中，任选k个对象作为初始的簇的中心；
Word 资料
.
2）对每一个由非中心对象h和中心对象i,计算i被h替代的总代价Tcih=?jCjih；
3）对每一个有h和i组成的对象对，如果Tcih<0,i被h替换，然后将每一个非中心点对象根据与中心点的距离分配给离它最近的中心点； 4）重复2）3）两个步骤；
5） 一直到不再发生变化为止。
2.2.4 K中心点聚类算法性能分析
K中心点聚类算法有很强的鲁棒性，因为它用簇内真实样本作为簇中心，这样可以降低噪音及离群点对聚类结果做产生的影响.但缺点是，它不适合于大型的数据集，由其初始的中心是随机选的，仍会存在局部最优解，且时间复杂度为O（k(n-k)2），时间复杂度较大。由此看来，只要确定恰当的聚类数目k 值及初始的聚类中心点，才能加快聚类过程的收敛的速度，以提高聚类的效率。
2.3 K-众数聚类算法
K—Modes聚类算法[7]是通过对K—Means聚类算法的扩展，使其应用于分类属性数据聚类．它采用简单匹配方法度量同一分类属性下两个属性值之间的距离，用Mode代替K—Means聚类算法中的Means，通过基于频率的方法在聚类过程中不断更新Modes．
相关性d的计算公式是比较两记录之间所有属性，如果属性不同则给d加1,如相同则不加，所以d越大，记录间的不相关程度越强。假设X，Y是数据集中的两个对象，它们用m维属性描述，则这两个对象之间的相异度为：d(X,Y)=
??(x,y),当
jjj?1m（xj,yj）xj=yj时，?=0；当xj?yj时，
?（xj,yj）=1。更新modes，使用一个簇的每个属性出现频率最大的那个属性值作为代表簇的属性
值（如{[a,1][a,2][b,1][a,1][c,3]}代表模式为[a,1]）。重新调整记录所属的簇，直到不会再产生变化。
2.4 K-prototypes聚类算法
K-Prototype算法[8]是结合K-Means与K-modes算法，针对混合属性的。解决两个核心问题如下:
度量具有混合属性的方法是，数值属性采用K-means方法得到P1，分类属性采用K-modes方法P2，那么D=P1+a*P2,a是权重。如果觉得分类属性重要，则增加a，否则减少a,a=0时即只有数值属性；更新一个簇的中心的方法，是结合K-Means与K-modes的更新。
2.5 基于划分的聚类算法研究现状
近几年来，人们对于基于划分的聚类挖掘技术的研究，研究最多的、发展较快的也就是对K 均值聚类算法的改进.Mac Queen 在1967 年提出了K 均值聚类算法的概念， 但该算法不能发现非凸面，而且，对噪声数据的敏感过强.于是，学者们又对其进行改进，在1990 年的时候， Rousseeuw 等人提出了PAM 和CLARA（Clustering Large Applications）算法。国内外研究者们大都把目光集中在聚类中心的初始化和聚类数目k 值的确定问题上，但是，聚类中心的初始化和聚类数目k 值并没有普遍适用的解决的办法。
Word 资料