数据挖掘概念、技术--聚类

2020年5月13日星期三DataMining:ConceptsandTechniques1Chapter8.聚类分析什么是聚类分析?聚类分析中的数据类型主要聚类分析方法分类划分方法（PartitioningMethods）分层方法基于密度的方法基于表格的方法基于模型（Model-Based）的聚类方法异常分析总结2020年5月13日星期三DataMining:ConceptsandTechniques3聚类的常规应用模式识别空间数据分析在GIS中，通过聚类发现特征空间来建立主题索引；在空间数据挖掘中，检测并解释空间中的簇；图象处理经济学(尤其是市场研究方面)文档分类分析WEB日志数据来发现相似的访问模式2020年5月13日星期三DataMining:ConceptsandTechniques4应用聚类分析的例子市场销售:帮助市场人员发现客户中的不同群体，然后用这些知识来开展一个目标明确的市场计划；土地使用:在一个陆地观察数据库中标识那些土地使用相似的地区；保险:对购买了汽车保险的客户，标识那些有较高平均赔偿成本的客户；城市规划:根据类型、价格、地理位置等来划分不同类型的住宅；地震研究:根据地质断层的特点把已观察到的地震中心分成不同的类；2020年5月13日星期三DataMining:ConceptsandTechniques5什么是一个好的聚类方法?一个好的聚类方法要能产生高质量的聚类结果——簇，这些簇要具备以下两个特点：高的簇内相似性低的簇间相似性聚类结果的好坏取决于该聚类方法采用的相似性评估方法以及该方法的具体实现；聚类方法的好坏还取决与该方法是能发现某些还是所有的隐含模式；2020年5月13日星期三DataMining:ConceptsandTechniques6RequirementsofClusteringinDataMining可伸缩性能够处理不同类型的属性能发现任意形状的簇在决定输入参数的时候，尽量不需要特定的领域知识；能够处理噪声和异常对输入数据对象的顺序不敏感能处理高维数据能产生一个好的、能满足用户指定约束的聚类结果结果是可解释的、可理解的和可用的2020年5月13日星期三DataMining:ConceptsandTechniques7Chapter8.ClusterAnalysis什么是聚类分析?聚类分析中的数据类型主要聚类分析方法分类划分方法（PartitioningMethods）分层方法基于密度的方法基于表格的方法基于模型（Model-Based）的聚类方法异常分析总结2020年5月13日星期三DataMining:ConceptsandTechniques8两种数据结构数据矩阵(twomodes)差异度矩阵(onemode)npx...nfx...n1x...............ipx...ifx...i1x...............1px...1fx...11x0...)2,()1,(:::)2,3()...ndnd0dd(3,10d(2,1)02020年5月13日星期三DataMining:ConceptsandTechniques9评价聚类质量差异度/相似度矩阵:相似度通常用距离函数来表示；有一个单独的质量评估函数来评判一个簇的好坏；对不同类型的变量，距离函数的定义通常是不同的，这在下面有详细讨论；根据实际的应用和数据的语义，在计算距离的时候，不同的变量有不同的权值相联系；很难定义“足够相似了”或者“足够好了”只能凭主观确定；2020年5月13日星期三DataMining:ConceptsandTechniques10聚类分析中的数据类型区间标度变量（Interval-scaledvariables）:二元变量（Binaryvariables）:标称型，序数型和比例型变量（Nominal,ordinal,andratiovariables）:混合类型变量（Variablesofmixedtypes）:2020年5月13日星期三DataMining:ConceptsandTechniques11区间标度变量数据标准化计算绝对偏差的平均值:其中计算标准度量值(z-score)使用绝对偏差的平均值比使用标准偏差更健壮（robust）.)...211nffffxx(xnm|)|...|||(|121fnffffffmxmxmxnsffififsmxz2020年5月13日星期三DataMining:ConceptsandTechniques12计算对象之间的相异度通常使用距离来衡量两个对象之间的相异度。常用的距离度量方法有:明考斯基距离（Minkowskidistance）:其中i=(xi1,xi2,…,xip)和j=(xj1,xj2,…,xjp)是两个p维的数据对象,q是一个正整数。当q=1时,d称为曼哈坦距离（Manhattandistance）qqppqqjxixjxixjxixjid)||...|||(|),(2211||...||||),(2211ppjxixjxixjxixjid2020年5月13日星期三DataMining:ConceptsandTechniques13SimilarityandDissimilarityBetweenObjects(Cont.)当q=2时,d就成为欧几里德距离:距离函数有如下特性：d(i,j)0d(i,i)=0d(i,j)=d(j,i)d(i,j)d(i,k)+d(k,j)可以根据每个变量的重要性赋予一个权重)||...|||(|),(2222211ppjxixjxixjxixjid2020年5月13日星期三DataMining:ConceptsandTechniques14二元变量二元变量的可能性表其中每个对象有p个变量，且p=a+b+c+dpdbcasumdcdcbabasum0101ObjectiObjectj2020年5月13日星期三DataMining:ConceptsandTechniques15二元变量对称的如果一个二元变量的两个状态是同等价值的，具有相同的权重。即可以任取其中一种状态编码为1或者0对于对称的二员变量，采用简单匹配系数来评价两个对象之间的相异度dcbacbjid),(2020年5月13日星期三DataMining:ConceptsandTechniques16二元变量非对称的如果变量的两个状态不是同样重要的，则称该变量是不对称的。根据惯例，将比较重要通常也是出现概率比较小的状态编码为1，将另一中状态编码为0。对于非对称的二员变量，采用Jaccard系数来评价两个对象之间的相异度cbacbjid),(2020年5月13日星期三DataMining:ConceptsandTechniques17二元变量的相异度计算实例gender是一个对称的二元变量其它的都是非对称的二元变量将值Y和P编码为1,值N编码为0，根据Jaccard系数计算得：NameGenderFeverCoughTest-1Test-2Test-3Test-4JackMYNPNNNMaryFYNPNPNJimMYPNNNN75.021121),(67.011111),(33.010210),(maryjimdjimjackdmaryjackd2020年5月13日星期三DataMining:ConceptsandTechniques18标称变量（NominalVariables）标称变量是二元变量的推广，它可以具有多于两个的状态，比如变量map_color可以有red,yellow,blue,green四种状态。有两种计算相异度的方法：方法1:简单匹配方法M是匹配的数目,p是全部变量的数目方法2:使用二元变量为每一个状态创建一个新的二元变量，可以用非对称的二元变量来编码标称变量。pmpjid),(2020年5月13日星期三DataMining:ConceptsandTechniques19序数型变量一个序数型变量可以是离散的也可以是连续的离散的序数型变量类似于标称变量，除了它的M个状态是以有意义的序列排序的，比如职称连续的序数型变量类似于区间标度变量，但是它没有单位，值的相对顺序是必要的，而其实际大小并不重要。2020年5月13日星期三DataMining:ConceptsandTechniques20序数型变量相异度的计算与区间标度变量的计算方法相类似将xif用它对应的秩代替将每个变量的值域映射到[0.0，1.0]上，使得每个变量都有相同的权重。这通过用zif来替代rif来实现用前面所述的区间标度变量的任一种距离计算方法来计算11fififMrz},...,1{fifMr2020年5月13日星期三DataMining:ConceptsandTechniques21比例标度型变量（Ratio-scaledvariable）比例标度型变量:总是取正的度量值，有一个非线性的标度，近似的遵循指数标度，比如AeBtorAe-Bt计算相异度的方法:采用与处理区间标度变量相同的方法—不是一个好的选择进行对数变换，对变换得到的值在采用与处理区间标度变量相同的方法yif=log(xif)将其作为连续的序数型数据，将其秩作为区间标度的值来对待。2020年5月13日星期三DataMining:ConceptsandTechniques22混合类型的变量一个数据库可能包含了所有这6中类型的变量用以下公式计算对象i，j之间的相异度.其中，p为对象中的变量个数如果xif或xjf缺失（即对象i或对象j没有变量f的值），或者xif=xjf=0，且变量f是不对称的二元变量，则指示项δij(f)=0；否则δij(f)=1)(1)()(1),(fijpffijfijpfdjid2020年5月13日星期三DataMining:ConceptsandTechniques23混合类型的变量f是二元变量或标称变量:ifxif=xjfdij(f)=0,elsedij(f)=1f是区间标度变量:dij(f)=|xif-xjf|/maxhxhf-minhxhf其中h遍取变量f的所有非空缺对象f是序数型或比例标度型计算秩rif计算zif并将其作为区间标度变量值对待11fifMrzif2020年5月13日星期三DataMining:ConceptsandTechniques24Chapter8.ClusterAnalysis什么是聚类分析?聚类分析中的数据类型主要聚类分析方法分类划分方法（PartitioningMethods）分层方法基于密度的方法基于表格的方法基于模型（Model-Based）的聚类方法异常分析总结2020年5月13日星期三DataMining:ConceptsandTechniques25MajorClusteringApproachesPartitioningalgorithms:ConstructvariouspartitionsandthenevaluatethembysomecriterionHierarchyalgorithms:Createahierarchicaldecompositionofthesetofdata(orobjects)usingsomecriterionDensity-based:basedonconnectivityanddensityfunctionsGrid-based:basedonamultiple-levelgranularitystructureModel-