Differences

This shows you the differences between two versions of the page.

--- keynote:lesson04 [2010/03/31 20:49]
hongxin
+++ keynote:lesson04 [2010/06/26 19:34]
10921021
@@ Line 2: / Line 2: @@
 ====== 4.1 聚类 ======
 ===== 4.1.1 聚类的简介 =====
-**1.定义**
+====1.定义====
-   聚类是将数据点集分成由类似的点组成的多个类的过程，它是一种非监督的学习过程。\\
+聚类是将数据点集分成由类似的点组成的多个类的过程，它是一种非监督的学习过程。\\
-   {{:keynote:11.jpg}}
+{{:keynote:11.jpg}}
-**2.聚类与分类的区别**
+====2.聚类与分类的区别====
     * **聚类**
         * 实例： $\{ {\mathbf{x}}\}_{i=1}^N $
@@ Line 16: / Line 17: @@
 <note tip> 聚类所要求划分的类是未知的。</note>
-**3.聚类的应用**
+====3.聚类的应用====
 聚类方法可以运用于图像分割领域, 下图就是两个运用Mean-shift方法作图像分割的例子。\\
  {{:keynote:14.jpg}} \\
@@ Line 22: / Line 23: @@
 ===== 4.1.2 几种聚类方法 =====
-**1.层次（从顶到下）聚类**
+==== 1.层次（从顶到下）聚类 ====
   * **__思想__：** 顺序地将最近的两个点/类合并；
   * **__具体过程__**
     - 找到两个最近的点（类），并将其合并；
-     - 重复上步操作，直至所有的点聚为一个类；
+    - 重复上述操作，直至所有的点聚为一个类；
-  * **__变量定义__**
+  * **__变量定义（可聚类的两个前提条件）__**
-    - 两个数据点间的距离：{{:keynote:17.jpg|}}；
+    - 可以度量两个数据点间的距离：$d(x_i, x_j)$；
-     - 两个类间的距离：
+    - 可以度量两个类间的距离：
-         - 单点距离：{{:keynote:18.jpg|}}；
+         - 单点距离：  \[ d_{kl} = min_{x_i \in C_k, x_j \in C_l} d(x_i, d_j)\]
-         - 平均点距离：{{:keynote:19.jpg|}}；
+         - 平均点距离：\[ d_{kl} = \frac{1}{ |C_k| + |C_l| } \sum_{x_i \in C_k, x_j \in C_l} {d(x_i, d_j)} \]
-         - 质心距离：{{:keynote:20.jpg|}}；
+         - 质心距离：  \[ d_{kl} = d(c_l, c_k), c_k = \frac{1}{ |C_k|  } \sum_{x_i \in C_k} {x_i} \]
   * **__层次聚类的树形图表示__**
-  * {{:keynote:21.jpg|}}
+{{:keynote:21.jpg}}
   * 其中，每一对数据点之间的高度为两个类之间的距离。
-**2.频谱聚类**
+==== 2.频谱聚类 ====
   * **__三要素__**
     - 最近点邻接图{{:keynote:22.jpg|}}；
