第六章：聚类4

数据挖掘第六章：聚类本章内容6.1什么是聚类分析6.2聚类分析中的数据类型6.3划分方法6.4层次方法6.5基于密度的方法基本要求：掌握聚类的定义、相似度的量化方法问题，掌握基于划分、层次、密度等典型聚类算法聚类分析（简称聚类）：把一个数据对象划分为子集的过程。每个子集称为一个簇（cluster）:同一簇中的数据对象尽可能相似不同簇中的数据对象尽可能不相似无监督学习（unsupervisedlearning）未指定类标签不是通过样本学习簇的数目也是未知的6.1什么是聚类分析（Clustinganalysis）6.1什么是聚类分析HardClustering–每个数据对象仅属于一个簇SoftClustering–每个数据对象可能属于多个簇6.1什么是聚类分析好的聚类算法能产生高质量的簇：较高的簇内相似度较低的簇间相似度好的聚类结果同时依赖于相似度计算方法与聚类算法相似度计算方法通常比聚类算法更重要6.1什么是聚类分析–难点6.1什么是聚类分析–难点ConsiderNdatapointstobesplitinto“c”groups(clusters).Thenumberofpossiblesplits(partitions)isdescribedasEvenforasmallproblemofN=100andc=5weendupwith1067partitionsNc1iiciic1)(c!16.1什么是聚类分析-需求与挑战可伸缩性：如何应对海量数据？处理不同数据类型：数值,布尔,枚举,序数,连接以及混合类型发现任意形状的簇：球形簇：欧几里得距离、曼哈顿距离任意形状：森林火灾边缘基于约束的聚类：各种约束条件下的聚类：ATM部署（考虑河流、公路网）利用领域知识确定输入参数许多聚类算法要求用户输入一定的参数,如希望产生的簇的数目.聚类结果对于输入参数十分敏感参数难以确定,增加了用户的负担,使聚类质量难以控制处理噪音数据的能力：一些聚类算法对于噪音数据敏感,可能导致低质量的聚类结果现实世界中的数据库大都包含了错误数据、缺失数据、离群点聚类高维数据的能力可解释性与可用性聚类结果可用特定的语义解释或与应用相连6.1什么是聚类分析-需求与挑战市场销售:帮助市场人员发现客户中的不同群体，然后用这些知识来开展一个目标明确的市场计划土地使用:在一个陆地观察数据库中标识那些土地使用相似的地区保险:对购买了汽车保险的客户，标识那些有较高平均赔偿成本的客户城市规划:根据类型、价格、地理位置等来划分不同类型的住宅地震研究:根据地质断层特点把已观察到的地震中心分成不同的类WEB文档分类6.1典型应用本章内容6.1什么是聚类分析6.2聚类分析中的数据类型6.3划分方法6.4层次方法6.5基于密度的方法6.2聚类分析中的数据类型数据矩阵(twomodes)差异度矩阵(onemode)npx...nfx...n1x...............ipx...ifx...i1x...............1px...1fx...11x0...)2,()1,(:::)2,3()...ndnd0dd(3,10d(2,1)06.2聚类分析中的数据类型差异度/相似度矩阵:相似度通常用距离函数来表示对不同类型的变量，距离函数的定义通常是不同的根据实际的应用和数据的语义，在计算距离的时候，不同的变量有不同的权值相联系6.2聚类分析中的数据类型区间标度变量（Interval-scaledvariables）二元变量（Binaryvariables）枚举型，序数型和比例型变量（Nominal,ordinal,andratiovariables）混合类型变量（Variablesofmixedtypes）6.2聚类分析中的数据类型-区间标度变量区间标度变量：一种线形标度的连续度量数据标准化计算绝对偏差的平均值:其中计算标准度量值(z-score)使用绝对偏差的平均值比使用标准偏差更健壮（robust）|)|...|||(|121fnffffffmxmxmxns.)...211nffffxx(xnmffififsmxz距离可用于测量两个数据对象间的相似性或差异性常用的距离表示：MinkowskiDistance与是两个q-维的数据对象，q为正整数如果q=1，d为ManhattanDistance6.2聚类分析中的数据类型如果q=2，d为EuclideanDistance性质6.2聚类分析中的数据类型–数值型6.2聚类分析中的数据类型–布尔型布尔型数据的列联表（Contingencytable）简单匹配系数（Simplematchingcoefficient）Jaccard系数pdbcasumdcdcbabasum0101ObjectiObjectj二元变量是对称的二元变量是非对称的6.2聚类分析中的数据类型–布尔型例子Gender是对称属性其余属性是非对称的设属性值Y、P为1,N为0NameGenderFeverCoughTest-1Test-2Test-3Test-4JackMYNPNNNMaryFYNPNPNJimMYPNNNN6.2聚类分析中的数据类型–枚举型标称变量（NominalVariables）是二元变量的推广，具有多于两个的状态，如变量color可有red,yellow,blue,green四种状态。两种计算相异度的方法：方法1:简单匹配方法•M是匹配的数目,p是全部变量的数目方法2:使用二元变量•为每一个状态创建一个新的二元变量，可以用非对称(?)的二元变量来编码标称变量。pmpjid),(一个序数型变量可以是离散的也可以是连续的离散的序数型变量类似于标称变量，除了它的m个状态是以有意义的序列排序的，比如职称连续的序数型变量类似于区间标度变量，但是它没有单位，值的相对顺序是必要的，而其实际大小并不重要。相异度计算：与区间标度变量的计算方法相类似将xif用它对应的秩代替将每个变量的值域映射到[0.0,1.0]上，使得每个变量都有相同的权重。这通过用zif来替代rif来实现用前面所述的区间标度变量的任一种距离计算方法来计算6.2聚类分析中的数据类型–序数型},...,1{fifMr11fififMrz比例标度型变量(Ratio-scaledvariable):总是取正的度量值，有一个非线性的标度，近似的遵循指数标度，比如AeBtorAe-Bt相异度计算:采用与区间标度变量相同的方法—不是一个好的选择进行对数变换，对变换得到的值在采用与处理区间标度变量相同的方法yif=log(xif)将其作为连续的序数型数据，将其秩作为区间标度的值来对待6.2聚类分析中的数据类型–比例标度型一个数据库可能包含了多种类型的变量，可用以下公式计算对象i，j之间的相异度.其中，p为对象中的变量个数；如果xif或xjf缺失（即对象i或对象j没有变量f的值），或者xif=xjf=0，且变量f是不对称的二元变量，则指示项δij(f)=0；否则δij(f)=1)(1)()(1),(fijpffijfijpfdjid6.2聚类分析中的数据类型–混合类型f是二元变量或标称变量:ifxif=xjfdij(f)=0,elsedij(f)=1f是区间标度变量:dij(f)=|xif-xjf|/maxhxhf-minhxhf其中h遍取变量f的所有非空缺对象f是序数型或比例标度型计算秩rif计算zif并将其作为区间标度变量值对待11fifMrzif6.2聚类分析中的数据类型–混合类型本章内容6.1什么是聚类分析6.2聚类分析中的数据类型6.3划分方法6.4层次方法6.5基于密度的方法6.3划分方法-主要的聚类算法聚类算法种类繁多，具体的算法选择取决于数据类型，聚类应用和目的，常用聚类算法包括：划分方法（PartitioningMethods）层次方法（HierarchicalMethods）基于密度的方法（Density-BasedMethods）基于网格的方法（Grid-BasedMethods）基于模型的聚类方法（Model-BasedMethods）实际应用中，往往是多种聚类算法中方法的整合6.3划分方法-主要的聚类算法划分方法:给定n个对象或元组的数据库，一个划分方法构建数据的k个划分，每个划分表示一个簇，并且k=n。•每个组至少包含一个对象•每个对象属于且仅属于一个组划分准则：同一个聚类中的对象尽可能的接近或相关，不同聚类中的对象尽可能的原理或不同簇的表示•k-means算法:由簇的平均值来代表整个簇•k-medoids算法:由处于簇的中心区域的某个值代表整个簇适合发现中小规模数据库中的球状聚类,不适合大规模数据库和处理任意形状的聚类6.3划分方法-主要的聚类算法层次方法:对给定数据对象集合进行层次的分解凝聚方法(自底向上):开始将每个对象作为单独的一个组;然后继续地合并相近的对象或组,直到所有的组合并为一个(层次的最上层),或者达到一个终止条件分裂方法(自顶向下):开始将所有的对象置于一个簇;在迭代的每一步,一个簇被分裂为更小的簇,直到最终每个对象在单独的一个簇中,或者达到一个终止条件6.3划分方法-主要的聚类算法基于密度的方法:只要临近区域的密度(对象或数据点的数目)超过某个阀值,就继续聚类.也就是说,对给定类中的每个数据点,在一个给定范围的区域中必须至少包含一定数目的点该方法可以用来过滤“噪音”与“离群点”数据，发现任意形状的簇6.3划分方法-k-means簇的相似度是关于簇中对象的均值度量，可以看作簇的质心（centroid）k均值算法流程随机选择k个对象，每个对象代表一个簇的初始均值或中心对剩余的每个对象，根据它与簇均值的距离，将他指派到最相似的簇计算每个簇的新均值回到步骤2，循环，直到准则函数收敛常用准则函数：平方误差准则21iCpkimpEi(p是空间中的点，mi是簇Ci的均值)6.3划分方法-k-means012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910K=2ArbitrarilychooseKobjectasinitialclustercenterAssigneachobjectstomostsimilarcenterUpdatetheclustermeansUpdatetheclustermeansreassignreassign6.3划分方法-k-means例子1：Given:{2,4,10,12,3,20,30,11,25},k=2a)K1={2,3},K2={4,10,12,20,30,11,25},m1=2.5,m2=16b)K1={2,3,4},K2={10,12,20,30,11,25},m1=3,m2=18c)K1={2,3,4,10},K2={12,20,30,11,25},m1=4.75,m2=19.6d)K1={2,3,4,10,11,12},K2={20,30,25},m1=7,m2=25当簇与中心值不再改变时，算法结束。6.3划分方法-k-means例子2：药品聚类；k=2MedicineWeightpH-IndexA11B21C43D546.3划分方法-k-means例子2：药品聚类；k=2Step1：选择两个种子节点作为中心Bc,Ac2124.4)14()25(),(5)14()15(),(222221cDdcDd将每个数据对象分配给最近的中心Eu