混合聚类算法

聚类算法的应用

聚类主要应用于模式识别中的语音识别、字符识别等,机器学习中的聚类算法应用于图像分割和机器视觉,图像处理中聚类用于数据压缩和信息检索.聚类的另一个主要应用是数据挖掘(多关系数据挖掘)、时空数据库应用(GIS等)、序列和异类数据分析等，聚类分析对生物学、心理学、考古学、地质学、地理学以及市场营销等研究也都有重要作用。

典型的聚类过程主要包括数据(或称之为样本或模式)准备、特征选择和特征提取、接近度计算、聚类(或分组)、对聚类结果进行有效性评估等步骤。

聚类过程:

1) 数据准备:包括特征标准化和降维.

2) 特征选择:从最初的特征中选择最有效的特征,并将其存储于向量中.

3) 特征提取:通过对所选择的特征进行转换形成新的突出特征.

4) 聚类(或分组):首先选择合适特征类型的某种距离函数(或构造新的距离函数)进行接近程度的度量; 而后执行聚类或分组。

5) 聚类结果评估:是指对聚类结果进行评估.评估主要有 3 种:外部有效性评估、内部有效性评估和相关性测试评估。

Ｖａｌｕｅ　Ｅｎｇｉｎｅｅｒｉｎｇ　・２２３・　基于自适应遗传算法的Ｋ均值混合聚类算法　Ｋ　Ｍｅａｎｓ　Ｈｙｂｒｉｄ　Ｍｏｄｅｌ－ｂａｓｅｄ　Ｃｌｕｓｔｅｒｉｎｇ　Ａｌｇｏｒｉｔｈｍｓ　Ｂａｓｅｄ　ｏｎ　Ａｄａｐｔｉｖｅ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ　董俊磊①Ｄｏｎｇ　Ｊｕｎｌｅｉ；杨进②Ｙａｎｇ　Ｊｉｎ　（①河南职业技术学院，郑州４５００００ｉ②中国石油天然气管道局天津大港工程建设有限公司，天津３０００００）　（（￣）Ｈｅ＇ｎａｎ　Ｃｏｌｌｅｇｅ　ｏｆ　Ｖｏｃａｔｉｏｎａｌ　ａｎｄ　Ｔｅｃｈｎｉｃａｌ，Ｚｈｅｎｇｚｈｏｕ　４５００００，Ｃｈｉｎａ；　（￣）Ｐｅｔｒｏ　Ｃｈｉｎａ，Ｎａｔｕｒａｌ　Ｇａｓ　Ｐｉｐｅｌｉｎｅ　Ｂｕｒｅａｕ，Ｔｉａｎｊｉｎ　Ｄａｇａｎｇ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｃｏｎｓｔｒｕｃｔｉｏｎ　Ｃｏ．，Ｌｔｄ．，Ｔｉａｎｊｉｎ　３０００００，Ｃｈｉｎａ）　摘要：本文将ＡＧＡ算法与Ｋ均值聚类方法结合，并将其应用在国际标准数据集ｉｒｉｓ的聚类上，取得了较好的聚类效果。　Ａｂｓｔｒａｃｔ：Ｔｈｉｓ　ｐａｐｅｒ　ｃｏｍｂｉｎｅｓ　ＡＧＡ　ａｌｇｏｒｉｔｈｍ　ｗｉｔｈ　ｔｈｅ　Ｋ　ｍｅａｎｓ　ｃｌｕｓｔｅｒｉｎｇ　ｍｅｔｈｏｄ　ａｎｄ　ａｐｐｌｉｅｓ　ｉｔ　ｉｎ　ｔｈｅ　ｉｎｔｅｒｎａｔｉｏｎａｌ　ｓｔａｎｄａｒｄ　ｃｌｕｓｔｅｒｉｎｇ　ｉｒｉｓ　ｄａｔａ　ｓｅｔ，ｗｈｉｃｈ　ａｃｈｉｅｖｅｄ　ｂｅｔｔｅｒ　ｃｌｕｓｔｅｒｉｎｇ　ｒｅｓｕｈｓ．　关键词：自适应遗传算法；聚类分析；ｋ一均值聚类　Ｋｅｖ　ｗｏｒｄｓ：ａｄａｐｔｉｖｅ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ；ｃｌｕｓｔｅｒ　ａｎａｌｙｓｉｓ；ｋ—ｍｅａｎｓ　ｃｌｕｓｔｅｒｉｎｇ　中图分类号：ＴＰ３１　文献标识码：Ａ　文章编号：１００６—４３１１（２０１０）３０—０２２３—０１　１　Ｋ均值聚类方法　假设有Ｎ个未知标号的样本（ｘ　Ｉｘ２，…Ｘ　），聚类的目的是根据　样本的特征向量，将Ｎ个样本聚为Ｋ类：（Ｃ。，ｃ：，…ｃ　），假设第ｋ类　的样本数目为Ｎ　，则Ｎ＝　Ｎ　，　表示第ｉ个类内的任意一个样　品。采用ｋ均值聚类算法进行聚类的步骤如下：①从（ｘ　，ｘ：，…ｘ　）中　随机选取Ｋ个点Ｃ　，Ｃ：，…ｃ　作为Ｋ个聚类集合的中心点。②计算　各个样本与这Ｋ个聚类中心的距离，并将其划分到距离最近的那个　类中。③计算每个类中各样本点的均值，将其作为新的中心点。④　计算各个样本点与新的聚类中心点的距离，并根据距离最小原则将　其划分到新的各个类别中。⑤计算平方误差函数：Ｅ＝　ＩＸ　一Ｃｉｌ　。．　⑥重复步骤③一⑤，直至Ｅ不再发生明显变化，或者达到某个预先设　置的最大迭代次数。　２自适应遗传算法　２．１标准遗传算法　①选择，根据各个个体的适应度，按照一定的规则或方法，从ｔ　代群体Ｐ（ｔ）中选择出一些优良的个体。②交叉，以交叉概率Ｐ　，将从　群体中选择出的一些个体随机地搭配成对，对每～对个体以某种规　则或方法交换它们之间的部分遗传基因。③变异，以变异概率Ｐ　从　群体中选择～个或几个个体，以某种规则或方法改变某一个或几个　遗传基因的值。　对第ｔ代群体Ｐ（ｔ）进行了上述的遗传操作之后，得到新的群体　Ｐ（ｔ＋ｌ　ｏ不断的重复这个过程，从而得到最优解或近似最优解。　２．２自适应遗传算法　①根据适应值及进化代数来调节个体的交叉率、变异率，ＡＧＡ　自适应交叉概率、变异率按下式进行调节：　一　。篱　”■　ｉ　，ｌ…　，　，　…　式中：Ｐ。表示交叉概率Ｐ。～表示最大交叉概率，Ｐ　一表示最小　交叉概率，Ｐ　为变异概率，Ｐ　～为最大变异概率，Ｐ　一为最小变异　概率，ｉｔｍａｘ为最大代数，　表示种群平均适应度值，ｒ表示在要交　叉的两个个体中较大的适应度值，ｆ为要变异的个体适应度值。　从式（１）和（２）可以看出，如果个体较差（其适应度值小于平均　适应度值），对其就给予较大的交叉概率和较小的变异概率，如果个　体较优良（其适应度值大于平均适应度值），则依据其优良程度和迭　代状态赋予此个体相应的交叉概率和变异概率。此改进措施有助于　保护优良个体的有效模式，便于找到全局最优点，防止早熟现象出　现。　②在进行交叉（变异）后比较个体适应度值是增大还是减小，如　果个体适应度值增大就保留该个体的变化，否则保留原个体。在标　准ＧＡ操作算子中，选择算子可以保证选出的都是优良个体，但是　变异算子和交叉算子仅仅是引入了新的个体，其操作本身并不能保　证新的个体是否优良。此改进措施有效的保证了ＧＡ所产生的新个　体都是优良的，明确了进化的方向，加快了ＧＡ的进化速度，避免了　进化过程中个别个体退化的现象。　３基于ＡＧＡ的Ｋ均值混合聚类算法　控制参数的选择．　采用变长位串的编码方法，群体规模ｎ＝１００，初始交叉概率ｐｃ＝　０．６，初始变异概率ｐｒｏ＝０．０５。评估函数以Ｋ均值聚类方法中的平方　Ｋ　ｎ　误差函数来计算：Ｅ＝　ｌｘ｛”一ＣｉＩ　（３）　ｉ＝１　ｘｊ∈　其中Ｋ是聚类中心的个数，ｃ；是第ｉ个类的聚类中心，ｘ　表示　第ｉ个类内的任意一个样品。评估函数越小，说明这种分类方法的　误差越小，该个体被选择到下一代的几率也就越大。　以（３）式所求得的评估函数值Ｅ为基础，利用下式作为适应度　函数。　Ｆ＝ＯＬ（１－ａ）－　一　（４）　其中ｉｎｄｅｘ是评估值Ｅ由小到大排序（依次编号为１，２，…，Ｐ，Ｐ　是群体规模）的排序编号。ｏ【的取值范围是（０，１），算法中取ｄ：０．６。　选择算子按下述方法来计算：利用下面的（５）式循环统计从第　个个体到第ｉ个个体适应度值之和占所有个体适应度值总和的　比例。循环产生随机数ｒ，当ｒ＜ｓ．时，对应的个体被复制到下一代中，　直到生成１００个中间群体。　ｓ．：∑ｐ（ｔ）．Ｆ／∑ｐ（ｉ）．Ｆ　（５）　以２．２的方法找到自适应的交叉概率ｐｃ，和变异概率ｐｍ。利用　交叉概率生成一个“一点交叉”的交叉位，随机的从中间群体中选择　两个个体，对交叉位后的基因进行交叉运算，直到中间群体中所有　个体都被选择过。对所有个体，循环每一个基因位，产生随机数ｒ，当　概率ｒ＜ｐ　时，对该位基因进行变异运算，随机产生一个１到Ｋ（聚类　中心的个数）之间的数赋值给该位，生成子代群体。　４结论　由结果可见通过采用遗传算法的搜索，Ｋ均值聚类方法的全局　寻优能力得到了提高，当对标准遗传算法进行自适应改进之后，效　果更好。从而得到结论：基于ＡＧＡ的Ｋ均值聚类方法能有效得到聚　类目标函数的全局极小值，优于Ｋ均值聚类方法和基于ＧＡ的Ｋ均　值聚类方法。　参考文献：　［１］（加）韩家炜，（加）坎伯（Ｋａｍｂｅｒ，Ｍ．）．数据挖掘：概念与技术［Ｍ］．范明　等，译．北京：机械工业出版社，２００１．　［２】傅景广，许刚，王裕国．基于遗传算法的聚类分析【Ｊ１．计算机工程，　２００４，３０（４）：１２２—１２４．　［３】余嘉元．基于ＧＡ的Ｋ均值聚类分析在消费心理学中的应用　广西　师范大学学报（自然科学版），２００９，２７（３）８１—８４．　［４］解可新，韩健，林友联．最优化方法［Ｍ】．天津：天津大学出版社，２００４．

