数据挖掘Chapter9

数据挖掘导论Pang-ningTan,MichaelStieinbach,andVipinKumar著PearsonEducationLTD.范明等译人民邮电出版社第9章聚类分析:附加的问题与算法9.1数据、簇和聚类算法的特性2019年10月21日星期一数据挖掘导论4K均值和DBSCAN比较都是将每个对象指派到单个簇的划分聚类算法，但是K均值一般聚类所有对象，而DBSCAN丢弃被它识别为噪声的对象K均值使用基于原型的概念，而DBSCAN使用基于密度的概念DBSCAN可以处理不同大小和不同形状的簇，并且不太受噪声和离群点的影响。K均值很难处理非球形的簇和不同大小的簇。当簇具有很不相同的密度时，两种算法的性能都很差K均值只能用于具有明确定义的质心的数据。DBSCAN要求密度定义对于数据是有意义的2019年10月21日星期一数据挖掘导论5K均值和DBSCAN比较K均值可以用于稀疏的高维数据，如文档数据。DBSCAN通常在这类数据上性能很差都能扩展,处理非欧几里得数据DBSCAN不对数据的分布做任何假定。基本K均值算法假定所有的簇都来自球形高斯分布,具有不同的均值,但具有相同的协方差矩阵DBSCAN和K均值都寻找使用所有属性的簇，即它们都不寻找可能只涉及某个属性子集的簇K均值可以发现不是明显分离的簇，即便簇有重叠（见图8-2b）也可以发现，但是DBSCAN会合并有重叠的簇2019年10月21日星期一数据挖掘导论6K均值和DBSCAN比较K均值算法的时间复杂度是O(m)，而DBSCAN的时间复杂度是O(m2)DBSCAN多次运行产生相同的结果，而K均值可能产生不同结果DBSCAN自动地确定簇个数,但必须指定Eps（邻域半径）和MinPts（最少点数）；对于K均值，簇个数需要作为参数指定K均值聚类可以看作优化问题，DBSCAN不基于任何形式化模型2019年10月21日星期一数据挖掘导论7数据特性高维性在高维数据集中,传统的欧几里得密度定义（单位体积中点的个数）变得没有意义规模许多聚类算法都不能很好处理大型数据集稀疏性稀疏数据通常由非对称的属性组成噪声和离群点对K均值这样的基于原型的算法有很大影响属性和数据集类型不同的邻近性和密度度量适合于不同类型的数据当属性具有很多不同的类型时，邻近性和密度更难定义2019年10月21日星期一数据挖掘导论8数据特性尺度不同的属性，如高度和重量，可能用不同的尺度度量如果使用欧几里得距离作为邻近性度量，则需要规范化数据空间的数学性质有些聚类技术计算数据点集合的均值另一些算法要求密度的定义对于数据是有意义的2019年10月21日星期一数据挖掘导论9簇特性数据分布某些聚类技术假定数据具有特定的分布形状有些簇具有规则的形状更一般地，簇可以具有任意形状不同大小当簇具有不同的大小时,许多算法不能很好地处理不同密度具有很不相同的密度的簇可能对诸如DBSCAN和K均值等算法造成问题无明显分离的簇当簇接触或重叠时，有些聚类技术将应当分开的簇合并2019年10月21日星期一数据挖掘导论10簇特性簇之间的联系如簇的相对位置大部分聚类技术中，都不明显地考虑簇之间的联系子空间簇簇可能只在维（属性）的一个子集中存在，并且使用一个维集合确定的簇可能与使用另一个维集合确定的簇很不相同2019年10月21日星期一数据挖掘导论11聚类算法的一般特性次序依赖性某些算法所产生的簇的质量和个数可能因数据处理的次序不同而显著地变化非确定性像K均值这样的聚类算法每次运行都产生不同的结果，因为它们依赖于需要随机选择的初始化步骤可伸缩性对于大型数据集，即使具有O(m2)复杂度的算法也不切实际参数选择大部分聚类算法需要用户设置一个或多个参数参数越少越好2019年10月21日星期一数据挖掘导论12聚类算法的一般特性变换聚类问题到其他领域例如,基于图的聚类将发现簇的任务映射成将邻近度图划分成连通分支将聚类作为最优化问题处理聚类常常被看作优化问题：将点划分成簇，根据用户指定的目标函数度量，最大化结果簇集合的优良度穷举的方法在计算上是不可行的9.2基于原型的聚类2019年10月21日星期一数据挖掘导论14基于原型的聚类扩展基于原型的概念允许对象属于多个簇对象以某个权值属于每一个簇用统计分布对簇进行建模对象通过一个随机过程，由一个被若干统计参数（如均值和方差）刻画的统计分布产生簇被约束为具有固定的联系通常,联系是指定近邻关系的约束2019年10月21日星期一数据挖掘导论151.模糊聚类对每个对象和每个簇赋予一个权值，指明该对象属于该簇的程度即,wij是对象xi属于簇Cj的权值模糊集合1965年，LotfiZadeh引进模糊集合论（fuzzysettheory）和模糊逻辑（fuzzylogic）模糊集合论允许对象以0和1之间的隶属度属于一个集合模糊逻辑允许一个陈述以0和1之间的确定度为真例,“天空多云”的为真程度可以定义为天空被云覆盖的百分比2019年10月21日星期一数据挖掘导论16模糊簇数据点的集合X={x1,x2,…,xm}，其中每个点xi是一个n维点模糊簇集C1,C2,...,Ck是X的模糊子集即,对于每个点xi和每个簇Cj，隶属权值（度）wij均已赋予0和1之间的值模糊伪划分（fuzzypsuedo-partition）满足给定点xi的所有权值之和为1每个簇Cj以非零权值至少包含一个点，但不以权值1包含所有的点11kijjwmwmiij102019年10月21日星期一数据挖掘导论17模糊c均值在聚类文献中，不使用簇质心增量更新的K均值版本有时称作c均值模糊c均值算法有时称作FCM算法9.1基本模糊c均值算法1：选择一个初始模糊伪划分，即对所有的wij赋值2：repeat3：使用模糊伪划分，计算每个簇的质心4：重新计算模糊伪划分，即计算wij5：until质心不发生变化替换的终止条件如果误差的变化低于指定的阈值如果所有wij的变化的绝对值都低于指定的阈值2019年10月21日星期一数据挖掘导论18模糊c均值:细节初始化通常使用随机初始化,但必须满足模糊伪划分条件计算质心对于簇Cj，对应的质心cj由下式定义p的选择:p接近1,c均值类似于K均值(划分越清晰);p越大,所有簇质心都趋向于全局质心(划分越模糊).通常,p=2与传统质心不同所有点都要考虑每个点对质心的贡献要根据它的隶属度加权11/mmppjijiijiicwwx2019年10月21日星期一数据挖掘导论19模糊c均值:细节更新模糊伪划分即更新所有的权值wij当p=2时，112211=1(1/(,))(1/(,))kppijijiqqwdistdistxcxc22=11/(,)1/(,)kijijiqqwdistdistxcxc2019年10月21日星期一数据挖掘导论20模糊c均值计算SSE优缺点具有与K均值相同的优点和缺点，但计算密集程度更高一些附加的优点产生指示任意点属于任意簇的程度212k=11SSE(,,...,)=(,)kmpijijjiCCCwdistxc2019年10月21日星期一数据挖掘导论21模糊c均值:例例9.1三个圆形簇上的模糊c均值2019年10月21日星期一数据挖掘导论222.使用混合模型的聚类混合模型（mixturemodels）使用若干统计分布对数据建模数据看作从不同的概率分布得到的观测值的集合,每一个分布对应于一个簇通常,假定正态分布而每个分布的参数提供对应簇的描述使用最大似然估计（maximumlikelihoodestimation，MLE）估计简单统计模型的参数使用期望最大化（expectation-maximization，EM）算法估计混合模型的参数对参数做初始猜测，然后迭代地改进这些估计2019年10月21日星期一数据挖掘导论23混合模型假定有K个分布和m个对象X={x1,x2,…,xm}Θ={1,...,K},其中j为第j个分布的参数prob(xi|j)是第i个对象来自第j个分布的概率选取第j个分布产生一个对象的概率由权值wj(1≤j≤K)给定，其中权值受限于其和为1的约束对象x的概率如果对象以独立的方式产生，则整个对象集的概率是每个对象xi的概率的乘积1(|)(|)KjjjjprobwpxxmiKjjjjmiipwprobprob111)|()|()|(xxX2019年10月21日星期一数据挖掘导论24混合模型:例单变量的高斯混合分布一维高斯分布在点x的概率密度函数是假定有两个高斯分布，具有共同的标准差2，均值分别为4和4。还假定每个分布以等概率选取,于是22()21(|)2xiprobxe22(4)(4)8811(|)2222xxprobxee2019年10月21日星期一数据挖掘导论25混合模型:例(续)混合模型的概率密度函数和混合模型产生的20000个点的直方图2019年10月21日星期一数据挖掘导论26使用最大似然估计模型参数假定m个点服从高斯分布可以通过最大化上式来估计参数=(,).这等价于通过最大化估计参数=(,).这称作最大似然估计(maximumlikelihoodprinciple)L(|X)称为似然函数(likelihoodfunction)l(|X)称为对数似然函数mixieprobL12)(2221)|()|(XXlog2log5.02)()|(ln)|(122mmxproblmiiXX2019年10月21日星期一数据挖掘导论27使用最大似然估计模型参数(续)例：最大似然参数估计200个点的集合，其直方图和最大对数似然图如下使对数概率最大化的参数值是=4.1和=2.1，与基本高斯分布的参数值=4.0和=2.0很接近2019年10月21日星期一数据挖掘导论28EM算法EM算法假定聚类被多个参数模型描述EM算法估计模型参数算法9.2EM算法1：选择模型参数的初始集；（与K均值一样，可以随机地选，也可以用各种方法）2：repeat3：期望步（E步）:对于每个对象,计算每个对象属于每个分布的概率,即计算prob(分布j|xi,Θ);4：最大化步（M步）:给定期望步得到的概率,找出最大化该期望似然的新的参数估计;5：until参数不再改变;（替换地，如果参数的改变低于预先指定的阈值则停止）2019年10月21日星期一数据挖掘导论29EM聚类:例具有三个簇的二维数据点集的EM聚类假定3个簇服从高斯分布，具有不同的均值和相同的协方差矩阵2019年10月21日星期一数据挖掘导论30EM聚类:例具有两个不同密度的簇的二维数据点集的EM聚类两个簇，每个簇大约500个点一个数据集的中心在(4,1)，标准差为2；而另一个的中心在(0,0)，标准差为0.52019年10月21日星期一数据挖掘导论31EM聚类与K均值聚类1000个点的EM聚类与K-均值聚类K-均值不能很好地处理,但EM效果很好混合模型聚类产生的簇K均值聚类产生的簇2019年10月21日星期一数据挖掘导论32混合模型聚类的优点和局限性优点比K均值或模糊c均值更一般,可以发现不同大小和椭球形状的簇用数据拟合一个模型是一种简化数据的好办法只用少量参数描述数据（簇）许多数据集实际上是随机处理的结果，因此应当满足这些模型的统计假设缺点EM算法可能很慢,可收敛不到最优解必须选择正确的模型形式在有噪声和离群点时也可能有问题9.3基于密度的聚类2019年10月21日星期一数据挖掘导论34基于网格的聚类基本思想将每个属性的可能值分割成许多相邻的区间,创建网格单元的集合扫描一遍数据,把对象指派到网格单元中;统