• 1. Chapter 8. 聚类分析什么是聚类分析? 聚类分析中的数据类型 主要聚类分析方法分类 划分方法(Partitioning Methods) 分层方法 基于密度的方法 基于表格的方法 基于模型(Model-Based)的聚类方法 异常分析 总结 2018/10/221Data Mining: Concepts and Techniques
  • 2. 什么是聚类分析?簇(Cluster):一个数据对象的集合 在同一个类中,对象之间0具有相似性; 不同类的对象之间是相异的。 聚类分析 把一个给定的数据对象集合分成不同的簇; 聚类是一种无监督分类法: 没有预先指定的类别; 典型的应用 作为一个独立的分析工具,用于了解数据的分布; 作为其它算法的一个数据预处理步骤;
  • 3. 聚类的常规应用 模式识别 空间数据分析 在GIS中,通过聚类发现特征空间来建立主题索引; 在空间数据挖掘中,检测并解释空间中的簇; 图象处理 经济学 (尤其是市场研究方面) WWW 文档分类 分析WEB日志数据来发现相似的访问模式2018/10/223Data Mining: Concepts and Techniques
  • 4. 应用聚类分析的例子市场销售: 帮助市场人员发现客户中的不同群体,然后用这些知识来开展一个目标明确的市场计划; 土地使用: 在一个陆地观察数据库中标识那些土地使用相似的地区; 保险: 对购买了汽车保险的客户,标识那些有较高平均赔偿成本的客户; 城市规划: 根据类型、价格、地理位置等来划分不同类型的住宅; 地震研究: 根据地质断层的特点把已观察到的地震中心分成不同的类;2018/10/224Data Mining: Concepts and Techniques
  • 5. 什么是一个好的聚类方法?一个好的聚类方法要能产生高质量的聚类结果——簇,这些簇要具备以下两个特点: 高的簇内相似性 低的簇间相似性 聚类结果的好坏取决于该聚类方法采用的相似性评估方法以及该方法的具体实现; 聚类方法的好坏还取决与该方法是能发现某些还是所有的隐含模式;2018/10/225Data Mining: Concepts and Techniques
  • 6. Requirements of Clustering in Data Mining 可伸缩性 能够处理不同类型的属性 能发现任意形状的簇 在决定输入参数的时候,尽量不需要特定的领域知识; 能够处理噪声和异常 对输入数据对象的顺序不敏感 能处理高维数据 能产生一个好的、能满足用户指定约束的聚类结果 结果是可解释的、可理解的和可用的2018/10/226Data Mining: Concepts and Techniques
  • 7. Chapter 8. Cluster Analysis什么是聚类分析? 聚类分析中的数据类型 主要聚类分析方法分类 划分方法(Partitioning Methods) 分层方法 基于密度的方法 基于表格的方法 基于模型(Model-Based)的聚类方法 异常分析 总结 2018/10/227Data Mining: Concepts and Techniques
  • 8. 两种数据结构数据矩阵 (two modes) 差异度矩阵 (one mode)2018/10/228Data Mining: Concepts and Techniques
  • 9. 评价聚类质量差异度/相似度矩阵: 相似度通常用距离函数来表示; 有一个单独的质量评估函数来评判一个簇的好坏; 对不同类型的变量,距离函数的定义通常是不同的,这在下面有详细讨论; 根据实际的应用和数据的语义,在计算距离的时候,不同的变量有不同的权值相联系; 很难定义“足够相似了”或者“足够好了” 只能凭主观确定;2018/10/229Data Mining: Concepts and Techniques
  • 10. 聚类分析中的数据类型区间标度变量(Interval-scaled variables): 二元变量(Binary variables): 标称型,序数型和比例型变量(Nominal, ordinal, and ratio variables): 混合类型变量(Variables of mixed types):2018/10/2210Data Mining: Concepts and Techniques
  • 11. 区间标度变量数据标准化 计算绝对偏差的平均值: 其中 计算标准度量值 (z-score) 使用绝对偏差的平均值比使用标准偏差更健壮(robust)2018/10/2211Data Mining: Concepts and Techniques
  • 12. 计算对象之间的相异度通常使用距离来衡量两个对象之间的相异度。 常用的距离度量方法有: 明考斯基距离( Minkowski distance): 其中 i = (xi1, xi2, …, xip) 和 j = (xj1, xj2, …, xjp) 是两个p维的数据对象, q是一个正整数。 当q = 1时, d 称为曼哈坦距离( Manhattan distance) 2018/10/2212Data Mining: Concepts and Techniques
  • 13. Similarity and Dissimilarity Between Objects (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) 可以根据每个变量的重要性赋予一个权重2018/10/2213Data Mining: Concepts and Techniques
  • 14. 二元变量二元变量的可能性表 其中每个对象有p个变量,且 p=a+b+c+dObject iObject j2018/10/2214Data Mining: Concepts and Techniques
  • 15. 二元变量对称的 如果一个二元变量的两个状态是同等价值的,具有相同的权重。即可以任取其中一种状态编码为1或者0 对于对称的二员变量,采用简单匹配系数来评价两个对象之间的相异度 2018/10/2215Data Mining: Concepts and Techniques
  • 16. 二元变量非对称的 如果变量的两个状态不是同样重要的,则称该变量是不对称的。 根据惯例,将比较重要通常也是出现概率比较小的状态编码为1,将另一中状态编码为0。 对于非对称的二员变量,采用Jaccard系数来评价两个对象之间的相异度 2018/10/2216Data Mining: Concepts and Techniques
  • 17. 二元变量的相异度计算实例 gender 是一个对称的二元变量 其它的都是非对称的二元变量 将值 Y和 P 编码为1, 值 N 编码为 0,根据Jaccard系数计算得:2018/10/2217Data Mining: Concepts and Techniques
  • 18. 标称变量(Nominal Variables)标称变量是二元变量的推广,它可以具有多于两个的状态,比如 变量map_color可以有 red, yellow, blue, green四种状态。有两种计算相异度的方法: 方法1: 简单匹配方法 M是匹配的数目, p是全部变量的数目 方法2: 使用二元变量 为每一个状态创建一个新的二元变量,可以用非对称的二元变量来编码标称变量。2018/10/2218Data Mining: Concepts and Techniques
  • 19. 序数型变量一个序数型变量可以是离散的也可以是连续的 离散的序数型变量类似于标称变量,除了它的M个状态是以有意义的序列排序的,比如职称 连续的序数型变量类似于区间标度变量,但是它没有单位,值的相对顺序是必要的,而其实际大小并不重要。2018/10/2219Data Mining: Concepts and Techniques
  • 20. 序数型变量相异度的计算 与区间标度变量的计算方法相类似 将xif 用它对应的秩代替 将每个变量的值域映射到[0.0,1.0]上,使得每个变量都有相同的权重。这通过用zif来替代rif来实现 用前面所述的区间标度变量的任一种距离计算方法来计算 2018/10/2220Data Mining: Concepts and Techniques
  • 21. 比例标度型变量(Ratio-scaled variable)比例标度型变量: 总是取正的度量值,有一个非线性的标度,近似的遵循指数标度,比如 AeBt or Ae-Bt 计算相异度的方法: 采用与处理区间标度变量相同的方法 — 不是一个好的选择 进行对数变换,对变换得到的值在采用与处理区间标度变量相同的方法 yif = log(xif) 将其作为连续的序数型数据,将其秩作为区间标度的值来对待。2018/10/2221Data Mining: Concepts and Techniques
  • 22. 混合类型的变量一个数据库可能包含了所有这6中类型的变量 用以下公式计算对象i,j之间的相异度. 其中,p为对象中的变量个数 如果xif或xjf 缺失(即对象i或对象j没有变量f的值),或者xif = xjf =0,且变量f是不对称的二元变量,则指示项δij(f)=0;否则δij(f)=12018/10/2222Data Mining: Concepts and Techniques
  • 23. 混合类型的变量f 是二元变量或标称变量: if xif = xjf dij(f) = 0, else dij(f) = 1 f 是区间标度变量: dij(f) = | xif-xjf |/maxhxhf-minhxhf 其中h遍取变量f的所有非空缺对象 f 是序数型或比例标度型 计算秩 rif 计算 zif并将其作为区间标度变量值对待 2018/10/2223Data Mining: Concepts and Techniques
  • 24. Chapter 8. Cluster Analysis什么是聚类分析? 聚类分析中的数据类型 主要聚类分析方法分类 划分方法(Partitioning Methods) 分层方法 基于密度的方法 基于表格的方法 基于模型(Model-Based)的聚类方法 异常分析 总结2018/10/2224Data Mining: Concepts and Techniques
  • 25. Major Clustering ApproachesPartitioning algorithms: Construct various partitions and then evaluate them by some criterion Hierarchy algorithms: Create a hierarchical decomposition of the set of data (or objects) using some criterion Density-based: based on connectivity and density functions Grid-based: based on a multiple-level granularity structure Model-based: A model is hypothesized for each of the clusters and the idea is to find the best fit of that model to each other2018/10/2225Data Mining: Concepts and Techniques
  • 26. http://www.cs.sfu.ca/~hanThank you !!!2018/10/2226Data Mining: Concepts and Techniques