聚类通常是一种非监督学习方法，对大量的未标注数据集按照数据内在的相似性划分为若干个类别。比如对客户进行价值分析，根据不同客户群体制定不同的营销策略，需要准确的将客户分成"重点客户"、"潜在客户"、"一般客户"，就会用到聚类的算法。下面介绍3种常用聚类算法和1种判断曲线相似度的算法。此外还有层次聚类，密度最大值聚类等。

PS：算法只是整个数据挖掘过程中的很小一部分，而根据先验知识去选择指标，建立模型，数据预处理才是平时工作中耗时的部分

K-means++

简单介绍

K-means++是对K-means算法的升级，在初值选择时更佳合理。由于K-means聚类对初始质心的选择非常敏感，因此选择恰当的质心对算法的优劣很关键。K-means++算法在选择初始质心时，选择彼此距离尽可能远的K个点

算法过程

1、选择初值与簇的个数：

通常情况下，簇的个数是根据先验知识来选择的。

初始质心选择彼此距离尽可能远的K个点：首先随机选择一个点作为第一个初始类簇中心点（也可以根据图像自己指定），记作A；然后选择距离A点最远的那个点作为第二个初始类簇中心点，记作B；然后再选择距离A,B的最近距离最大的点作为第三个初始类簇的中心点，记为C，以此类推，直至选出K个初始类簇中心点。

解释一下C点的选择，"距离A,B的最近距离最大的点"：假设已经有了A,B两个点，用d(3,A)表示3号点到A点的距离，假设：

d(3,A)=5,d(3,B)=6，那么3号点距离A,B的最近距离是5；

d(4,A)=10,d(4,B)=20，那么4号点距离A,B的最近距离是10；

d(5,A)=2,d(5,B)=3，那么4号点距离A,B的最近距离是2；

在5,10,2中选择最大的距离是10，那么C点就是4号节点，C点是离A,B都很远的那个点。

2、k-means算法过程

a.选取k个簇的质心c1,c2...ck

b.对于每个样本xi，分别计算d(xi, ci)，将其标记为距离簇最近的类别

c.如果当前结果与上次分类结果相同，那么跳出循环。终止条件也可以换位其他条件，比如迭代次数，MSE，簇中心变化率

d.将每个簇中心更新为新分类后所有样本的均值

e.循环b,c,d过程。

适用范围

适用于类似圆形的聚类。

适用：

不适用：

---

DBSCAN

简单介绍

dbscan是基于密度的聚类，密度聚类算法通常可以把紧密相连，不断接触延伸的数据汇聚到一起。可以不指定K值。

算法过程

1、先给出若干定义

对象的ε邻域：样本在半径ε的区域。

核心对象：给定数目m，如果一个样本的ε邻域内至少包含m个样本，则称此样本为核心对象。

直接密度可达：如果p在q的ε邻域内，并且q是一个核心对象，那么就说p从对象q出发是密度可达的。

密度可达：如果存在一个对象链p1p2...pn，p1 = q，pn = p，对于1≤i≤n，p[i+1]是p[i]关于ε和m直接密度可达，那么p是从对象q出发关于ε和m密度可达的。

密度相连：如果集合中存在一个对象o，p和q是从o出发关于ε和m密度可达，那么p和q是关于ε和m密度相连。

噪声：不包含在任何簇中的样本，称为噪声。注：如果m值选的过小，那么包含过少对象的簇也可以被认为是噪声。

2、dbscan算法过程：

a.人工给定ε邻域距离和数值m，如果一个点p的ε邻域内包含多余m个对象，则创建一个p为核心对象的新簇。

b.寻找并合并核心对象直接密度可达的对象。

c.没有新点更新时，算法结束

适用范围

可以发现任何形状的聚类

---

谱聚类

简单介绍

谱聚类是求拉普拉斯矩阵的特征向量后，对特征向量的特征值进行聚类。对数据分布的适应性更强

算法过程

1、先给出若干定义

拉普拉斯矩阵：L = D - W

2、谱聚类算法过程

a、计算相似度矩阵W和度矩阵D

b、计算拉普拉斯矩阵L = D - W

c、计算L的特征值和特征向量Lu = λu，因为L是n*n的对称矩阵，所以L有n个特征值和特征向量。

d、对特征值λ从小到大排序，取前K个特征值的特征向量u1,u2...uk，组成特征向量矩阵U(n行k列)。

e、1号样本的特征认为是U矩阵的第一行u11,u12...u1k

      n号样本的特征认为是U矩阵的第一行un1,un2...unk

f、有了样本，样本也选好了特征，使用k-means将n个样本做聚类，得到K个簇。

g、这个聚类的最终结果就是谱聚类的结果。

适用范围

适用于各种距离，处理稀疏数据会比其他算法更有效

弗雷歇距离

度量点之间的距离有很多，这里介绍一种度量曲线相似度的方法，Frechet distance。

网上常见的描述方式是

Fréchet distance就是狗绳距离：主人走路径A，狗走路径B，各自走完这两条路径过程中所需要的最短狗绳长度。

下面更直白的表述一下

两条曲线L1，L2。a表示L1上的点，b表示L2上的点d(a,b)表示两点间的距离

当a在0号点时，计算d(0,1),d(0,2)...d(0,n)各个距离，记为集合s0，D0 = max(s0)

当a在1号点时，计算d(1,1),d(1,2)...d(1,n)各个距离，记为集合s1，D1 = max(s1)

以此类推得到D2,D3...Dn

frechet_distance = min(D0,D1,...,Dn)

弗雷歇距离的参考文献

https://zhuanlan.zhihu.com/p/2015996

题外话：是否能够根据曲线相似度去判断两支股票的k线趋势是否相同，从而去挑选趋势相同的股票呢？