青岛科技大学研究生学位论文
范围分为有限个组得到。一个序数变量可以映射到一个等级集合上。如：若一个顺序变量f包含M个状态，那么这些有序的状态就映射为1,2,?,M的等级。
5．混合类型属性
以上讨论了各种数据类型和它们差异度的计算方法，在实际数据库中，数据对象往往是由混合数据类型描述的。在实际聚类分析中，将不同类型的变量组合在同一个差异度矩阵中，并将它们所有有意义的值全部映射到[0,1]区间内。
设一个数据集包含m个不同类型的属性，对象i和j之间的差异度定义为：
m?? d(i,j)?p?1m(p)ijdij(p) (2-9)
(p)ij??p?1其中，如果：xip或xjp数据缺失(对象i或对象j的变量p无测量值)，或
xip?xjp?0(p)且变量p为非对称二值变量，则标记?ij(p)?0；否则?ij(p)?1。
(p)?ij表示变量p对对象i和对象j之间差异程序的贡献，dij可以根据其具体
变量类型进行相应计算。
若变量p为二值变量或符号变量，则：如果xip?xjp，那么dij(p)?0，否则
dij(p)?1。
xip?xjpmaxh若变量p为间隔数值变量，则d量p所有可能的对象。
(p)ij?xhp?minhxhp，这里的h为非空变
若变量p为序数变量，将其转化为数值变量来进行计算处理。
综上所述，即使在对象是由不同类型变量描述时，也能够计算相应每两个对象间的距离。
2.4聚类分析中的相似度度量方法
对象间的相似性是聚类的核心，而对相似性进行度量是用以区别对象的主要基础，传统的相似度度量方法有两类，即距离和相似系数。距离通常用于数值型数据，距离越接近0，相似性越大；相似系数通常用于分类型数据，相似系数越接近1，相似性越大[33]。
15
基于遗传算法的k-means聚类挖掘方法研究
2.4.1距离
距离是聚类分析常用的分类统计量。假设每个对象有m个属性，可以把一个对象视为m维空间的一个点，n个对象就是m维空间的n个点。因此，很自然地想到用点之间的距离来衡量对象之间的相似程度。距离越小，对象间的相似度就越大。用dij表示对象xi和对象xj之间的距离，则距离应该满足一下四个性质：
(1) 非负性，即对所有的i和j，恒有dij?0。当且仅当xi?xj时，dij?0。 (2) 对称性，即对所有的i和j，恒有dij?dji。
(3) 三角不等式，即对所有的i，j，k，恒有dij?dik?dkj。 在聚类分析中，常用的距离公式有以下几个： (1) 明科夫斯基距离
1 dij????xik?xjk?k?1mp?pp>0 (2-10) ? ，?如果取q=1,2,∞时，则分别得到以下三个距离： (2) 曼哈顿距离
m dij??k?1xik?xjk (2-11)
(3) 欧氏距离
1 dij?m???xik?xjk??k?12?2? (2-12) ??(4) 切比雪夫距离
dij?maxxik?xjk (2-13)
1?k?m在以上的几种距离中，最常用的是欧式距离，其特点是对坐标系进行平移和旋转变换之后，欧氏距离保持不变，因此对象仍然保持原来的相似结构。
值得注意的是在采用明科夫斯基距离时，一定要采用相同量纲的变量。如果变量的量纲不同，测量值变异范围相差悬殊时，要先进行数据的标准化处理，然后进行计算距离。另外，明科夫斯基距离没有考虑变量的多重相关性。
16
青岛科技大学研究生学位论文
2.4.2相似系数
相似系数体现对象之间的相似程度，相似系数越大，对象的相似性也越大。对于m维空间中的两个对象xi和xj，rij表示对象i和j之间的相似系数，rij则满足以下条件：
rij=1。(1) 绝对值不大于1，即对所有的i和j，恒有rij?1。当且仅当xi?xj时，
(2) 对称性，即对所有的i和j，恒有rij?rji。 常用的相似系数度量方法一般有以下几种形式：
m?x(1) 夹角余弦法：rij?k?1m2k?1ikxjk，用两个向量之间的余弦作为相似系
m2k?1(?xik)(?xjk)数，范围为[-1，1]，当两个向量正交时取值为0，表示完全不相似。
m?(x(2) 相关系数法：rij?k?1mik?xi)(xjk?xj)m，其中xi?jk1mm?x，，
ikk?1?(xk?1ik?xi)2?(xk?1?xj)2xj?1mm?x，计算两个向量之间的相关度，范围为[-1,1]，其中0表示不相关，
jkk?11表示正相关，-1表示负相关。
2.5聚类分析中的聚类准则函数[34]
在样本相似度量的基础上，聚类分析还需要一定的准则函数才能把真正属于同一类的样本聚合到一个类中，而把不同类的样本分离开。如果聚类准则选的好，聚类质量就会高。同时，聚类准则函数还可以用来评价聚类结果的质量，如果聚类质量不满足要求，就要重复执行聚类过程，以便优化聚类结果。
常用的聚类准则函数有如下几种： (1) 误差平方和准则函数Jc
这是一种最常用的聚类准则函数。混合样本集X??x1,x2,?,xn?，在某种相似性度量基础上，它被聚类成C个分离开的类X1,X2,?,XC，每个类分别包括
17
基于遗传算法的k-means聚类挖掘方法研究
n1,n2,?,nc个样本。衡量聚类的质量误差平方和准则函数定义为：
Cnj2 JC???j?1k?1xk(j)?mj (2-14)
式中，mj(j=1,2,3,…,C)是C个聚类中心，取值为每一类中样本的均值，即
mjn?1?j??xj?，j=1,2,…,C。 ???nj?j?1?可以看出，JC是样本和聚类中的函数，在样本集X给定的情况下，JC的值取决于C个聚类中心。JC描述n个样本聚类成C个类型时所产生的总的误差平方和。若JC值越大，说明误差越大，聚类结果越不好。因此，应该寻求使JC最小的聚类结果，即在误差平方和准则下的最优结果。这种聚类通常称为最小方差划分。误差平方和准则函数适用于各类样本比较密集且样本数目悬殊不大的样本分布。当不同类型的样本数目相差较大时，采用误差平方和准则有时可能把样本数目多的类型分开，以便达到总的误差平方和最小。本文采用误差平方和准则函数来衡量聚类结果的好坏。
(2) 加权平均平方距离和准则Jj 加权平均平方距离和准则Jj定义为：
c Jj??j?1*pjsj (2-15)
*式中，sj是类内样本间平均平方距离，即
s?*j2nj(nj?1)??x?xix?xj*x?x*2 (2-16)
因此Jj以先验概率pj为加权的总类内平均平方距离之和，其中先验概率pj可以用各类样本数nj及样本总数n来估计，即
pj?njn,j?1,2,?C (2-17)
当各类样本数目悬殊比较大时，使用加权平均平方距离和准则比使用误差平
18
青岛科技大学研究生学位论文
方和准则容易得到正确的聚类结果。
(3) 类间距离和准则Jb
为了描述聚类结果的类间距离分布状态，可以利用类间距离和准则Jb1以及加权的类间距离和准则Jb2，它们的定义分别如下：
c Jb1??(mj?1cj?m)(mj?m) (2-18)
T Jb2??j?1pj(mj?m)(mj?m) (2-19)
T式中，mj为类cj的样本均值向量，m为全部样本的均值向量，而pj为类cj的先验概率。
类间距离和准则函数描述了不同类型之间的分离程度。显然，类间距离和准则函数的值越大，表示聚类结果的各类分离性越好，所以聚类质量就高。
2.6 聚类算法的分类及其典型算法
目前聚类的方法有很多，总的来说主要分为以下几种类型:划分方法、层次方法、密度方法、模型方法、网格方法、模糊聚类。 2.6.1基于划分的方法
对于给定的包含n个数据对象的数据库，通常基于划分的方法[35]要求用户给定构建数据的最终划分数目k，通过采用目标函数最小化策略，将数据分成k个簇。每个簇同时满足以下两个条件：(1)每个簇至少包含一个数据对象；(2)每个数据对象属于且唯一的属于一个簇(注意：但在某些模糊划分技术中第二个要求可以放宽)。给定划分数目k，算法首先创建一个初始划分，通常采用的方法是随机选取k个数据对象作为初始聚类中心点，然后采用一种迭代的重定位技术，尝试通过对象在划分间移动来改进划分，使得每一次改进之后的分组方案都比前一次好，判断划分好坏的准则是：在同一个簇中的数据对象尽可能相似，不同的簇中的数据对象尽可能相异。
基于划分的聚类算法是一种基于爬山式的优化搜索算法，此法简单、快速而有效，但是此方亦存在不足之处，如：对初始值敏感；对输入顺序敏感；常陷入局部最优等等。根据对象在划分之间移动的衡量参数和簇的表示方法不同，基于
19