第第5章章 聚类分析聚类分析 本章概述 本章的学习目标主要内容1 什么是聚类什么是聚类l聚类（聚类（Clustering）就是将数据分组成为多个类）就是将数据分组成为多个类（（Cluster或译为簇）或译为簇）l在同一个类内对象之间具有较高的相似度，不同类之在同一个类内对象之间具有较高的相似度，不同类之间的对象差别较大间的对象差别较大簇之间的距离最大化在一个簇内的距离最小化2 l从机器学习的角度讲，簇相当于隐藏模式聚类是搜从机器学习的角度讲，簇相当于隐藏模式聚类是搜索簇的无监督学习过程索簇的无监督学习过程l与分类不同，无监督学习不依赖预先定义的类或带类与分类不同，无监督学习不依赖预先定义的类或带类标记的训练实例，需要由聚类学习算法自动确定标记，标记的训练实例，需要由聚类学习算法自动确定标记，而分类学习的实例或数据对象有类别标记而分类学习的实例或数据对象有类别标记3 什么是聚类什么是聚类l早在孩提时代，人就通过不断改进下意识中的聚类模早在孩提时代，人就通过不断改进下意识中的聚类模式来学会如何区分猫和狗，动物和植物式来学会如何区分猫和狗，动物和植物l将周围的人分为家人和非家人将周围的人分为家人和非家人4 聚类分析无处不在聚类分析无处不在l谁经常光顾商店，谁买什么东西，买多少？谁经常光顾商店，谁买什么东西，买多少？►按忠诚卡记录的光临次数、光临时间、性别、按忠诚卡记录的光临次数、光临时间、性别、年龄、职业、购物种类、金额等变量分类年龄、职业、购物种类、金额等变量分类►这样商店可以这样商店可以….►识别顾客购买模式（如喜欢一大早来买酸奶和识别顾客购买模式（如喜欢一大早来买酸奶和鲜肉，习惯周末时一次性大采购）鲜肉，习惯周末时一次性大采购）►刻画不同的客户群的特征（用变量来刻画，就刻画不同的客户群的特征（用变量来刻画，就象刻画猫和狗的特征一样）象刻画猫和狗的特征一样）5 什么情况下需要聚类什么情况下需要聚类l为什么这样分类？为什么这样分类？l因为每一个类别里面的人消费方式都不一样，需要针因为每一个类别里面的人消费方式都不一样，需要针对不同的人群，制定不同的关系管理方式，以提高客对不同的人群，制定不同的关系管理方式，以提高客户对公司商业活动的响应率。
户对公司商业活动的响应率6 聚类分析无处不在聚类分析无处不在l挖掘有价值的客户，并制定相应的促销策略：挖掘有价值的客户，并制定相应的促销策略：►如，对经常购买酸奶的客户如，对经常购买酸奶的客户►对累计消费达到对累计消费达到12个月的老客户个月的老客户l针对潜在客户派发广告，比在大街上乱发传单命中率针对潜在客户派发广告，比在大街上乱发传单命中率更高，成本更低！更高，成本更低！7 聚类分析无处不在聚类分析无处不在l谁是银行信用卡的黄金客户？谁是银行信用卡的黄金客户？►利用储蓄额、刷卡消费金额、诚信度等变量对客利用储蓄额、刷卡消费金额、诚信度等变量对客户分类，找出户分类，找出“黄金客户黄金客户”！！►这样银行可以这样银行可以……►制定更吸引的服务，留住客户！比如：制定更吸引的服务，留住客户！比如：•一定额度和期限的免息透资服务！一定额度和期限的免息透资服务！•百盛的贵宾打折卡！百盛的贵宾打折卡！•在他或她生日的时候送上一个小蛋糕！在他或她生日的时候送上一个小蛋糕！l套餐的制定套餐的制定8 聚类的应用领域聚类的应用领域l经济领域：经济领域：►帮助分析人员从客户数据库中发现不同的客户群，帮助分析人员从客户数据库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。
并且用购买模式来刻画不同的客户群的特征►谁喜欢打国际长途，在什么时间，打到那里？谁喜欢打国际长途，在什么时间，打到那里？►对住宅区进行聚类，确定自动提款机对住宅区进行聚类，确定自动提款机ATM的安放的安放位置位置►股票市场板块分析，找出最具活力的板块龙头股股票市场板块分析，找出最具活力的板块龙头股►企业信用等级分类企业信用等级分类►……9 l生物学领域生物学领域►推导植物和动物的分类推导植物和动物的分类(门、纲、目、科、属、种门、纲、目、科、属、种)；；►对基因分类，获得对种群的认识对基因分类，获得对种群的认识l数据挖掘领域数据挖掘领域►作为其他数学算法的预处理步骤，获得数据分布作为其他数学算法的预处理步骤，获得数据分布状况，集中对特定的类做进一步的研究状况，集中对特定的类做进一步的研究10 聚类分析原理介绍聚类分析原理介绍l聚类分析中聚类分析中“类类”的特征：的特征：►聚类所说的类不是事先给定的，而是根据数据的聚类所说的类不是事先给定的，而是根据数据的相似性和距离来划分相似性和距离来划分►聚类的数目和结构都没有事先假定聚类的数目和结构都没有事先假定11 有多少个簇？四个簇2个簇6个簇簇簇(类类)的概念可能是模糊的的概念可能是模糊的如何对汉语方言进行分类？如何对汉语方言进行分类？12 聚类分析原理介绍聚类分析原理介绍l我们看以下的例子：我们看以下的例子：l有有16张牌张牌l如何将他们分为如何将他们分为 一组一组的牌呢？一组一组的牌呢？AKQJ13 聚类分析原理介绍聚类分析原理介绍l分成四组分成四组l每组里每组里花色相同花色相同l组与组之间花色相异组与组之间花色相异AKQJ花色相同的牌为一副花色相同的牌为一副Individual suits14 聚类分析原理介绍聚类分析原理介绍l分成四组分成四组l符号相同符号相同的牌为一组的牌为一组AKQJ符号相同的的牌符号相同的的牌Like face cards15 聚类分析原理介绍聚类分析原理介绍l分成两组分成两组l颜色相同颜色相同的牌为一组的牌为一组AKQJ颜色相同的配对颜色相同的配对Black and red suits16 聚类分析原理介绍聚类分析原理介绍l分成两组分成两组l大小程度相近大小程度相近的牌分到的牌分到一组一组AKQJ大配对和小配对大配对和小配对Major and minor suits17 聚类分析原理介绍聚类分析原理介绍l这个例子告诉我们，分这个例子告诉我们，分组的意义在于我们怎么组的意义在于我们怎么定义并度量定义并度量“相似性相似性” (Similar)l因此衍生出一系列度量因此衍生出一系列度量相似性的方法相似性的方法AKQJ大配对和小配对大配对和小配对Major and minor suits18 聚类分析原理介绍聚类分析原理介绍变量按测量尺度（变量按测量尺度（Measurement Level）分类）分类l区间（区间（Interval）值变量）值变量►连续变量，如长度、重量、速度、温度等连续变量，如长度、重量、速度、温度等l有序（有序（Ordinal）值变量）值变量►等级变量，不可加，但可比，如一等、二等、三等级变量，不可加，但可比，如一等、二等、三等奖学金等奖学金l名词性（名词性（Nominal）变量）变量►类别变量，不可加也不可比，如性别、职业等类别变量，不可加也不可比，如性别、职业等l下面介绍对各种不同类型的变量如何进行度量下面介绍对各种不同类型的变量如何进行度量19 度量对象间的相似与差异度量对象间的相似与差异l对象间的对象间的相似度相似度或或相异度相异度通常基于每对对象间的距离通常基于每对对象间的距离的计算的计算l欧几里得距离欧几里得距离lMinkowski距离距离20 度量对象间的相似与差异度量对象间的相似与差异l曼哈顿距离曼哈顿距离(Block距离距离)l欧几里得距离是当欧几里得距离是当q=2时的时的Minkowski距离的特例距离的特例l曼哈顿距离是当曼哈顿距离是当q=1时的时的Minkowski距离的特例距离的特例l当当q= 时得到无得到无穷距离距离(无无穷范数范数)，由向量，由向量间各分量各分量的最大差决定的最大差决定21 度量对象间的相似与差异度量对象间的相似与差异l距离所应满足的数学性质距离所应满足的数学性质►d(i,j) 0►d(i,i) = 0►d(i,j) = d(j,i)►d(i,j) d(i,k) + d(k,j)l除此之外，还可以使用除此之外，还可以使用加权加权的距离的距离22 二元属性变量二元属性变量l二元变量只有两种状态：二元变量只有两种状态：0或或1►例如给定描述患者的变量例如给定描述患者的变量smoker，，1表示患者抽表示患者抽烟，烟，0表示不抽烟表示不抽烟l像处理一般数值量一样来处理二元变量会产生误导的像处理一般数值量一样来处理二元变量会产生误导的聚类结果聚类结果23 二元属性变量的相依表二元属性变量的相依表l如果所有的二元变量具有相同的权重，则可以得到上如果所有的二元变量具有相同的权重，则可以得到上表所示的两行两列的相依表表所示的两行两列的相依表►q是对象是对象i和和j值都为值都为1的变量的数目的变量的数目►r是在对象是在对象i值为值为1，但对象，但对象j值为值为0的变量数目的变量数目►……►变量的总数是变量的总数是p=q+r+s+tObject iObject j24 对称二元变量和非对称二元变量对称二元变量和非对称二元变量l对二元变量的相异度计算还要考虑变量的对二元变量的相异度计算还要考虑变量的对称性对称性l对称二元变量对称二元变量►如果他的两个状态具有同等价值和相等的权重如果他的两个状态具有同等价值和相等的权重►输出用输出用0或或1编码没有优先权，如性别编码没有优先权，如性别l对称二元相异度对称二元相异度25 对称二元变量和非对称二元变量对称二元变量和非对称二元变量l非对称二元变量非对称二元变量►如果状态的输出不是同等重要的如果状态的输出不是同等重要的►例如基本检查的阳性和阴性结果。
根据惯例，将例如基本检查的阳性和阴性结果根据惯例，将比较重要的输出结果比较重要的输出结果(通常也是出现机率较小的结通常也是出现机率较小的结果果)编码为编码为1，而将另一种结果编码为，而将另一种结果编码为0(如如HIV阴性阴性)►给定两个非对称二元变量，两个都取值给定两个非对称二元变量，两个都取值1的情况认的情况认为比两个都取值为比两个都取值0的情况更有意义的情况更有意义l非对称二元相异度非对称二元相异度26 对称二元变量和非对称二元变量对称二元变量和非对称二元变量l有时采用两个二元变量的有时采用两个二元变量的相似度相似度而不是而不是相异度相异度来测量来测量他们之间的距离他们之间的距离l非对称二元相似度非对称二元相似度sim(i,j)如下定义如下定义l系数系数sim(i,j)常称作常称作Jaccard系数系数27 例例 二元变量之间的相异度二元变量之间的相异度l假设一个患者记录表包含上述属性，其中假设一个患者记录表包含上述属性，其中name是标是标识符，性别是对称二元属性，其余的属性都是非对称识符，性别是对称二元属性，其余的属性都是非对称二元属性二元属性l对于非对称属性，值对于非对称属性，值Y和和P(positive)置为置为1，值，值N(no或或negative)置为置为028 例例 二元变量之间的相异度二元变量之间的相异度l假设对象之间的距离只基于非对称变量来计算。
根据假设对象之间的距离只基于非对称变量来计算根据公式，三个患者公式，三个患者Jack、、Mary和和Jim两两之间的两两之间的相异相异度度如下：如下：l度量显示度量显示Jim和和Mary不大可能患相似的疾病，而不大可能患相似的疾病，而Jack和和Mary最可能患相似的疾病最可能患相似的疾病29 名词性属性变量名词性属性变量l可取多个相异值，之间没有序关系可取多个相异值，之间没有序关系l如产品颜色可以取：红、黄、绿、蓝等如产品颜色可以取：红、黄、绿、蓝等►也可以用也可以用0，，1，，2，，3等代码来表示，但注意这里等代码来表示，但注意这里的数字仅是标识，不能做运算的数字仅是标识，不能做运算l两个对象两个对象i和和j之间的相异度简单的处理方法是计算不之间的相异度简单的处理方法是计算不匹配率：匹配率：►其中其中p是全部变量的数目，是全部变量的数目，m是匹配的数目是匹配的数目l也可以构造一个大的二元变量数组，再按二元变量处也可以构造一个大的二元变量数组，再按二元变量处理理30 余弦相似度余弦相似度l文档数据文档数据31 l 在在信信息息检索索、、文文本本文文档档聚聚类和和生生物物学学分分类中中，，需需要要对包含了大量符号包含了大量符号实体的复体的复杂对象象进行比行比较和聚和聚类l为了了测量量复复杂对象象间的的距距离离，，通通常常期期望望放放弃弃传统的的度度量距离量距离计算，而引入算，而引入非度量非度量的相似度函数的相似度函数l 如果如果d1 和和 d2 是两个文档向量，是两个文档向量，则 cos( d1, d2 ) = (d1 d2) / ||d1|| ||d2|| , l 其其中中 表表示示向向量量的的点点积(内内积)，，|| d ||表表示示向向量量的的范范数数.l问题：：余余弦弦相相似似度度的的范范围？？取取最最大大值时是是否否两两个个向向量量相等？相等？余弦相似度余弦相似度32 余弦相似度计算的例子余弦相似度计算的例子ld1 = 3 2 0 5 0 0 0 2 0 0 ld2 = 1 0 0 0 0 0 0 1 0 2 ld1 d2 = 3*1 + 2*0 + 0*0 + 5*0 + 0*0 + 0*0 + 0*0 + 2*1 + 0*0 + 0*2 = 5l||d1|| = (3*3+2*2+0*0+5*5+0*0+0*0+0*0+2*2+0*0+0*0)0.5 = (42) 0.5 = 6.481l||d2|| = (1*1+0*0+0*0+0*0+0*0+0*0+0*0+1*1+0*0+2*2) 0.5 = (6) 0.5 = 2.245lcos( d1, d2 ) = 5/(6.481*2.245).315033 如何选择恰当的度量如何选择恰当的度量l有很多方法用来选择一个具体的相似度或距离函数，有很多方法用来选择一个具体的相似度或距离函数，但是还没有一个通用的标准用来指导这样的选择但是还没有一个通用的标准用来指导这样的选择l这种度量的选择高度依赖于具体的应用。
这种度量的选择高度依赖于具体的应用34 主要聚类方法的分类主要聚类方法的分类l划分方法划分方法：给定：给定n个对象，划分方法构建数据的个对象，划分方法构建数据的k个个划分，每个划分表示一簇，划分，每个划分表示一簇，k<=n，满足如下要求，满足如下要求►每组至少包含一个对象每组至少包含一个对象►每个对象必须只属于一个组每个对象必须只属于一个组(在软聚类技术中可放在软聚类技术中可放宽宽)l对于给定的划分数目对于给定的划分数目k，通常创建一个初始划分，然，通常创建一个初始划分，然后采用迭代方法尝试通过对象在组间移动来改进划分后采用迭代方法尝试通过对象在组间移动来改进划分35 主要聚类方法的分类主要聚类方法的分类l好的划分的标准：同一个簇中的对象之间尽可能相似，好的划分的标准：同一个簇中的对象之间尽可能相似，不同簇的对象尽可能有大的差异不同簇的对象尽可能有大的差异l常用方法：常用方法：►k均值方法：每个簇都用该簇中对象的均值来表示均值方法：每个簇都用该簇中对象的均值来表示►k中心点法：每个簇用接近簇中心的一个对象来表中心点法：每个簇用接近簇中心的一个对象来表示示36 l层次方法创建给定数据对象的层次分解层次方法创建给定数据对象的层次分解l根据使用的方法，层次的方法可以分类为凝聚的或分根据使用的方法，层次的方法可以分类为凝聚的或分裂的方法裂的方法►凝聚法：也称自底向上的方法，开始将每个对象凝聚法：也称自底向上的方法，开始将每个对象形成单独的组，然后逐次合并相近的对象或组，形成单独的组，然后逐次合并相近的对象或组，直到所有的组合并为一个或满足某个终止条件直到所有的组合并为一个或满足某个终止条件►分裂法：自顶向下的方法，一开始将所有对象置分裂法：自顶向下的方法，一开始将所有对象置于一个簇中，每次迭代，簇分裂为更小的簇，直于一个簇中，每次迭代，簇分裂为更小的簇，直到每个对象在一个簇中或满足终止条件到每个对象在一个簇中或满足终止条件层次方法层次方法37 基于模型的方法基于模型的方法l为每簇假定一个模型，并寻找数据对给定模型的最为每簇假定一个模型，并寻找数据对给定模型的最 佳拟合佳拟合l常见算法常见算法►EM算法：基于统计模型并进行期望最大化分析算法：基于统计模型并进行期望最大化分析►COBWEB：概念学习算法，进行概率分析并把概：概念学习算法，进行概率分析并把概念作为簇模型念作为簇模型►SOM(自组织映射自组织映射)：一种基于神经网络的算法，：一种基于神经网络的算法，通过把高维数据映射到通过把高维数据映射到2维或维或3维特征空间进行聚维特征空间进行聚类类38 划分聚类划分聚类原始点原始点划分聚类划分聚类39 层次聚类层次聚类Traditional Hierarchical ClusteringNon-traditional Hierarchical ClusteringNon-traditional DendrogramTraditional Dendrogram40 l互斥的与非互斥的互斥的与非互斥的►在非互斥聚类中，点可以属于多个簇在非互斥聚类中，点可以属于多个簇.►可以表示多重类或边界类可以表示多重类或边界类l模糊聚类与非模糊聚类模糊聚类与非模糊聚类►模糊聚类中，一个点到隶属于每个簇的情况可模糊聚类中，一个点到隶属于每个簇的情况可以用一个在以用一个在0到到1之间的隶属度描述之间的隶属度描述其他的聚类类型的差别其他的聚类类型的差别41 不同的簇类型不同的簇类型l明显分离的簇明显分离的簇l基于中心的簇基于中心的簇l基于近邻的簇基于近邻的簇l基于密度的簇基于密度的簇l概念簇概念簇42 不同的簇类型不同的簇类型l明显分离的簇明显分离的簇: ►每个点到同簇中任意点的距离比到不同簇中所每个点到同簇中任意点的距离比到不同簇中所有点的距离更近有点的距离更近3 个明显分离的簇个明显分离的簇43 不同的簇类型不同的簇类型l基于中心的簇基于中心的簇► 每个点到其簇中心的距离比到任何其他簇中心每个点到其簇中心的距离比到任何其他簇中心的距离更近的距离更近 ►簇的中心通常是重心，簇中所有点的平均值，簇的中心通常是重心，簇中所有点的平均值，或者是簇的原型，即一个簇中最具代表性的点或者是簇的原型，即一个簇中最具代表性的点4 center-based clusters44 不同的簇类型不同的簇类型l基于近邻的簇基于近邻的簇(基于图的基于图的——连通分支连通分支)►每个点到该簇中至少一个点的距离比到不同簇每个点到该簇中至少一个点的距离比到不同簇中任意点的距离更近中任意点的距离更近8 contiguous clusters45 不同的簇类型不同的簇类型l基于密度的簇基于密度的簇►簇是被低密度区域分开的高密度区域簇是被低密度区域分开的高密度区域. ►当簇不规则或互相盘绕，并且有噪声和离群点当簇不规则或互相盘绕，并且有噪声和离群点时，通常使用基于密度的簇定义时，通常使用基于密度的簇定义6 density-based clusters46 划分方法划分方法l对于一个给定的对于一个给定的n个对象或元组的数据库，采用目标个对象或元组的数据库，采用目标函数最小化的策略，通过迭代把数据分成函数最小化的策略，通过迭代把数据分成k个划分块，个划分块，每个划分块为一个簇，这就是划分方法。
每个划分块为一个簇，这就是划分方法 l划分方法满足两个条件：划分方法满足两个条件：►（（1）每个分组至少包含一个对象；）每个分组至少包含一个对象；►（（2）每个对象必属于且仅属于某一个分组每个对象必属于且仅属于某一个分组 l常见的划分方法有常见的划分方法有k-均值方法和均值方法和k-中心点方法其他中心点方法其他方法大都是这两种方法的变形方法大都是这两种方法的变形 47 k-均值算法均值算法 lk-均值聚类算法的核心思想是通过迭代把数据对象划均值聚类算法的核心思想是通过迭代把数据对象划分到不同的簇中，以求分到不同的簇中，以求目标函数目标函数最小化，从而使生成最小化，从而使生成的簇尽可能地紧凑和独立的簇尽可能地紧凑和独立►随机选取随机选取k个对象作为初始的个对象作为初始的k个簇的质心；个簇的质心；►将其余对象根据其与各个簇质心的距离分配到最将其余对象根据其与各个簇质心的距离分配到最近的簇；再求新形成的簇的质心近的簇；再求新形成的簇的质心►这个迭代重定位过程不断重复，直到目标函数最这个迭代重定位过程不断重复，直到目标函数最小化为止小化为止 48 k-均值算法均值算法 算法算法K均值均值输入输入K：簇的数目：簇的数目D：包含：包含n个对象的点集个对象的点集输出输出K个簇的集合个簇的集合方法方法1从从D中任意选择中任意选择K个点作为初始簇中心个点作为初始簇中心2Repeat3根据簇中对象的均值，将每个对象再指派到最相似的簇根据簇中对象的均值，将每个对象再指派到最相似的簇4更新簇均值，即计算每个簇中对象的均值更新簇均值，即计算每个簇中对象的均值5Until 不再发生变化不再发生变化49 初始质心的选择非常重要初始质心的选择非常重要50 使用使用K均值算法的迭代过程均值算法的迭代过程51 K-K-均值算法均值算法 012345678910012345678910012345678910012345678910K=2Arbitrarily choose K object as initial cluster centerAssign each objects to most similar centerUpdate the cluster meansUpdate the cluster meansreassignreassign52 欧几里得空间中的数据欧几里得空间中的数据l通常使用误差的平方和通常使用误差的平方和(sum of the squared error, SSE)作为度量聚类质量的目标函数作为度量聚类质量的目标函数lSSE也称散布也称散布(scatter)：计算每个数据点的误差：计算每个数据点的误差——即它到最近质心的欧几里得距离，然后计算误差的即它到最近质心的欧几里得距离，然后计算误差的 平方和平方和l给定由两次运行给定由两次运行K均值产生的两个不同的簇集，我们均值产生的两个不同的簇集，我们更喜欢误差的平方和最小的那个，这意味着聚类的更喜欢误差的平方和最小的那个，这意味着聚类的 原型原型(质心质心)是簇中点的更好代表是簇中点的更好代表53 欧几里得空间中的数据欧几里得空间中的数据l可以证明在欧几里得空间中是簇的可以证明在欧几里得空间中是簇的SSE最小的质心最小的质心 就是均值就是均值lK均值算法的第均值算法的第3步和第步和第4步试图直接最小化步试图直接最小化SSE►步骤步骤3通过将点指派到最近的质心形成簇，最小化通过将点指派到最近的质心形成簇，最小化关于给定质心集的关于给定质心集的SSE►步骤步骤4重新计算质心，进一步最小化重新计算质心，进一步最小化SSEl问题：问题：K均值的步骤均值的步骤3和和4只能找到关于只能找到关于SSE的的局部最局部最小值小值，因为它们是对选定的质心和簇，而不是对，因为它们是对选定的质心和簇，而不是对 所所有可能的选择来优化有可能的选择来优化SSE54 初始质心的选择非常重要初始质心的选择非常重要55 初始质心的选择非常重要初始质心的选择非常重要56 随机初始化随机初始化l由于由于K均值算法会陷入局部最小值而得到次优聚类，均值算法会陷入局部最小值而得到次优聚类，一种常用的选取初始质心的方法是多次运行，每次使一种常用的选取初始质心的方法是多次运行，每次使用一组不同的随机初始质心，然后选取具有最小用一组不同的随机初始质心，然后选取具有最小SSE的簇集的簇集l下面我们看一看这种方法的问题下面我们看一看这种方法的问题l下页的图中有下页的图中有5个簇对，每个簇对有上下两个簇。
个簇对，每个簇对有上下两个簇►如果每个簇对有两个初始质心，则效果较好如果每个簇对有两个初始质心，则效果较好►如果有一个簇对中只有一个初始中心，而另一个如果有一个簇对中只有一个初始中心，而另一个簇对中有三个初始中心，则会出现错误簇对中有三个初始中心，则会出现错误57 Starting with two initial centroids in one cluster of each pair of clusters5个簇对，个簇对，10个簇的例子个簇的例子58 Starting with two initial centroids in one cluster of each pair of clusters5个簇对，个簇对，10个簇的例子个簇的例子59 Starting with some pairs of clusters having three initial centroids, while other have only one.5个簇对，个簇对，10个簇的例子个簇的例子60 Starting with some pairs of clusters having three initial centroids, while other have only one.5个簇对，个簇对，10个簇的例子个簇的例子61 解决初始质心设置问题的方法解决初始质心设置问题的方法l多次运行多次运行►不一定总有效不一定总有效l对数据作采样并使用层次聚类，从中提取对数据作采样并使用层次聚类，从中提取K个簇并使个簇并使用这些簇的质心作为初始质心用这些簇的质心作为初始质心l选取多于选取多于k个的初始质心，然后从其中选择个的初始质心，然后从其中选择k个个►最分离的最分离的k个点个点l后处理后处理l二分二分K-均值均值62 二分二分K均值均值l基本思想：基本思想：l为了得到为了得到K个簇，将所有点的集合分裂成两个簇，从个簇，将所有点的集合分裂成两个簇，从这些簇中选取一个继续分裂，如此下去直到产生这些簇中选取一个继续分裂，如此下去直到产生K个个簇簇l可以使用多种方法选择待分裂的簇可以使用多种方法选择待分裂的簇►最大的簇最大的簇►具有最大具有最大SSE的簇的簇►基于大小和基于大小和SSEl二分二分K均值得到的最终的簇集并不代表使均值得到的最终的簇集并不代表使SSE局部最局部最小的聚类小的聚类63 二分二分K均值算法均值算法算法算法二分二分K均值均值1初始化簇表，使之包含有所有的点组成的簇初始化簇表，使之包含有所有的点组成的簇2Repeat3从簇表中取出一个簇从簇表中取出一个簇4对选定的簇进行多次二分试验对选定的簇进行多次二分试验5for i=1 to 试验次数试验次数 do6 使用基本使用基本K均值，二分选定的簇均值，二分选定的簇7end for8从二分试验中选择具有最小总从二分试验中选择具有最小总SSE的两个簇的两个簇9将这两个簇添加到簇表中将这两个簇添加到簇表中10until 簇表中包含簇表中包含K个簇个簇64 二分二分K-均值的例子均值的例子65 K-均值方法的缺陷均值方法的缺陷lK-均值方法当簇在下述方面有较大不同时会出现问题均值方法当簇在下述方面有较大不同时会出现问题 ►不同大小不同大小►不同密度不同密度►非球形的形状非球形的形状66 Original PointsK-means (3 Clusters)K-均值的缺陷：不同的簇大小均值的缺陷：不同的簇大小WHY？？67 Original PointsK-means (3 Clusters)K-均值的缺陷均值的缺陷—不同的密度分布不同的密度分布WHY？？68 Original PointsK-means (2 Clusters)K—均值的缺陷：非球形形状均值的缺陷：非球形形状K均值目标函数是最小化等尺度和等密度的球形簇，或明显分均值目标函数是最小化等尺度和等密度的球形簇，或明显分离的簇离的簇69 Original PointsK-means Clusters一种方法是使用更多的簇，再反过来使其部分合并一种方法是使用更多的簇，再反过来使其部分合并克服克服K—均值方法的缺陷均值方法的缺陷70 Original PointsK-means Clusters克服克服K—均值方法的缺陷均值方法的缺陷71 Original PointsK-means Clusters克服克服K—均值方法的缺陷均值方法的缺陷72 层次聚类方法层次聚类方法l定义：对给定的数据进行层次的分解：定义：对给定的数据进行层次的分解：l凝聚的（凝聚的（agglomerative）方法（自底向上））方法（自底向上）►思想：一开始将每个对象作为单独的一组，然后思想：一开始将每个对象作为单独的一组，然后根据同类相近，异类相异的原则，合并对象，直根据同类相近，异类相异的原则，合并对象，直到所有的组合并成一个，或达到一个终止条件为到所有的组合并成一个，或达到一个终止条件为止。
止l分裂的方法（分裂的方法（divisive）（自顶向下））（自顶向下）►思想：一开始将所有的对象置于一类，在迭代的思想：一开始将所有的对象置于一类，在迭代的每一步中，一个类不断地分为更小的类，直到每每一步中，一个类不断地分为更小的类，直到每个对象在单独的一个类中，或达到一个终止条件个对象在单独的一个类中，或达到一个终止条件 73 凝聚的和分裂的层次聚类凝聚的和分裂的层次聚类 74 层次聚类方法层次聚类方法l产生一个相邻簇的集合，通常用一棵树来表示产生一个相邻簇的集合，通常用一棵树来表示lCan be visualized as a dendrogram►树状图记录了分裂或合并的序列树状图记录了分裂或合并的序列以树状图和嵌套簇图显示的以树状图和嵌套簇图显示的4个点的层次聚类个点的层次聚类75 层次聚类法的特点层次聚类法的特点l不用预知不用预知(预设预设)簇的数目簇的数目►任何需要簇数的聚类可以通过在树状图的适当层任何需要簇数的聚类可以通过在树状图的适当层次切割而得到次切割而得到l得到更有意义的结构得到更有意义的结构►如生物学中的分类如生物学中的分类l传统的层次聚类算法使用相似度矩阵或距离矩阵传统的层次聚类算法使用相似度矩阵或距离矩阵►每次合并或分裂一个簇每次合并或分裂一个簇76 1 计算距离矩阵计算距离矩阵2 令每个点为一个簇令每个点为一个簇3 Repeat4 合并最接近的两个簇合并最接近的两个簇5 更新距离矩阵更新距离矩阵6 until 仅剩下一个簇仅剩下一个簇基本凝聚层次聚类算法基本凝聚层次聚类算法77 l关键步骤在于计算两个簇之间的邻近度关键步骤在于计算两个簇之间的邻近度►不同的定义簇之间的距离的方法区分了不同的不同的定义簇之间的距离的方法区分了不同的算法算法基本凝聚层次聚类算法基本凝聚层次聚类算法78 开始开始...l每个点为一个簇，计算各个簇两两之间的距离矩阵每个点为一个簇，计算各个簇两两之间的距离矩阵p1p3p5p4p2p1p2p3p4p5. . ....距离矩阵距离矩阵79 接下来接下来...l经过若干凝聚步骤，得到如下的簇经过若干凝聚步骤，得到如下的簇 C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5距离矩阵距离矩阵80 接下来接下来...l合并两个最靠近的簇合并两个最靠近的簇 (C2 和和 C5) 并更新距离矩阵并更新距离矩阵C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5距离矩阵距离矩阵81 合并后合并后l问题变为如何更新距离矩阵问题变为如何更新距离矩阵C1C4C2 U C5C3? ? ? ? ???C2 U C5C1C1C3C4C2 U C5C3C4距离矩阵距离矩阵82 p1p3p5p4p2p1p2p3p4p5. . ....距离距离lMIN(单链单链)lMAX(全链全链)lGroup Average(组平均组平均)l质心的距离质心的距离l其他的源自目标函数的方法其他的源自目标函数的方法►Ward方法使用平方差方法使用平方差距离矩阵距离矩阵如何定义簇之间的邻近度如何定义簇之间的邻近度83 p1p3p5p4p2p1p2p3p4p5. . ....距离矩阵距离矩阵lMIN(单链单链)lMAX(全链全链)lGroup Average(组平均组平均)l质心的距离质心的距离l其他的源自目标函数的方法其他的源自目标函数的方法►Ward方法使用平方差方法使用平方差如何定义簇之间的邻近度如何定义簇之间的邻近度84 p1p3p5p4p2p1p2p3p4p5. . ....距离矩阵距离矩阵lMIN(单链单链)lMAX(全链全链)lGroup Average(组平均组平均)l质心的距离质心的距离l其他的源自目标函数的方法其他的源自目标函数的方法►Ward方法使用平方差方法使用平方差如何定义簇之间的邻近度如何定义簇之间的邻近度85 p1p3p5p4p2p1p2p3p4p5. . ....距离矩阵距离矩阵lMIN(单链单链)lMAX(全链全链)lGroup Average(组平均组平均)l质心的距离质心的距离l其他的源自目标函数的方法其他的源自目标函数的方法►Ward方法使用平方差方法使用平方差如何定义簇之间的邻近度如何定义簇之间的邻近度86 p1p3p5p4p2p1p2p3p4p5. . ....距离矩阵距离矩阵 lMIN(单链单链)lMAX(全链全链)lGroup Average(组平均组平均)l质心的距离质心的距离l其他的源自目标函数的方法其他的源自目标函数的方法►Ward方法使用平方差方法使用平方差如何定义簇之间的邻近度如何定义簇之间的邻近度87 MIN或单链或单链l两个簇之间的邻近度基于两个簇中最近的两个点的距两个簇之间的邻近度基于两个簇中最近的两个点的距离离►由一个点对决定，或者说由图中的一条链决定由一个点对决定，或者说由图中的一条链决定1234588 Nested ClustersDendrogram12345612345层次聚类层次聚类: MIN89 Original PointsTwo Clusters•可以处理非椭圆的形状可以处理非椭圆的形状MIN的优点的优点90 Original PointsTwo Clusters• 对噪声点和离群点很敏感对噪声点和离群点很敏感MIN的不足的不足91 MAX或全链或全链l两个簇之间的邻近度由两个簇间最不相似的两个簇之间的邻近度由两个簇间最不相似的(最大距最大距离的离的)点对决定点对决定►由两个簇中所有的点对决定由两个簇中所有的点对决定1234592 Nested ClustersDendrogram12345612534MAX或全链或全链93 Original PointsTwo Clusters•对噪声点和离群点不太敏感对噪声点和离群点不太敏感MAX的优点的优点94 Original PointsTwo Clusters•倾向于分裂大的簇倾向于分裂大的簇►倾向于球状的簇倾向于球状的簇MAX的不足的不足95 组平均组平均l两个簇的邻近度定义为不同簇的所有点对的平均逐对邻近度两个簇的邻近度定义为不同簇的所有点对的平均逐对邻近度lNeed to use average connectivity for scalability since total proximity favors large clusters1234596 Nested ClustersDendrogram12345612534组平均组平均97 组平均组平均l是单链和全链之间的一个折中，该法利用了所有样是单链和全链之间的一个折中，该法利用了所有样本的信息，被认为是较好的层次聚类法本的信息，被认为是较好的层次聚类法l优点优点►对噪声和离群点不太敏感对噪声和离群点不太敏感l不足不足►倾向于球状的簇倾向于球状的簇98 Ward方法和质心方法方法和质心方法l两个簇的邻近度定义为两个簇合并时导致的平方误差两个簇的邻近度定义为两个簇合并时导致的平方误差的增量，该方法使用的目标函数与的增量，该方法使用的目标函数与K均值相同均值相同►可以证明，当取距离的平方作为两个点间的邻近可以证明，当取距离的平方作为两个点间的邻近度时，度时，Ward方法与组平均方法相似方法与组平均方法相似l对噪声和离群点不太敏感对噪声和离群点不太敏感l倾向于球状的簇倾向于球状的簇l可以用来初始化可以用来初始化K均值方法均值方法99 层次聚类法：比较层次聚类法：比较Group AverageWard’s Method12345612534MINMAX123456125341234561253412345612345100 lO(N2) 空间复杂度，因为要存储邻近度矩阵，空间复杂度，因为要存储邻近度矩阵，N为点为点的数目的数目l最坏情况下最坏情况下O(N3) 的时间复杂度的时间复杂度►共有共有N步，在每一步中要更新和搜索步，在每一步中要更新和搜索N2规模的邻规模的邻近度矩阵近度矩阵►在某些算法中可以接近在某些算法中可以接近O(N2 log(N) ) 的时间复杂的时间复杂度度层次聚类：时间和空间复杂度层次聚类：时间和空间复杂度101 层次聚类方法的优缺点层次聚类方法的优缺点l层次聚类方法的优点在于可以在不同粒度水平上对层次聚类方法的优点在于可以在不同粒度水平上对数据进行探测，而且容易实现相似度量或距离度量。
数据进行探测，而且容易实现相似度量或距离度量 l单纯的层次聚类算法终止条件含糊，而且执行合并单纯的层次聚类算法终止条件含糊，而且执行合并或分裂簇的操作后不可修正，这很可能导致聚类结或分裂簇的操作后不可修正，这很可能导致聚类结果质量很低果质量很低l通常考虑把层次聚类方法与其他方法（如迭代重定通常考虑把层次聚类方法与其他方法（如迭代重定位方法）相结合来解决实际聚类问题位方法）相结合来解决实际聚类问题 102 lDBSCAN是一种基于密度的聚类算法是一种基于密度的聚类算法►密度密度 = 给定半径给定半径(Eps)内点的数目内点的数目►核心点核心点(core point ) 在半径在半径Eps的邻域内拥有的邻域内拥有多于特定数目多于特定数目(MinPts)的邻点的点，在基于密的邻点的点，在基于密度的簇内部的点度的簇内部的点►边界点边界点(border point )在半径在半径Eps的邻域内拥的邻域内拥有多于特定数目有多于特定数目(MinPts)的邻点的点，但是落的邻点的点，但是落在某个核心点的邻域内在某个核心点的邻域内►噪声点噪声点(noise point )既非核心点也非边界点既非核心点也非边界点的任何点的任何点基于密度的聚类：基于密度的聚类：DBSCAN103 DBSCAN: 核心点，边界点和噪声点核心点，边界点和噪声点104 DBSCAN 算法算法l算法算法►1：将所有点标记为核心点、边界点或噪声点：将所有点标记为核心点、边界点或噪声点►2：删除噪声点：删除噪声点►3：为距离在：为距离在Eps之内的所有核心点之间赋予一条之内的所有核心点之间赋予一条边边►4：每组连通的核心点形成一个簇：每组连通的核心点形成一个簇►将每个边界点指派到一个与之关联的核心点的簇将每个边界点指派到一个与之关联的核心点的簇中中105 原始点原始点点的类型点的类型: 核心核心, 边界边界 和和噪声噪声Eps = 10, MinPts = 4DBSCAN 算法算法106 原始点原始点得到的簇得到的簇• 对噪声不敏感对噪声不敏感• 可以处理不同形状和大小的簇可以处理不同形状和大小的簇当当DBSCAN工作良好时工作良好时107 原始点集原始点集(MinPts=4, Eps=9.75). (MinPts=4, Eps=9.92)• 变密度的簇变密度的簇• 对高维数据计算量巨大对高维数据计算量巨大当当DBSCAN工作不佳时工作不佳时108 l基本方法：观察点到它的基本方法：观察点到它的k个最近邻的距离个最近邻的距离(称作称作k-距离距离)。
对于属于某个簇的点，如果对于属于某个簇的点，如果k不大于簇不大于簇的大小的话，则的大小的话，则k-距离将很接近距离将很接近l噪声点由于不在簇中，其噪声点由于不在簇中，其k-距离将相对较大距离将相对较大l对于某个对于某个k，计算所有点的，计算所有点的k-距离，以递增次序将距离，以递增次序将它们排序，然后绘制排序后的值，则预期会看到它们排序，然后绘制排序后的值，则预期会看到k-距离的急剧变化处对应于合适的距离的急剧变化处对应于合适的Eps值值DBSCAN算法算法: 确定确定EPS和和 MinPts109 DBSCAN算法算法: 确定确定EPS和和 MinPts110 簇评估簇评估 l对于有监督的分类，我们可以有多种方式评价模型的对于有监督的分类，我们可以有多种方式评价模型的优劣优劣►准确度准确度, 精度精度, 召回率召回率l对于聚类分析对于聚类分析, 相应的问题是如何评价聚类结果是否相应的问题是如何评价聚类结果是否是是 “好好”的的l评估簇的目的评估簇的目的►避免寻找噪声中的模式避免寻找噪声中的模式►比较不同的聚类算法比较不同的聚类算法►比较两个聚类的结果比较两个聚类的结果►比较两个簇比较两个簇111 在随机数据中发现的簇在随机数据中发现的簇100个个随机分随机分布的点布的点K-均值均值DBSCAN全链聚类全链聚类112 1.确定数据的聚类趋势确定数据的聚类趋势( clustering tendency ), 即识别数据中是否实际存在非随机结构即识别数据中是否实际存在非随机结构. 2.比较聚类分析的结果与通过外部知识得到的类标比较聚类分析的结果与通过外部知识得到的类标(确定正确的簇个数确定正确的簇个数).3.评估聚类分析的结果在不引用附加信息的情况下评估聚类分析的结果在不引用附加信息的情况下是否能较好拟合数据是否能较好拟合数据.4.比较两个不同的聚类结果的优劣比较两个不同的聚类结果的优劣.5.确定确定“正确正确”的类的个数的类的个数l对于对于 2, 3, 4, 还可以进一步分为是要比较整个分类还可以进一步分为是要比较整个分类结果还是其中的某个簇结果还是其中的某个簇簇评估簇评估113 l用于评估簇各方面的评估度量或指标分成如下三类用于评估簇各方面的评估度量或指标分成如下三类►监督的监督的(外部指标外部指标): 度量聚类算法发现的聚类结度量聚类算法发现的聚类结构与某种外部结构的匹配程度。
例如熵，度量簇构与某种外部结构的匹配程度例如熵，度量簇标号与外部提供的标号的匹配程度标号与外部提供的标号的匹配程度 ►非监督的非监督的(内部指标内部指标): 聚类结构的优良性度量，聚类结构的优良性度量，不考虑外部因素如不考虑外部因素如SSE(平方误差和平方误差和)簇的有效性的非监督度量常常可以进一步分成两类：效性的非监督度量常常可以进一步分成两类：•簇的凝聚性（紧凑性）：度量簇中对象如何密切相关簇的凝聚性（紧凑性）：度量簇中对象如何密切相关•簇的分离性（孤立性）：度量确定一个簇如何不同于簇的分离性（孤立性）：度量确定一个簇如何不同于其它簇其它簇 度量簇的正确性度量簇的正确性114 l用于评估簇各方面的评估度量或指标分成如下三类用于评估簇各方面的评估度量或指标分成如下三类►相对指标相对指标: 比较不同的聚类或簇是用于比较的比较不同的聚类或簇是用于比较的监督或非监督评估度量，例如监督或非监督评估度量，例如SSE或熵或熵度量簇的正确性度量簇的正确性115 通过相关性度量簇的有效性通过相关性度量簇的有效性l给定数据集的相似度矩阵和数据集聚类分析得到的类给定数据集的相似度矩阵和数据集聚类分析得到的类标号，则可以通过考察相似度矩阵和基于类标号的相标号，则可以通过考察相似度矩阵和基于类标号的相似度矩阵的理想版本之间的相关性，来评估聚类的优似度矩阵的理想版本之间的相关性，来评估聚类的优良性良性l一个理想的簇：它的点与簇内所有点的相似度为一个理想的簇：它的点与簇内所有点的相似度为1，，而与其它簇中的所有点的相似度为而与其它簇中的所有点的相似度为0l如果我们将相似度矩阵的行和列排列，使得属于相同如果我们将相似度矩阵的行和列排列，使得属于相同簇的对象在一起，则理想的相似度矩阵具有块对角结簇的对象在一起，则理想的相似度矩阵具有块对角结构：在相似度矩阵中代表簇内相似度的相的块内部相构：在相似度矩阵中代表簇内相似度的相的块内部相似度非似度非0，而其它地方为，而其它地方为0116 通过相关性度量簇的有效性通过相关性度量簇的有效性l理想的相似度矩阵如下构造：创建一个矩阵，每个数理想的相似度矩阵如下构造：创建一个矩阵，每个数据点一行一列，矩阵的一个项为据点一行一列，矩阵的一个项为1，如果它所关联的，如果它所关联的一对点属于同一个簇，否则为一对点属于同一个簇，否则为0l理想和实际相似度矩阵之间高度相关表明属于同一个理想和实际相似度矩阵之间高度相关表明属于同一个簇的点相互之间很接近。
簇的点相互之间很接近l由于实际和理想相似度矩阵都是对称的，所以只需要由于实际和理想相似度矩阵都是对称的，所以只需要对矩阵对角线下方或上方的对矩阵对角线下方或上方的n(n-1)/2个项计算相关度个项计算相关度117 l对如下的两个数据集使用对如下的两个数据集使用K-均值算法得到的簇计算相均值算法得到的簇计算相似度矩阵似度矩阵 Corr = 0.9235Corr = 0.5810实际的和理想的相似度矩阵实际的和理想的相似度矩阵118 l按照簇标号调整相似度矩阵的行列次序，然后画出按照簇标号调整相似度矩阵的行列次序，然后画出它们如果有明显分离的簇，则相似度矩阵应当粗它们如果有明显分离的簇，则相似度矩阵应当粗略的是块对角的略的是块对角的 通过相似度矩阵可视化的评价聚类通过相似度矩阵可视化的评价聚类119 l随机数据的簇的相似度矩阵随机数据的簇的相似度矩阵DBSCAN随机数据的簇的相似度矩阵随机数据的簇的相似度矩阵120 l随机数据的簇的相似度矩阵随机数据的簇的相似度矩阵K-means随机数据的簇的相似度矩阵随机数据的簇的相似度矩阵121 Complete Link随机数据的簇的相似度矩阵随机数据的簇的相似度矩阵122 l在随机数据上，在随机数据上，DBSCAN、、K均值和全链发现的簇的均值和全链发现的簇的重新排序的相似度矩阵中也存在弱对角模式重新排序的相似度矩阵中也存在弱对角模式123 DBSCAN通过相似度矩阵可视化的评价聚类通过相似度矩阵可视化的评价聚类124 l有更复杂图像的簇很难被分离有更复杂图像的簇很难被分离l内部指标内部指标: 不使用外部信息而独立簇结构的优良性不使用外部信息而独立簇结构的优良性►SSElSSE可以较好地比较两个聚类结果或具体的两个簇可以较好地比较两个聚类结果或具体的两个簇内部测度内部测度: SSE125 l可以用来估计簇的个数。
左图的数据集有可以用来估计簇的个数左图的数据集有10个自然个自然簇当簇个数等于簇当簇个数等于10时，时，SSE有一个明显的拐点有一个明显的拐点内部测度内部测度: SSE126 内部测度内部测度: SSEl更复杂数据集的更复杂数据集的SSE曲线曲线SSE of clusters found using K-means127 聚类趋势聚类趋势l确定数据集中是否包含簇的一种显而易见的方法是使确定数据集中是否包含簇的一种显而易见的方法是使着对它聚类着对它聚类l给定数据，几乎所有的聚类算法都会发现簇给定数据，几乎所有的聚类算法都会发现簇l为了处理这一问题，我们可以评估结果簇，至少有些为了处理这一问题，我们可以评估结果簇，至少有些簇具有好的质量，才能说数据集包含簇簇具有好的质量，才能说数据集包含簇l问题在于数据集中可能存在不同于我们是有的聚类算问题在于数据集中可能存在不同于我们是有的聚类算法所能发现的簇类型法所能发现的簇类型►尝试使用多种方法，并评估结果簇的质量如果尝试使用多种方法，并评估结果簇的质量如果簇都很差，则可能表示数据中确实没有簇簇都很差，则可能表示数据中确实没有簇128 Hopkins统计量统计量l使用统计检验来检验空间随机性使用统计检验来检验空间随机性l产生产生p个随机地分别在数据空间上的点，并且也抽取个随机地分别在数据空间上的点，并且也抽取p个实际数据点。
个实际数据点l对于这两个点集，找出每个点到原数据集的最近邻距对于这两个点集，找出每个点到原数据集的最近邻距离设ui是人工产生的点的最近邻距离，而是人工产生的点的最近邻距离，而wi是样本是样本点到原数据集的最近邻距离点到原数据集的最近邻距离lHopkins统计量统计量H由下式定义由下式定义129 Hopkins统计量统计量l如果随机产生的点与样本点具有大致相同的最近距离，如果随机产生的点与样本点具有大致相同的最近距离，则则H将在将在0.5左右H接近接近0或或1表明数据是高度聚类的表明数据是高度聚类的和数据在数据空间是有规律分布的和数据在数据空间是有规律分布的l对于对于p=20和和100的不同实验，左图的的不同实验，左图的H平均值为平均值为0.95，标准差为，标准差为0.0006，右图的，右图的H平均值为平均值为0.59，标准差，标准差为为0.03130 聚类：选择聚类的个数聚类：选择聚类的个数l如何选择如何选择k-均值算法中的均值算法中的k？可能的策略？可能的策略►对不同的可能个数进行试验，选择能使所有点离对不同的可能个数进行试验，选择能使所有点离开它们聚类中心的距离平方的总和达到最小的开它们聚类中心的距离平方的总和达到最小的k值值►从一个给定的最小个数开始，一直试验到一个较从一个给定的最小个数开始，一直试验到一个较小的固定的最大值，用交叉验证法找出最好的个小的固定的最大值，用交叉验证法找出最好的个数数►根据距离平方和标准来决定最佳聚类训练数据的根据距离平方和标准来决定最佳聚类训练数据的方法，将总是选择和数据点一样多的聚类。
为了方法，将总是选择和数据点一样多的聚类为了抑制选择很多聚类的方案，必须采用诸如最短描抑制选择很多聚类的方案，必须采用诸如最短描述长度准则，或采用交叉验证述长度准则，或采用交叉验证131 如何理解聚类如何理解聚类l 坦哥，你好啊，关于数据挖掘作业，我试着先坦哥，你好啊，关于数据挖掘作业，我试着先聚类再决策树分析，很多时候都会导致聚类得到的结聚类再决策树分析，很多时候都会导致聚类得到的结果跟决策树有冲突，例如：聚类后得到影响某个属性果跟决策树有冲突，例如：聚类后得到影响某个属性的几个属性，但是在决策树分析中决定我感兴趣的的几个属性，但是在决策树分析中决定我感兴趣的l那个属性的决策树却不存在这几个属性子结点，这样那个属性的决策树却不存在这几个属性子结点，这样反而是聚类影响了决策树的准确性了我想问几个问反而是聚类影响了决策树的准确性了我想问几个问题：题：l1.我发现项目里的两个问题用决策树是可以完全解决，我发现项目里的两个问题用决策树是可以完全解决，为什么还要先聚类再用决策树分析呢？为什么还要先聚类再用决策树分析呢？132 如何理解聚类如何理解聚类l2.聚类分析跟决策树之间有何联系？对于具体问题，聚类分析跟决策树之间有何联系？对于具体问题，应该如何将它们联系起来分析。
困惑中应该如何将它们联系起来分析l3.聚类分析在于分类，但是我感觉聚类分析要应用到聚类分析在于分类，但是我感觉聚类分析要应用到实际问题中很困难，请指教实际问题中很困难，请指教l我跟很多同学请教过这些问题，发现他们也有类似疑我跟很多同学请教过这些问题，发现他们也有类似疑惑，请坦哥不吝赐教啊惑，请坦哥不吝赐教啊133 如何理解聚类如何理解聚类l数据挖掘的任务是寻找有意义的数据模式，但这种模数据挖掘的任务是寻找有意义的数据模式，但这种模式不是立刻就能得到式不是立刻就能得到►有时候根本找不到有时候根本找不到(明显的明显的)模式模式►有时候的问题不是缺乏模式，而是模式太多有时候的问题不是缺乏模式，而是模式太多l这些数据可能包含很多复杂的结构以至于最佳数据挖这些数据可能包含很多复杂的结构以至于最佳数据挖掘技术也不能找出有意义的模式掘技术也不能找出有意义的模式l当挖掘这些数据集以寻找特定问题的答案时，相互对当挖掘这些数据集以寻找特定问题的答案时，相互对立的解释往往使彼此相互抵消立的解释往往使彼此相互抵消134 如何理解聚类如何理解聚类l象接受无线电信号一样，太多相互竞争的信号叠加到象接受无线电信号一样，太多相互竞争的信号叠加到一起就变为噪音。
一起就变为噪音l聚类提供了一种获悉复杂数据结构的方法，即将竞争聚类提供了一种获悉复杂数据结构的方法，即将竞争的信号的杂音分解成各自的成分的信号的杂音分解成各自的成分l当人们试图弄清复杂问题的意义时，往往趋向于将问当人们试图弄清复杂问题的意义时，往往趋向于将问题分解为更小的片断，每一个片断可以更简单地解释题分解为更小的片断，每一个片断可以更简单地解释l在许多情况下，非常杂乱的数据集实际上可能由许多在许多情况下，非常杂乱的数据集实际上可能由许多表现较好的簇组成，聚类分析的目的就是如何发现它表现较好的簇组成，聚类分析的目的就是如何发现它们135 如何理解聚类如何理解聚类l聚类分析是一种描述性的任务，用来发现数据集的分聚类分析是一种描述性的任务，用来发现数据集的分布特征也可以作为对他发现的簇运行的数据挖掘算布特征也可以作为对他发现的簇运行的数据挖掘算法的预处理步骤法的预处理步骤136 案例研究：聚类城镇案例研究：聚类城镇l《《波士顿环球报波士顿环球报》》是服务于波士顿以及东马萨诸塞州是服务于波士顿以及东马萨诸塞州和新罕布什尔南部周围区域的两家大日报之一，是波和新罕布什尔南部周围区域的两家大日报之一，是波士顿的主流报纸。
士顿的主流报纸l2003年的日发行量超过年的日发行量超过457 000份，在周日发行量超份，在周日发行量超过过705 000份l《《波士顿环球报波士顿环球报》》面临如下问题：波士度核心市场读面临如下问题：波士度核心市场读者群在缩减，郊区报业市场面临来自地方报纸的有力者群在缩减，郊区报业市场面临来自地方报纸的有力竞争，一些读者已流失竞争，一些读者已流失137 案例研究：聚类城镇案例研究：聚类城镇l为了与郊区报纸更好地竞争，环球报加入了为不同地为了与郊区报纸更好地竞争，环球报加入了为不同地区定制的报纸版面，为按照地域划分的区定制的报纸版面，为按照地域划分的12个地区加个地区加入了特别编辑内容每周有两天，读者都可以读到为入了特别编辑内容每周有两天，读者都可以读到为本区精心整理的一些地方报道页本区精心整理的一些地方报道页l环球报使用的编辑区域利用的是环球报已有的数据、环球报使用的编辑区域利用的是环球报已有的数据、常识性内容以及地图，但没有正式的统计分析常识性内容以及地图，但没有正式的统计分析138 案例研究：聚类城镇案例研究：聚类城镇l编辑区域组成方面有一些限制条件编辑区域组成方面有一些限制条件►地域必须是地理上连续的，以便运输地域必须是地理上连续的，以便运输►地域必须适度紧凑，且包含足够人口已证明特殊地域必须适度紧凑，且包含足够人口已证明特殊化编辑的内容是恰当的化编辑的内容是恰当的►编辑区域必须接近于过去做广告的地理区域。
编辑区域必须接近于过去做广告的地理区域l下面采用数据挖掘技术来把相似的城镇聚集在一起形下面采用数据挖掘技术来把相似的城镇聚集在一起形成编辑区成编辑区139 1 创造城镇特征创造城镇特征l在做聚类分析之前，首要的问题是找到描述城镇的特在做聚类分析之前，首要的问题是找到描述城镇的特征，需要包括可以用于表征城镇特点，以及可用于比征，需要包括可以用于表征城镇特点，以及可用于比较该城镇及其邻近城镇的每个特征的一个列较该城镇及其邻近城镇的每个特征的一个列l城镇特征标识可以有几个来源，大部分数据可以从城镇特征标识可以有几个来源，大部分数据可以从1990年和年和2001年城镇级的年城镇级的美国人口普查数据美国人口普查数据(census data)得到，包括年龄、种族、宗教信仰、职业、收得到，包括年龄、种族、宗教信仰、职业、收入、住宅价值、平均通勤时间以及其他令人感兴趣的入、住宅价值、平均通勤时间以及其他令人感兴趣的变量140 1 创造城镇特征创造城镇特征l此外还有外围数据提供商提供的关于订户家庭层次的此外还有外围数据提供商提供的关于订户家庭层次的数据，还有每个城镇的发行量数据，以订阅者层次的数据，还有每个城镇的发行量数据，以订阅者层次的信息，如优惠计划、投诉和订户类型信息，如优惠计划、投诉和订户类型(日常、周日常、周日或者两者都是日或者两者都是)等等l数据的处理：本例中通过四个基本步骤来创建城镇特数据的处理：本例中通过四个基本步骤来创建城镇特征征►聚集聚集►归一化归一化►计算趋势计算趋势►创建衍生变量创建衍生变量141 1 创造城镇特征创造城镇特征l聚集：将较细层次的数据汇总到城镇层次，例如聚集聚集：将较细层次的数据汇总到城镇层次，例如聚集订户的数据以得出每个城镇中订户的总数和中值订户订户的数据以得出每个城镇中订户的总数和中值订户家庭收入家庭收入l归一化：将计数值归一化：将计数值(例如收入、住宅价值和孩子数目例如收入、住宅价值和孩子数目)转变成百分比。
这实际上是把人口差别很大的不同城转变成百分比这实际上是把人口差别很大的不同城镇的数据归一化，为了可以有效地进行对比例如镇的数据归一化，为了可以有效地进行对比例如2001年有年有4年大学学历的年大学学历的27573个人住在个人住在Borrkline，，这只占到教育水平高的城镇的这只占到教育水平高的城镇的47.5%在波士顿，具在波士顿，具有类似学位的人非常多，但只占到当地总人口的有类似学位的人非常多，但只占到当地总人口的19.4%.142 1 创造城镇特征创造城镇特征l计算趋势：人口普查数据中每个变量都有相隔计算趋势：人口普查数据中每个变量都有相隔11年的年的两个值可以使用历史数据的一个令人感兴趣的地方两个值可以使用历史数据的一个令人感兴趣的地方是可以观察到其中的趋势如人口的变化：包括学龄是可以观察到其中的趋势如人口的变化：包括学龄人口的变化、不同族裔人口的变化，或拥有自有住房人口的变化、不同族裔人口的变化，或拥有自有住房人口比例的变化人口比例的变化l创建衍生变量：从已存在的变量中衍生另外一些变量创建衍生变量：从已存在的变量中衍生另外一些变量例如从邮政编码数据数据中产生各个城镇到中心城市例如从邮政编码数据数据中产生各个城镇到中心城市（波士顿）的距离（波士顿）的距离143 创建簇创建簇l利用人口统计学和地理学数据描述该城镇的特征标识利用人口统计学和地理学数据描述该城镇的特征标识l使用这些特征得到的聚类结果不能直接用于创建报纸使用这些特征得到的聚类结果不能直接用于创建报纸的编辑区，因为还有地理方面的约束条件，即编辑区的编辑区，因为还有地理方面的约束条件，即编辑区域必须由相邻的城镇构成。
域必须由相邻的城镇构成l有相似人口统计学数据的城镇未必在地理上相邻，这有相似人口统计学数据的城镇未必在地理上相邻，这个问题可以通过使用加权的方式来增加形成簇过程中个问题可以通过使用加权的方式来增加形成簇过程中地理变量的重要性地理变量的重要性l但在本案例中最终放弃了地域簇的设计，因为目标是但在本案例中最终放弃了地域簇的设计，因为目标是寻找至少部分基于人口统计学的相似性，更侧重于人寻找至少部分基于人口统计学的相似性，更侧重于人口统计学方面口统计学方面144 lMassachusetts东部及东部及New Hampshire南部各南部各城镇人口统计学聚类情况城镇人口统计学聚类情况145 确定簇的正确数量确定簇的正确数量l处于商业方面的原因，可能需要处于商业方面的原因，可能需要12个编辑区域，但个编辑区域，但不能保证找到这么多不能保证找到这么多好的簇这直接提出如何为数据这直接提出如何为数据集确定合适数目的簇的问题集确定合适数目的簇的问题l这里使用类似二分这里使用类似二分K均值的算法首先以较低的均值的算法首先以较低的K值值确定簇数目，使用普通的确定簇数目，使用普通的K均值算法构建均值算法构建K聚类，利聚类，利用适应度度量用适应度度量(如如SSE)确定最差的簇，然后把这个簇确定最差的簇，然后把这个簇分裂为分裂为2个簇，反复重复这个过程，一直到簇数达到个簇，反复重复这个过程，一直到簇数达到上界。
上界l每次迭代后，记录该簇的总体适应度每次迭代后，记录该簇的总体适应度146 l对于实际商业问题，簇的最重要的适应度度量是难以对于实际商业问题，簇的最重要的适应度度量是难以量化的度量量化的度量——簇对某个应用的有效性簇对某个应用的有效性Cluster 2Cluster 1BCluster 1AB按照算法的建议，聚类算法的下一按照算法的建议，聚类算法的下一次迭代将把簇次迭代将把簇2进行分裂形成的簇进行分裂形成的簇有明确的差异，但对于环球报感兴有明确的差异，但对于环球报感兴趣的变量而言，所形成的新簇都没趣的变量而言，所形成的新簇都没有不同的表现，如家庭递送穿透度有不同的表现，如家庭递送穿透度或订户资历等或订户资历等147 城镇的最终的四个分组城镇的最终的四个分组l簇簇2包含了包含了50个城镇中的个城镇中的31300个家庭，其中个家庭，其中137000个家庭订阅日报或周末版环球报个家庭订阅日报或周末版环球报 它是它是“最佳簇最佳簇”“Best” based on delivery penetration“2nd Best” based on delivery penetrationCluster 2Cluster 1BCluster 1AB148 l簇簇2与其他簇和人口总体区分开的变量是住宅价值和与其他簇和人口总体区分开的变量是住宅价值和教育程度。
这个簇有最高的住宅价值比例、最高的有教育程度这个簇有最高的住宅价值比例、最高的有4年大学学历的人数比例、最高受教育的品均年数和年大学学历的人数比例、最高受教育的品均年数和最低的蓝领工作人员比例最低的蓝领工作人员比例149 l从家庭递送穿透度来看，次好的簇是簇从家庭递送穿透度来看，次好的簇是簇1AA住宅价值和家庭收入与总人口的均值非常接近值和家庭收入与总人口的均值非常接近l簇簇1B的特征：主要以有最低家庭收入的特征：主要以有最低家庭收入 历时最久且临近波士顿的订户历时最久且临近波士顿的订户“Best” based on delivery penetration“2nd Best” based on delivery penetrationCluster 2Cluster 1BCluster 1AB150 l簇簇1AB是唯一主要以地域为特征形成的簇，都是远离是唯一主要以地域为特征形成的簇，都是远离波士顿的城镇，其家庭递送穿透度很低波士顿的城镇，其家庭递送穿透度很低►其住宅价值最低，但家庭收入为平均数其住宅价值最低，但家庭收入为平均数l簇簇1AB中的人选择在离城市较远的中的人选择在离城市较远的 地方居住，因为他们希望有自己的地方居住，因为他们希望有自己的 住宅住宅(郊区边缘房间较便宜郊区边缘房间较便宜)151 利用簇调整区域边界利用簇调整区域边界l聚类项目的目标是确定已存聚类项目的目标是确定已存在的编辑区域是否最优。
每在的编辑区域是否最优每个编辑区域都是处于上述四个编辑区域都是处于上述四个簇之一的城镇集合构成个簇之一的城镇集合构成l下一个步骤是通过手工方法下一个步骤是通过手工方法将某些城镇交换到邻近的区将某些城镇交换到邻近的区域，以增加每个区域的纯度域，以增加每个区域的纯度城镇城镇编辑区域编辑区域所属簇所属簇BrooklineCity2BostonCity1BCambridgeCity1BSomervilleCity1BNeedhamWest 12NewtonWest 12WellesleyWest 12WalthamWest 11BWestonWest 12WatertownWest 11B152 l除除Brookline外，所以处于外，所以处于city区域的城镇都属于簇区域的城镇都属于簇1B中中►将将Brookline交换到邻近交换到邻近的的West1区域区域►将将Waltham和和Watertown交换到邻近的交换到邻近的City区域区域l新的新的West1区域是整个簇区域是整个簇2l新的新的City区域是整个簇区域是整个簇1B城镇城镇编辑区域编辑区域所属簇所属簇BrooklineCity2BostonCity1BCambridgeCity1BSomervilleCity1BNeedhamWest 12NewtonWest 12WellesleyWest 12WalthamWest 11BWestonWest 12WatertownWest 11B有了相似城镇组成的编辑区域，就可以容易的集中对本地内容有了相似城镇组成的编辑区域，就可以容易的集中对本地内容提供有针对性的评论，增加发行量和广告销售。
提供有针对性的评论，增加发行量和广告销售153 Microsoft 聚类分析算法聚类分析算法lMicrosoft 聚类分析算法提供两种创建分类并为分类聚类分析算法提供两种创建分类并为分类分配数据点的方法分配数据点的方法►第一种方法是第一种方法是 K-means 算法，属于硬聚类方法算法，属于硬聚类方法这意味着一个数据点只能属于一个分类这意味着一个数据点只能属于一个分类►第二种方法是第二种方法是“期望值最大化期望值最大化”(EM) 方法，这是方法，这是“软聚类分析软聚类分析”方法这意味着一个数据点总是方法这意味着一个数据点总是属于多个分类，并会为每个数据点和分类的组合属于多个分类，并会为每个数据点和分类的组合计算一个概率计算一个概率l可以通过设置可以通过设置 CLUSTERING_METHOD 参数来选择参数来选择要使用的算法聚类分析的默认方法是可缩放的要使用的算法聚类分析的默认方法是可缩放的 EM154 EM 聚类分析聚类分析l在在 EM 聚类分析中，此算法反复优化初始分类模型以聚类分析中，此算法反复优化初始分类模型以适合数据，并确定数据点存在于某个分类中的概率适合数据，并确定数据点存在于某个分类中的概率。
当概率模型适合于数据时，此算法终止这一过程用当概率模型适合于数据时，此算法终止这一过程用于确定是否适合的函数是数据适合模型的对数可能性于确定是否适合的函数是数据适合模型的对数可能性lEM 聚类分析方法的结果是概率性的这意味着每个聚类分析方法的结果是概率性的这意味着每个数据点都属于所有分类，但数据点向分类的每次分配数据点都属于所有分类，但数据点向分类的每次分配都有一个不同的概率都有一个不同的概率155 lMicrosoft 实现提供两个选项：可缩放实现提供两个选项：可缩放 EM 和不可缩和不可缩放放 EMl默认情况下，在可缩放默认情况下，在可缩放 EM 中，前中，前 50,000 个记录用个记录用于为初始扫描设种子如果成功，则模型将仅仅使用于为初始扫描设种子如果成功，则模型将仅仅使用这些数据如果使用这些数据如果使用 50,000 个记录时模型不适合，个记录时模型不适合，则会继续读取则会继续读取 50,000 个记录l在不可缩放在不可缩放 EM 中，总是读取整个数据集，而不考虑中，总是读取整个数据集，而不考虑数据集的大小数据集的大小►此方法可能会创建更准确的分类，但内存需求非此方法可能会创建更准确的分类，但内存需求非常高。
常高156 l因为可缩放因为可缩放 EM 作用于本地缓冲区，所以循环访问数作用于本地缓冲区，所以循环访问数据要快得多，并且此算法对据要快得多，并且此算法对 CPU 内存缓存的利用率内存缓存的利用率比不可缩放比不可缩放 EM 要高得多要高得多l此外，可缩放此外，可缩放 EM 比不可缩放比不可缩放 EM 快三倍，即使所快三倍，即使所有数据都可容纳于主内存中也是如此有数据都可容纳于主内存中也是如此l在大多数情况下，性能改进不会导致完成的模型的质在大多数情况下，性能改进不会导致完成的模型的质量下降157 k-means 聚类分析聚类分析lk-means 通过尽量缩小一个分类中的项之间的差异，通过尽量缩小一个分类中的项之间的差异，同时尽量拉大分类之间的距离，来分配分类成员身份同时尽量拉大分类之间的距离，来分配分类成员身份lk-means 中的中的 "means" 指的是分类的指的是分类的“中点中点”，它，它是任意选定的一个数据点，之后反复优化，直到真正是任意选定的一个数据点，之后反复优化，直到真正代表该分类中的所有数据点的平均值代表该分类中的所有数据点的平均值l"k" 指的是用于为聚类分析过程设种子的任意数目的指的是用于为聚类分析过程设种子的任意数目的点。
点k-means 算法计算一个分类中的数据记录之间算法计算一个分类中的数据记录之间的欧几里得距离的平方，以及表示分类平均值的矢量，的欧几里得距离的平方，以及表示分类平均值的矢量，并在和达到最小值时在最后一组并在和达到最小值时在最后一组 k 分类上收敛分类上收敛158 k-means 聚类分析聚类分析lk-means 算法仅仅将每个数据点分配给一个分类，算法仅仅将每个数据点分配给一个分类，并且不允许成员身份存在不确定性分类中的成员身并且不允许成员身份存在不确定性分类中的成员身份表示为与中点的距离份表示为与中点的距离l通常，通常，k-means 算法用于创建连续属性的分类，在算法用于创建连续属性的分类，在这种情况下，计算与平均值的距离非常简单但是，这种情况下，计算与平均值的距离非常简单但是，Microsoft 实现通过使用概率针对分类离散属性对实现通过使用概率针对分类离散属性对 k-means 方法进行改编方法进行改编l注意：注意：Microsoft 聚类分析算法不公开用于计算聚类分析算法不公开用于计算 k-means 的距离函数，并且在完成的模型中不能测量的距离函数，并且在完成的模型中不能测量距离。
但是，可以使用预测函数返回与距离对应的值，距离但是，可以使用预测函数返回与距离对应的值，在这种情况下，距离计算为某个数据点属于此分类的在这种情况下，距离计算为某个数据点属于此分类的概率请参阅概率请参阅 ClusterProbability159 自定义自定义 Microsoft 聚类分析算法聚类分析算法 lMicrosoft 聚类分析算法支持几个参数，这些参数会聚类分析算法支持几个参数，这些参数会影响所生成的挖掘模型的行为、性能和准确性影响所生成的挖掘模型的行为、性能和准确性l设置算法参数设置算法参数►这些参数影响生成的挖掘模型的性能和准确性这些参数影响生成的挖掘模型的性能和准确性lCLUSTERING_METHOD：指定算法要使用的聚类：指定算法要使用的聚类分析方法，默认值为分析方法，默认值为 1（可缩放（可缩放 EM） ID 方法 1可缩放 EM2不可缩放 EM3可缩放 k-means4不可缩放 k-means160 lCLUSTER_COUNT ►指定将由算法生成的大致分类数如果无法基于指定将由算法生成的大致分类数如果无法基于相应的数据生成该大致数目的分类，则算法将生相应的数据生成该大致数目的分类，则算法将生成尽可能多的分类。
如果将成尽可能多的分类如果将 CLUSTER_COUNT 设置为设置为 0，则算法将使用试探性方法最准确地确定，则算法将使用试探性方法最准确地确定要生成的分类数要生成的分类数►默认值为默认值为 10161 lCLUSTER_SEED ►指定在为建模初始阶段随机生成分类时所要使用指定在为建模初始阶段随机生成分类时所要使用的种子数字的种子数字►通过更改此数字，可以更改生成初始分通过更改此数字，可以更改生成初始分���的的方法，然后使用不同的种子比较已生成的模型方法，然后使用不同的种子比较已生成的模型如果种子已更改，但所发现的分类并没有太大的如果种子已更改，但所发现的分类并没有太大的更改，则模型可被视为相对稳定更改，则模型可被视为相对稳定►默认值为默认值为 0162 lMINIMUM_SUPPORT ►指定生成某个分类至少需要的事例数如果分类指定生成某个分类至少需要的事例数如果分类中的事例数小于此数目，则此分类将被视为空，中的事例数小于此数目，则此分类将被视为空，并将被丢弃并将被丢弃►如果将这个数目设置得过高，则可能遗漏有效分如果将这个数目设置得过高，则可能遗漏有效分类l注意：如果使用注意：如果使用 EM，即默认聚类分析方法，则一些，即默认聚类分析方法，则一些分类可能具有低于指定值的支持值。
这是因为会计算分类可能具有低于指定值的支持值这是因为会计算每个事例在所有可能分类中的成员身份，对于某些分每个事例在所有可能分类中的成员身份，对于某些分类，可能仅存在最小支持类，可能仅存在最小支持163 lMODELLING_CARDINALITY ►指定在聚类分析过程中构建的示例模型数指定在聚类分析过程中构建的示例模型数►减少候选模型数会提高性能，但存在遗漏一些好减少候选模型数会提高性能，但存在遗漏一些好的候选模型的风险的候选模型的风险►默认值为默认值为 10164 lSTOPPING_TOLERANCE ►指定一个值，它可确定何时达到收敛而且算法完指定一个值，它可确定何时达到收敛而且算法完成建模当分类概率中的整体变化小于成建模当分类概率中的整体变化小于 STOPPING_TOLERANCE 参数与模型大小之比参数与模型大小之比时，即达到收敛时，即达到收敛►默认值为默认值为 10165 lSAMPLE_SIZE ►如果如果 CLUSTERING_METHOD 参数设置为其中参数设置为其中一个可缩放聚类分析方法，请指定算法在每个传一个可缩放聚类分析方法，请指定算法在每个传递中使用的事例数。
如果将递中使用的事例数如果将 SAMPLE_SIZE 参数参数设置为设置为 0，则会导致在单个传递中对整个数据集进，则会导致在单个传递中对整个数据集进行聚类分析操作在单个传递中加载整个数据集行聚类分析操作在单个传递中加载整个数据集会导致内存和性能问题会导致内存和性能问题►默认值为默认值为 50000166 lMAXIMUM_INPUT_ATTRIBUTES ►指定算法在调用功能选择之前可以处理的最大输指定算法在调用功能选择之前可以处理的最大输入属性数将该值设置为入属性数将该值设置为 0 表示不限制属性的最表示不限制属性的最大数目►增大属性的数目会大大降低性能增大属性的数目会大大降低性能►默认值为默认值为 255167 lMAXIMUM_STATES ►指定算法支持的最大属性状态数如果属性的状指定算法支持的最大属性状态数如果属性的状态数超过此最大值，则算法将使用最常见状态，态数超过此最大值，则算法将使用最常见状态，而忽略其余状态而忽略其余状态►增大状态的数目会大大降低性能增大状态的数目会大大降低性能►默认值为默认值为 100168 。