主要收集介绍一些常用的基础聚类算法及python实现。
本文将要介绍的内容如下图所示：
聚类(Clustering)
概念与发展
何为聚类？
从类别的角度来说，聚类属于无监督学习任务中的一种，目的是将无标记的数据集中的样本划分为若干个不相交的子集(一般境况下)。
举个例子：你刚搬到一个新城市，发现路边有个无人看守的水果摊，各种水果混在一起像座小山。不负责任的摊主只留下一句话：”按种类摆好，价格牌在桌上”。于是乎，你决定根据水果的”颜色”和”大小”来分类：发现很多红彤彤、拳头大小的球体聚在一起（苹果）；一堆黄色弯月形的物体明显自成一群（香蕉）；某些紫色小圆球总是紧挨着出现（葡萄）。不依赖任何标签，纯粹根据相似性自主划分为几个不同簇的的任务便是聚类。
如何评判聚类任务的好坏？
聚类看似简单，那我如何可以在没有监督的条件之下进行模型算法的性能估计呢？
当然，评估一个模型不可能只依靠內源的数据集，基于内部考察 (internal index) 和基于外部“参考模型” (extrenal index) 的两类聚类性能度量 (validity index) 中均有使用。
常使用的外部指标是：
- Jaccard系数
$J = \frac{|A \cap B|}{|A \cup B|}$
衡量聚类结果与参考模型的交并比，值域[0,1]，越接近1相似性越高
- FM指数
$FM = \sqrt{\frac{TP}{TP+FP} \cdot\frac{TP}{TP+FN}}$
通过精确率和召回率的几何平均评估一致性，TP为真阳性样本对
3.Rand指数
$Rand = \frac{TP + TN}{TP + TN + FP + FN}$
计算正确分类样本对比例，考虑所有样本对的匹配程度
常使用的内部指标是：
- DB指数 (DBI)
$DBI = \frac{1}{k} \sum_{i=1}^k \max_{j\neq i} \left( \frac{s_i + s_j}{d(c_i,c_j)} \right)$
簇内平均距离s越小且簇中心距离d越大时指标越优。
- Dunn指数
$Dunn = \min_{i<j} \left( \frac{d(i,j)}{\max_l diam(l)} \right)$
簇间最小距离与最大簇内直径的比值，值越大表示簇间分离度越好。
”距离“这个概念如何在聚类中玩出花的？
公理化定义（需满足4个条件）
首先给出幼儿园老师就告诉我们的距离的要求：
非负性：$d(x,y) \geq 0$
同一性：$d(x,y)=0\iff x=y$
对称性：$d(x,y)=d(y,x)$
三角不等式：$d(x,z) \leq d(x,y)+d(y,z)$
常见距离度量
对于n维空间的点$x=(x_1,x_2,…,x_n)$和$y=(y_1,y_2,…,y_n)$，常用的距离度量有：
-Minkowski距离，闵可夫斯基距离的核心在于它提供了一种在多维空间中测量两点间距离的方法。它的特别之处在于，通过一个参数p，可以适应不同的问题空间和数据特征。通常定义如下：
$d(x,y) = (\sum_{i=1}^n |x_i - y_i|^p)^{1/p}$
-当 $p=1$时为曼哈顿距离，曼哈顿距离是标量空间中两点间各维度差的绝对值之和。在二维空间中，曼哈顿距离可以理解为从一个点到另一个点只能沿着水平或垂直方向行走的最小距离。通常用定义如下：
$d(x,y) = \sum_{i=1}^n |x_i - y_i|$
-当 $p=2$时为欧氏距离，欧氏距离是标量空间中两点间各维度差的平方之和的平方根。在二维空间中，欧氏距离可以理解为从一个点到另一个点的直线距离。通常定义如下：
$d(x,y) = \sqrt{\sum_{i=1}^n (x_i - y_i)^2}$
-当 $p=\infty$时为切比雪夫距离，二个点之间的距离定义是其各坐标数值差绝对值的最大值。
通常定义如下：
$d(x,y) = \max_{i=1\dots n} |x_i - y_i|$
