keynote:lesson04
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
keynote:lesson04 [2010/03/31 21:14] hongxin |
keynote:lesson04 [2010/06/26 20:09] 10921021 |
||
|---|---|---|---|
| Line 2: | Line 2: | ||
| ====== 4.1 聚类 ====== | ====== 4.1 聚类 ====== | ||
| ===== 4.1.1 聚类的简介 ===== | ===== 4.1.1 聚类的简介 ===== | ||
| - | **1.定义** | + | ====1.定义==== |
| 聚类是将数据点集分成由类似的点组成的多个类的过程，它是一种非监督的学习过程。\\ | 聚类是将数据点集分成由类似的点组成的多个类的过程，它是一种非监督的学习过程。\\ | ||
| {{:keynote:11.jpg}} | {{:keynote:11.jpg}} | ||
| - | **2.聚类与分类的区别** | + | ====2.聚类与分类的区别==== |
| * **聚类** | * **聚类** | ||
| * 实例： $\{ {\mathbf{x}}\}_{i=1}^N $ | * 实例： $\{ {\mathbf{x}}\}_{i=1}^N $ | ||
| Line 17: | Line 17: | ||
| <note tip> 聚类所要求划分的类是未知的。</note> | <note tip> 聚类所要求划分的类是未知的。</note> | ||
| | | ||
| - | **3.聚类的应用** | + | ====3.聚类的应用==== |
| 聚类方法可以运用于图像分割领域, 下图就是两个运用Mean-shift方法作图像分割的例子。\\ | 聚类方法可以运用于图像分割领域, 下图就是两个运用Mean-shift方法作图像分割的例子。\\ | ||
| {{:keynote:14.jpg}} \\ | {{:keynote:14.jpg}} \\ | ||
| Line 23: | Line 23: | ||
| ===== 4.1.2 几种聚类方法 ===== | ===== 4.1.2 几种聚类方法 ===== | ||
| - | **1.层次（从顶到下）聚类** | + | ==== 1.层次（自底向上）聚类 ==== |
| * **__思想__：** 顺序地将最近的两个点/类合并； | * **__思想__：** 顺序地将最近的两个点/类合并； | ||
| * **__具体过程__** | * **__具体过程__** | ||
| - 找到两个最近的点（类），并将其合并； | - 找到两个最近的点（类），并将其合并； | ||
| - | - 重复上步操作，直至所有的点聚为一个类； | + | - 重复上述操作，直至所有的点聚为一个类； |
| - | * **__变量定义__** | + | * **__变量定义（可聚类的两个前提条件）__** |
| - | - 两个数据点间的距离：$d(x_i, x_j)$； | + | - 可以度量两个数据点间的距离：$d(x_i, x_j)$； |
| - | - 两个类间的距离： | + | - 可以度量两个类间的距离： |
| - 单点距离： \[ d_{kl} = min_{x_i \in C_k, x_j \in C_l} d(x_i, d_j)\] | - 单点距离： \[ d_{kl} = min_{x_i \in C_k, x_j \in C_l} d(x_i, d_j)\] | ||
| - 平均点距离：\[ d_{kl} = \frac{1}{ |C_k| + |C_l| } \sum_{x_i \in C_k, x_j \in C_l} {d(x_i, d_j)} \] | - 平均点距离：\[ d_{kl} = \frac{1}{ |C_k| + |C_l| } \sum_{x_i \in C_k, x_j \in C_l} {d(x_i, d_j)} \] | ||
| - | - 质心距离： \[ d_{kl} = d(c_l, c_k), c_l = \frac{1}{ |C_k| } \sum_{x_i \in C_l} {x_i} \] | + | - 质心距离： \[ d_{kl} = d(c_l, c_k), c_k = \frac{1}{ |C_k| } \sum_{x_i \in C_k} {x_i} \] |
| * **__层次聚类的树形图表示__** | * **__层次聚类的树形图表示__** | ||
| Line 40: | Line 40: | ||
| * 其中，每一对数据点之间的高度为两个类之间的距离。 | * 其中，每一对数据点之间的高度为两个类之间的距离。 | ||
| - | **2.频谱聚类** | + | ==== 2.频谱聚类 ==== |
| * **__三要素__** | * **__三要素__** | ||
| - 最近点邻接图{{:keynote:22.jpg|}}； | - 最近点邻接图{{:keynote:22.jpg|}}； | ||
| Line 47: | Line 47: | ||
| - 若两点间无边，则其权值为0； | - 若两点间无边，则其权值为0； | ||
| - 变换成概率矩阵 {{:keynote:24.jpg|}}； | - 变换成概率矩阵 {{:keynote:24.jpg|}}； | ||
| - | * **__随机流动的性质__** | + | * **__随机漫步的性质__** |
| * {{:keynote:26.jpg|}} | * {{:keynote:26.jpg|}} | ||
| * 随着t的增大，t步后数据点的分布渐趋相似。若图为连通的，则最终的结果与初始点的选取无关。 | * 随着t的增大，t步后数据点的分布渐趋相似。若图为连通的，则最终的结果与初始点的选取无关。 | ||
| Line 57: | Line 57: | ||
| * **__频谱聚类的实例__** | * **__频谱聚类的实例__** | ||
| * {{:keynote:29.jpg|}} | * {{:keynote:29.jpg|}} | ||
| - | * **3.Flat聚类方法** | + | |
| - | - **K-means聚类** | + | ==== 3.Flat聚类方法 ==== |
| + | === 1.K-means聚类 === | ||
| * **__思想__** | * **__思想__** | ||
| - | * {{:keynote:30.jpg|Unordered List Item}} | + | * {{:keynote:30.jpg|}} |
| * **__具体过程__** | * **__具体过程__** | ||
| - | * {{:keynote:31.jpg|Unordered List Item}} | + | * {{:keynote:31.jpg|}} |
| - | - **混合高斯聚类** | + | === 2.混合高斯聚类 === |
| - | <note important> Revised by Zhang Xiaoli(张晓丽), <zhangxiaoli@zjucadcg.cn> </note> | + | |
| + | K-means 是一种 hard-assign 的聚类方法，就是说，在 K-means 中一个数据点“确定地”属于某一个类别，而混合高斯聚类（Gaussian Mixture Model, GMM）中则采用了一种 soft-assign 的方法，它并不确定地将一个数据点划分到某个类别，而是给出了该点属于不同类别的概率，一方面，我们可以直接选取概率最大的那个分类，进行 hard-assign ，另一方面，由于有了概率信息，我们通常可以做更多的事情，例如拒绝处理“模糊不清”的边界点等等。 | ||
| + | 具体来说，GMM 假设数据是服从一个混合高斯分布，也就是许多个独立的高斯模型的加权，聚类的过程实际上就是对这个 model 进行 fitting 的过程，恢复出各个高斯模型的参数之后，每个数据点属于该类别的概率也就很自然地使用该高斯模型生成这个数据的概率来表示了。通常我们都使用最大似然的方式来对概率模型进行 fitting ，但是混合高斯模型由于对多个高斯分布进行加权，结果的概率式子很难解析地或者直接地求得最大似然的解，所以在计算的过程中采用了分布迭代的过程，具体是使用了一种叫做 Expectation Maximization (EM) 的方法，进行迭代求解。 | ||
| + | GMM 有一些缺点，比如有时候其中一个 Gaussian component 可能会被 fit 到一个很小的范围内的点或者甚至单个数据点上，这种情况被称作 degeneration ，这个时候该模型的协方差矩阵会很小，而那里的概率值会变得非常大甚至趋向于无穷，这样一来我们可以得到极大的似然值，但是这样的情况通常并没有什么实际用处。解决办法通常是给模型参数加上一些先验约束，或者显式地检测和消除 degeneration 的情况。 | ||
| + | 另一个比较明显的缺点就是 GMM 模型中需要 fit 的参数非常多，特别是在维度较高的时候，协方差矩阵中需要 fit 的参数就极具增加了，这样的结果通常会导致很严重的 overfitting ，陷入唯独灾难中。一些可能的解决办法是限制协方差矩阵的结构，从而降低参数的个数。 | ||
| + | <note important> Revised by Zhang Xiaoli(张晓丽), <zhangxiaoli@zjucadcg.cn> </note> | ||
| + | <note important>Extended by --- //[[pluskid@gmail.com|张驰原]] 2010/04/26 14:53// GMM</note> | ||
| | | ||
| Line 393: | Line 399: | ||
| {{:keynote:qfqf23.jpg|}}\\ | {{:keynote:qfqf23.jpg|}}\\ | ||
| + | <note important> Revised by Feiwei Qin(秦飞巍), <qinfeiwei@zjucadcg.cn> </note> | ||
| + | |||
keynote/lesson04.txt · Last modified: 2021/04/13 21:35 (external edit)
Page Tools
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 4.0 International