@@ Line 53: / Line 57: @@
   * **__频谱聚类的实例__**
   * {{: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 138: / Line 148: @@
 根据马尔科夫链计算公式求得DK一周都出现高气压的概率非常小，而Cal的概率较大些
-=====4.2.3隐马尔科夫模型（HMM）=====
+=====4.2.3 隐马尔科夫模型（HMM）=====
-   HMM概念
+==== 隐马尔科夫模型定义 ====
 HMM的状态时不确定或不可见的，只有通过观测序列的随机过程才能表现出来\\
 观察到得事件与状态并不是一一对应，而是通过一组概率分布相联系\\
@@ Line 153: / Line 165: @@
 B：给定状态下,观测概率分布,$b_j(O_t)=P(O_t=V_j|q_t=s_j)$表示在$t$时刻、状态$S_j$条件下，观察符号为$V_j$的概率\\
 $\pi$：初始状态空间的概率分布，$\pi$={$a_0$}\\
-    用HMM产生一串序列
+==== 隐马尔科夫模型序列生成 ====
 给定一个HMM，可以按如下步骤产生一个长度为n的观察序列：\\
 .	在状态$q_1$开始，根据概率$a_{0t1}$转移\\
@@ Line 160: / Line 174: @@
 .	……直到发射出$o_n$\\
 {{keynote:f_6.jpg|}}\\
-    HMM计算公式
+==== 隐马尔科夫模型计算公式 ====
 给定一个状态序列Q=$q_1q_2...q_T$\\
 对于Q的观察序列O是：\\
@@ Line 169: / Line 185: @@
 P(O|$\lambda$)=$a_{0q1}a_{q1q2}a_{q2q3}...a_{qT-1qT}$\\
 P(O,Q|$\lambda$)=$a_{0q1}b_{q1}(O_1)a_{q1q2}b_{q2}(O_2)a_{q2q3}...a_{qT-1qT}b_{qT}(O_T)$\\
-    HMM实例——描述
+==== 隐马尔科夫模型实例 ====
 高低气压模型：假设不能测量气压值，天气状况受大气压影响，可以建立HMM，隐藏状态用高低气压表示，观察值是天气状况，如下图：\\
-{{keynote:f_7.jpg|}}\\
+{{keynote:f_7.jpg}}\\
-    用HMM计算公式求解
+==== 隐马尔科夫模型计算公式 ====
+HMM求解公式为:
 $P(x,\pi)=(a_{OL}e_L(R)) (a_{LL}e_L(S)) (a_{LL}e_L(R)) (a_{LH}e_H(S)) (a_{HH}e_L(R))$\\
 $\qquad=(\frac{8}{11}\frac{8}{10})(\frac{7}{10}\frac{8}{10})(\frac{7}{10}\frac{2}{10})(\frac{7}{10}\frac{8}{10})(\frac{3}{10}\frac{8}{10})(\frac{2}{10}\frac{8}{10})(\frac{8}{10}\frac{8}{10})$\\
 $\qquad=0.0006278$
-    HMM需要解决的三个基本问题
+==== 隐马尔科夫模型的三个基本问题 ====
+HMM可基本总结为对三类基本问题的求解:
 .	赋值问题\\
 给定观察序列$O$以及模型$M=${$S,V,A,B,\pi$}，如何计算$P(O|M)$？\\
@@ Line 184: / Line 207: @@
 给定模型$M=${$S,V,A,B,\pi$}，但没有指定A,B，如何调整模型参数$(\pi，A，B)$使得观测序列$O$的概率最大？
 基本算法——针对以上三个问题，提出相应的算法\\
-    解决赋值问题：
+==== 隐马尔科夫模型的赋值问题 ====
+解决HMM的赋值问题可采用:
 ）基础方法——穷举法\\
 给定一个固定的状态序列$S=(q_1，q_2，q_3…)$通过累加所有可能的状态序列$q$\\
@@ Line 192: / Line 218: @@
 $P(O|\lambda)=\sum\limits_{所有s}P(O|S,\lambda) P(O|\lambda)$\\
 计算复杂性为$O（N^7）$\\
 ）	前向算法：动态规划的思想\\
 定义前向变量： $\alpha _t(i)=P(O_1O_2…O_i,q_i=S_i|\lambda)$\\
@@ Line 197: / Line 224: @@
 迭代 $\overline{\alpha_{t+1}(i)}=[\sum\limits_{i=1}^{N}\alpha_t(i)a_{ij}]b_j(O_{t+1})$\\
 终止 $P(O|\lambda)=\sum\limits_{i=1}^{N}\alpha_T(i)$\\
 ）	后向算法：与前向算法类似
 定义后向变量： $\beta_t(i)=P(O_{t+1}O_{t+2}…O_T|q_t=S_i,\lambda)$\\
@@ Line 202: / Line 230: @@
 迭代 $\beta_T(i)= \sum\limits_{j=1}^{N}a_{ij}b_j(O_{t+1})\beta_{t+1}（j）$\\
 终止 $P(O|\lambda)=\sum\limits_{j=1}^{N}a_{0j}b_1(O_1)\beta_1(j) $
-      解决解码问题
+==== 隐马尔科夫模型的赋值问题 ====
 目的：$P(Q|O,\lambda)=\frac{ P(O|Q,\lambda)}{ P(O|\lambda)}$\\
 最大化 等价于最大化 $P(Q|O,\lambda)=a_{i_1} b_{i_1o_1} a_{i_1i_2} b_{i_2o_2} a_{i_2i_3} b_{i_3o_3}…. a_{i_{T-1}i_T} b_{i_To_T}$\\
-这是寻找最佳路径问题\\
+这是寻找最佳路径问题
- $max P(O|Q,\lambda)=max ln P(O|Q,\lambda)=max(ln(a_{i_1} b_{i_1o_1})+ ln(a_{i_1i_2} b_{i_2o_2})+…+ln(a_{i_{T-1}i_T} b_{i_To_T}))$
+\[max P(O|Q,\lambda)=max ln P(O|Q,\lambda)=max(ln(a_{i_1} b_{i_1o_1})+ ln(a_{i_1i_2} b_{i_2o_2})+…+ln(a_{i_{T-1}i_T} b_{i_To_T}))\]
-     Viterbi 算法（N是状态数目，T是序列长度）
-初始化$\delta_1(i)=a_{oi}b_i(O_1)$  $\psi_1(i)=0$\\
+**Viterbi 算法**（N是状态数目，T是序列长度）\\
-递归$\delta_t(j)=max_i[\delta_{i-1}(i)a_{ij}]b_j(O_t) \qquad t=2,…T \qquad j=1…N $
+初始化:
-$\qquad\psi_1(j)=argmax_i[\delta_{i-1}(i)a_{ij}] \qquad t=2,…T \qquad j=1…N $\\
+\[ \delta_1(i)=a_{oi}b_i(O_1),  \psi_1(i)=0 \]
-终止$P^*=max_i\delta_T(i)$ ${q_T}^*=argmax_i[\delta_T(i)]$\\
+递归:
-回溯求S序列${q_T}^*=\psi_1({q^*}_{t+1}) \qquad t=T-1,T-2,...,1$\\
+\[\delta_t(j)=max_i[\delta_{i-1}(i)a_{ij}]b_j(O_t) \qquad t=2,…T \qquad j=1…N \]
+\[\qquad\psi_1(j)=argmax_i[\delta_{i-1}(i)a_{ij}] \qquad t=2,…T \qquad j=1…N \]
+终止:
+\[ P^*=max_i\delta_T(i)$ ${q_T}^*=argmax_i[\delta_T(i)] \]
+回溯求$S$序列:
+\[ {q_T}^*=\psi_1({q^*}_{t+1}) \qquad t=T-1,T-2,...,1 \]
 算法示意图如下所示：\\
 {{keynote:f_8.jpg|}}\\
-时间复杂度$O(K^2N)$\\
-空间复杂度 $O(KN)$\\
+据此可知, Viterbi算法的时间复杂度为$O(K^2N)$, 空间复杂度 $O(KN)$
-    解决学习问题
+==== 隐马尔科夫模型的学习问题 ====
 估计HMM的参数分两种情况：\\
 ）	观察序列O和状态序列Q已知，学习模型  $\lambda=(A,B,\pi)$\\
 ）	只有观察序列O已知，需要学习状态序列和模型  $\lambda=(A,B,\pi)$\\
     针对情况一：
 给定序列Q和O，则参数的似然值由下式给出\\
@@ Line 360: / Line 399: @@
 {{:keynote:qfqf23.jpg|}}\\
+<note important> Revised by Feiwei Qin(秦飞巍), <qinfeiwei@zjucadcg.cn> </note>

Applied Mathematics for Computer Science

User Tools

Site Tools

Differences

Page Tools