基于遗传算法的k-means聚类挖掘方法研究
第二章 聚类分析
人类认识世界的一种重要方法是将认识的对象按照类别进行划分。同一事物往往具有更多的近似特征，因此分门别类地对事物进行研究远比在一个混杂多变的集合中研究更清晰、细致。“人以群分，物以类聚”，聚类作为一种重要的分类工具，在今天基于海量数据的分析中起着很大的作用。随着相关研究的开展，聚类分析被纳入数据挖掘范围，并成为数据挖掘中的一项核心技术。
2.1聚类分析的基本概念[30]
所谓聚类(Clustering)就是将物理对象或抽象对象的集合分成由相似对象组成的多个类。也就是说由聚类生成的簇是一组数据对象的集合，簇必须同时满足以下两个条件：(l)每个簇至少包含一个数据对象；(2)每个数据对象必须属于且唯一的属于一个簇。同一个簇中的数据对象尽可能相似，不同的簇中的数据对象尽可能相异。在许多应用中，可以将一簇中的数据对象作为一个整体来对待。
聚类就是按照一定的要求和规律对事物进行区分和分类的过程。在这一过程中没有任何关于分类的先验知识，也没有教师的指导，仅靠事物间的相似性作为类属划分的准则，因此属于无监督分类的范畴。
聚类分析(Cluster Analysis)则是指用数学的方法研究和处理给定对象的分类。它主要是从数据集中寻找数据间的相似性，并以此对数据进行分类。使得不同类别中的数据尽可能相异，而同一类数据之间尽可能相似，从而发现数据其中隐含的、有用的信息。
2.2数据挖掘对聚类算法的要求
聚类分析是数据挖掘中的一项重要功能，而聚类算法是目前聚类挖掘领域研究的核心。聚类算法的质量取决于算法对相似性的判别标准，算法的具体实现以及算法发现隐藏模式的能力。由于大型数据库、数据仓库十分复杂，数据挖掘中的聚类算法必然要面对由此产生的计算要求，具体要求如下：
(1) 可伸缩性：可伸缩性是指算法不仅对小数据集有效，对大数据集也应同样有效。目前许多聚类算法在小于200个数据对象的小数据集合上工作的很好，但是一个大规模的数据库可能包含几百万个对象，在这样的大数据集合样本上进
10
青岛科技大学研究生学位论文
行聚类可能会导致有偏差的结果，我们需要有高度可伸缩性的聚类算法。可伸缩性算法应该随着数据库大小的变化，其运行时间也应该线性变化。
(2) 处理不同类型属性的能力：算法不仅要能处理数值型的数据，还要有处理其他类型字段的能力，如布尔型，枚举型、序数型，或者这些数据类型的混合。
(3) 发现任意形状的簇：许多聚类算法基于欧氏距离或曼哈顿距离度量来决定聚类。基于这样的距离度量的算法趋向于发现具有相近尺度和密度的球形簇，但现实数据库中的聚类可以是任意形状，因此，研究能发现任意形状的簇的算法是很重要的。
(4) 输入参数对领域知识的弱依赖性：在聚类分析当中，许多聚类算法都要求用户输入一些参数，例如需要发现的聚类数。聚类结果通常都对用户输入这些参数十分敏感，并且对高维数据，这些参数有时相当难以确定的。这样不仅加重了用户的负担，也使得聚类质量难以保证。
(5) 能够处理异常数据：现实数据库中常常包含有异常数据，例如孤立点、未知数据、数据空缺或包含错误数据。有一些聚类算法可能会对这些数据很敏感，从而导致低质量的分析结果。我们希望聚类算法能够在聚类过程中检测到这些异常数据，然后删除它们或消除它们的负面影响。
(6) 对输入记录的顺序不敏感：有些算法对记录的输入顺序很敏感，对同一个数据集，当以不同的顺序输入时，用同一个算法处理可能得到不同的聚类结果，这是应当避免的。
(7) 满足约束条件：在实际应用当中，聚类可能会在有各种约束的情况下进行。对于聚类算法来说既满足约束条件，又取得好的聚类结果是非常具有挑战性的。在这种受约束的情况下我们希望聚类算法仍有好的表现。
(8) 可解释性和可用性：聚类的结果最终是面向用户的，因此其结果应当是容易解释和理解的，并且是可应用的。这要求聚类算法必须与一定的语义环境及语义解释相关联。领域知识如何影响聚类分析算法的设计是很重要的一个研究方面。
2.3聚类分析中的数据结构和类型
2.3.1聚类分析中的数据结构
在聚类分析中，许多基于内存的聚类算法一般会选择如下两种有代表性的数据结构[31]：
1．数据矩阵
11
基于遗传算法的k-means聚类挖掘方法研究
数据矩阵又称为“对象—属性”结构，类似于关系表的形式，它表示具有p个属性的n个对象(例如：人可以用年龄、身高、体重、性别、等属性来描述)可以用如下n?p(n个对象?p个变量)的矩阵来表示：
?x11??x21 ????xn1?x12x22?xn2????x1p??x2p?? (2-1) ??xnp??其中，每列代表对象的一个属性，每一行为一个元组，代表一个数据对象。 2．相似度矩阵
相似度矩阵又称为“对象—对象”结构。主要用来存储n个对象两两之间的相似度，表现形式是n?n维矩阵：
?1??d(2,1) ????d(n,1)?d(1,2)1?d(n,2)????d(1,n)??d(2,n)?? (2-2) ??1??其中d(i,j)是对象i和j之间相似性的量化表示，通常为非负数，且
i和j越相似，则d(i,j)越接近于1；相反，对象i和j的差
d(i,j)?d(j,i)。对象
异越大，则d(i,j)就越大。每个对象与自身的相似度最高，其值为d(i,i)?1。 2.3.2 聚类分析中的数据类型
数据挖掘的对象复杂多样，这就要求聚类分析的方法不仅能够处理属性为数值类型的数据，还能够处理其他类型的数据。一般而言，在数据挖掘中，对象属性经常出现的数据类型有:数值型，二值型，符号型、顺序变量型以及混合类型[32]。不同类型的数据有不同的性质，在计算时所采用的处理手段是不同的。
1．数值属性
属性值用实数表示，典型的例子则包括重量、高度和温度等。为了将数据集进行分类，必须定义相异性和相似性的测度来度量同一类别数据的相似性和不同类别数据之间的相异性。如果数据的多个属性采用的测量单位不同，则会对聚类分析产生影响。往往一个较小的测量单位就会使得它所表示的属性取值范围变大，从而对聚类结果产生较大影响。为了避免属性对测量单位的依赖，所以在计算数据的相似性之前先要对数据进行标准化。
12
青岛科技大学研究生学位论文
标准化就是将一个属性取值范围投射到一个特定的范围之内，以消除数值型属性因测量单位大小不一而造成聚类结果的偏差。对于基于距离计算的聚类挖掘，规格化方法可以帮助消除因属性取值范围不同而影响挖掘结果的公正性。下面介绍三种标准化方法。
(1) 最大最小标准化
最大最小标准化方法是将属性A的值m映射到n且有n∈[new_minA,new_maxA]，具体映射计算公式如下：
n?m?minAmaxA?minA(new_maxA?new_minA)?new_minA
(2-3)
最大最小标准化保留了原来数据中存在的关系。但若将来遇到超过目前属性A取值范围的数值，将会引起系统出错。
(2) 均值标准化
该方法是根据属性A的均值与偏差来对A进行标准化。属性A的m值可以通过以下计算公式获得其映射值n。
n?m?A?A (2-4)
其中，A和?A分别为属性A的均值和方差。这种规格化方法常用于属性A最大值与最小值未知。
(3) 基数变换标准化
该方法是通过移动属性A值的小数位置来达到标准化目的。
n?m10j (2-5)
其中，j为使max?n??1成立的最小值。
数据标准化处理以后就可以进行由数值属性所描述对象之间的差异(或相似)程度的测量，经常通过计算相应两个对象之间距离来确定，常用的距离有明考夫斯基距离、欧式距离、曼哈顿距离等。
2．二值属性
一个二值变量只有两个取值：0或1，其中0代表所表示的状态不存在，1代表相应的状态存在。二值变量又分为对称二值变量和不对称二值变量，如果0和1所表示的状态重要性相同，则称其为对称的二值属性。
设两个对象xi和xj，q是属性值在两个对象中都为1的属性个数，r是属性值在xi中为1而在xj中为0的属性个数，s是属性值在xi中为0而在xj中为1的
13
基于遗传算法的k-means聚类挖掘方法研究
属性个数，t是属性值在两个对象中都为0的属性个数。如果认为所有的二值属性的权值均相同，那么就能得到一个2×2条件表，如图示：
表2-1二值属性条件表
Table.2-1 Binary attribute conditions table
i j 1 0 合计 q s q+s r t r+t q+r s+t p 1 0 合计 度量上面两个变量的差异度可以由简单匹配系数(对称的情况)和Jaccard系数(非对称的情况)决定。
简单匹配系数的计算公式如下：
d(i,j)?r?sq?r?s?t (2-6)
如果一个二值属性取0或1所表示内容的重要性是不一样的，那么二值属性就是非对称的，如果认为取1值比取0值重要，描述对象i和对象j之间差异参数就是Jaccard相关系数，它的具体定义描述如式3－7。
d(i,j)?3．符号属性
符号属性是二值属性的一个推广，符号属性可以对两个以上的状态进行描述，状态之间是无序的。例如，头发的颜色是一个符号变量，具有少量可能的值{黑色，金色，棕色，白色，灰色，??}。对于符号变量，最常用的计算对象i与对象j之间差异的方法就是简单匹配方法，具体公式如下：
d?p?mpr?sq?r?s (2-7)
(2-8)
其中，m表示对象i和对象j中取同样状态的符号变量的个数，p为所有符号属性的个数。
4．序数属性
一个离散序数变量属性与一个符号变量属性相似，不同的是它的各个状态是有意义的序列。序数变量在描述难以用客观方法表示的主观质量评估时是非常有用的。序数变量的数值常常是通过对间隔数值的离散化获得，也就是通过将取值
14