Clustering

2020-03-01 150浏览

1.聚类 Clustering 戎天泽
2.基本术语 Terminology • 机器学习可以由一个训练集 () 确定模型的内部参数，这一过程称作训练 (Training) 。 • 训练完成的模型便可以将输入值 X 转化为输出值 Y* 。目标值 Y 并不总是必须的，需要输入 Y 的模型叫做监督学习 (Supervise d) 。不输入 Y 的模型叫无监督学习 (Unsupervised) X X Y* M 预测集 Testing Set Y 标记 Label 预测标记 Testing Label 训练集 Training Set
3.聚类 Clustering • 报数游戏 3
4.聚类 Clustering • 报数游戏 3
5.聚类 Clustering • 报数游戏 4
6.聚类 Clustering • 报数游戏报数游戏是聚类在现实生活中的一个实例 4
7.聚类 Clustering • 报数游戏报数游戏是聚类在现实生活中的一个实例 4 类别数簇 Cluster
8.定义 Definition • 聚类的定义仍然没有共识，但是一般认为聚类有以下几个特征 • 同一个簇内的元素尽可能相似 • 不同簇内的元素尽可能不相似 • 相似性 Similarity 与不相似性 Dissimilarity 的定义是完备且有意义的 • 聚类的一般步骤是 • • • • 提取特征 Features Extraction 设计算法 Algorithm Design 结果评估 Result Validation 结果解释 Result Explanation 什么是相似和不相似如何去划分
9.定义 Definition • 关于簇标签是否为划分的问题 • 对于严格定义的聚类而言，其簇标签往往为数据集的划分 • 由于聚类技术的发展，现在出现了模糊聚类 Fuzzy Clustering 和基于分布的聚类，其并不满足划分的性质。 • 聚类不依赖于外部数据标签，仅通过数据内部的结构进行标注
10.相似度 Similarity
11.距离和相似度 Distance and Similarity • 对于有序 Ordinal 的数据，可以采用距离 Distance 来度量 • 非负性 • 对称性 • 三角不等式 • 对于无序数据，可以采用相似度 Similarity 来度量
12.距离 Distance • 闵氏距离 • 衡量几何关系时常用的一种距离 • 可以由 p 生成大部分几何距离 • P=1 为 Manhattan 距离， p=2 为欧氏距离， p=∞ 为切比雪夫距离 • 余弦距离 • 两向量夹角的余弦值 • 常用于 NLP 等领域 • Pearson 相关系数 • 两样本间的相关性
13.距离 Distance • 马氏距离 Mahalanobis distance X- 样本向量μ- 总体均值 Σ- 总体协方差矩阵 • 表示样体中某样样样样样本与样样样本样样体的差异程度样样样样样
14.距离 Distance • Bregman 散度 • 可以解决非凸性，或不规则形状等问题
15.相似度 Similarity • Jaccard 相似度 • 衡量两集合的相似度 • Humming 码距 • 衡量两个编码间的距离 • 交叉样样、KL 散度、互信息…… • 非度量距离
16.数据的划分 • 数据划分的种类多种多样错综复杂 • • • • • 基于划分基于密度基于层次基于分布 …… • 很多算法往往被样属到不止一种分样样样样样样样样样中去样
17.原型聚类 —— 诸建超
18.原型聚类 • 亦称“基于原型的聚类” • 通常情况下，先初始化 k 个原型变量，然后对他们进行迭代更新求解，最终得到 k 个聚类结果。 • 主要算法： K-means 、 LVQ 、 GMM
19.K-means——K 均值聚类 • 给定样本集 D = {x1, x2, …, xm} ， k-means 算法针对聚类所得簇，将 D 划分为 k 个类别，即 C = {C1, C2, …, Ck} • 最小化平方误差： • 其中 μi 是簇 Ci 的均值向量。 • 在一定程度上， E 刻画了簇内样本围绕簇均值向量的紧密程度， E 值越小则簇内样本相似度越高。
20.K-means—— 算法流程 ① 对均值向量进行初始化 ② 计算样本到每个均值向量的距离，并将该样本划入距离最小的簇中 ③ 更新均值向量
21.K-means—— 算法流程
22.K-means—— 算法实例演示 C3 C2 C1 0.369 0.506 0.166
23.K-means—— 算法实例演示
24.K-means—— 算法实例演示
25.LVQ—— 学习向量量化 • 与 k 均值算法类似，“学习向量量化”（ Learning Vector Quan tization ， LVQ ）也是样样样找到一样样样样原型向量来刻画聚样样样样样样样样样样构。样 • 不同的是 LVQ 假设数据样本带有类别标记，即输入的数据集为 D = {(x1,y1), (x2,y2), …, (xm,ym)} ，其中 yi 为 xi 的类别标记，学习过程中利用样本的这些监督信息来辅助聚类。
26.LVQ—— 算法流程 ① 初始化原型向量 ② 计算样本与每个原型向量的距离，找出最近的原型向量 ③ 根据样本实际类别标记与原型向量预设的类别标记是否相等，来更新原型向量
27.LVQ—— 算法实例演示 C1 C2 0.28 3 0.50 6 √ 0.43 4 0.26 0 0.03 2 x 1 x5 x12 x18 x23 x2 p 1 p 2 p 3 p 4 p 5 样样样样样 c1 c2 c2 c1 c1 C1
28.LVQ—— 算法实例演示
29.LVQ—— 算法实例演示
30.GMM—— 高斯混合聚类 • 与 K-means 、 LVQ 使用原型向量来刻画聚类结构不同，高斯混合聚类采用概率模型来表达聚类原型 • 高斯分布——正态分布 • 高斯混合模型就是几个正态分布的叠加，每一个正态分布代表一个类别
31.GMM—— 高斯混合聚类 • 高斯混合聚类得到的是每个样本点属于各个类的概率，而不是判定它完全属于一个类，所以有时也会被称为软聚类。
32.GMM—— 算法流程 ① 初始化模型参数 ② 针对每一个样本，计算其在各个高斯分布下的概率 ③ 更新模型参数 ④ 根据高斯混合分布确定簇划分
33.GMM—— 算法实例演示
34.GMM—— 算法实例演示
35.GMM—— 算法实例演示
36.GMM—— 算法实例演示
37.层次聚类（ hierarchical clustering ）上述的 k-means 算法确实是一种方便好用的聚类算法，但是始终有 K 值选择和初始聚类中心点选择的问题，而这些问题也会影响聚类的效果。为了避免这些问题，我们可以选择另外一种比较实用的聚类算法 - 层次聚类算法（ hierarchical clustering ）。层次聚类试图在不同层次上对数据集进行划分，从而形成树形（ dendrogram ）的聚类结构，以此来记录聚合和分拆的过程。
38.两种策略 •—— 自底向上（ Agglomerative ）：也叫做凝聚法，指的是初始时将每个样本点当做一个类簇，所以原始类簇的个数等于样本点的个数，然后依据某种准则合并这些初始的类簇，直到达到某种条件或者达到设定的分类数目。 •—— 自顶向下（ Divisive ）：也叫做分裂法，指的是初始时将所有的样本归为一个类簇，然后依据某种准则进行逐渐的分裂，直到达到某种条件或者达到设定的分类数目
39.聚合聚类算法（ AGNES ， AGglomerative NEStin g） • 是更加常用的层次聚类算法，其基础算法十分简单： • 1. 初始化距离矩阵 (proximity matrix) ，用来记录聚类簇之间的某种距离 2. 将数据集中的每一个样本看作一个初始聚类簇 Repeat 合并距离最近的两个聚类簇更新距离矩阵 Until 达到预设的聚类簇个数（例如最后设置为一个聚类簇）
40.关键因素：聚类簇间的距离度量 1 最小距离：取两个样簇中距离最近的两个样本的距离作样样为这两个类簇的距离，此时称 AGNES 算法为单链接 2 最大距离：取两个类簇中距离最远的两个样本的距离作为这两个类簇的距离，此时称 AGNES 算法为全链接 3 平均距离：把两个类簇中的样本两两间的距离全部放在一起求一个平均值作为这两个类簇距离，称为均连接 4 取两两距离的中间值作为类簇距离，与取均值相比更加能够解除个别偏离样本对结果的干扰 5 把两个类簇中的样本两两间的距离全部放在一起求和然后除以两个集合中的元素个数作为类簇距离 6 求每个类簇的中心点 ( 就是将类簇中的所有样本的对应维度相加然后再除以样本个数得到的一个向量 ) ，然后用中心点代替类簇再去求类簇间的距离 7 其他方法…
41.最小距离度量的优缺点聚类后的类别优点：可以较好地处理非椭圆形的数据分布噪声点实际的类别缺点：对噪声和极端值比较敏感聚类后的类别
42.最大距离度量的优缺点优点：可以一定程度容忍噪声和极端值缺点：可能会使较大的类簇分裂聚类后的类别
43.BIRCH （ Balanced Iterative Reducing and Clustering Us ing Hierarchies ） • 利用层次方法的平衡迭代规约和聚类 • 比较适合于数据量大，类别数 K 也比样样多的情况。它运行速度很快，只需要样样样样样样样样样样样样样样样单遍扫描数据集就能进行聚类。 • BIRCH 算法利用了一个样样样构来帮助我样样样样样样快速的聚样样样样样，一般称之样样聚类特征树样样样 (Clustering Featu re Tree ，简称 CF Tree)
44.CF Tree 这颗树的每一个节点是由若干个聚类特征 (Clustering Feature ，简称 CF) 组成。从下图我们可以看看聚类特征树是什么样子的：每个节点包括叶子节点都有若干个 CF ，而内部节点的 CF 有指向孩子节点的指针，所有的叶子节点用一个双向链表链接起来。 CF ：每一个 CF 是一个三元组，可以用（ N ， LS ， SS ）表示。其中 N 代表了样样个CF 中拥有的样本点的数量，样样样样样样样样个好理解；样样样样 LS 代表了这个 CF 中拥有的样本点各特征维度的和向量， SS 代表了这个 CF 中拥有的样本点各特征维度的平方和
45.CF 有一个很好的性质，就是满足线性关系，也就是 CF1+CF2= （ N1+N2,LS1+LS2,SS1+SS2) 。这个性质从定义也很好理解。如果把这个性质放在 CF Tree 上，也就是说，在 CF Tree 中，对于每个父节点中的 CF 节点，它的 (N,LS,SS) 三元样样的样样等于样样样 CF 个节点所指向的所有子节点的三元组之和。从左图中可以看出，根节点的 CF1 的三元组的值，可以从它指向的 6 个子节点（ CF7 - CF12 ）的值相加得到。这样我们在更新 CF Tree 的时候，可以很高效。对于 CF Tree ，我们一般有几个重要参数，第一个参数是每个内部节点的最大 CF 数 B ，第二个参数是每个叶子节点的最大 CF 数 L ，第三个参数是针对叶子节点中某个 CF 中的样本点来说的，它是叶节点每个 CF 的最大样本半径阈值 T ，也就是说，在这个 CF 中的所有样本点一定要在半径小于 T 的一个超球体内。对于左图中的 CF Tree ，限定了 B=7 ， L=5 ，也就是说内部节点最多有 7 个 CF ，而叶子节点最多有 5 个 CF 。
46.CF Tree 的插入 • 首先需要定义好 CF Tree 的参数：即内部节点的最大 CF 数 B ，叶子节点的最大 CF 数 L ，叶节点每个 CF 的最大样本半径阈值 T 。 • 1. 从根节点向下寻找和新样本距离最近的叶子节点和叶子节点里最近的 CF 节点。 • 2. 如果新样本加入后，这个 CF 节点对应的超球体半径仍然满足小于阈值 T ，则更新路径上所有的 CF 三元组，插入结束。否则转入 3. • 3. 如果当前叶子节点的 CF 节点个数小于阈值 L ，则创建一个新的 CF 节点，放入新样本，将新的 CF 节点放入这个叶子节点，更新路径上所有的 CF 三元组，插入结束。否则转入 4 。 • 4. 将当前叶子节点划分为两个新叶子节点，选择旧叶子节点中所有 CF 元组里超球体距离最远的两个 CF 元组，分布作为两个新叶子节点的第一个 CF 节点。将其他元组和新样本元组按照距离远近原则放入对应的叶子节点。依次向上检查父节点是否也要分裂，如果需要按和叶子节点分裂
47.第一个样本点，将它放第二个样本点，我们发现这个第三个节点，结果我们发现这个节点入一个新的 CF 三元组 A 样本点和第一个样本点 A ，在不能融入刚才前面的节点形成的超球半径为 T 的超球体范围内，也体内，也就是说，我们需要一个新的就是说，它们属于一个 CF ，我 CF 三元组 B ，来容纳这个新的值。们将第二个点也加入 CF A, 此此时根节点有两个 CF 三元组 A 和 B 时需要更新 A 的三元组的值
48.第四个样本点的时候，我们发现和 B 在半径小于 T 的超球体，于是加入 CF B
49.样点分裂：如图，叶子节点 LN1 有三个 CF ， LN2 和 LN3 各有两个 CF 。我们设置的叶子节点的最大 CF 数 L=3 。此时一个新的样本点来了，我们发现它离 LN1 节点最近，因此开始判断它是否在 sc1,sc2,sc3 样 3 个 CF 对应的超球体之内，但是很不幸，它不在，因此它需要建立一个新的 CF ，即 sc8 来容纳它。问题是我们的 L=3 ，也就是说 LN1 的 CF 个数已经达到最大值了，不能再创建新的 CF 了，怎么办？此时就要将 LN1 叶子节点一分为二了。
50.我们将 LN1 里所有 CF 元组中，找到两个最远的 CF 做这两个新叶子节点的种子 CF ，然后将 LN1 节点里所有 CF （ sc1, sc2, sc3 ），以及新样本点的新元组 sc8 划分到两个新的叶子节点上。将 LN1 节点划分后的 CF Tree 如上图
51.将所有的训练集样本建立了CF Tree，一个基本的BIRCH算法就完成了，对应的输出就是若干个 CF节点，每个节点里的样本点就是一个聚类的簇。也就是说BIRCH算法的主要过程，就是建立CF 样样样样样样 Tree的过程。当然，真实的BIRCH算法除了建立CF Tree 来聚类，其实还有一些可选的算法步骤的，现在我们就来看看 BIRCH 算法的流程。 1 ）将所有的样样本依次样样样样入，根据上述做法在内存中建立一样样样样样样样样样样样样样 CF 样样Tree。 2）（可选）将第一步建立的CF Tree样行样样样，去除一些异常样样样样样 CF节点，这些节点一般里面的样本点很少。对于一些超样球体距离非常近的元组进行合并。 3）（可选）利用其它的一些聚类算法比如K-Means 对所有的 CF元组进行聚类，得到一颗比较好的CF Tree。这一步的主要目的是消除由于样本读入顺序导致的不合理的树结构，以及一些由于节点 CF个数限制导致的树结构分裂。 4）（可选）利用第三步生成的CF Tree的所有CF节点的质心，作为初始质心点，对所有的样本点按距离远近进行聚类。这样进一步减少了由于CF Tree的一些限制导致的聚类不合理的情况。从上面可以看出，BIRCH算法的关键就是步骤1，也就是CF Tree的生成，其他步骤都是为了优化最后的聚类结果。
52.BIRCH 算法小结 • BIRCH 算法可以不用输入类别数 K 值，这点和 K-Means ， Mini Batch K-Means 不同。如果不输入 K 值，则最后的 CF 元组的组数即为最终的 K ，否则会按照输入的 K 值对 CF 元组按距离大小样行合并。 • 一般来说， BIRCH 算法适用于样本量较大的情况，这点和 Mini Batch K-Means 类似，但是 BIRC H 适用于类别数比较大的情况，而 Mini Batch K-Means 一般用于类别数适中或者较少的时候。 B IRCH 除了聚类还可以额外做一些异常点检测和数据初步按类别规约的预处理。但是如果数据特征的维度非常大，比如大于 20 ，则 BIRCH 不太适合，此时 Mini Batch K-Means 的表现较好。 • 对于调参， BIRCH 要比 K-Means ， Mini Batch K-Means 复杂，因为它需要对 CF Tree 的几个关键的参数进行调参，这几个参数对 CF Tree 的最终形式影响很大。
53.BIRCH 算法的样缺点样样 • BIRCH 算法的主要优点有： 1) 节约内存，所有的样本都在磁盘上， CF Tree 仅仅存了 CF 节点和对应的指针。 2) 聚类速度快，只需要一遍扫描训练集就可以建立 CF Tree ， CF Tree 的增删改都很快。 3) 可以识别噪音点，还可以对数据集进行初步分类的预处理。 • BIRCH 算法的主要缺点有： 1) 由于 CF Tree 对每个节点的 CF 个数有限制，导致聚类的结果可能和真实的类别分布不同。 2) 对高维特征的数据聚类效果不好。此时可以选择 Mini Batch K-Means 。 3) 如果数据集的分布簇不是样样似于样超球体，或者说不是凸的，则聚类效果不好。
54.ROCK (RObust Clustering using linK s) • ROCK 是 Sudipno Guha 等人于 1999 年提出的一个著名的面向分类属性数据的聚类算法，其突出样献是采用公共近邻（链接）数的全局信息作样样样样为评价数据点间相关性的度量标准，而不是传统的基于两点间距离的局部度量函数。 • ROCK 聚类算法是一种鲁棒的用于分类属性的聚类算法。该算法属于凝聚型的层次聚类算法。之所以鲁棒是因为在确认两对象（样本点 / 簇）之样样的样样系样样考样样了他样样样共同的样样样样居（相似样本点）的数量，在算法中被叫做链接（ Link ）的概念。而一些聚类算法只关注对象之间的相似度。
55.ROCK 中的四个关键概念 • 邻居（ Neighbors ）：如果两个样本点的相似度达到了阈值（ θ ），这两个样本点就是邻居。阈值（ θ ）有用户指定，相似度也是通过用户指定的相似度函数计算。常用的分类属性的相似度计算方法有： Jaccard 系数，余弦相似度。 • 链接（ Links ）：两个对象的共同邻居数量。 • 目标函数（ Criterion Function ）：最大化下面目标函数以获得最优的聚类结果。（通过最大化目标函数使得簇之间的链接总数最小，而簇内的链接总数最大）。其中， Ci ：第 i 个簇， k ：簇的个数， ni ： Ci 的大小（样本点的数量）。一般可使用 f(θ) = (1-θ)/(1+θ) 。 f(θ) 一般具有以下性质： Ci 中的每个样本点在 Ci 中有 ni f(θ) 个邻居。
56.• 相似性的度量（ Goodness Measure ）：使用下面公式计算所有对象的两两相似度，将相似性最高的两个对象合并。对于 ROCK 聚类的每一步，通过该相似性度量不断地凝聚对象至 k 个簇，最终计算上面目标函数值必然是最大的。
57.ROCK 算法主要思路输入：需要聚类的个数： k ，和相似度阈值： θ 算法： • 开始每个点都是单独的聚类簇，根据计算点与点间的相似度，生成相似度矩阵。 • 根据相似度矩阵和相似度阈值 θ ，计算邻居矩阵 A 。如果两点相似度 >=θ, 取值为 1 （邻居），否则取值 0 。 • 计算链接矩阵 L=A x A • 计算相似性的度量（ Goodness Measure ），此度量引入了 Link ，将相似性最高的两个对象合并。回到第 2 步进行迭代直到形成 k 个聚类或聚类的数量不在发生变换。 • 输出： • 簇和异常值（不一定存在）
58.ROCK 算法总结 • 其他传统的聚类算法主要是采用距离进行相似性度量，这样往往不会产生高质量的聚类簇，而 ROCK 算法采用了随机抽样技术，在计算两个对象的相似度时，同时考虑了周围对象的影响，并使用凝聚性的层次聚类，使得聚类的结果在某些场合下比传统聚类方法要好。 • 可以识别形状复杂，大小不一的聚类，还可以过滤异常值。 • 可以处理混合型的数据（如同时包含连续型变量、名义型变量和顺序型变量的数据），而其他方法（例如 BIRCH 和 DBSCAN ）只能处理数值型的数据。
59.层次聚类的问题和缺陷 • 一旦两个结点合并为一个类簇，它们就不会再分开了。 • 没有一个具体的目标函数可以直接优化。 • 不同的层次聚类算法都或多或少有以下的问题： 1 ）对噪声和异常值敏感 2 ）不能很好地解决各种不同形状的数据集 3 ）会将较大的聚类簇拆分
60.密度聚类杜星波
61.密度聚类原理 • 假定类别可以通过样本分布的紧密程度决定。 • 通过将紧密相连的样本划为一类，得到一个聚类类别。 • 通过将各组紧密相连的样本划为各个不同的类别，得到最终的聚类结果。
62.密度聚类 • 密度聚类的主要特点是能将密度足够大的相邻区域连接，能有效处理异常数据，主要用于对空间数据的聚类。 • 典型算法： • DBSCAN ：不断生长足够高密度的区域 • OPTICS ：针对数据在空间中呈现的不同密度分不对 DBSCAN 作了改进 • DENCLUE ：根据数据点在属性空间中的密度进行聚类，密度和网格与处理的结合 • CLIQUE ：结合网格和密度聚类的思想，能处理大规模高维度数据
63.DBSCAN ——Density-Based Spatial Clustering of Applications with Noise •DBSCAN:Ester, et al. (KDD’96) • DBSCAN 基于邻域来描述样本集的紧密程度，参数（ ε ， MinP ts ）用来描述邻域的样本分布紧密程度。
64.DBSCAN 的一些概念 —— Density-Based Spatial Clustering of Applications with Noise • ε- 邻域：对其 ε- 邻域包含样本集 D 中与的距离不大于 ε 的样本，即。
65.DBSCAN 的一些概念 —— Density-Based Spatial Clustering of Applications with Noise • 核心对象（ core object ）：若的至少包含个样本，即，则是一个核心对象。
66.DBSCAN 的一些概念 —— Density-Based Spatial Clustering of Applications with Noise • 密度直达（ directly density-reachabl e ）：若位于的，且是核心对象，则称由密度直达。
67.DBSCAN 的一些概念 —— Density-Based Spatial Clustering of Applications with Noise • 密度可达（ density-reachable ）：对与，若存在样本序列，其中，且由密度直达，则称由密度可达。
68.DBSCAN 的一些概念 —— Density-Based Spatial Clustering of Applications with Noise • 密度相连（ density-connected ）：对与，若存在使得与均由密度可达，则称与密度相连。
69.DBSCAN 的簇 (cluster) ——Density-Based Spatial Clustering of Applications with Noise • 由这些概念， DBSCAN 将“簇 (cluster)” 定义为：由密度可达（ density-reachable ）关系导出的最大的密度相连（ density-connected ）样本集合。 • 即满足： 1 ）连接性 2 ）最大性
70.DBSCAN 的算法流程 —— Density-Based Spatial Clustering of Applications with Noise 找出所有核心对象以任一未被访问的核心对象为出发点，找出其密度可达的样本生成聚类簇是否还有核心对象未被访问否聚类完成是
71.DBSCAN 的实例 —— Density-Based Spatial Clustering of Applications with Noise
72.DBSCAN 的优缺点 —— Density-Based Spatial Clustering of Applications with Noise DBSCAN 的主要优点有： 1 ）可以样样任意形状的稠密数据集样样样样样样样样样样样行聚样样 2 ）可以在聚类的同时发现异常点。 3 ）聚类结果没有偏倚。 DBSCAN 的主要缺点有： 1 ）如果样本集的密度不均匀、聚类间距差相差很大时，聚类质量较差，这时用 DBSCAN 聚样样一般不适合。样样样样样 3 ）调参相对于传统的 K-Means 之样样的聚样样样算法稍样样样样
73.DBSCAN 聚样样效果不好的情况样样样样样样 —— Density-Based Spatial Clustering of Applications with Noise
74.OPTICS ——Ordering Points To Identify the Clustering Structure •OPTICS:Ankerst, et al (SIGMOD’99) • OPTICS 的思想和 DBSCAN 非常相似，但是 OPTICS 可以获得不同密度的聚类。因为 OPTICS 算法输出的是样本的一个有序队列，从这个队列里可以获得任意密度的聚类。
75.OPTICS 的一些新概念 —— Ordering Points To Identify the Clustering Structure • 核心距离： • 可达距离：
76.OPTICS 的算法流程 —— Ordering Points To Identify the Clustering Structure •• 输入：数据样本 D ，半径 ε ，最少点数 • 1. 建立两个队列，有序队列和结果队列。 • 2. 选取 D 中一个未处理且为核心对象的点，放入结果队列，找到该核心点的直接密度可达点，如果不存在于结果队列中，则放入有序队列，并按可达距离升序排列。 • 3. 从有序队列中抽取第一个点，保存至结果队列中。 • 3.1 判断该点是否为核心点，不是则返回 3 ，是的话找到其所有直接密度可达点，并将这些点放入有序队列（如果不在结果队列的话），并按可达距离重新排序，如果该点已经在有序队列中，且新的可达距离较小，则更新该点的可达距离。 • 3.2 重复步骤 3 ，直至有序队列为空，跳至 2 ，直到 D 中所有点都处理完毕。 • 4. 算法结束。
77.OPTICS 的算法流程 —— Ordering Points To Identify the Clustering Structure • 最后输出结果序列。如果该点的可达距离不大于给定半径，则该点属于当前类别。 • 不在结果队列中的点则该点为噪声，可以忽略。
78.图聚类
79.谱聚类 —— spectral clustering • 谱聚类是从图论中演化出来的算法。 • 核心思想是把空间中的点用边样接起来。 • 距离较小的点，它们的边权值较大；反之样样样低。 • 通过对所有数据点组成的图进行切图，完成聚类的目的。
80.谱聚类——邻接矩阵 W ——spectral clustering • 距离较小的点，它们的边权值较大；反之权值较低。 • 考样样用相似度矩样样样样样样（ ε- 邻近法、 K- 邻近法、全连接法）
81.谱聚类——度矩阵 D ——spectral clustering • 每个点的度定义为与它相连的所有边的权重之和。
82.谱聚类——拉普拉斯矩阵 —— spectral clustering • 拉普拉斯矩阵定义为，它具有如下性质： • 1 ）拉普拉斯矩阵是对称矩阵。 • 2 ）拉普拉斯矩阵的所有特征值都是实数。 • 3 ）拉普拉斯矩阵都是半正定的，所有特征值都大于等于 0 。 ≥0
83.谱聚类——切图 —— spectral clustering • 切图目的：让子图内的点权重和高，子图间的点权重和低。 • 最小化：
84.谱聚类——切图聚类 —— spectral clustering • RatioCut 切图（同时考虑最大化每个子图的个数） • 最小化： • Ncut 切图（同时考虑最大化每个子图的权重和） • 最小化：
85.谱聚类——切图聚类 —— spectral clustering • RatioCut 切图（同时考虑最大化每个子图的个数） • 最小化： • 引入指示向量：
86.谱聚类——切图聚类 —— spectral clustering
87.谱聚类——切图聚类 —— spectral clustering • 最样目的：样样样 • 找到最小的 k 个特征值所对应的特征向量，组成 H ，标准化样理。样样 • 然后用样样样聚样样方法（如样样样 K-means ）对 H 的行向量进行聚类。
88.谱聚类——算法流程输入样本集 D ，降维后的维度 k1 ，聚类后的维度 k2 构建相似矩阵 S 计算邻接矩阵 W ，构建度矩阵 D 计算拉普拉斯矩阵L 构建标准化后的拉普拉斯矩阵 D-1/2LD-1/2 计算 D-1/2LD-1/2 最小的 k1 个特征值所对应的特征向量 f 将对应的特征向量 f 组成的矩阵按行标准化，最终组成 n*k1 的特征矩阵 F 对 F 的每一行进行聚类得到簇划分 C(c1,c2,…ck2)
89.谱聚类——优缺点 • 谱聚类的优点有： • 1. 便于处理稀疏数据的聚类。 • 2. 相比传统聚类，由于使用了降维，因此处理高维数据聚类时复杂度较好。 • 谱聚类的缺点有： • 1. 若最终聚类的维度非常高，会导致运行速度和聚类效果都不好。 • 2. 聚类效果依赖于相似矩阵。
90.Chimeleon 算法
91.Chameleon 算法 • 优点 • 能处理复杂图形和各种病态数据 • 平衡了局部信息和整体信息 • 缺点 • 时间复杂度达到 o(n^3) • 空样样样样度也非常大，往往不能全部装入内存样样样样样样样样样样样样样样样
92.Mean Shift 算法
93.
94.基于模糊 Fuzzy-based • 当标签的归属关系无法用单纯的属于 / 不属于描述时，引入模糊集的概念，其中的元素有一个参数叫做归属度。 • 模糊聚类中假设每个样本都属于每一个标签，但归属度不同。 • 经典算法是在 K-mean 的基础上改进而成的 Fuzzy C-mean(FC M)
95.基于网格 Grid-based
96.基于神经网路 NN-based • 自组织映射 SOM
97.基于 AP 算法
98.半监督聚类 • 基于约束 • 必须相连 • 不能相连 • 基于标记样本 • 标签传播 • 约束种子 k-mean
99.其他聚样算法样样 • 在线聚类算法 • STREAM, CluStream, DenStream • 量子算法 • QC ， DQC • 核方法 • Kk-mean ， k-som • 集成算法
100.CV 领域
101.NLP 领域 • 词聚类
102.其他应用 • 用户画像 • 数据分析 • ……
103.
104.
105.聚类评价 • 类内相似度 • 类间区分度 • 外标法 External Index • 内标法 Internal Index
106.
107.外标评估 • 纯度 Purity • 分类正确占总样本的比例 • 信息熵 Entropy • Jaccard 系数 • FMI 指数 • Rand 指数
108.
109.内标评价 • 紧性 Compactness • SSE 、最小平均距离 • 区分性 Separation • 交叉熵
110.Silhoutte 系数