聚类算法：凝聚层次聚类

凝聚层次聚类：

所谓凝聚的，指的是该算法初始时，将每个点作为⼀个簇，每⼀步合并两个最接*的簇。另外即使到最后，对于噪⾳点或是离群点也往往还

是各占⼀簇的，除⾮过度合并。对于这⾥的“最接*”，有下⾯三种定义。我在实现是使⽤了MIN，该⽅法在合并时，只要依次取当前最*的点

对，如果这个点对当前不在⼀个簇中，将所在的两个簇合并就⾏：

(1)单链(MIN):定义簇的邻*度为不同两个簇的两个最*的点之间的距离。

(2)全链(MAX):定义簇的邻*度为不同两个簇的两个最远的点之间的距离。

(3)组*均：定义簇的邻*度为取⾃两个不同簇的所有点对邻*度的*均值。

根据该算法，实现如下代码。开始时计算每个点对的距离，并按距离降序依次合并。另外为了防⽌过度合并，定义的退出条件是90%的簇被

合并，即当前簇数是初始簇数的10%：

实现代码如下：

[python]

1. # scoding=utf-8

2. # Agglomerative Hierarchical Clustering(AHC)

3. import pylab as pl

4. from operator import itemgetter

5. from collections import OrderedDict,Counter

6.

