KMEANS INFO

有四个牧师去郊区布道，一开始牧师们随意选了几个布道点，并且把这几个布道点的情况公告给了郊区所有的村民，于是每个村民到离自己家最近的布道点去听课。听课之后，大家觉得距离太远了，于是每个牧师统计了一下自己的课上所有的村民的地址，搬到了所有地址的中心地带，并且在海报上更新了自己的布道点的位置。牧师每一次移动不可能离所有人都更近，有的人发现A牧师移动以后自己还不如去B牧师处听课更近，于是每个村民又去了离自己最近的布道点……就这样，牧师每个礼拜更新自己的位置，村民根据自己的情况选择布道点，最终稳定了下来。

• 村民牧师解释
  • 四个牧师: K(种类 ML中叫类聚中心)
  • 村民: K种样本集合
  • 牧师更改布道点: 更改类聚中心位置
  • 村民根据自己情况选择布道点: 迭代已达到稳定

KMEANS DETAILS

• 1.初始化K个样本作为初试类聚中心a = a1、a2、a3、a4、a5
• 2.针对每个样本中的xi计算到每个样本类聚中心的距离(欧氏距离)最小值，分到对应的类聚中心的类中

$$d=\sqrt{\sum _{i=0}^N(x_{1i}-x_{2i}{)}^2}$$

• 3.针对每个类别ai,重新计算它的类聚中心

$$a_j=\frac{1}{|C_i|}\sum x(xϵC_i)$$

• 4.重复上面 2 3 两步操作，直到达到某个中止条件（迭代次数、最小误差变化等）

SHORTCOMING

• K 值需要人为设定，不同 K 值得到的结果不一样 (Gap statistic)
• 对初始的簇中心敏感，不同选取方式会得到不同结果 (Kmeans++ | Kmeans II)
• 对异常值敏感 (Pretreatment)
• 不适合太离散的分类、样本类别不平衡的分类、非凸形状的分类 (核函数)
• 样本只能归为一类，不适合多分类任务 (ISODATA细分样本)

OPTIMIZATION OF KMEANS

• 手肘法(人工确定K)

当 K < 2 时，曲线急速下降；当 K > 2 时，曲线趋于平稳，通过手肘法我们认为拐点 2 为 K 的最佳值

• Gap statistic

$$d_{i{i}^{\prime }}=\Sigma (x_{ij}-x_{i^{\prime }j}{)}^2(i=1,2\dots n;j=1,2,\dots p)\to 描述与中心的距离$$

$$n_r=|C_r|\to 样本空间$$

$$W_k=\Sigma (\frac{1}{2n_r}{D}_r)\to 损失函数$$

最终公式→Gapn(k)=E∗{log(Wk)}−log(Wk)最终公式\to Gap_n(k)=E^*\{log(W_k)\}-log(W_k) 最终公式→Gapn​(k)=E∗{log(Wk​)}−log(Wk​)

E∗{log(Wk)}→howtoget?E^*\{log(W_k)\}\to how\ to\ get? E∗{log(Wk​)}→how to get?

参考论文: Estimating the number of clusters in a data set via the gap statistic

Robert Tibshirani , Guenther Walther and Trevor Hastie

Stanford University

MONTE CARLO METHOD

• 解决两类问题

一类是所求解的问题本身具有内在的随机性，借助计算机的运算能力可以直接模拟这种随机的过程

另一种类型是所求解问题可以转化为某种随机分布的特征数，比如随机事件出现的概率，或者随机变量的期望值

• 理解

假设你有一袋豆子，把豆子均匀地朝这个图形上撒，然后数这个图形之中有多少颗豆子，这个豆子的数目就是图形的面积。当你的豆子越小，撒的越多的时候，结果就越精确。借助计算机程序可以生成大量均匀分布坐标点，然后统计出图形内的点数，通过它们占总点数的比例和坐标点生成范围的面积就可以求出图形面积。

Kmeans -> Kmeans++ -> Kmeans II

Kmeans

# 获取数据 n 个 m维 的数据# 随机生成 K 个 m维 的点(where)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

Kmeans++

• 1.随机选取ai
• 2.计算数据到之前 n 个聚类中心最远的距离 , 并以一定的概率

$$\frac{D(x{)}^2}{\sum D(x{)}^2}$$

​ 选择新的中心点ai

• 3.重复步骤2

Kmeans II

• 在Kmeans++基础上 每次遍历取样k个，重复该取样过程klog(n)次，得到一个集合，然后随机选取 K个点作为类聚中心

PRETREATMENT

当样本点过于离散时的效果

• 1.预处理提前过滤掉异常值
• 2.通过一个非线性映射，将输入空间中的数据点映射到高位的特征空间中，并在新的特征空间中进行聚类。非线性映射增加了数据点线性可分的概率，从而在经典的聚类算法失效的情况下，通过引入核函数可以达到更为准确的聚类结果。

ISODATA

ISODATA (迭代自组织数据分析法)。它解决了 K 的值需要预先人为的确定这一缺点。而当遇到高维度、海量的数据集时，人们往往很难准确地估计出 K 的大小

• 当属于某个类别的样本数过少时把这个类别去除，当属于某个类别的样本数过多、分散程度较大时把这个类别分为两个子类别