聚类分析（2）：其他问题与算法

一、数据、簇、聚类算法

（1）数据特性

可能影响聚类分析的因素：
高维性、规模、稀疏性、噪声和离群点、尺度

二、基于原型的聚类

（1）模糊聚类

1、模糊集合

模糊集合论允许对象以 0 和 1 之间的某个隶属度隶属于一个集合。

2、模糊簇

xi 为数据点集合，Ci 为模糊子集簇。

xi 的权值

给定xi的所有权值之和为 1：
$$ \sum_{j=1}^{k}w_{ij}=1$$

Ci 的限制

每个 Ci 以非零权值至少包含一个点，但不以权值1包含所有点：
$$ 0< \sum_{i=1}^{m}w_{ij} < m$$

3、模糊 c 均值

模糊 c 均值算法（FCM算法）

算法：

目标函数：

计算SSE（误差平方和）：
$$ SSE(C_{1},C_{2},…,C_{k})=\sum_{j=1}^{k}\sum_{i=1}^{m}w_{ij}^{p}dist(x_{i},c_{j})^{2}$$

cj 是第 j 个簇的质心。

初始化：

随机初始化，但是限定求和为1.

计算质心：

$$ c_{j}=\frac{\sum_{i=1}^{m}w_{ij}^{p}x_{i}}{\sum_{i=1}^{m}w_{ij}^{p}}$$

p为模糊权重，p=1时候，很想传统k均值，p越大，划分越模糊。一般选取p=2。

更新模糊伪划分

当使用p时候，最小化SSE，可以推导出：
$$ w_{ij}=\frac{(\frac{1}{dist(x_{i},c_{j})^{2}})^{\frac{1}{p-1}}}{\sum_{q=1}^{k}(\frac{1}{dist(x_{i},c_{q})^{2}})^{\frac{1}{p-1}}}$$

当使用p=2的时候，公式得到简化：
$$ w_{ij}=\frac{\frac{1}{dist(x_{i},c_{j})^{2}}}{\sum_{q=1}^{k}\frac{1}{dist(x_{i},c_{q})^{2}}}$$

下面显示了一个模糊聚类的例子：

4、优点与缺点

与K均值相同的有点和缺点。

（2）使用混合模型聚类

1、混合模型

混合模型将数据看作从不同的概率分布得到的观测值集合。其数据产生过程为，给定几个分布（通常类型相同，参数不同）随机的选择一个分布并由它产生一个对象，重复该过程m次。

假定有 K 个分布和 m 个对象{x1,x2，…,xm}，\Theta 是参数的集合，则：
$$ prob(x_{i}|\theta _{j})$$
是第 i 个对象来自第 j 个分布的概率。
由于权值受限，其和为 1 。对于对象 x 的概率由公式给出：
$$ prob(x|\Theta)=\sum_{j=1}^{K}w_{j}p_{j}(x|\theta_{j})$$

如果对象以独立的方式产生，则对象集的概率是每个对象 xi 的概率的乘积。
$$ prob(\chi |\Theta)=\prod_{i=1}^{m}prob(x_{i}|\Theta)=\prod_{i=1}^{m}\sum_{j=1}^{K}w_{j}p_{j}(x_{i}|\theta_{j})$$

混合高斯分布

假定有两个高斯分布，有相同的标准差 2，均值分别为 -4 和 4 。还假定每个分布以等概率选取，即为 w1=w2=0.5。公式为：
$$ prob(x|\Theta)=\frac{1}{2\sqrt{2\pi}}e^{-\frac{(x+4)^{2}}{8}}+\frac{1}{2\sqrt{2\pi}}e^{-\frac{(x-4)^{2}}{8}}$$

则该模型产生的 20000 个点的直方图：