K-Means

算法流程（密度聚类）

1）随机初始化k个组，求其中心点作为初始簇的中心点。

2）计算每个数据点到中心点的距离，数据点距离哪个中心点最近就划分到哪一类中。

3）计算每一类中中心点作为新的中心点。

4）重复，直到每一类中心在每次迭代后变化不大为止。（也可以多次随机初始化中心点，然后选择运行结果最好的一个。）

优点：收敛速度快；计算简便；可解释性强。

缺点：如何设k值；对于非凸数据集难以准确收敛；类别不平衡结果不佳；局部最优；噪声敏感。

优化：K-Medians，用中位数代替均值，减少异常值的影响；但是数据排序求中位数的过程使速度变慢。

---

DBSCAN

算法流程

1）确定密度阈值和邻域半径。从一个没有被访问过的任意数据点开始，以这个点为中心，r为半径的圆内包含的点的数量是否大于或等于minPoints，如果大于或等于minPoints则改点被标记为中心点，反之标记为噪声点。 

2）重复1的步骤，如果一个噪声点存在于某个中心点为半径的圆内，则这个点被标记为边缘点，反之仍为噪声点。

3）重复步骤1，直至所有的点都被访问过。

优点：不需要知道簇的数量；可检测任意形状簇；噪声不敏感。

缺点：需要确定距离r和minPoints；收敛时间长；不平衡数据结果不好。

---

Mean-Shift

算法流程（基于滑动窗口）

1）在未被标记的数据点中随机选择一个点作为起始中心点center；

2）找出以center为中心半径为R的区域中出现的所有数据点，认为这些点同属于一个簇。同时在该聚类中记录数据点出现的次数加1。

3）以center为中心点，落在窗口圆中的所有点和圆心都会对应的一个向量，把所有这些向量相加，最终我们只得到一个向量，就是meanshift向量。

4）移动窗口（以meanshift向量的终点为新的圆心），计算窗口内的中心点以及窗口内的密度，直到没有方向在窗口内可以容纳更多的点，即一直移动到圆内密度不再增加为止。

5）重复4）直至shift的很小，此时的中心点就是该簇的中心，这个迭代过程中的所有窗口内的点都属于该簇。

6）如果收敛时当前簇C的center与其它已经存在的簇C2中心的距离小于阈值，那么把簇合并，数据点出现次数也对应合并。

7）重复，直到所有的点都被标记为已访问。

优点：不需要提前知道簇的数量；相比K-Means来说受均值影响较小

缺点：需要确定R（R的选择可能不重要）

---

GMM

算法流程

1）选择簇的数量，随机初始化每个簇的高斯分布参数（均值和方差）。（也可以先观察数据给出一个相对精确的均值和方差。 ）

2）给定每个簇的高斯分布，计算每个数据点属于每个簇的概率。（一个点越靠近高斯分布的中心就越可能属于该簇。）

3）基于概率，计算高斯分布参数使得数据点的概率最大化，可以使用数据点概率的加权来计算这些新的参数，权重就是数据点属于该簇的概率。

4）重复迭代2和3直到在迭代中的变化不大。

优点：簇可以呈现出椭圆形而不是仅仅限制于圆形。（K-Means是GMMs的一个特殊情况，是方差在所有维度上都接近于0时簇就会呈现出圆形。）；使用概率，所以一个数据点可以属于多个簇，也就是说GMMs可以支持混合资格。

缺点：形状不是任意的；需要提前确定簇数。

优化：常先用K-Means初步计算，再输入至GMM。

---

凝聚层次聚类

算法流程

1）将每个数据点视为一个单一的簇，选择一个测量两个簇之间距离的度量标准。

2）每次迭代，将两个具有最小距离的簇合并成为一个簇。

3）重复2），直至所有数据点合并成一个簇，然后选择需要的簇。

优点：不需要知道有多少个簇 ；对距离度量标准的选择不敏感。

缺点：效率低。