• 1. 第八章 聚类分析8.1 什么是聚类分析? 8.2 聚类分析中的数据类型 8.3主要聚类分析方法分类 8.4 划分方法(Partitioning Methods) 8.5 分层方法 8.6 基于密度的方法 8.7 基于网格的方法 8.8 基于模型(Model-Based)的聚类方法 8.9 孤立点分析 8.10 总结 2018/10/231Data Mining: Concepts and Techniques
  • 2. 8.1什么是聚类分析?簇(Cluster):一个数据对象的集合 聚类分析 把一个给定的数据对象集合分成不同的簇; 在同一个簇(或类)中,对象之间具有相似性; 不同簇(或类)的对象之间是相异的。 聚类是一种无监督分类法: 没有预先指定的类别; 典型的应用 作为一个独立的分析工具,用于了解数据的分布; 作为其它算法的一个数据预处理步骤;
  • 3. 聚类的常规应用 模式识别 空间数据分析 在GIS中,通过聚类发现特征空间来建立主题索引; 在空间数据挖掘中,检测并解释空间中的簇; 图象处理 经济学 (尤其是市场研究方面) WWW 文档分类 分析WEB日志数据来发现相似的访问模式2018/10/233Data Mining: Concepts and Techniques
  • 4. 应用聚类分析的例子市场销售: 帮助市场人员发现客户中的不同群体,然后用这些知识来开展一个目标明确的市场计划; 土地使用: 在一个陆地观察数据库中标识那些土地使用相似的地区; 保险: 对购买了汽车保险的客户,标识那些有较高平均赔偿成本的客户; 城市规划: 根据类型、价格、地理位置等来划分不同类型的住宅; 地震研究: 根据地质断层的特点把已观察到的地震中心分成不同的类;2018/10/234Data Mining: Concepts and Techniques
  • 5. 什么是一个好的聚类方法?一个好的聚类方法要能产生高质量的聚类结果——簇,这些簇要具备以下两个特点: 高的簇内相似性 低的簇间相似性 聚类结果的好坏取决于该聚类方法采用的相似性评估方法以及该方法的具体实现; 聚类方法的好坏还取决与该方法是能发现某些还是所有的隐含模式;2018/10/235Data Mining: Concepts and Techniques
  • 6. 数据挖掘对聚类的典型要求:可伸缩性 能够处理不同类型的属性 能发现任意形状的簇 在决定输入参数的时候,尽量不需要特定的领域知识; 能够处理噪声和异常 对输入数据对象的顺序不敏感 能处理高维数据 能产生一个好的、能满足用户指定约束的聚类结果 结果是可解释的、可理解的和可用的2018/10/236Data Mining: Concepts and Techniques
  • 7. 8.2 聚类分析中的数据类型两种数据结构数据矩阵 (two modes) 差异度矩阵 (one mode)2018/10/237Data Mining: Concepts and Techniques
  • 8. 评价聚类质量差异度/相似度矩阵: 相似度通常用距离函数来表示; 有一个单独的质量评估函数来评判一个簇的好坏; 对不同类型的变量,距离函数的定义通常是不同的,这在下面有详细讨论; 根据实际的应用和数据的语义,在计算距离的时候,不同的变量有不同的权值相联系; 很难定义“足够相似了”或者“足够好了” 只能凭主观确定;2018/10/238Data Mining: Concepts and Techniques
  • 9. 聚类分析中的数据类型区间标度变量(Interval-scaled variables): 二元变量(Binary variables): 标称型,序数型和比例型变量(Nominal, ordinal, and ratio variables): 混合类型变量(Variables of mixed types):2018/10/239Data Mining: Concepts and Techniques
  • 10. 区间标度变量数据标准化 计算绝对偏差的平均值: 其中 计算标准度量值 (z-score) 使用绝对偏差的平均值比使用标准偏差更健壮(robust)2018/10/2310Data Mining: Concepts and Techniques
  • 11. 计算对象之间的相异度通常使用距离来衡量两个对象之间的相异度。 常用的距离度量方法有: 明考斯基距离( Minkowski distance): 其中 i = (xi1, xi2, …, xip) 和 j = (xj1, xj2, …, xjp) 是两个p维的数据对象, q是一个正整数。 当q = 1时, d 称为曼哈坦距离( Manhattan distance) 2018/10/2311Data Mining: Concepts and Techniques
  • 12. 当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/2312Data Mining: Concepts and Techniques
  • 13. 二元变量二元变量的可能性表 其中每个对象有p个变量,且 p=q+r+s+tObject iObject j2018/10/2313Data Mining: Concepts and Techniques
  • 14. 二元变量对称的 如果一个二元变量的两个状态是同等价值的,具有相同的权重。即可以任取其中一种状态编码为1或者0 对于对称的二员变量,采用简单匹配系数来评价两个对象之间的相异度 2018/10/2314Data Mining: Concepts and Techniques
  • 15. 二元变量非对称的 如果变量的两个状态不是同样重要的,则称该变量是不对称的。 根据惯例,将比较重要通常也是出现概率比较小的状态编码为1,将另一中状态编码为0。 对于非对称的二员变量,采用Jaccard系数来评价两个对象之间的相异度 2018/10/2315Data Mining: Concepts and Techniques
  • 16. 二元变量的相异度计算例8.1 gender 是一个对称的二元变量 其它的都是非对称的二元变量 将值 Y和 P 编码为1, 值 N 编码为 0,根据非对称变量Jaccard系数计算得:2018/10/2316Data Mining: Concepts and Techniques
  • 17. 标称变量(Nominal Variables)标称变量是二元变量的推广,它可以具有多于两个的状态,比如 变量map_color可以有 red, yellow, blue, green四种状态。有两种计算相异度的方法: 方法1: 简单匹配方法 M是匹配的数目, p是全部变量的数目 方法2: 使用二元变量 为每一个状态创建一个新的二元变量,可以用非对称的二元变量来编码标称变量。2018/10/2317Data Mining: Concepts and Techniques
  • 18. 序数型变量一个序数型变量可以是离散的也可以是连续的 离散的序数型变量类似于标称变量,除了它的M个状态是以有意义的序列排序的,比如职称 连续的序数型变量类似于区间标度变量,但是它没有单位,值的相对顺序是必要的,而其实际大小并不重要。2018/10/2318Data Mining: Concepts and Techniques
  • 19. 序数型变量相异度的计算 与区间标度变量的计算方法相类似 将xif 用它对应的秩代替 将每个变量的值域映射到[0.0,1.0]上,使得每个变量都有相同的权重。这通过用zif来替代rif来实现 用前面所述的区间标度变量的任一种距离计算方法来计算 2018/10/2319Data Mining: Concepts and Techniques
  • 20. 比例标度型变量(Ratio-scaled variable)比例标度型变量: 总是取正的度量值,有一个非线性的标度,近似的遵循指数标度,比如 AeBt or Ae-Bt 计算相异度的方法: 采用与处理区间标度变量相同的方法 — 不是一个好的选择 进行对数变换,对变换得到的值在采用与处理区间标度变量相同的方法 yif = log(xif) 将其作为连续的序数型数据,将其秩作为区间标度的值来对待。2018/10/2320Data Mining: Concepts and Techniques
  • 21. 混合类型的变量(230页)一个数据库可能包含了所有这6中类型的变量 用以下公式计算对象i,j之间的相异度. 其中,p为对象中的变量个数 如果xif或xjf 缺失(即对象i或对象j没有变量f的值),或者xif = xjf =0,且变量f是不对称的二元变量,则指示项δij(f)=0;否则δij(f)=12018/10/2321Data Mining: Concepts and Techniques
  • 22. 混合类型的变量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/2322Data Mining: Concepts and Techniques
  • 23. 8.3主要聚类分析方法分类Partitioning 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/2323Data Mining: Concepts and Techniques
  • 24. 8.4 划分方法(232页)划分方法: 将一个包含n个数据对象的数据库组织成k个划分(k<=n),其中每个划分代表一个簇(Cluster)。 给定一个k,要构造出k个簇,并满足采用的划分准则: 全局最优:尽可能的列举所有的划分; 启发式方法: k-平均和k-中心点算法 k-平均 (MacQueen’67):由簇的中心来代表簇; k-中心点或 PAM (Partition around medoids) (Kaufman & Rousseeuw’87): 每个簇由簇中的某个数据对象来代表。 2018/10/2324Data Mining: Concepts and Techniques
  • 25. K-平均算法给定k,算法的处理流程如下: 1.随机的把所有对象分配到k个非空的簇中; 2.计算每个簇的平均值,并用该平均值代表相应的簇; 3.将每个对象根据其与各个簇中心的距离,重新分配到与它最近的簇中; 4.回到第二步,直到不再有新的分配发生。 2018/10/2325Data Mining: Concepts and Techniques
  • 26. K-平均算法例8.22018/10/2326Data Mining: Concepts and Techniques
  • 27. K-平均算法优点 相对高效的: 算法复杂度O(tkn), 其中n 是数据对象的个数, k 是簇的个数, t是迭代的次数,通常k, t << n. 算法通常终止于局部最优解; 缺点 只有当平均值有意义的情况下才能使用,对于类别字段不适用; 必须事先给定要生成的簇的个数; 对“噪声”和异常数据敏感; 不能发现非凸面形状的数据。2018/10/2327Data Mining: Concepts and Techniques
  • 28. K-平均算法的变种一些变种在下面几个方面有所不同: 初始k个平均值的选择; 相异度的计算; 计算簇的平均值的策略; 处理种类字段: k-模算法 (Huang’98) 用模来替代平均值; 用新的相异度计算方法来处理类别字段; 用基于频率的方法来修改簇的模; k-原型算法:综合k-平均和k-模算法,能同时处理类别字段和数值字段。2018/10/2328Data Mining: Concepts and Techniques
  • 29. K-中心点算法找出簇中位置最中心的对象,即中心点来代表簇 PAM (Partitioning Around Medoids, 1987) 设定一个中心点的初始集合,然后反复的用非中心点对象来替代中心点对象,以改进聚类的质量; PAM 算法在大数据集上效率较低,没有良好的可伸缩性; CLARA (Kaufmann & Rousseeuw, 1990) CLARANS (Ng & Han, 1994): Randomized sampling2018/10/2329Data Mining: Concepts and Techniques
  • 30. PAM (Partitioning Around Medoids) (1987)PAM (Kaufman and Rousseeuw, 1987) 用真实的数据对象来代表簇 随机选择k个对象作为初始的中心点; Repeat 对每一个由非中心对象h 和中心对象 i, 计算i被h替代的总代价 Tcih 对每一个有h和I组成的对象对 If TCih < 0, i 被 h替换 然后将每一个非中心点对象根据与中心点的距离分配给离它最近的中心点 Until不发生变化。2018/10/2330Data Mining: Concepts and Techniques
  • 31. PAM Clustering: Total swapping cost TCih=jCjihjihttihjhitjtihj2018/10/2331Data Mining: Concepts and Techniques
  • 32. CLARA (Clustering Large Applications) (1990)CLARA (Kaufmann and Rousseeuw in 1990) 该算法首先获得数据集的多个采样,然后在每个采样上使用PAM算法,最后返回最好的聚类结果作为输出。 优点: 能够处理大数据集。 缺点: 效率依赖于采样的大小; 如果样本发生偏斜,基于样本的一个好的聚类不一定代表得了整个数据集合的一个好的聚类;2018/10/2332Data Mining: Concepts and Techniques
  • 33. CLARANS (“Randomized” CLARA) (1994)CLARANS (A Clustering Algorithm based on Randomized Search) (Ng and Han’94) CLARANS 在搜索的每一步动态的抽取一个样本; 聚类过程可以被描述为对一个图的搜索,图中的每个节点是一个潜在的解,即k个中心点的集合;在替换 了一个中心点后的结果被称为当前结果的邻居。 如果找到了一个局部最优,算法从随即选择的节点开始寻找新的局部最优; 比PAM 和 CLARA更有效和有更好的伸缩性; 采用聚焦技术和空间数据结构等能进一步提高性能(Ester et al.’95)2018/10/2333Data Mining: Concepts and Techniques
  • 34. 8.5 分层方法采用距离作为衡量聚类的标准。该方法不在需要指定聚类的个数,但用户可以指定希望得到的簇的数目作为一个结束条件。Step 0Step 1Step 2Step 3Step 4bdceaa bd ec d ea b c d eStep 4Step 3Step 2Step 1Step 0agglomerative (AGNES)divisive (DIANA)2018/10/2334Data Mining: Concepts and Techniques
  • 35. AGNES (Agglomerative Nesting)由 Kaufmann 和 Rousseeuw 提出;(1990) 使用单链接方法和差异度矩阵; 合并那些具有最小差异度的节点; Go on in a non-descending fashion 最后所有的对象合并形成一个簇。2018/10/2335Data Mining: Concepts and Techniques
  • 36. A Dendrogram Shows How the Clusters are Merged HierarchicallyDecompose data objects into a several levels of nested partitioning (tree of clusters), called a dendrogram. A clustering of the data objects is obtained by cutting the dendrogram at the desired level, then each connected component forms a cluster.2018/10/2336Data Mining: Concepts and Techniques
  • 37. DIANA (Divisive Analysis)由 Kaufmann 和 Rousseeuw 提出(1990) AGNES算法的逆过程; 最终每个新的簇只包含一个对象;2018/10/2337Data Mining: Concepts and Techniques
  • 38. 层次方法的主要缺点: 没有良好的伸缩性: 时间复杂度至少是 O(n2) 一旦一个合并或分裂被执行,就不能修复; 综合层次聚类和其它的聚类技术: BIRCH (1996): uses CF-tree and incrementally adjusts the quality of sub-clusters CURE (1998): selects well-scattered points from the cluster and then shrinks them towards the center of the cluster by a specified fraction CHAMELEON (1999): hierarchical clustering using dynamic modeling2018/10/2338Data Mining: Concepts and Techniques
  • 39. BIRCH (1996)Birch: Balanced Iterative Reducing and Clustering using Hierarchies, by Zhang, Ramakrishnan, Livny (SIGMOD’96) 增量的构造一个CF树 Phase 1: 扫描数据库,建立一个初始存放于内存的CF树,它可以被看作数据的多层压缩,试图保留数据内在的聚类结构; Phase 2: 采用某个聚类算法对CF树的叶子节点进行聚类; 可伸缩性: 数据集合的单边扫描产生了一个基本的聚类,额外的扫描可以进一步的改进聚类的质量。 缺点: 只能处理数值型数据;对于非球状的簇不能很好的工作。2018/10/2339Data Mining: Concepts and Techniques
  • 40. Clustering Feature VectorClustering Feature: CF = (N, LS, SS) N: Number of data points LS: Ni=1=Xi SS: Ni=1=Xi2CF = (5, (16,30),(54,190))(3,4) (2,6) (4,5) (4,7) (3,8)2018/10/2340Data Mining: Concepts and Techniques
  • 41. CF TreeCF1child1CF3child3CF2child2CF6child6CF1child1CF3child3CF2child2CF5child5CF1CF2CF6prevnextCF1CF2CF4prevnextB = 7 L = 6RootNon-leaf nodeLeaf nodeLeaf node2018/10/2341Data Mining: Concepts and Techniques
  • 42. CURE (Clustering Using REpresentatives )CURE: proposed by Guha, Rastogi & Shim, 1998 Stops the creation of a cluster hierarchy if a level consists of k clusters Uses multiple representative points to evaluate the distance between clusters, adjusts well to arbitrary shaped clusters and avoids single-link effect2018/10/2342Data Mining: Concepts and Techniques
  • 43. Drawbacks of Distance-Based MethodDrawbacks of square-error based clustering method Consider only one point as representative of a cluster Good only for convex shaped, similar size and density, and if k can be reasonably estimated2018/10/2343Data Mining: Concepts and Techniques
  • 44. Cure: The AlgorithmDraw random sample s. Partition sample to p partitions with size s/p Partially cluster partitions into s/pq clusters Eliminate outliers By random sampling If a cluster grows too slow, eliminate it. Cluster partial clusters. Label data in disk2018/10/2344Data Mining: Concepts and Techniques
  • 45. Data Partitioning and Clusterings = 50 p = 2 s/p = 25xxxyyyyxyxs/pq = 52018/10/2345Data Mining: Concepts and Techniques
  • 46. Cure: Shrinking Representative PointsShrink the multiple representative points towards the gravity center by a fraction of . Multiple representatives capture the shape of the clusterxyxy2018/10/2346Data Mining: Concepts and Techniques
  • 47. K-modes(补充)A Fast Clustering Algorithm to Cluster Very Large Categorical Data Sets in Data Mining,Zhexue Huang,1997 K-模,对k-平均方法的改进,k-原型的简化 处理分类属性 分类属性:A1,A2,…,Am为空间的m个属性, DOM(Ai)为属性的值域,如果DOM(Ai) 是确定和无序的,即对任何a,b A,只有a=b或者ab,则称Ai为分类属性 如果A1,A2,…,Am都为分类属性,则属性为分类空间2018/10/2347Data Mining: Concepts and Techniques
  • 48. 相异度度量设X,Y为m个分类属性的分类对象,它们之间的相异度定义为: d(x,y)对一个属性上的每个类赋予了相同的权重 考虑属性出现的频率 对出现频率较低的类给予了更大的权重 nxj为数据集中属性j上的值为xj的对象数2018/10/2348Data Mining: Concepts and Techniques
  • 49. 数据集的模(mode)设X为一组分类对象,分类属性包括A1,A2,…,AM X={X1,X2,…Xn}的模:向量Q=[q1,q2,…,qm], 使得 最小 定理:函数D(Q,X)为最小,当且仅当 对所有的j=1,…,m有 Nck,j是在属性上Ai值为ck,j的对象数 2018/10/2349Data Mining: Concepts and Techniques
  • 50. K模算法1.为每个簇选择初始模,共k个 2.根据d,把对象分配给最近的簇。根据定理重新计算簇的模 3.计算每个对象对当前模的相异度,重新分配对象到簇 4.重复上述2,3过程,直到簇中的对象不再发生变化2018/10/2350Data Mining: Concepts and Techniques
  • 51. 8.6 基于密度的方法 将簇看作是数据空间中被低密度区域分割开的高密度区域。 优点:可发现任意形状的聚基于密度的方法: DBSCAN 基于高密度连接区域的密度聚类方法 OPTICS 通过对象排序识别聚类结构 DENCLUE 基于密度分布函数的聚类2018/10/2351Data Mining: Concepts and Techniques
  • 52. DBSCAN(基于高密度连接区域的密度聚类方法)Density-Based Spatial Clustering of Applications with Noise A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise Martin Ester,KDD-96 2018/10/2352Data Mining: Concepts and Techniques
  • 53. 定义给定半径和MinPts ,每个聚类中的对象的-邻域中至少包含MinPts个对象 给定对象集合D  邻域N(q): 给定对象半径内的区域,即{q  D | dist(p,q) <= } 核心对象:q  D,|N(q)|MinPts 对象p从对象q出发是直接密度可达:pN(q)且|N(q)|  MinPtspqMinPts = 5  = 1 cm2018/10/2353Data Mining: Concepts and Techniques
  • 54. 定义(续)对象p从对象q关于和MinPts密度可达:存在对象链p1,p2,…,pn,p1=q,pn=p,piD,pi+1是从pi关于和MinPts直接密度可达的(非对称) 对象p和q关于和MinPts密度相连:存在对象o D,使得对象p和q 从o关于和MinPts密度可达(对称)pqopqp12018/10/2354Data Mining: Concepts and Techniques
  • 55. DBSCAN基本思想簇:基于密度可达性的最大的密度相连对象的集合 噪音:不在任何簇中的对象 边界对象:不是核心对象,但在簇中,即至少从一个核心对象直接可达核心对象边界点噪音 = 1cm MinPts = 52018/10/2355Data Mining: Concepts and Techniques
  • 56. DBSCAN算法1)任意选择没有加簇标签的点 p 2)找到从p关于 and MinPts 密度可达的所有点 3)如果|N(q)|MinPts ,则p是核心对象,形成一个新的簇,给簇内所有的对象点加簇标签 4)如果p 是边界点, 则处理数据库的下一点 5)重复上述过程,直到所有的点处理完毕 = 1cm MinPts = 52018/10/2356Data Mining: Concepts and Techniques
  • 57. 不足和改进只能发现密度相仿的簇 对用户定义的参数(  and MinPts )敏感 计算复杂度为O(n2) 采用R-树等空间索引技术,计算复杂度为o(nlogn) 2018/10/2357Data Mining: Concepts and Techniques
  • 58. 图示A 和 B被认为是噪音 C1和C2两个簇合并了2018/10/2358Data Mining: Concepts and Techniques
  • 59. OPTICSOPTICS:Ordering Points To Identify the Clustering Structure(通过对象排序识别聚类结构) Mihael Ankerst .ACM SIGMOD’99 Int.Conf,1999 对DBSCAN的改进 对输入参数不敏感 可以发现不同密度的簇 用图表等可视化的方式来表示 按可达距离排序 可自动开采,也可与用户交互2018/10/2359Data Mining: Concepts and Techniques
  • 60. 引入两个新概念P 为对象,数据集D,为距离值,N(q)为邻域,MinPts P 的核心距离:使得P成为核心对象的最小 若|( N(q)| MinPts,即P不是核心对象,则无定义,即无穷大 否则,定义为使P成为核心对象的的最小值 P 关于对象q的可达距离:p的核心距离和p,q的欧几里得距离之间的较大值 若|N(q)| MinPts,即P不是核心对象,则无定义 否则,定义为Max(核心距离,|(p,q)|)2018/10/2360Data Mining: Concepts and Techniques
  • 61. 图示核心距离 可达距离2018/10/2361Data Mining: Concepts and Techniques
  • 62. OPTICS算法1.计算数据点p的核心距离和可达距离 2.如果p为核心对象,找到所有它的关于 和MinPts的直接密度可达点,按可达距离排序并插入队列。 3.处理下一个数据点 2018/10/2362Data Mining: Concepts and Techniques
  • 63. 寻找簇Reachability-distanceundefined‘Cluster-order of the objects2018/10/2363Data Mining: Concepts and Techniques
  • 64. 不同密度、形状、大小的簇2018/10/2364Data Mining: Concepts and Techniques
  • 65. 参数的影响减小,则可达距离为无穷大的点增多; MinPts减小,核心对象增多,图象更尖锐2018/10/2365Data Mining: Concepts and Techniques
  • 66. 确定参数MinPts 经验值:10-202018/10/2366Data Mining: Concepts and Techniques
  • 67. DENCLUEDENsity-based CLUstering An Efficient Application to Clustering in Large Multimedia Databases with Noise(在带噪音的大型多维数据库上的高效的聚类方法) Alexander Hinnebug,19982018/10/2367Data Mining: Concepts and Techniques
  • 68. 数学基础1.影响函数描述了一个数据点在邻域的影响 2.数据空间的整体密度函数为所有数据点的影响函数之和 3.聚类可以通过确定密度吸引点来得到,密度吸引点为密度函数的局部最大2018/10/2368Data Mining: Concepts and Techniques
  • 69. 影响函数假设x 和y是特征空间中的对象。数据对象y对x的影响函数为 原则上影响函数可以是任意的函数,它由邻域内的两个对象之间的距离决定 方波影响函数 高斯函数 一个点x是被一个密度吸引点y密度吸引的:如果存在一组点x0,…,xk,x0=x,xk=y,对0
  • 70. 梯度和密度吸引点2018/10/2370Data Mining: Concepts and Techniques
  • 71. 爬山算法1.在收缩空间随机选择一点. 2.考虑当前状态的所有邻域 3.选择最佳的邻域,当前状态转向它 4.重复过程2,3,直到当前状态为邻域中最佳 5.返回当前状态作为结果2018/10/2371Data Mining: Concepts and Techniques
  • 72. 对一个2维数据集的可能的密度函数2018/10/2372Data Mining: Concepts and Techniques
  • 73. 簇密度吸引点x的中心定义的簇是一个被x密度吸引的子集C,在x的密度函数不小于阈值;否则它被认为是孤立点 一个任意形状的簇是子集C的集合,每一个都是密度吸引的,有不小于阈值的密度函数值;并从每个区域到另一个都存在一条路径p,路径上的每个点的密度函数值都不小于2018/10/2373Data Mining: Concepts and Techniques
  • 74. Chapter 8. Cluster Analysis 基于密度的方法 DBSCAN OPTICS DENCLUE 基于网格的方法 STING WaveCluster CLIQUE 基于模型的方法 统计学方法 神经网络方法 孤立点分析 小结2018/10/2374Data Mining: Concepts and Techniques
  • 75. 8.7 基于网格的方法 采用一个多分辨率的网状数据结构。将空间化为有限数目的单元,这些单元形成了网格结构,聚类在网格上进行。 优点:处理速度快,处理时间独立于数据对象的数目,仅依赖于量化空间中每一维上的单元数目。 基于网格的方法 STING 利用存储在网格单元中的统计信息; WaveCluster 用一种小波转换方法来聚类对象; CLIQUE 在高维数据空间中基于网格和密度的聚类方法。2018/10/2375Data Mining: Concepts and Techniques
  • 76. STINGSTatistical Information Grid (统计信息网格方法) STING: A Statistical Information Grid Approach to Spatial Data Mining Wei Wang,Los Angeles,1997 2018/10/2376Data Mining: Concepts and Techniques
  • 77. 主要思想数据空间区域被划分为有限数目矩形单元 对应于不同级别的分辨率,存在着不同级别的矩形单元:高层的每个单元被分为多个低一层的单元。 每个网格单元的统计信息被预先计算和存储,以供处理查询之用 2018/10/2377Data Mining: Concepts and Techniques
  • 78. 统计信息(1)n(网格中的对象数), m(平均值),s(标准偏差),min(最小值),max(最大值) 2018/10/2378Data Mining: Concepts and Techniques
  • 79. 统计信息(2)分布类型(type of distribution) 假设dist为大多数数据点的分布类型,confl为分布类型不同的数据点的个数 1.distidist,mim,sis,则conflconfl+ni 3. distidist,mim,sis,则confl  confl 4. mim,sis中有某个不成立,则confl n 如果 ,(t为一个指定域值),则dist为NONE. 否则,dist不变.2018/10/2379Data Mining: Concepts and Techniques
  • 80. 统计信息(3) n=220 dist4dist m=20.27 confl=10 s=2.37 confl/n=0.045<0.05 min=3.8 max=40 dist=normal 2018/10/2380Data Mining: Concepts and Techniques
  • 81. 自顶向下地回答查询1.从层次中选定一层(包含较少的单元)作为查询处理的开始。 2.对当前层次的每个单元,计算置信度区间,用以反映该网格单元与给定查询的关联程度 3.当前层次处理完毕,转低一层,直至底层2018/10/2381Data Mining: Concepts and Techniques
  • 82. 优缺点独立于查询 有利于并行处理和增量更新 计算统计信息的复杂度为o(n),n为对象数,查询处理事件的复杂度为o(g),g为最低层的网格数,g<
  • 83. Wavecluster(小波变换)Wavecluster:基于大型空间数据库的多分辨率的聚类方法(the 24th VLDB Conference,NewYork,USA,1998) 基于网格和密度的 多维空间数据对象可以用多维特征空间来表示。从信号处理的角度来看,n 维特征空间的对象就是n维的信号。 信号的高频率区:对象分布情况变化剧烈的区域,即孤立点 信号的低频率高振幅区:对象分布密集区,即簇 n维信号的变换用多次 的一维小波变换来实现 2018/10/2383Data Mining: Concepts and Techniques
  • 84. 小波变换的原理通过过滤,可以给出信号的瞬间频率值 一维信号S与过滤系数Ck卷积 M:过滤系数的个数 Ck:过滤系数 S:输入信号 2018/10/2384Data Mining: Concepts and Techniques
  • 85. Wavecluster 分类算法输入:多维数据对象的特征向量 输出:聚类的对象 1.量化特征空间,把对象分配到各个单元 2.对各个单元做小波变换 3.按照不同的分辨率,在变换后的子波带中找到簇 4.给簇加类标签 5.生成查找表 6.给对象加类标签2018/10/2385Data Mining: Concepts and Techniques
  • 86. 量化有d维的特征空间,每一维分成m个间隔,设每一维的m是相等的,且mi=m,则共有单元md个。 Fk=(f1,f2,…,fd)是对象o的原始特征向量,Mj=(v1,v2,…,vd)是一个在原始特征空间的单元,1vimi,1id,是单元Mi在向量轴上的位置 若 i(vi-1)*sifivi*si,1id,则对象ok在单元Mj中2018/10/2386Data Mining: Concepts and Techniques
  • 87. 图示A0为输入信号, 为低通过滤器, 为高通过滤器 Dj为详细信号(detail signal),反映孤立点信息 Ai为平均信号(average signal),反映簇的信息 Ai的分辨率比Ai+1要高2018/10/2387Data Mining: Concepts and Techniques
  • 88. 加类标签,查找表c Tk,Tkc  lTk=cn,ccr lTk为经小波变换后的单元Tk的类标签 簇的标签不能直接用于原始空间 LT表:变换前后的单元对应 c Mj,oiMj,loi=cn,ccr,1iN loi是对象oi的类标签2018/10/2388Data Mining: Concepts and Techniques
  • 89. 特性时间复杂度(NK) 1)扫描数据库,分配空间: O(N) 2)设K=md,做小波变换:O(K) 3)标签:O(K),LT表:O(K) 4)加类标签:O(N) 2018/10/2389Data Mining: Concepts and Techniques
  • 90. 多分辨率强调水平边强调垂直边强调转角强调平均领域2018/10/2390Data Mining: Concepts and Techniques
  • 91. 任意形状的簇的发现2018/10/2391Data Mining: Concepts and Techniques
  • 92. 小波变换的优点无监督分类:hat-shape过滤,没有事先假定的聚类形状,边界的弱信息不会屏蔽 剔除孤立点:采用低通过滤,对信号中的高低频分量通低不通高 多分辨率:不同的变换次数产生不同的分辨率 高效率:本身运算开销不大,并可以采用并行处理 处理高维数据,多达20维2018/10/2392Data Mining: Concepts and Techniques
  • 93. CLIQUECLIQUE:Clustering In QUEst,1998 给定多维数据集合,数据点在数据空间中不是均衡分布的。 如果一个单元中的包含数据点超过了某个输入模型参数,则该单元是密集的。 簇:相连的密集单元的最大集合2018/10/2393Data Mining: Concepts and Techniques
  • 94. 主要步骤1.将数据空间划分为互不相交的长方形单元,记录每个单元里的对象数 2.用先验性质识别包含簇的子空间 3.识别簇: 在符合兴趣度的子空间中找出密集单元 在符合兴趣度的子空间中找出相连的密集单元 4.为每个簇生成最小化的描述 先验性质:如果一个K维单元是密集的,那么它在k-1空间上的投影也是密集的。即给定一个k维的侯选密集单元,如果检查它的k-1维投影空间,发现任何一个不是密集的,那么知道第k维的单元也不可能是密集的。2018/10/2394Data Mining: Concepts and Techniques
  • 95. Salary (10,000)Vacation(week)2030405060age543126702030405060age54312670ageVacationSalary3050 = 3关于age对salary和vocation维的密集单元,这些密集单元相交形成更高维度密集单元的一个侯选搜索空间2018/10/2395Data Mining: Concepts and Techniques
  • 96. 有效性和缺点自动地发现最高维的子空间,高密度聚类存在于这些子空间中。 对元组的输入顺序不敏感,无需假设任何规范的数据分布 随输入数据的大小线形地扩展,当数据的维数增加时具有良好的可伸缩性 聚类结果的精确度降低 2018/10/2396Data Mining: Concepts and Techniques
  • 97. Chapter 8. Cluster Analysis 基于密度的方法 DBSCAN OPTICS DENCLUE 基于网格的方法 STING WaveCluster CLIQUE 基于模型的方法 统计学方法 神经网络方法 孤立点分析 小结2018/10/2397Data Mining: Concepts and Techniques
  • 98. 8.8基于模型的聚类方法试图优化给定的数据和某些数学模型之间的适应性 假设:数据是根据潜在的概率分布生成的 统计学方法 神经网络方法2018/10/2398Data Mining: Concepts and Techniques
  • 99. 统计学方法概念聚类 机器学习中的一种聚类方法,给出一组未标记的对象。 产生对象的一个分类模式 为每组对象发现了特征描述(分类) COBWEB 简单增量概念聚类算法 以分类树的形式创建层次聚类 每个节点代表一个概念,包含对概念的概率描述2018/10/2399Data Mining: Concepts and Techniques
  • 100. 分类效用(Category Utility)概率表示 类内相似性。该值越大,共享该属性-值对的类成员比例就更大。 概率表示 类间相异性。该值越大,在对照类中共享该属性-值对的类成员比例就更大。 分类效用: N是在树的某个层次上形成的一个划分{C1,C2,…,Ck}的节点、概念或“种类”的数目。 在给定的划分中能够正确猜测期望的属性值的数目中,分类效用是随没有此种知识时期望的正确猜测的树木而增加的。 2018/10/23100Data Mining: Concepts and Techniques
  • 101. COBWEB:分类树2018/10/23101Data Mining: Concepts and Techniques
  • 102. 分类树的节点插入将对象临时置于每个节点,并计算结果划分的分类效用。产生最高分类效用的位置是对象节点的好的选择 计算为给定对象创建一个新的节点所产生的分类效用,与基于现存节点的计算相比较。 根据产生最高效用的划分,对象被置于一个已存在的类,或者为它创建一个新类。2018/10/23102Data Mining: Concepts and Techniques
  • 103. 优缺点假设每个属性上的概率分布是彼此独立的。 聚类的概率分布表示使得更新和存储聚类相当昂贵 时间和空间复杂度取决于属性的数目、每个属性的值的数目 对偏斜的数据输入不是高度平衡的,可能导致空间和时间复杂性的剧烈变化 不适合大数据库2018/10/23103Data Mining: Concepts and Techniques
  • 104. 神经网络方法将每个簇描述为一个标本(examplar),作为聚类的原型 根据某些距离度量,新的对象被分配给标本与其最相似的簇 竞争学习(competitive learning) 自组织特征映射2018/10/23104Data Mining: Concepts and Techniques
  • 105. 竞争学习采用了若干个单元的层次结构(神经元) 神经元以一种“胜者全取”的方式对系统当前处理的对象进行竞争 1.激发式的连接(excitatory):在某个给定层次中的单元可以接收来自低一层次所有单元的输入。 2.每一层中活动单元的布局代表了高一层的输入模式 3.一个层次内的联系是抑制式(inhibitory)的,在某个给定的层次中,一个簇中的单元彼此竞争,对低一层的输入模式做出反应 4.获胜的单元修正它与簇中其他单元连接上的权重,以便它能够对与当前对象相似或一样的对象做出较强的反应 每个簇可被看成一个新的低层特征向高层特征的映射2018/10/23105Data Mining: Concepts and Techniques
  • 106. 输入模式 层3抑制簇层2抑制簇层1输入单元激发联接2018/10/23106Data Mining: Concepts and Techniques
  • 107. 自组织特征映射Self-Organizing feature Map(SOM) 通过若干个单元竞争当前对象来进行聚类 权重向量最接近当前对象的单元为获胜或活跃的单元 对获胜单元及其最近的邻居的权重进行调整 类似大脑的处理过程 用于可视化高维数据2018/10/23107Data Mining: Concepts and Techniques
  • 108. 神经元网络的结构竞争层 Competitive layer输出层 Output layer2018/10/23108Data Mining: Concepts and Techniques
  • 109. 输入层: 接受多维输入模式,每个输入模式即一个向量 输入层的每个神经元代表输入模式的一个维 输入层的神经元把它得到的输入向量传给竞争层 竞争层: 竞争层的神经元接受来自输入层向量的加权和 每个神经元有它的邻域,包括一组其它的神经元 给定一个输入,某些神经元可被激活,这些神经元可抑制或激发它的邻域内的神经元 生物上的“on-center,off-surround”结构,lateral feedback/inhibition 输出层: 输出层的组织依赖于具体的应用程序 2018/10/23109Data Mining: Concepts and Techniques
  • 110. 数学模型输入向量为v=(v1,v2,…,vn) 竞争层的每个单元i都有一个相关的权重向量:w=(w1,w2,…,wn) 则每个神经元的输入为 可见,输入为标量,即权重向量与输入向量的点乘 2018/10/23110Data Mining: Concepts and Techniques
  • 111. 数学模型(续) 计算角度angle(v,w)以决定“胜出”的神经元2018/10/23111Data Mining: Concepts and Techniques
  • 112. 初始化训练集的选择: 神经元网络构建的很重要的环节 反映输入数据的概率分部 将训练集里的数据随机化 神经元权重初始化: 对训练集中至少一个输入有“获胜”的机会,或在获胜单元的邻域中2018/10/23112Data Mining: Concepts and Techniques
  • 113. 性能无监督学习 复杂度大大降低 系统是个黑盒 需要很大的训练集 结果有时不易理解 多维的竞争层不一定收敛 2018/10/23113Data Mining: Concepts and Techniques
  • 114. 8.9 孤立点分析孤立点:与数据的其他部分不同的数据对象 一个人的噪音是另一个人的信号 信用卡欺诈探测、收入极高或极低的客户分区、医疗分析 孤立点挖掘 在给定的数据集合中定义什么样的数据为不一致的 找到一个有效的方法来挖掘孤立点 统计学方法 基于距离的方法 基于偏移的方法2018/10/23114Data Mining: Concepts and Techniques
  • 115. 基于统计的孤立点检测工作假设(working hypothesis) N个数据对象的整个数据集合来自一个初始的分布模型F 不一致检测 数据分布 分布参数(平均值、变量等) 孤立点数目的期望值 缺点 只能在单属性上作检测 大部分情况下,数据分布未知2018/10/23115Data Mining: Concepts and Techniques
  • 116. 基于距离的孤立点检测解决了统计方法的主要缺陷 在未知数据分布状态下做多维数据分析 基于距离的DB(p,d)孤立点:数据集合T中至少有p部分与对象o的距离大于d 主要算法 基于索引的算法 嵌套-循环算法 基于单元的算法2018/10/23116Data Mining: Concepts and Techniques
  • 117. 基于偏离的孤立点检测检查组中对象的主要特征 偏离主要特征的对象被认为是孤立点 序列异常技术(sequential exception technique ) 模仿了人类从一系列推测类似的对象中识别异常对象的方式 OLAP数据立方体方法( OLAP data cube technique) 在大型多维数据中使用数据立方体来确定反常区域2018/10/23117Data Mining: Concepts and Techniques
  • 118. 8.10 小结什么是聚类分析 聚类分析中的数据类型 主要聚类方法的分类 划分方法:k-means 层次方法: 基于密度方法:DBSCAN,OPTICS,DENCLUE 基于网格的方法:STING,WAVECLUSTER,CLIQUE 基于模型的方法:SOM 孤立点分析2018/10/23118Data Mining: Concepts and Techniques