聚类
1.聚类
定义
聚类(Clustering)是按照某个特定标准(如距离)把一个数据集分割成不同的类或簇，使得同一个簇内的数据对象的相似性尽可能大，同时不在同一个簇中的数据对象的差异性也尽可能地大。也即聚类后同一类的数据尽可能聚集到一起，不同类数据尽量分离。
聚类和分类的区别
- 聚类(Clustering)：是指把相似的数据划分到一起，具体划分的时候并
不关心这一类的标签，目标就是把相似的数据聚合到一起，聚类是一种无监督学习(Unsupervised Learning)方法。 - 分类(Classification)：是把不同的数据划分开，其过程是
通过训练数据集获得一个分类器，再通过分类器去预测未知数据，分类是一种监督学习(Supervised Learning)方法。
聚类的一般过程
- 数据准备：特征标准化和降维
- 特征选择：从最初的特征中选择最有效的特征，并将其存储在向量中
- 特征提取：通过对选择的特征进行转换形成新的突出特征
- 聚类：基于某种距离函数进行相似度度量，获取簇
- 聚类结果评估：分析聚类结果，如
距离误差和(SSE)等
数据对象间的相似度度量
相似性度量的准则可以参考欧式距离与曼哈顿距离。
cluster之间的相似度度量
除了需要衡量对象之间的距离之外，有些聚类算法（如层次聚类）还需要衡量cluster之间的距离 。
Single-link：定义两个cluster之间的距离为两个cluster之间距离最近的两个点之间的距离，这种方法会在聚类的过程中产生链式效应，即有可能会出现非常大的cluster。
Complete-link定义的是两个cluster之间的距离为两个cluster之间距离最远的两个点之间的距离，这种方法可以避免链式效应,对异常样本点（不符合数据集的整体分布的噪声点）却非常敏感，容易产生不合理的聚类
UPGMA正好是Single-link和Complete-link方法的折中，他定义两个cluster之间的距离为两个cluster之间所有点距离的平均值
WPGMA方法计算的是两个 cluster 之间两个对象之间的距离的加权平均值，加权的目的是为了使两个 cluster 对距离的计算的影响在同一层次上，而不受 cluster 大小的影响，具体公式和采用的权重方案有关。
2.数据聚类方法
数据聚类方法主要可以分为划分式聚类方法(Partition-based Methods)、基于密度的聚类方法(Density-based methods)、层次化聚类方法(Hierarchical Methods)等。
划分式聚类方法
划分式聚类方法需要事先指定簇类的数目或者聚类中心，通过反复迭代，直至最后达到簇内的点足够近，簇间的点足够远的目标。经典的划分式聚类方法有k-means及其变体k-means++、bi-kmeans、kernel k-means等。
k-means算法
经典的k-means算法的流程如下：
1.创建K个点作为初始质心（通常是随机选择）
2.当任意一个点的簇分配结果发生改变时
1.对数据集中的每个数据点
1.对每个质心
1.计算质心与数据点之间的距离
2.将数据点分配到距其最近的簇
2.对每个簇，计算簇中所有点的均值并将均值作为质心
下左图是原始数据集，通过观察发现大致可以分为4类，所以取(K=4)，测试数据效果如下右图所示。
度量标准
k-means算法以距离作为数据对象间相似性度量的标准，通常采用欧氏距离来计算数据对象间的距离。
其中D表示数据对象的属性个数。
更新方式
k-means算法聚类过程中，每次迭代，对应的类簇中心需要重新计算（更新）：对应类簇中所有数据对象的均值，即为更新后该类簇的类簇中心。定义第(k)个类簇的类簇中心为 (Center_k)，则类簇中心更新方式如下：
其中(C_k)表示第k个类簇，(|C_k|)表示第k个类簇中数据对象的个数，这里的sum是指类簇(C _k)中所有元素在每列属性上的和，因此(Center_k)也是一个含有D个属性的向量：(Center_k=(Center_{k,1},Center_{k,2},...,Center_{k,D}))
迭代结束条件
k-means算法需要不断地迭代来重新划分类簇，并更新类簇中心，那么迭代终止的条件是什么呢？一般情况，有两种方法来终止迭代：一种方法是设定迭代次数 T，当到达第T次迭代，则终止迭代，此时所得类簇即为最终聚类结果；另一种方法是采用误差平方和准则函数，函数模型如下：
其中，K表示类簇的个数。当两次迭代(J)的差值小于某一阈值，即(Delta J<delta)时则终止迭代。
k-means算法思想可描述为：
1.首先初始化K个类簇中心
2.然后计算各个数据对象到聚类中心的距离，把数据对象划分至距离其最近的聚类中心所在类簇中
3.接着根据所得类簇，更新类簇中心
4.然后继续计算各个数据对象到聚类中心的距离，把数据对象划分至距离其最近的聚类中心所在类簇中
5.一直迭代，直到达到最大迭代次数T，或者两次迭代J的差值小于某一阈值时，迭代终止，得到最终聚类结果
算法缺点：
- 需要用户事先指定类簇个数K
- 聚类结果对初始类簇中心的选取较为敏感
- 容易陷入局部最优
- 只能发现球型类簇
代码
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs # 导入产生模拟数据的方法
from sklearn.cluster import KMeans
# 1. 产生模拟数据
k = 5
X, Y = make_blobs(n_samples=1000, n_features=2, centers=k, random_state=1)
# 2. 模型构建
km = KMeans(n_clusters=k, init='k-means++', max_iter=30)
km.fit(X)
# 获取簇心
centroids = km.cluster_centers_
# 获取归集后的样本所属簇对应值
y_kmean = km.predict(X)
# 呈现未归集前的数据
plt.scatter(X[:, 0], X[:, 1], s=50)
plt.yticks(())
plt.show()
plt.scatter(X[:, 0], X[:, 1], c=y_kmean, s=50, cmap='viridis')
plt.scatter(centroids[:, 0], centroids[:, 1], c='black', s=100, alpha=0.5)
plt.show()
make_blobs函数
功能：生成各向同性的高斯点以进行聚类。
参数：
n_samples：int或数组类，可选参数（默认值= 100）
如果为int，则为簇之间平均分配的点总数。
如果是数组，则序列中的每个元素表示每个簇的样本数。
n_features：int，可选（默认值= 2）
每个样本的特征数量。
centers：int或形状数组[n_centers，n_features]，可选（默认= None）
要生成的中心数或固定的中心位置。
如果n_samples是一个int且center为None，则将生成3个中心。
如果n_samples是数组类，则中心必须为None或长度等于n_samples长度的数组。
cluster_std: 浮点数或浮点数序列，可选（默认值为1.0）
聚类的标准偏差。
center_box: 一对浮点数（最小，最大），可选（默认=（-10.0，10.0））
随机生成中心时每个聚类中心的边界框。
shuffle：布尔值，可选（默认= True）
样本洗牌
random_state：int，RandomState实例或无（默认）
确定用于创建数据集的随机数生成。 为多个函数调用传递可重复输出的int值。
sklearn.datasets.make_blobs(n_samples=100, n_features=2, centers=None, cluster_std=1.0, center_box=(-10.0, 10.0), shuffle=True, random_state=None)
k-means++算法
k-means++算法只是优化了k-means算法中的初始质心的选取。
聚类中心选取方法：
- 从输入的数据点集合中随机选择
一个点作为第一个聚类中心 - 对于数据集中的每一个点x，计算它与最近聚类中心(指已选择的聚类中心)的距离D(x)
- 选择一个新的数据点作为新的聚类中心，选择的原则是：
D(x)较大的点，被选取作为聚类中心的概率较大 - 重复2和3直到k个聚类中心被选出来
- 利用这k个初始的聚类中心来运行标准的k-means算法
关键第三步如何将D(x)反映到点被选择的概率上,算法如下：
- 先从我们的数据库随机挑个随机点当
种子点 - 对于每个点，我们都计算其和最近的一个
种子点的距离D(x)并保存在一个数组里，然后把这些距离加起来得到Sum(D(x))。 - 然后，再取一个随机值，用权重的方式来取计算下一个
种子点。这个算法的实现是，先取一个能落在Sum(D(x))中的随机值Random，然后用Random -= D(x)，直到其<=0，此时的点就是下一个种子点。- 这个Random 可以这么取： Random = Sum(D(x)) * 0至1之间的一个小数
- 之所以取一个能落在Sum(D(x))中是值是因为，Random是随机的，那么他有更大的机率落在D(x)值较大的区域里。如下图，Random有更大的机率落在D(x3)中。
- Random -= D(x) 的意义在于找出当前Random到底落在了哪个区间。
从上图可以看出，假设Random落在D(x3)这个区间内，然后用Random -= D(x),直到其<=0，此时找到的点就是D(x3)，就是这步的中心点。
重复2和3直到k个聚类中心被选出来
利用这k个初始的聚类中心来运行标准的k-means算法。
缺点：
由于聚类中心点选择过程中的内在有序性，在扩展方面存在着性能方面的问题(第k个聚类中心点的选择依赖前k-1个聚类中心点的值)。
bi-kmeans算法
一种度量聚类效果的指标是SSE(Sum of Squared Error)，他表示聚类后的簇离该簇的聚类中心的平方和，SSE越小，表示聚类效果越好。 bi-kmeans是针对kmeans算法会陷入局部最优的缺陷进行的改进算法。该算法基于SSE最小化的原理，首先将所有的数据点视为一个簇，然后将该簇一分为二，之后选择其中一个簇继续进行划分，选择哪一个簇进行划分取决于对其划分是否能最大程度的降低SSE的值。
算法流程：
首先将所有点视为一个簇，当簇的个数小于k时，对每一个簇计算总误差，并在给定的簇上进行k-means聚类（k=2），计算将该簇一分为二后的总误差，选取使得误差最小的那个簇进行划分操作。
3.基于密度的方法
k-means算法对于凸性数据具有良好的效果，能够根据距离来讲数据分为球状类的簇，但对于非凸形状的数据点，就无能为力了，当k-means算法在环形数据的聚类时，我们看看会发生什么情况。
从上图可以看到，kmeans聚类产生了错误的结果，这个时候就需要用到基于密度的聚类方法了，该方法需要定义两个参数(varepsilon、M)，分别表示密度的邻域半径和邻域密度阈值。DBSCAN就是其中的典型。
DBSCAN算法
已知集合(X={x^{(1)},x^{(2)},...,x^{(n)}}),定义
(varepsilon)领域：(N_{varepsilon}(x)={yin X|d(x,y)<varepsilon)})
密度(x):( ho(x)=|N_{epsilon}(x)|)
核心点：设(xin X)，若( ho(x)geq M)，则x称为X的核心点，记X中所有核心点构成的集合为(X_c)，记所有非核心点构成的集合为(X_{nc})
边界点：若(xin X_{nc})，且(exist yin X)，满足(yin N_{varepsilon}(x)cap X_c)，即x的(varepsilon)领域中存在核心点，则称x为X的边界点，记X中所有的边界点构成的集合为(X_{bd})。
此外，边界点也可以这么定义：若(xin X_{nc})，且(x)落在某个核心点的(varepsilon)领域内，则称x为X的一个边界点，一个边界点可能同时落入一个或多个核心点的(varepsilon)邻域。
噪声点：若x满足(xin X,x otin X_c且x otin X_{bd})，则x为噪声点。
如图，M=3，则A为核心点，B、C为边界点，N为噪声点。
算法流程：
效果：
当设置不同的(varepsilon)时，会产生不同的结果，如下图所示
当设置不同的M时，会产生不同的结果，如下图所示
参考：https://zhuanlan.zhihu.com/p/104355127
https://www.cnblogs.com/nocml/p/5150756.html