聚类算法k-means
无监督学习: 训练数据只有特征值, 没有目标值
k-means聚类步骤
- 1、随机设置K个特征空间内的点作为初始的聚类中心
- 2、对于其他每个点计算到K个中心的距离，未知的点选择最近的一个聚类中心点作为标记类别
- 3、接着对着标记的聚类中心之后，重新计算出每个聚类的新中心点（平均值）
- 4、如果计算得出的新中心点与原中心点一样（质心不再移动），那么结束，否则重新进行第二步过程
k-means算法api
sklearn.cluster.KMeans(n_clusters=8)
- 参数:
- n_clusters:开始的聚类中心数量
- 整型，缺省值=8，生成的聚类数，即产生的质心（centroids）数。
- 方法:
- estimator.fit(x)
- estimator.predict(x)
- estimator.fit_predict(x)
- 计算聚类中心并预测每个样本属于哪个类别,相当于先调用fit(x),然后再调用predict(x)
模型评估
- 误差平方和SSE
所有样本到对应类别中心得距离的平方相加
S S E=\sum_{i=1}^{k} \sum_{p \in C_{i}}\left|p-m_{i}\right|^{2}
随着迭代, sse减少, 若质心初始值选择不好, sse只会达到一个不怎么好的局部最优解.
- 肘方法确定k值
（1）对于n个点的数据集，迭代计算k from 1 to n，每次聚类完成后计算每个点到其所属的簇中心的距离的平方和；
（2）平方和是会逐渐变小的，直到k==n时平方和为0，因为每个点都是它所在的簇中心本身。
（3）在这个平方和变化过程中，会出现一个拐点也即“肘”点，下降率突然变缓时即认为是最佳的k值。
在决定什么时候停止训练时，肘形判据同样有效，数据通常有更多的噪音，在增加分类无法带来更多回报时，我们停止增加类别。
-
轮廓系数法silhouette coefficient
越大越好
凝聚度: 样本i到同一簇内其他点不相似程度的平均值
分离度: 样本i到其他簇的平均不相似程度的最小值
\mathbf{S}=\frac{(b-a)}{\max (a, b)}
每个样本都算出一个轮廓系数[-1,1] 所有的轮廓系数取平均值(平均轮廓系数)
轮廓系数也可确定k值好坏
若s<0, 该样本可能分类错误
- CH系数(Calinski-Harabasz Index越大越好)
协方差矩阵
\mathrm{s}(\mathrm{k})=\frac{\operatorname{tr}\left(B_{k}\right)}{\operatorname{tr}\left(W_{k}\right)} \frac{m-k}{k-1}
tr为矩阵的迹, Bk为类别之间的协方差矩阵，Wk为类别内部数据的协方差矩阵;
m为训练集样本数，k为类别数。
k-means算法优化算法
k-means严重依赖初始化的k个中心点
- Canopy算法
不用指定k值 t1 t2同心圆 重复画
t1 t2长度不好确定
- K-means++
P=\frac{D(x)^{2}}{\sum_{x \in X} D(x)^{2}}
随机选一个中心点, 求其他点的P, 按P抽取第二个中心点(距离远的点被抽到的概率打), 以此类推直到抽取k个点
- 二分K-means
- 1.所有点作为一个簇
- 2.将该簇一分为二
- 3.选择能最大限度降低聚类代价函数（也就是误差平方和）的簇划分为两个簇。
- 4.以此进行下去，直到簇的数目等于用户给定的数目k为止。
- k_medoids k-中心聚类算法
与k-means相同, 只是在一个簇中, 对于每个点都计算其距离, 选距离最小的点作为新中心店
- Kernel k-means
对于同中心点两簇数据
核函数把样本映射到更高纬度空间
核函数比较难找
6 . ISODATA
不用指定k值, 设定分裂合并规则
类别数目随着聚类过程而变化:
“合并”：（当聚类结果某一类中样本数太少，或两个类间的距离太近时）
“分裂”（当聚类结果中某一类的类内方差太大，将该类进行分裂）
- Mini Batch K-means
以部分代替整体, 每次迭代抽一部分数据
适合大数据
