资源描述
聚 类聚 类1内容提要n符号说明及定义符号说明及定义n相似性度量相似性度量n聚类分析中的数据类型聚类分析中的数据类型n聚类的准则函数聚类的准则函数n聚类分析的过程聚类分析的过程n聚类方法与算法聚类方法与算法内容提要符号说明及定义2什么是聚类分析？什么是聚类分析？n聚类（簇）：数据对象的集合聚类（簇）：数据对象的集合在同一个聚类（簇）中的对象彼此相似不同簇中的对象则相异n聚类分析聚类分析将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程n聚类是一种无指导的学习：没有预定义的类编号聚类是一种无指导的学习：没有预定义的类编号什么是聚类分析？聚类（簇）：数据对象的集合3有指导的学习有指导的学习 VS.VS.无指导的学无指导的学习习n有指导的学习（用于分类）模型的学习在被告知每个训练样本属于哪个类的“指导”下进行新数据使用训练数据集中得到的规则进行分类n无指导的学习（用于聚类）每个训练样本的类编号是未知的，要学习的类集合或数量也可能是事先未知的通过一系列的度量、观察来建立数据中的类编号或进行聚类有指导的学习 VS.无指导的学习有指导的学习（用于分类）4符号说明符号说明 n2.2.数据样本集数据样本集数据样本集数据样本集记为记为X X X XX X1 1,X,X2 2,X,Xn n，第，第i i个样本记个样本记为为X Xi ix xi1i1,x,xidid，许多情况下聚类的样本本集，许多情况下聚类的样本本集看成是一个看成是一个nd(nnd(n个样本个样本dd个属性个属性)的数据矩阵：的数据矩阵：n 1.数据样本数据样本数据样本数据样本X X，由，由d个属性值组成：个属性值组成：X(x1,x2,xd）,其中其中xi表示样本中的各属性，表示样本中的各属性，d是样本或样本空间的是样本或样本空间的维数（或属性个数）。维数（或属性个数）。符号说明 2.数据样本集记为XX1,X2,Xn，第i5符号说明符号说明 n3.3.簇簇C Ci i：数数据据样样本本集集X X分分成成k k个个簇簇，每每个个簇簇是是相相应应数数据据样样本本的的集集合合，相相似似样样本本在在同同一一簇簇中中，相相异样本在不同簇中。异样本在不同簇中。簇簇C Ci i（i=1,2,ki=1,2,k）中中样样本本的的数数量量n ni i。簇簇记记为为C Ci iX Xj1j1i i,X,Xj2j2i i,X,Xjnijnii i，C Ci i（i i1,1,k,k）是）是X X的子集，如下所示：的子集，如下所示：C C1 1C C2 2C Ck kX X 且且 C Ci iC Cj j，ijij符号说明 3.簇Ci：数据样本集X分成k个簇，每个簇是相应数6符号说明符号说明 用下面的特征来描述簇：用下面的特征来描述簇：簇簇簇簇的的的的质质质质心心心心（centroidcentroid）：（样样本本的的平平均均值值）是是簇簇的的“中中间间值值”，但并不需要是簇中实际点。，但并不需要是簇中实际点。令令n ni i表示簇表示簇C Ci i中样本的数量，中样本的数量，m mi i表示对应样本的均值：表示对应样本的均值：centroidcentroid簇的半径，是簇中两个点间的均方差的平方根。簇的半径，是簇中两个点间的均方差的平方根。符号说明 用下面的特征来描述簇：7定 义 定定义（聚聚聚聚类类）：给定定一一数数据据样本本集集X XX X1 1,X,X2 2,X,Xn n，根根据据数数据据点点间的的相相似似程程度度将将数数据据集集合合分分成成k k簇簇：C C1 1,C,C2 2,C,Ck k的的过程称程称为聚聚类，i=1i=1k kC Ci iX X，C Ci iC Cj j，ijij 相似样本在同一簇中，相异样本在不同簇中。相似样本在同一簇中，相异样本在不同簇中。关关于于同同一一簇簇中中的的样本本比比来来自自不不同同簇簇的的样本本更更为相相似似的判断的判断问题主要涉及以下两个独立的子主要涉及以下两个独立的子问题：a.a.怎样度量样本之间的相似性怎样度量样本之间的相似性怎样度量样本之间的相似性怎样度量样本之间的相似性；b.b.怎怎怎怎样样衡量衡量衡量衡量对样对样本集的一种划分的好坏本集的一种划分的好坏本集的一种划分的好坏本集的一种划分的好坏。定 义 定义（聚类）：给定一数据样本集XX1,X2,8相似性度量相似性度量 相异度矩阵相异度矩阵相异度矩阵相异度矩阵（dissimilarity matrixdissimilarity matrix）用来存储）用来存储n n个个 样本两两之间的相似性，表现形式是一个样本两两之间的相似性，表现形式是一个nnnn维的矩阵：维的矩阵：d(Xd(Xi i，X Xj j)是样本是样本X Xi i和样本和样本X Xj j间相异性的量化表示。间相异性的量化表示。最明显的相似性度量是最明显的相似性度量是样本之间的距离样本之间的距离样本之间的距离样本之间的距离。相似性度量 相异度矩阵（dissimilarity matr9相似性度量相似性度量 X Xi ix xi1i1,x,xidid和和X Xj jx xj1j1,x,xjdjd是是两两个个具具有有d d个个属属性性的的两两个个样本本。距距离离度度量量标准准d d（X Xi i，X Xj j）表表示示第第i i个个样本与第本与第j j个个样本本间的距离。的距离。在聚在聚类分析中，最常用的距离定分析中，最常用的距离定义如下：如下：最著名的距离度量标准是最著名的距离度量标准是d d维空间中的维空间中的欧几里德距离欧几里德距离欧几里德距离欧几里德距离：d d（X Xi i，X Xj j）（）（2 2）1/21/2相似性度量 Xixi1,xid和Xjxj10相似性度量相似性度量 更广义的更广义的d d维空间中的度量为维空间中的度量为明考斯基距离明考斯基距离明考斯基距离明考斯基距离度量度量L Lk k（X Xi i，X Xj j）（）（k k）1/k1/k 通通常常也也被被称称为为L L L Lk k k k范范范范数数数数，欧欧欧欧几几几几里里里里德德德德距距距距离离离离即即L L2 2范范数数。而而L L1 1范数则常被称为范数则常被称为曼哈坦距离或城区距离曼哈坦距离或城区距离曼哈坦距离或城区距离曼哈坦距离或城区距离 相似性度量 更广义的d维空间中的度量为明考斯基距离度量11相似性度量相似性度量 例：对于一个例：对于一个4 4维向量维向量 X X1 11,0,1,01,0,1,0和和 X X2 22,1,-3,-12,1,-3,-1，这些距离的度量标准这些距离的度量标准L L1 1（X X1 1，X X2 2）1+1+4+11+1+4+17 7，L L2 2（X X1 1，X X2 2）（）（1+1+16+11+1+16+1）1/21/24.364.36L L3 3（X X1 1，X X2 2）（）（1+1+64+11+1+64+1）1/31/34.064.06。L Lk k（X Xi i，X Xj j）（）（k k）1/k1/k相似性度量 例：对于一个4维向量12聚类算法聚类算法 聚聚类类算算法法:即即是是先先定定义义一一个个合合适适的的度度量量，然然后后计计算算任任意意两两个个样样本本之之间间的的距距离离。当当两两个个样样本本之之间间的的欧欧几几里里德德距距离离小小于于某某个个阈阈值值d d0 0时时，这这两两个个样样本本就就属属于于同同一一类类。距距离离阈阈值值d d0 0影影响响簇簇的的数数量量和和大大小小，d d0 0越越小小，每每个个簇簇就就越越小小，簇簇的的数数目目就就越越多多。如如果果d d0 0太太大大，则则所所有有样样本本将将会会被被分分为为同同一一簇簇；如如果果d d0 0太太小小，每每个个样样本本又又会会单单成一类成一类。聚类算法 聚类算法:即是先定义一个合适的度量，然后计算13聚类分析中的数据类型聚类分析中的数据类型1.1.区间标度变量区间标度变量2.2.二元变量二元变量3.3.标称型标称型4.4.序数型序数型.混合型变量混合型变量聚类分析中的数据类型1.区间标度变量14区间标度变量区间标度变量n区间标度度量是一个粗略线性标度的连续度量，比如重量、高度等n选用的度量单位将直接影响聚类分析的结果，因此需要实现度度量值的标准化量值的标准化，将原来的值转化为无单位的值，给定一个变量f的度量值，可使用以下转化：计算平均的绝对偏差其中计算标准化的度量值区间标度变量区间标度度量是一个粗略线性标度的连续度量，比如重15二元变量 n一个二元变量只有两种状态：0或1；n一个对象可以包含多个二元变量。n二元变量的可能性表：如何计算两个二元变量之间的相似度？Object iObject j二元变量 一个二元变量只有两种状态：0或1；Object i16二元变量 n对称的 和 不对称的 二元变量对称的二元变量指变量的两个状态具有同等价值，相同权重；例 性别基于对称的二元变量的相似度称为恒定的相似度，可以使用简单匹配系数评估它们的相异度：不对称的二元变量中，变量的两个状态的重要性是不同的；例 HIV阳性 VS HIV阴性基于不对称的二元变量的相似度称为非恒定的相似度，可以使用Jaccard系数评估它们的相异度二元变量 对称的 和 不对称的 二元变量17标称变量n标称变量是二元变量的推广，它可以具有多于两个的状态值。比如：红、绿、蓝、黄。对于标称型变量。n计算标称变量所描述的对象（一个对象可以包含多个标称变量）i和j之间的相异度方法一：简单匹配方法nm:匹配的数目，即对象i和j取值相同的变量的数目(也可加上权重)方法二：对M个标称状态中的每个状态创建一个新的二元变量，并用非对称的二元变量来编码标称变量红绿蓝黄取值0100绿0010蓝标称变量标称变量是二元变量的推广，它可以具有多于两个的状态值18序数型变量n一个序数型变量可以是离散的或者是连续的n序数型变量的值之间是有顺序关系的，比如：讲师、副教授、正教授。n假设f是描述n个对象的一组序数型变量之一，f的相异度计算如下：1.设的i个对象的f值为xif，则用它在值中的序rif代替2.将每个变量的值域映射到0,1的空间3.采用区间标度变量的相异度计算方法计算f的相异度序数型变量一个序数型变量可以是离散的或者是连续的19混合类型的变量n在真实的数据库中，数据对象不是被一种类型的度量所描述，而是被多种类型（即混合类型）的度量所描述，包括：区间标度度量、对称二元变量，不对称二元变量，标称区间标度度量、对称二元变量，不对称二元变量，标称变量，序数型变量合比例标度变量变量，序数型变量合比例标度变量n计算混合型变量描述的对象之间的相异度将变量按类型分组，对每种类型的变量进行单独的聚类分析n在每种聚类分析导出相似结果的情况下可行所有变量一起处理，进行一次聚类分析，可以将不同类型的变量组合在单个相异度矩阵中，把所有有意义的变量转换到共同的值域区间0,1之内混合类型的变量在真实的数据库中，数据对象不是被一种类型的度量20簇间的距离度量标准簇间的距离度量标准用于簇用于簇C Ci i和簇和簇C Cj j之间的距离度量标准是：之间的距离度量标准是：1)1)最小距离：最小距离：其中其中X Xi iCCi i和和X Xj jCCj j2)2)最大距离：最大距离：其中其中X Xi iCCi i和和X Xj jCCj j簇间的距离度量标准用于簇Ci和簇Cj之间的距离度量标准是：213)3)中间距离：中间距离：其中其中m mi i和和m mj j是是C Ci i和和C Cj j的质心的质心4)4)平均距离：平均距离：其中其中X Xi iCCi i和和X Xj jCCj j，且，且n ni i和和n nj j是类是类C Ci i和和C Cj j间的样本数。间的样本数。簇间的距离度量标准簇间的距离度量标准3)中间距离：簇间的距离度量标准22聚类的准则函数聚类的准则函数 误差平方和准则误差平方和准则：其中其中XCXCi i，m mi i是是C Ci i的的质心心 J Je e即所有即所有样本的平方本的平方误差和。差和。聚类的准则函数 误差平方和准则：23聚类的分析过程聚类的分析过程 聚类的分析过程 24聚类技术概览聚类技术概览 n划分的方法划分的方法n层次的方法层次的方法n基于密度的方法基于密度的方法n基于网格的方法基于网格的方法n基于模型的方法基于模型的方法聚类技术概览 划分的方法25 划分方法划分方法（partitioning methodpartitioning method）划划分分方方法法的的基基本本思思想想是是，给给定定一一个个n n个个样样本本的的数数据据库库，划划分分方方法法将将数数据据划划分分为为k k个个划划分分（k=nkX)=3.40=X1 1CC1 1；d(M d(M1 1,X,X2 2)=1.79)=1.79 和和 d(M d(M2 2,X,X2 2)=3.40=X)=3.40=X2 2CC1 1 d(M d(M1 1,X,X3 3)=0.83)=0.83 和和 d(M d(M2 2,X,X3 3)=2.01=X)=2.01=X3 3CC1 1 d(M d(M1 1,X,X4 4)=3.41)=3.41 和和 d(M d(M2 2,X,X4 4)=2.01=X)=2.01=X4 4CC2 2 d(M d(M1 1,X,X5 5)=3.60)=3.60 和和 d(M d(M2 2,X,X5 5)=2.01=X)=2.01=X5 5CC2 2 新簇新簇C C1 1X X1 1,X,X2 2,X,X3 3和和C C2 2X X4 4,X,X5 5基于质心的 kmeans聚类算法第2步：取距离其中一个质心31基于质心的基于质心的 k kmeansmeans聚类算法聚类算法第第3 3步：计算步：计算新的质心新的质心新的质心新的质心：M M1 10.50.5，0.670.67；M M2 25.05.0，1.01.0。相应的方差及总体平方误差分别是：相应的方差及总体平方误差分别是：e e1 12 24.174.17；e e2 22 22.002.00；E E6.176.17；可可以以看看出出第第一一次次迭迭代代后后，总体体误差差显著著减减小小（从从值27.4827.48到到6.176.17）。在在这个个简单的的例例子子中中，第第一一次次迭迭代代同同时也也是是最最后后一一次次迭迭代代，因因为如如果果继续分分析析新新中中心心和和样本本间的的距距离离，样本本将将会会全全部分部分给同同样的簇，不将重新分配，算法停止的簇，不将重新分配，算法停止。基于质心的 kmeans聚类算法第3步：计算新的质心：32k kmeansmeans算法的特点算法的特点 要要求求用用户必必须事事先先给出出要要生生成成的的簇簇的的数数目目，选择初初始划分的最佳方向、更新分区和停止准始划分的最佳方向、更新分区和停止准则。大小很不相同的簇或具有凹状的簇。大小很不相同的簇或具有凹状的簇。算算法法只只有有在在簇簇的的平平均均值被被定定义的的情情况况下下才才能能使使用用，这不不适涉及有分适涉及有分类属性的数据。属性的数据。对噪音和异常点非常敏感噪音和异常点非常敏感 kmeans算法的特点 要求用户必须事先给出要生成的33层次聚类层次聚类 凝聚的层次聚类采用自底向上策略，首先将每个样本作为一个簇，然后合并这些原子簇形成越来越大的簇，减少簇的数目，直到所有的样本都在一个簇中，或某个终结条件被满足。分裂的层次聚类采用自顶向下策略，首先将所有样本置于一个簇中，然后逐渐细分为越来越小的簇，来增加簇的数目，直到每个样本自成一个簇，或者达到某个终结条件，例如达到了某个希望的簇的数目或两个最近的簇之间的距离超过了某个阈值。层次聚类 凝聚的层次聚类采用自底向上策略，首先将每个34凝聚层次聚类凝聚层次聚类 1.1.初初始始化化：计计算算包包含含每每对对样样本本间间距距离离（如如欧欧氏氏距距离离）的的相相似似矩矩阵，把每个样本作为一个簇；阵，把每个样本作为一个簇；2.2.选择：使用相似矩阵查找最相似的两个簇；选择：使用相似矩阵查找最相似的两个簇；3.3.更新：将两个簇合并为一个簇，簇的个数通过合并被更新；更新：将两个簇合并为一个簇，簇的个数通过合并被更新；同同时时更更新新相相似似矩矩阵阵，将将两两个个簇簇的的两两行行距距离离用用1 1行行距距离离替替换换反反映映合并操作。合并操作。4.4.重复：执行重复：执行n-1n-1次步骤次步骤2 2和步骤和步骤3 3；5.5.结结束束：当当所所有有样样本本都都合合并并成成一一个个簇簇或或满满足足指指定定的的簇簇的的数数目目时时，整个过程结束。整个过程结束。凝聚层次聚类 1.初始化：计算包含每对样本间距离（如欧氏距离35 一一单连接算法单连接算法单连接算法单连接算法（最近邻）：（最近邻）：基本思想：两个簇之间的距离用从两个簇中抽取的每基本思想：两个簇之间的距离用从两个簇中抽取的每 对样本的最小距离对样本的最小距离作作为为距距离离度度量量，一一旦旦最最近近的的两两个个类类的的距距离离超超过过某某个个任任意给定的阈值，算法就自动结束。意给定的阈值，算法就自动结束。二二全连接算法全连接算法全连接算法全连接算法三三平均连接算法平均连接算法平均连接算法平均连接算法凝聚层次聚类凝聚层次聚类 一单连接算法（最近邻）：凝聚层次聚类 36 先先将将五五个个样样本本都都分分别别看看成成是是一一个个簇簇，最最靠靠近近的的两两个个簇簇是是3 3和和4 4，因为他们具有最小的簇间距离，因为他们具有最小的簇间距离D D（3 3，4 4）=5.0=5.0。第一步：合并簇第一步：合并簇3 3和和4 4，得到新簇集合，得到新簇集合1,2,1,2,（3434）,5,5 单连接算法单连接算法 先将五个样本都分别看成是一个簇，最靠近的37 更新距离矩阵：更新距离矩阵：D(1,(34)=min(D(1,3),D(1,4)=min(20.6D(1,(34)=min(D(1,3),D(1,4)=min(20.6，22.4)=20.622.4)=20.6D(2,(34)=min(D(2,3),D(2,4)=min(14.1D(2,(34)=min(D(2,3),D(2,4)=min(14.1，11.2)=11.211.2)=11.2D(5,(34)=min(D(3,5),D(4,5)=min(25.0,25.5)=25.0.D(5,(34)=min(D(3,5),D(4,5)=min(25.0,25.5)=25.0.原原有有簇簇1,2,51,2,5间间的的距距离离不不变变，修修改改后后的的距距离离矩矩阵阵如如图图所所示示，在在四四个个簇簇1,2,(34),51,2,(34),5中中，最最靠靠近近的的两两个个簇簇是是1 1和和5 5，它它们们具具有有最最小簇间距离小簇间距离D D（1,51,5）7.077.07。单连接算法单连接算法 更新距离矩阵：单连接算法38 单连接算法单连接算法 单连接算法39 单连接算法单连接算法单连接树单连接树单连接树单连接树 单连接算法单连接树40基于密度的方法基于密度的方法 基基于于样样本本之之间间的的距距离离的的聚聚类类方方法法只只能能发发现现球球状状的的簇簇，基基于于密密度度的的方方法法可可用用来来过过滤滤“噪噪声声”孤孤立立点点数数据据，以以发发现现任任意意形形状状的的簇簇。其其主主要要思思想想是是只只要要临临近近区区域域的的密密度度（样样本本的的数数目目）超超过过某某个个阈阈值值则则继继续续聚聚类类。即即对对于于给给定定簇簇中中的的每每个个样样本本，在在一一个个给给定定范范围围的的区区域域中中必必须至少包含某个数目的样本。须至少包含某个数目的样本。基于密度的方法 基于样本之间的距离的聚类方法只能发现球状41基于密度的方法基于密度的方法 基于密度聚类的相关定义：基于密度聚类的相关定义：a.a.给定对象半径给定对象半径内的区域称为该对象的内的区域称为该对象的邻域。邻域。b.b.如如果果一一个个对对象象的的邻邻域域至至少少包包含含最最小小数数目目MinPtsMinPts个对象，则称该对象为核心对象。个对象，则称该对象为核心对象。c.c.给给定定一一个个对对象象集集合合D D，如如果果p p是是在在q q的的邻邻域域内内，而而q q是是一一个个核核心心对对象象，则则称称对对象象p p从从对对象象q q出出发发是是直直接接密度可达的。密度可达的。基于密度的方法 基于密度聚类的相关定义：42基于密度的方法基于密度的方法 d.d.如果存在一个对象链如果存在一个对象链p p1 1,p,p2 2,p,pn n，p p1 1q q，p pn np p，对对p pi iDD（1=i=n1=i=n），），p pi+1i+1是从是从p pi i关于关于和和MinPtsMinPts直直接密度可达的，则对象接密度可达的，则对象p p是从对象是从对象q q关于关于和和MinPtsMinPts密密度可达的。度可达的。e.e.如果对象集合如果对象集合D D中存在一个对象中存在一个对象o o，使得对象，使得对象p p和和q q是是从从o o关于关于和和MinPtsMinPts密度可达的，那么对象密度可达的，那么对象p p和和q q是关是关于于和和MinPtsMinPts密度相连的。密度相连的。基于密度的方法 d.如果存在一个对象链p1,p2,pn，43基于网格的方法基于网格的方法 n把对象空间量化为有限数目的单元，形成一个网格结构。所有的聚类都在这个网格结构上进行。优点：处理数度快（因为处理时间独立于数据对象数目，只与量化空间中每一维的单元数目有关）基于网格的方法 把对象空间量化为有限数目的单元，形成一个网格44基于模型的方法基于模型的方法 为每每个个簇簇假假定定一一个个模模型型，寻找找数数据据对给定定模模型型的的最最佳佳拟合合。统计学学方方法法和和神神经网网络方法方法 基于模型的方法 为每个簇假定一个模型，寻找数据对给定模45
展开阅读全文