基于遗传算法的混合类型数据聚类分析

摘要: 针对聚类分析算法在数据挖掘应用中存在的问题,该文结合遗传算法,对传统K均值聚类算法进行了改进,提出了混合类型数据聚类新算法,扩展了聚类分析的应用范围。实验结果表明,该算法具有较好的聚类性能。

关键词:遗传算法;层次化聚类;目标函数;优化

中图分类号:TP18文献标识码:A文章编号:1009-3044(2009)32-8875-02

A GA-Based Mixed Type Data Clustering Analysis

DONG Jian-kang1, WU Qi-ming2

(puter Science School, Gansu Political Science and Law Institute, Lanzhou 730070, China; 2.Department of Computer and Information Science, Hechi University, Yizhou 546300, China)

Abstract: To overcome the faultiness of the available clustering algorithm for the applications in data mining, a GA-based mixed type data clustering algorithm was proposed, which integrated genetic algorithm and improved the traditional K-means clustering algorithm. It extends the scope of the application of cluster analysis. The experiments show that the proposed algorithm works well.

Key words: genetic algorithms; clustering; objective function; optimization

聚类是根据数据的不同特征,将其划分为不同的数据类。它的目的是使得属于同一类别的个体之间的距离尽可能的小,而不同类别上的个体间的距离尽可能的大。数据的特征值多种多样。二元变量只有两个状态,非此即彼;区间标度变量是一个粗略线性标度的连续变量,如温度、高度、重量等;标称变量则由多个离散值组成,如地图颜色可能有五个状态:红色、黄色、绿色、粉红色、蓝色。作聚类分析时,可能用到一种变量,也可能是多种变量的组合。 传统的聚类分析是一种硬划分,它把每个待辨识的对象严格地划分到某类中,具有非此即彼的性质,因此这种类别划分的界限是分明的。而实际上大多数对象并没有严格的属性,如何对混和属性数据进行聚类分析是件极具挑战性的工作,也是目前聚类分析研究的主流[1]。

聚类算法可分为以下几类[2]:

1) 划分方法:给定一个包含n个对象的数据集,将其划分为k个子集,其中每个子集均代表一个聚类;

2) 层次方法:通过分解给定的数据集来创建一个层次,根据层次分解形成的方式采用自上而下或自下而上的方法进行聚类;

3) 基于密度方法:实际上就是不断增长所获得的聚类,直到“临近”密度小于一定阈值为止;

4) 基于网格方法:将数据集划分为有限数目的单元以形成网格结构,所有聚类操作均在这一网格结构上进行;

5) 基于模型的方法:为每个聚类假设一个模型,再去发现符合相应模型的数据对象。文章主要分析划分方法。

2 聚类分析的数学模型

假设X={x1,x2,…,xn}是待分析的对象全体,也可称为论域或样本集合。X中的每个对象(也可称为样本)(1≤i≤n)常用有限个参数值来刻画,每个参数值用于刻画xi的某个特征(属性)。于是对象xi就对应着一个向量P(xi)=(xi1,xi2,…,xim), 其中xij()是xi在j个特征上的值,P(xi)称为xi的特征向量或模式向量。聚类分析就是分析论域或样本集合X中的n个样本所对应的模式矢量间的空间距离及分散情况,按照各样本间的距离远近或相似程度把x1, x2,…, xn划分成k个不相交的模式子集X1, X2, …, Xk,并要求满足下列条件:

X1∪X2∪…∪Xk=X,Xi∩Xj=?准(1≤i, j≤k,i≠j)

样本xj(1≤j≤n)对子集xi(1≤i≤k)的隶属度关系可用隶属度函数表示为:

其中,隶属度函数必须满足条件Wij∈Mhk。也就是说:

1) 要求每一个样本能且只能隶属于某一类。

2) 要求每个子类都是非空的。

在这个表达式中是用于约束每一个样本能且只能属于某一类这一条件的;用于约束"每个子类都是非空的"。如果将以上定义的隶属度函数wij扩展到[0,1]这个区间即为模糊聚类的定义。模糊聚类又称为软聚类,相应的非模糊聚类也可称为硬聚类。

3 混合类型数据聚类算法的目标函数

