论文部分内容阅读
【摘 要】传统的k均值算法对初始聚类中心敏感。在实际应用中，找到一组初始中心点，从而获得一个较好的聚类效果并消除聚类结果的波动性对k均值算法具有重要意义。本文对文献提出的基于Huffman树构造的思想选取初始聚类中心、基于均值-标准差选取初始聚类中心、基于密度选取初始聚类中心、采用最大距离积法选取初始聚类中心等4个算法从算法思想、关键技术等方面进行了比较研究。
【关键词】初始聚类；算法
1.引言
聚类分析是数据挖掘的功能之一，是在训练数据不提供类标号的情况下按照最大化类内对象间的相似性、最小化不同类对象之间的相似性的原则聚类和分组数据。通过自动聚类能够识别对象空间中稠密和稀疏区域，从而发现全局分布模式和数据属性之间有趣的相关性。
目前，存在着大量的聚类算法，K均值算法是应用广泛的聚类算法之一。1967年，MacQueen首次提出了K均值聚类算法，该算法的核心思想是找出k个聚类中心 使得每一个数据点xi和与其最近的聚类中心cv的平方距离和被最小化。首先，随机地选择k个对象，每个对象代表一个簇的聚类中心。然后，对剩余的每个对象，根据其与各个聚类中心的距离，将它指派到最相似的簇；计算每个簇的均值，将它作为新的聚类中心。不断重复这个过程，直到准则函数收敛。准则函数采用平方误差准则，定义如（1.1）所示：
（1.1）
K均值算法具有思想简单、时间复杂度接近线性、对大规模数据的挖掘具有可伸缩性等优点，但是也存在對聚类初始值的依赖、聚类个数K 需要预先给定、准则函数易陷入局部极小、对离群点敏感等缺点。K均值算法对聚类初始值的依赖表现在从不同的初始聚类中心出发，得到的聚类结果也不一样，并且一般不会得到全局最优解。在实际应用中，由于初始输入不同而造成结果的波动是不能接受的。因此怎样找到一组初始中心点，从而获得一个较好的聚类效果并消除聚类结果的波动性对k-means算法具有重要意义。本文分析比较了文献提出的几个初始聚类中心选取算法，这几个算法分别是：基于Huffman树构造的思想选取初始聚类中心、基于均值-标准差选取初始聚类中心、基于密度选取初始聚类中心、采用最大距离积法选取初始聚类中心等4个算法。
2.基于Huffman树构造的思想选取初始聚类中心算法
基于Huffman树的思想的K-均值聚类算法流程大体分三步：
1）根据Huffman树的思想。基于数据相异度，将数据样本构造成一棵树。根据算法的实际需要，在构造树的时候做了改变：对于构造树，不用左右子树根结点权值之和作为新的二叉树根结点，而是采用左右结点的算法平均值作为新的二叉树根结点的值。
2）对于构造出来的Huffman树，按构造结点的逆序找到k-1个结点，根据图论理论可知，去掉这k-1个结点可将树分为k个子树，这k个子树的平均值即初始的k个聚类中心点。
3）对于已得的k个初始聚类中心，按照K均值聚类算法进行聚类。
算法中的数据点之间的相异度度量采用欧式距离。用一个例子说明构造树并得到初始中心的过程，假设有一组数据（x1，x2，x3，x4，x5，x6）。它们对应的权值为（12，34，56，78，8，89），需要将这6个点聚成3类。过程如下：
1）首先根据欧式距离计算6个对象之间的相异度，得到相异度矩阵见式（2.1），
（2.1）
2）找到矩阵中最小值是4，也就是数据点x1（12）和x5（8）的相异度，计算这两点的算术平均值为10，将此平均值记为x11并且作为x1和x2中间结点加入树见图2.1（b）。在数据集中删除x1和x5，并将x11加入到数据集时得到新的数据集（x11，x2，x3，x4，x6）对应的值为（10，34，56，78，98），计算它们的相异度矩阵见式（2.2）
（2.2）
3）重复第（2）步直到数据集中只剩下一个对象。剩下的迭代过程相异度矩阵变化如图2.1，树的构造过程示意图见图2.2
4） 将数据集聚成3类，即k=3，在已构造出来的树（图2.2（c））中按结点构造的逆序找出k-1个点，即57.75和27.5，去掉这两点即可将构造树分为3个子树（x1，x5）、（x2，x3）、（x4，x6）， 对应树中的结点为（8，12）、（34，56）、（78，98）。三个子树的平均值10，45，88即为三个簇的初始中心点。
3. 基于均值-标准差选取初始聚类中心算法
由K均值算法可知，如果所选的初始聚类中心取在几个密集区域的中心，其周围的点越容易分布到最近的点，聚类收敛越快，所需要迭代的次数越少。其中涉及最优初始聚类中心点的选取。
若要分析所有数据的分布情况计算其分布密度，那是非常复杂的事。根据随机函数的分布知识，聚类的数据应主要分布在所有数据的均值附近。标准差是评价数据分布的又一重要标志。假设所有数据的均值为μ，标志差为σ，则数据应该主要分布在（μ-σ， μ+σ）之间。假设分类数为k，选择初始分类点为（μ-σ， μ+σ）之间的k个等分点进行。设第i类的初始分类中心为mi，公式如（3.1）所示，
（3.1）[3]
如果参与分类的是多维数据，如d维，则每个初始聚类中心的各个向量为（μl-σl，μl+σl）之间，设第i类聚类初始中心值为（mi1，mi2，…，mid），公式如（3.2）所示，
（3.2）[3]
4. 基于密度选取初始聚类中心算法
基于密度选取初始聚类中心算法描述如下：
输入：聚类个数k以及包含n个数据对象的数据集；
输出：k个初始聚类中心。
1）计算任意两个数据对象间的距离d（xi，xj）； 2）计算每个数据对象的密度参数，把处于低密度区域的点删除，得到处于高密度区域的数据对象的集合D；
3）把处于最高密度区域的数据对象作为第1个中心z1；
4）把z1距离最远的数据对象作为第2个初始中心z2，z2∈D
5）令z3为满足max（min（d（xi，z1），d（xi，z2）），i=1，2，…，n[1]的数据对象xi，z3∈D。
6）令z4为满足max（min（d（xi，z1），d（xi，z2），d（xi，z3））），i=1，2，…，n的数据对象xi，z4∈D。
7）令zk为满足max（min（d（xi，zj））），i=1，2，…，n，j=1，2，…，k-1[1]的xi，zk∈D.
从这k个初始聚类中心出发，应用k均值聚类算法，得到聚类结果。
5. 采用最大距离积法选取初始聚类中心算法
基于密度选取初始聚类中心法与随机初始化聚类中心相比，降低了对初始聚类中心的敏感性，在收敛速度、准确率方面都有了较大的进步。但由于它所选聚类中心遵从最小距离的思想，可能造成初始聚类中心选取过于稠密，出现聚类冲突现象，使得原本属于一个簇的对象被分为两个不同的簇中，从而降低了聚类结果的质量。为了克服初始聚类中心所选过于稠密的现象，提出了最大距离积法，尽可能地疏忽初始聚类中心的分布。基本思想如下：
按照与基于密度选取初始聚类中心法同样的思路，根据密度参数找到高密度点集合D和初始的两个聚类中心z1，z2，z1，z2分别是最高密度区域的数据对象与次高密度区域的数据对象，再计算D中其余数据对象xi到z1，z2的距离d（xi，z1）和d（xi，z2）；令z3为满足 max（d（xi，z1））×d（xi，z2））的数据对象xi；令zk为满足max（d（xi，z1） ×d（xi，z2）×…×d（xi，zk-1））[4]的数据对象xi，xi∈D。依次可得到k个初始聚类中心。
其基本步骤描述如下：
1）计算任意两个数据对象间的距离d（xi，xj）；
2）通过密度参数MinPts和ε，把处于低密度区域的点删除，得到高密度区域的数据对象集合D；
3）把处于高密度区域的数据对象作为第1个聚类中心z1，加入集合Z（已初始化聚类中心）中，同时从集合D中删除；再在集合D中找到距离z1最远的点作为第2个聚类对象z2，将其加入集合Z中，并从集合D中删除。
4）在集合D中搜索到集合Z中的每个点的距离乘积最大的点作为当前所要找的聚类中心，并加入集合Z.
5）重复步骤4），直到集合Z中的样本个数达到k个，聚类中心初始化完成。
6.描述算法时涉及的定义
描述算法时涉及的定义如表6.1所示
7.小结
k均值聚类算法是一种广泛应用的聚类算法，但是聚类结果随不同的聚类中心波动的特性影响了这种算法的应用范围。本文分析的4种常见k均值初始聚类中心选择算法用于k均值算法，能消除算法对初始聚类中心的敏感性，并能得到较好的聚类结果。
参考文献：
[1]袁方，周志勇，宋鑫.初始聚类中心优化的k-means算法[J].计算机工程，2007，33（3）：65-66.
[2]吴晓蓉.K—均值聚类算法初始中心选取相关问题的研究[C].湖南大学硕士学位论文，2008.
[3]張文君，顾行发，陈良富，余涛，许华.基于均值-标准差的均值初始聚类中心选取算法[J].遥感学报，2006，10（5）：715-721
[4]熊忠阳，陈若田，张玉芳.一种有效的K-means聚类中心初始化方法[J].计算机应用研究，2011，28（11） ：4188-4190
【关键词】初始聚类；算法
1.引言
聚类分析是数据挖掘的功能之一，是在训练数据不提供类标号的情况下按照最大化类内对象间的相似性、最小化不同类对象之间的相似性的原则聚类和分组数据。通过自动聚类能够识别对象空间中稠密和稀疏区域，从而发现全局分布模式和数据属性之间有趣的相关性。
目前，存在着大量的聚类算法，K均值算法是应用广泛的聚类算法之一。1967年，MacQueen首次提出了K均值聚类算法，该算法的核心思想是找出k个聚类中心 使得每一个数据点xi和与其最近的聚类中心cv的平方距离和被最小化。首先，随机地选择k个对象，每个对象代表一个簇的聚类中心。然后，对剩余的每个对象，根据其与各个聚类中心的距离，将它指派到最相似的簇；计算每个簇的均值，将它作为新的聚类中心。不断重复这个过程，直到准则函数收敛。准则函数采用平方误差准则，定义如（1.1）所示：
（1.1）
K均值算法具有思想简单、时间复杂度接近线性、对大规模数据的挖掘具有可伸缩性等优点，但是也存在對聚类初始值的依赖、聚类个数K 需要预先给定、准则函数易陷入局部极小、对离群点敏感等缺点。K均值算法对聚类初始值的依赖表现在从不同的初始聚类中心出发，得到的聚类结果也不一样，并且一般不会得到全局最优解。在实际应用中，由于初始输入不同而造成结果的波动是不能接受的。因此怎样找到一组初始中心点，从而获得一个较好的聚类效果并消除聚类结果的波动性对k-means算法具有重要意义。本文分析比较了文献提出的几个初始聚类中心选取算法，这几个算法分别是：基于Huffman树构造的思想选取初始聚类中心、基于均值-标准差选取初始聚类中心、基于密度选取初始聚类中心、采用最大距离积法选取初始聚类中心等4个算法。
2.基于Huffman树构造的思想选取初始聚类中心算法
基于Huffman树的思想的K-均值聚类算法流程大体分三步：
1）根据Huffman树的思想。基于数据相异度，将数据样本构造成一棵树。根据算法的实际需要，在构造树的时候做了改变：对于构造树，不用左右子树根结点权值之和作为新的二叉树根结点，而是采用左右结点的算法平均值作为新的二叉树根结点的值。
2）对于构造出来的Huffman树，按构造结点的逆序找到k-1个结点，根据图论理论可知，去掉这k-1个结点可将树分为k个子树，这k个子树的平均值即初始的k个聚类中心点。
3）对于已得的k个初始聚类中心，按照K均值聚类算法进行聚类。
算法中的数据点之间的相异度度量采用欧式距离。用一个例子说明构造树并得到初始中心的过程，假设有一组数据（x1，x2，x3，x4，x5，x6）。它们对应的权值为（12，34，56，78，8，89），需要将这6个点聚成3类。过程如下：
1）首先根据欧式距离计算6个对象之间的相异度，得到相异度矩阵见式（2.1），
（2.1）
2）找到矩阵中最小值是4，也就是数据点x1（12）和x5（8）的相异度，计算这两点的算术平均值为10，将此平均值记为x11并且作为x1和x2中间结点加入树见图2.1（b）。在数据集中删除x1和x5，并将x11加入到数据集时得到新的数据集（x11，x2，x3，x4，x6）对应的值为（10，34，56，78，98），计算它们的相异度矩阵见式（2.2）
（2.2）
3）重复第（2）步直到数据集中只剩下一个对象。剩下的迭代过程相异度矩阵变化如图2.1，树的构造过程示意图见图2.2
4） 将数据集聚成3类，即k=3，在已构造出来的树（图2.2（c））中按结点构造的逆序找出k-1个点，即57.75和27.5，去掉这两点即可将构造树分为3个子树（x1，x5）、（x2，x3）、（x4，x6）， 对应树中的结点为（8，12）、（34，56）、（78，98）。三个子树的平均值10，45，88即为三个簇的初始中心点。
3. 基于均值-标准差选取初始聚类中心算法
由K均值算法可知，如果所选的初始聚类中心取在几个密集区域的中心，其周围的点越容易分布到最近的点，聚类收敛越快，所需要迭代的次数越少。其中涉及最优初始聚类中心点的选取。
若要分析所有数据的分布情况计算其分布密度，那是非常复杂的事。根据随机函数的分布知识，聚类的数据应主要分布在所有数据的均值附近。标准差是评价数据分布的又一重要标志。假设所有数据的均值为μ，标志差为σ，则数据应该主要分布在（μ-σ， μ+σ）之间。假设分类数为k，选择初始分类点为（μ-σ， μ+σ）之间的k个等分点进行。设第i类的初始分类中心为mi，公式如（3.1）所示，
（3.1）[3]
如果参与分类的是多维数据，如d维，则每个初始聚类中心的各个向量为（μl-σl，μl+σl）之间，设第i类聚类初始中心值为（mi1，mi2，…，mid），公式如（3.2）所示，
（3.2）[3]
4. 基于密度选取初始聚类中心算法
基于密度选取初始聚类中心算法描述如下：
输入：聚类个数k以及包含n个数据对象的数据集；
输出：k个初始聚类中心。
1）计算任意两个数据对象间的距离d（xi，xj）； 2）计算每个数据对象的密度参数，把处于低密度区域的点删除，得到处于高密度区域的数据对象的集合D；
3）把处于最高密度区域的数据对象作为第1个中心z1；
4）把z1距离最远的数据对象作为第2个初始中心z2，z2∈D
5）令z3为满足max（min（d（xi，z1），d（xi，z2）），i=1，2，…，n[1]的数据对象xi，z3∈D。
6）令z4为满足max（min（d（xi，z1），d（xi，z2），d（xi，z3））），i=1，2，…，n的数据对象xi，z4∈D。
7）令zk为满足max（min（d（xi，zj））），i=1，2，…，n，j=1，2，…，k-1[1]的xi，zk∈D.
从这k个初始聚类中心出发，应用k均值聚类算法，得到聚类结果。
5. 采用最大距离积法选取初始聚类中心算法
基于密度选取初始聚类中心法与随机初始化聚类中心相比，降低了对初始聚类中心的敏感性，在收敛速度、准确率方面都有了较大的进步。但由于它所选聚类中心遵从最小距离的思想，可能造成初始聚类中心选取过于稠密，出现聚类冲突现象，使得原本属于一个簇的对象被分为两个不同的簇中，从而降低了聚类结果的质量。为了克服初始聚类中心所选过于稠密的现象，提出了最大距离积法，尽可能地疏忽初始聚类中心的分布。基本思想如下：
按照与基于密度选取初始聚类中心法同样的思路，根据密度参数找到高密度点集合D和初始的两个聚类中心z1，z2，z1，z2分别是最高密度区域的数据对象与次高密度区域的数据对象，再计算D中其余数据对象xi到z1，z2的距离d（xi，z1）和d（xi，z2）；令z3为满足 max（d（xi，z1））×d（xi，z2））的数据对象xi；令zk为满足max（d（xi，z1） ×d（xi，z2）×…×d（xi，zk-1））[4]的数据对象xi，xi∈D。依次可得到k个初始聚类中心。
其基本步骤描述如下：
1）计算任意两个数据对象间的距离d（xi，xj）；
2）通过密度参数MinPts和ε，把处于低密度区域的点删除，得到高密度区域的数据对象集合D；
3）把处于高密度区域的数据对象作为第1个聚类中心z1，加入集合Z（已初始化聚类中心）中，同时从集合D中删除；再在集合D中找到距离z1最远的点作为第2个聚类对象z2，将其加入集合Z中，并从集合D中删除。
4）在集合D中搜索到集合Z中的每个点的距离乘积最大的点作为当前所要找的聚类中心，并加入集合Z.
5）重复步骤4），直到集合Z中的样本个数达到k个，聚类中心初始化完成。
6.描述算法时涉及的定义
描述算法时涉及的定义如表6.1所示
7.小结
k均值聚类算法是一种广泛应用的聚类算法，但是聚类结果随不同的聚类中心波动的特性影响了这种算法的应用范围。本文分析的4种常见k均值初始聚类中心选择算法用于k均值算法，能消除算法对初始聚类中心的敏感性，并能得到较好的聚类结果。
参考文献：
[1]袁方，周志勇，宋鑫.初始聚类中心优化的k-means算法[J].计算机工程，2007，33（3）：65-66.
[2]吴晓蓉.K—均值聚类算法初始中心选取相关问题的研究[C].湖南大学硕士学位论文，2008.
[3]張文君，顾行发，陈良富，余涛，许华.基于均值-标准差的均值初始聚类中心选取算法[J].遥感学报，2006，10（5）：715-721
[4]熊忠阳，陈若田，张玉芳.一种有效的K-means聚类中心初始化方法[J].计算机应用研究，2011，28（11） ：4188-4190