第11章 数据挖掘聚类分析

数据挖掘聚类分析引言“物以类聚，人以群分”。对事物进行分类，是人们认识事物的出发点，也是人们认识世界的一种重要方法。因此，分类学已成为人们认识世界的一门基础科学。在生物、经济、社会、人口等领域的研究中，存在着大量量化分类研究。例如：在生物学中，为了研究生物的演变，生物学家需要根据各种生物不同的特征对生物进行分类。在经济研究中，为了研究不同地区城镇居民生活中的收入和消费情况，往往需要划分不同的类型去研究。在地质学中，为了研究矿物勘探，需要根据各种矿石的化学和物理性质和所含化学成分把它们归于不同的矿石类。在人口学研究中，需要构造人口生育分类模式、人口死亡分类状况，以此来研究人口的生育和死亡规律。但历史上这些分类方法多半是人们主要依靠经验作定性分类，致使许多分类带有主观性和任意性，不能很好地揭示客观事物内在的本质差别与联系；特别是对于多因素、多指标的分类问题，定性分类的准确性不好把握。为了克服定性分类存在的不足，人们把数学方法引入分类中，形成了数值分类学。后来随着多元统计分析的发展，从数值分类学中逐渐分离出了聚类分析方法。随着计算机技术的不断发展，利用数学方法研究分类不仅非常必要而且完全可能，因此近年来，聚类分析的理论和应用得到了迅速的发展。聚类分析就是分析如何对样品（或变量-在多元统计中，它就是一个向量）进行量化分类的问题。通常聚类分析分为Q型聚类和R型聚类。Q型聚类是对样品进行分类处理，R型聚类是对变量进行分类处理。什么是聚类聚类（clustering）就是将数据分组成多个簇（cluster），使得同一个簇的对象之间具有较高的相似度，不同簇的对象相异早在孩提时代，人就通过不断改进下意识中的聚类模式来学会如何区分猫和狗、动物和植物聚类无所不在聚类无所不在聚类无所不在聚类的应用领域有贡献的领域什么情况下应该聚类聚类分析原理聚类与分类相似性及其度量从复杂数据中提取相对简单分组结构的主要工作是找到一个“紧密度”或相似性度量“当我们看到它的时候，我们即可领会”基于特征来测量相似性产生特征提炼特征规范化特征减少特征测量相似性在选择相似性度量时掺杂着大量的主观因素：变量的本质（离散的、连续的、二值的）或测量刻度（标称的、顺序的、间隔的、比值的）及主题知识当所有项被聚类后，通常用距离表明邻近度变量通常基于相关系数或关联度量而聚合距离度量的常见计算方法令O1和O2表示客观世界中的两个对象，O1和O2之间的距离（相异性）是一个实数，用distance(O1,O2)或d(O1，O2)明考夫斯基距离（4）幂距离（5）差异百分率二元属性对象的相似性当项不能用有意义的p维测量表示时，项对之间的比较通常根据某些特征的存在和缺失完成，相似的项具有更多的共同项引入二元变量来描述是否具有某种特征，若具有该特征变量值为1，否则变量值为0个体对的变量得分计算得分矩阵11的个数为a10的个数为b01的个数为c00的个数为d相似性系数简单匹配系数SMCJaccard系数Rao系数实例分析聚类的基本类型层次聚类自底向上（凝聚）假定所有项属于一个单独簇，然后寻找最佳配对并合并成一个新的簇自顶向下（分裂）开始将所有数据看作一个簇，考虑所有可能的方法，将簇一分为二选择最佳划分，并递归第在这两个上继续划分凝聚层次聚类依靠共同的距离度量，聚类过程从寻找距离最近的簇开始，并把这两个簇合并为一个簇。在开始时，让每个对象自成一簇，每个簇都以选定的距离度量定义合并后，如何确定新簇之间的距离？？？单连接（singlelinkage）完全连接（completelinkage）单连接（最近邻）两个簇的距离由不同簇的两个最近的对象间的距离决定簇的距离是属于不同簇的两个样本间的最近距离d(c1,c2)=min{d(o,O)}完全连接（最远邻）两个簇的距离隶属于不同簇的距离最远的两个对象的距离所决定（最远邻的距离）组平均两个簇的距离就是隶属不同簇的所有对象的距离的平均加权平均组质心加权组质心沃德法单连接完全连接层次聚类的优缺点优点可以通过观察树状图来确定正确的簇数目层次的本质很好地反映了人类对某些领域的直觉树状图的一个潜在应用时可以用来检测离群点缺点有时会表现出无意义的或者不合逻辑的模式无需事先指定簇的数目层次本质很好地反映了人类对某些领域认识的直觉可伸缩性不好：时间复杂性至少为O(n2),n是所有对象的数量和任何启发式搜素算法一样，局部最优是一个问题对结果的解释具有主观性算法的步骤决定k的取值初始化k个簇中心通过把对象分配给最近的簇中心来确定N个对象的簇隶属关系假设上面所得的隶属关系是正确的，重新计算k个簇中心若在最后一次迭代中N个对象无一再改变隶属关系，则退出，否则再转第3步K-means算法基本思想是初始随机给定K个簇中心，按照最邻近原则把待分类样本点分到各个簇。然后按平均法重新计算各个簇的质心，从而确定新的簇心。一直迭代，直到簇心的移动距离小于某个给定的值K-Means聚类算法主要分为三个步骤：

(1)第一步是为待聚类的点寻找聚类中心

(2)第二步是计算每个点到聚类中心的距离，将每个点聚类到离该点最近的聚类中去

(3)第三步是计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心

反