令X={x1,x2,…,xn},表示有n个样本的数据集,其中xi=[xi1,xi2,…,xim]T表示第i个样本的m个特征值。令K是一个正整数,那么对X进行聚类的目的就是要找到一个划分,将X中的目标分为K个类。

为了找到最好的一个划分,要求选择一个聚类难则来指导搜索划分。下面我们要寻找一个目标函数作为聚类准则。当前较为流行的目标函数有[3]:

当样本同时具有数值和类属混合特征时,样本的特征矢量用xi=[xi1r,…,xilr,xi,l+1c,…,ximc]T表示,混合类型目标xi和xj之间的相异胜测度可由下式计算:

公式右边第一项为欧几里德距离平方,用于计算数值型属性的相似性。第二项为二值型属性特征的相似性测度。其值为0和1。权值用来调节两种特征在目标函数中的比例,以避免偏向任何其中一个特征。

4 基于遗传的混合类型数据聚类算法

利用遗传算法可以进行全局的并行搜索,避免出现局部最优以及提高搜索效率问题。

4.1 编码和初始种群的生成

编码即遗传算法中样本的表示。编码方法有很多,如二进制编码、实数编码、符号编码等等。针对本文的问题,对矩阵W进行编码。

设n个样本分属于K类,则样本空间可以表示为:

X=(x1x2…xn)

其中xi取整数值1-K中的一个,表示第i个样本属于第xi个类。

4.2 选择算子的实现

遗传算法使用选择运算来实现对群体中的个体进行择优选择操作:适应度数值高的个体被遗传到下一代群体中的概率较大;适应度低的个体被遗传到下一代群体中的概率较小。通过调节遗传选择概率数值来获得较好的遗传进度。本文采用类似锦标赛选择法,首先,随机地从种群中挑选一定数目的个体,然后将最好的个体选择作为父代个体。重复进行这个过程直到选到足够的个体。锦标赛选择的参数为竞争规模Tour。适应度函数如第3小节所示。

4.3 交叉运算

交叉运算是指在父代个体中选择两个染色体,然后对其中的部分基因按某种方式相互交换,从而形成两个新的个体。交叉运算是遗传算法区别于其他自然计算算法的重要特征,它在遗传算法中起关键作用,是产生新个体的主要方法。由于需要聚类的数目一般不会很大,染色体长度也不会很大,因此本文采用单点交叉。单点交叉又称为简单交叉,它是指在个体编码串中随机设置一个交叉点,然后在该点相互交换两个配对个体的部分基因。本文采用的是单点交叉的形式。交叉点随机选择,但介于1-K之间。

如:父代为 1,5,8,9,2,3,7,6,4,10选择交叉点为7则7与10-7进行交叉。得到的子代为:1,5,6,9,2,3,7,8,4,10。

4.4 变异运算

变异运算是用来模拟生物在自然的遗传环境中由于各种偶然因素引起的基因突变现象,它以很小的概率随机地改变遗传基因的值。

在染色体以二进制编码的系统中,它随机地将染色体的某一个基因由1变成0,或由0变成1。通过变异操作,可确保群体中遗传基因类型的多样性,以使搜索能在尽可能大的空间中进行,避免丢失在搜索中有用的遗传信息而陷入局部解,获得质量较高的优化解答。遗传算法中的变异运算是产生新个体的辅助方法,它是必不可少的一个运算步骤。变异本身是一种局部随机搜索,与选择算子结合在一起,保证了遗传算法的有效性,使遗传算法具有局部的随机搜索能力,同时使得遗传算法保持种群的多样性,以防止出现过早收敛。

5 结论

我们分别用传统K均值聚类算法和基于遗传的混合类型数据聚类算法进行了实验,实验结果验证了最初的设想。基于遗传的混合类型数据聚类算法的正确率均在95%以上,比传统K均值聚类算法的正确率要高。说明基于遗传的混合类型数据聚类算法确实能达到全局最优。

参考文献:

[1] 郝占刚,王正欧.基于遗传算法和k-medoids算法的聚类新算法[J].现代图书情报技术,2006(5):44-46.

[2] 史忠植.知识发现[M].北京:清华大学出版社,2002:137-139.

[3] 范明,孟小峰.数据挖掘概念与技术[M].北京:机械工业出版社,2001:223-230.