7. points = [[int(eachpoint.split('#')[0]), int(eachpoint.split('#')[1])] for eachpoint in open("points","r")]

8.

9. # 初始时每个点指派为单独⼀簇

10. groups = [idx for idx in range(len(points))]

11.

12. # 计算每个点对之间的距离

13. disP2P = {}

14. for idx1,point1 in enumerate(points):

１６４　２００７，４３（３）　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　

基于遗传算法和遗传模糊聚类的混合聚类算法　

张　强　，李　淼　

ＺＨＡＮＧ　ＱｉａｎｇＩ，ＬＩ　Ｍｉａｏ　

１．中国科学院舍肥智能机械研究所，合肥２３００３１　

２．中国科学技术大学信息科学技术学院，合肥２３００２７　

１．Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｉｎｔｅｌｌｉｇｅｎｔ　Ｍａｃｈｉｎｅｓ，Ｃｈｉｎｅｓｅ　Ａｃａｄｅｍｙ　ｏｆ　Ｓｃｉｅｎｃｅｓ，Ｈｅｆｅｉ　２３００３１．Ｃｈｉｎａ　２．Ｓｃｈｏｏｌ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ　ｏｆ　Ｃｈｉｎａ，Ｈｅｆｅｉ　２３００２７．Ｃｈｉｎａ　Ｅ—ｍａｉｌ：ｑｉａｎｇ１２３＠ｍａｉｌ．ｕｓｔｃ．ｅｄｕ．ｅｎ　

