2 聚类算法的分析与研究
2.1 数据挖掘简介
数据挖掘（Data Mining），也被叫做在已知的数据库中对知识的发现（knowledge discovery ,KDD）,就是从数量巨大的、不完整的、有孤立点数据的、模糊的、随机的数据中，提取发掘出来隐含在当中的、人们在这之前不是特别了解的、但又是隐含有用的信息内容和知识内容的非平凡过程[2]。其实数据挖掘就是通过各种分析算法工具从巨大数量的数据中挖掘所需要的数据与模型两者关系的一个过程，可以通过得到的这些关系，对未来的数据与模型关系进行预测。通常根据不同用户的需求，和他们所提供的数据类型，数据挖掘的数据库的类型也是不一样的，通常包括关系数据库类型、事物数据库类型、多媒体数据库类型等。其中关系数据库实际上就是使用数学学科上的方法来处理数据之间的关系，我们生活中随处可见关系数据库，比如交通部的车辆数据库、银行的客户记录等。事务数据库一般是将几个事务数据库的数据一起导入到只能用来读数据的数据挖掘库中，做成一个数据集市，然后把其作为挖掘的对象。多媒体数据库顾名思义就是包含大量视频音频文件，模式识别技术被用于该领域。
数据挖掘包含很多类别，包括分类分析、聚类分析、关联分析孤立点分析等其他分析。其中分类分析包括分类和回归，分类分析是一种预测模型，通过现有数据预测将来的数据，如果预测的数据是离散的即叫做分类，如果是连续的即叫做回归。聚类分析则是将大量数据中形似的数据分到一组，一个数据集大概包括几组数据，聚类没有明显的属性目标，而是挖掘隐藏的属性来进行聚类，聚类分析中的基于划分的K-均值算法是本文的研究对象。关联分析分析数据与数据之间关联关系还有它与其他数据的派生关系。孤立点分析是针对那些远离数据集的点，对不同的客户，别人的孤立点可能对于他来说是很重要的信息，孤立点分析就是对这些远离数据集中心的数据信息进行挖掘。孤立点的研究是将来我们必须重点研究的领域，因为几个孤立点就会影响全局的聚类结果，这是不容忽视的。
2.2 聚类的基本知识
2.2.1 类的定义及表示 （1）类的定义
8
要想聚类操作首先要明确类的定义。世界错综复杂事物存在的方式也不尽相同，所以类的定义并不唯一。以下将列举出常用的类的定义：
设：含有K个样本的集合A，Mi是其中的某个样本，T和C是范围阀值，那么：如果任意的Mi，Mj ∈A，都有D（Mi，Mj）≤T，则A称为一类；
（2）类的表示；
聚类的表示方法也是有不同的，一般用以下三种：
① 自然语言表示：直接用自然语言直观的描述出这些数据是属于哪个簇的； ② DNF表示：用析取范式表示明了、简洁、易懂。例如： (36
2.2.2 聚类的相似度量方法
聚类分析按照数据样本性质的相似程度的大小进行划分，确定这些相似程度的大小必须有一个准则来判断它们的程度大小，这个判断准则叫做相似度方法，主要是在距离和相似系数的不同。
距离：样本点之间的相似性我们就用某种距离函数表示，距离近的表示样本点相似，具体计算时可以把样本看做有M个属性的变量，即这个样本就是在一个M维的空间中的一个点。
距离函数：设P是所有样本集合的集合名称，如果满足： ① 正定性D(M，N)≥0，if M≠N D(M，N)=0，if M=N ② 对称性D(M，N)=D(M，N)
③ 三角不等式D(M,N)+D(N，L)≧D(M，L) 我们称它们为距离函数。 聚类分析中经常使用的的距离函数有： ① 明氏(Minkowski)距离
?m?d(xi,xj)???(xik?xjk)??k?1?………………………………………… (2.1)
9
p1m当m取1时，则表示绝对距离，当m取2时就表示欧式(Euclid)距离，当m取无穷大时就表示切比雪夫(Chebyshev)距离。
如：欧氏距离
??d(xi,xj)???(xik?xjk)2??k?1?………………………………… (2.2)
② 马氏(Mahalanois)距离
p12d(xi,xj)???(xi?xj)S(xi?xj)??T?112……………………………… (2.3) ）算得的协方差矩阵：
其中 S 是由样品集N（
x1,x2,...,xj,...,xn1n1nx??xi,S?(xi?x)(xi?x)T?ni?1n?1i?1………………………………… (2.3.1)
样品聚类一般情况下被叫做Q型聚类，是以距离矩阵为出发点的。明氏距离改进后得到了马氏距离，所有的线性变换对于马氏距离来说是不变的，多重相关性马氏距离也把它克服了。
③ 方差加权距离
?p(xik?xjk)d(xi,xj)???2sk?1?k?2????…………………………………………… (2.4)
12其中
1n1n2x??xik,sk?(xik?xk)2.?ni?1n?1i?1…………………………….. (2.4.1)
在聚类分析中除了对样本点聚类，对特征变量也要根据实际情况进行聚类，所以对于特征向量而言，不必非用距离函数来确定它们的相似测度，还可以用相似系数。
相似系数：当对含有k个指标的变量的数据集进行聚类时，就用相似系数来作为判断所有变量之间的相似程度（或关联程度）的标准指标。一般地，若表示Cab变量Xa,Xb之间的相似系数，应满足：
1）| Cab|≤1且Cab=1；
2）Cab=1或Cab=—1→Xa=CXb； 3）Cab=Cba；
Cab的绝对值越与1接近，越说明变量Xa,Xb之间的关联性越大。
10
相似系数中相关系数和夹角余弦是目前最经常被使用的。 （1）相关系数 变量
x?,x?之间的相关系数我们可以这样定义为：
r???s??s??s????(x??x?)(x??x?)iii?1n?(x??x?)?(x??x?)2iii?1i?1nn,2…………………………….. (2.5)
之间
实际上，
r??只是变量
x?,x?之间的观测值
(x1?,x2?,...,xn?T)与(x1?x,2?,...,xn?T)的相关系数而已。相关系数表示两个向量的相关程度是多少。
（2）夹角余弦 变量
x?,x?的观测值
(x1?,x2?,...,xn?)T与(x1?,x2?,...,xn?)T，其夹角余弦我们可以这
样定义为：
c????x?x?iii?1n?x?x?2i?2ii?1i?1nn……………………………………… (2.6)
变量聚类一般情况下被叫作为 R 型聚类。一般R 型聚类，相似系数矩阵 C 是数据集聚类的出发点，相似系数矩阵不仅能够使用相关矩阵，而且能够使用夹角余弦矩阵。
2.2.3 聚类间的距离测度函数
对于不同的两个类，如果他们之间距离可定义，那么就用如下几种定义方式来定义他们的距离：
（1）最短距离法：顾名思义它表示两个类中的元素，相离最近的两个元素的距离来表示这两个类之间距离，公式表示为：
Drk?min{Dpk,Dqk}…………………………………… (2.7)
（2）最长距离法：跟最短距离法类似，表示两类之间距离的是两类中距离最远的元素，公式为：
Drk?max{Dpk,Dqk}………………………………….. (2.8)
（3）类平均法：求出两个类中任意两个数据的平均距离，用求出来的这个数据来表示这两个类的平均距离，这就是类平均法，我们可以用下面的公式来表示：
11
Drk?npnrDpk?nqnrDqk ………………………………… (2.9)
（4）重心距离法：它的定义表示两个类之间重心相邻的距离为类距离,公式表示为：
2Drk?npnrD2pk?nqnr2Dqk?npnq2?Dpqnrnr………………………… (2.10)
其中类的重心公式为：
Dpq?d(xp,xq) （也就是各元素的平均向量之间的距离）
（5）离差平方和距离：用类中各元素的离差平方和的总和得到两个类Gr和Gk的直径分别是Dr和Dk,类Gr+k=Gr Y Gk,用这种方法尽量让类间的离差平方和大，而类内部的元素间的值小，公式表示为：
D?2rknp?nknr?nkD?2pknq?nknr?nk2Dqk?nkD2nr?nkpq ……………………………. (2.11)
其中类直径：有的把类中相距最远的两个元素的距离作为直径，也有的将类中各元素指标的离差平方和的和作为直径，离差平方和的计算公式为：
D2pq?npnqnp?nq(xp?xq)T(xp?xq) ………………………………………… (2.12)
2.2.4 聚类分析的一般步骤
聚类分析的步骤大体可以分为四步[9-10]：
（1）数据的预处理：就是在拿到一个数据集的时候，首先分析对这个数据的聚类分析要求，并根据这个要求对现在的数据集做降维或者特征标准化等初步的处理操作，也就是去掉没用的特征值。
（2）特征的选择及提取：对于第一步得到的信息，进一步细分，就是将预处理后的信息再选择最有效的特征，并将选择出来的特征用向量的方法转换成新的有效突出特征，以供聚类分组时作为分组判定的条件。
（3）聚类：这就要用到前面的相似性度量函数，选择距离函数还是选择相似系数等方法来度量选出来的有效特征值的相似度，进而完成对该数据集的聚类分析。
（4）评估结果：结果进行分析，看有没有完成预定的要求，并根据聚类方法的评价标准对结果进行科学评估，即聚类分析的九个方面的要求是否满足，然后根据评估结果判断是否对本次的分析过程进行改进，以及怎样改进。
12