聚类

聚类评估算法

Silhouette算法：轮廓系数法

簇内不相似度：$a_i$样本i到同簇其它样本的平均距离

簇间不相似度：$b_i$样本到其它某簇的所有样本的平均距离

定义样本的轮廓系数：

$s(i) = \frac{b_i-a_i}{max\{a_i,b_i\}}$

$s(i) $接近1，则说明样本i聚类合理；

$s(i) $接近-1，则说明样本i更应该分类到另外的簇；

$s(i) $近似为0，则说明样本i在两个簇的边界上。

聚类算法

K-Means

算法步骤

选择初始化的 k 个样本作为初始聚类中心$a=a_1,a_2,a_3,···a_k$ ；
针对数据集中每个样本$x_i$计算它到 k 个聚类中心的距离并将其分到距离最小的聚类中心所对应的类中；
针对每个类别$a_j$，重新计算它的聚类中心 $a_j=\frac{1}{|c_i|}\sum{x}(x∈c_i)$（即属于该类的所有样本的质心)；
重复上面 2 3 两步操作，直到达到某个中止条件（迭代次数、最小误差变化等）。

获取数据 n 个 m 维的数据
随机生成 K 个 m 维的点
while(t)
    for(int i=0;i < n;i++)
        for(int j=0;j < k;j++)
            计算点 i 到类 j 的距离
    for(int i=0;i < k;i++)
        1. 找出所有属于自己这一类的所有数据点
        2. 把自己的坐标修改为这些数据点的中心点坐标
end

优点

容易理解，聚类效果不错，虽然是局部最优，但往往局部最优就够了
处理大数据集的时候，该算法可以保证较好的伸缩性
当簇近似高斯分布的时候，效果非常不错
算法复杂度低

缺点

K 值需要人为设定，不同 K 值得到的结果不一样；
对初始的簇中心敏感，不同选取方式会得到不同结果；
对异常值敏感；
样本只能归为一类，不适合多分类任务；
不适合太离散的分类、样本类别不平衡的分类、非凸形状的分类。

高斯混合模型GMM

$P(x|\theta)=\sum_{K=1}^{K}{\alpha _k\phi(x|\theta_k)}$

优化目标：似然函数$logL(\theta) = \sum_{j=1}^{N}{logP(x_j|\theta)}$

参数解释：

$x_j表示第j个观测数据$
$K是混合模型中子高斯模型的数量$
$\alpha_k是观测数据属于第k个子模型的概率$
$\phi(x|\theta_k)是第k个子模型的高斯分布密度函数，\theta_k=(\mu_k,\sigma_k^2)$

求解方法：EM——期望最大化算法（这个没怎么听懂，再听几遍）

E-step：根据当前参数，计算每个数据j来自子模型k的可能性

$\gamma_{jk}=\frac{\alpha_k\phi(x_j|\theta_k)}{\sum^{K}_{k=1}\alpha_k\phi(x_j|\theta_k)}$
M-step：计算新一轮迭代的模型参数

$\mu_k=\frac{\sum^{N}_{j}(\gamma_{jk}x_j)}{\sum^N_{j}\gamma_jk}$

$\sum_k=\frac{\sum^N_j{\gamma_jk(x_j-\mu_k)(x_j-\mu_k)^T}}{\sum^N_j\gamma_jk}$

$\alpha_k = \frac{\sum^N_{j=1}\gamma_jk}{N}$
重复计算E-step和M-step直至收敛：$||\theta_{i+1}-\theta_i||<\epsilon$

EM 算法具备收敛性，但并不保证找到全局最大值，有可能找到局部最大值。解决方法是初始化几次不同的参数进行迭代，取结果最好的那次

DBSCAN

算法流程：

1.将所有点标记为核心点、边界点或噪声点
2.删除噪声点
3.为距离在半径之内的所有核心点之间赋予一条边
4.每组连通的核心点形成一个簇
5.将每个边界点指派到一个与之关联的核心点的簇中