ＺＨＡＮＧ　Ｑｈｍｇ，ＬＩ　・Ｈｙｂｒｉｄ　ｃｌｕｓｔｅｒ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｇｅｎｅｒｉｃ　ａｌｇｏｒｉｔｈｍ　ａｎｄ　ｇｅｎｅｒｉｃ　ｆｕｚｚｙ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍ．　

Ｃｏｍｐｕｔｅｒ　Ｅｎ　ｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ，２００７，４３（３）：１６４－１６５．　

Ａｂｓｔｒａｃｔ：Ｉｎ　ｏｒｄｅｒ　ｔｏ　ｄｙｎａｍｉｃａｌｌｙ　ｇｅｔ　ｔｈｅ　ｎｕｍｂｅｒ　ｏｆ　ｃｌｕｓｔｅｒ　ｃｅｎｔｅｒ　Ｃ　ａｎｄ　ｔｈｅ　ｍｏｓｔ　ｏｐｔｉｍａｌ　ｃｌｕｓｔｅｒ　ｓａｍｐｌｅ，ｗｅ　ｃｏｎｓｔｒｕｃｔ　ａ　ｎｅｗ　

ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｇｅｎｅｒｉｃ　ａｌｇｏｒｉｔｈｍ　ａｎｄ　ｇｅｎｅｒｉｃ　Ｆｕｚｚｙ　Ｃ－Ｍｅａｎｓ（ｃａｌｌｅｄ　ＨＧＡ－ＦＧＣＭ）．Ｔｈｉｓ　ｍｅｔｈｏｄ　ｓｉｖｅｓ　ａ　ｎｅｗ　ｏｂｊｅｃｔ　ｅｖａｌｕａｔｉｏｎ　

ｆｕｎｃｔｉｏｎ，ｗｈｉｃｈ　ｔａｋｅｓ　ｉｎｔｏ　ｎｏｔ　ｏｎｌｙ　ｔｈｅ　ｓｃａｔｔｅｒ　ｄｅｇｒｅｅ　ａｍｏｎｇ　ｃｌｕｓｔｅｒｓ　ｂｕｔ　ａｌｓｏ　ｔｈｅ　ｃｏｍｐａｃｔｎｅｓｓ　ｉｎ　ｔｈｅ　Ｓ￣ｌｌｌｅ　ｃｌｕｓｔｅｒ．Ｍａｋｅ　ｕｓｅ　ｏｆ　ｔｈｅ　ＧＡ’ｓ　ｓｌｏｈａｌ　ｏｐｔｉｍａｌ　ｓｅａｒｃｈ　ａｂｉｌｉｔｙ；ｇｅｔ　ｔｈｅ　ｏｐｔｉｍａｌ　ｃｌｕｓｔｅｒｓ　ｕｎｄｅｒ　ｔｈｅ　ｇｉｖｅｎ　ｎｕｍｂｅｒ　ｏｆ　ｃｌｕｓｔｅｒ　ｃｅｎｔｅｒ　Ｃ．　Ｋｅｙ　ｗｏｒｄｓ：ｆｕｚｚｙ　ｃｌｕｓｔｅｒｉｎｇ；ｇｅｎｅｒｉｃ　ａｌｇｏｒｉｔｈｍ；Ｆｕｚｚｙ　Ｃ－Ｍｅａｎｓ；Ｇｅｎｅｒｉｃ　Ｆｕｚｚｙ　Ｃ－Ｍｅａｎｓ