聚类的定义和2个基本问题

无监督学习中，训练样本的信息是未知的，目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律，为进一步的数据分析提供基础。

应用最广也是研究最多的是-----聚类

聚类试图将数据集中的样本划分为若干个通常是不相交的子集，每个子集称为一个“簇”。聚类过程只能形成簇结构，而簇对应的概念语义需要由使用者来把握和命名。聚类既可以作为一个单独过程用来寻找数据内部的分布结构，也可以作为分类等其他学习任务的前驱过程。

聚类算法涉及的两个基本问题：性能度量和距离计算。

性能度量：

聚类希望结果表现簇内相似度高并且簇间相似度低。聚类性能度量分两类：一类是将聚类结果与某个“参考模型”进行比较，称为“外部指标”；另一类是直接考察聚类结果二不利用任何参考模型，称为内部指标。

外部指标：JC（Jaccard系数），FMI（FM指数），RI（Rand指数）。外部指标的结果值均在[0,1]区间，值越大越好。

内部指标：DBI（DB指数），DI（Dumn指数）。内部指标DBI的值越小越好，而DI则越大越好。

距离计算：

距离度量的基本性质：若函数dis(·,·)是一个距离度量（distance measure），那么（1）非负性：dist(xi,xj)>=0（2）同一性：dist(xi,xj)=0当且仅当xi=xj（3）对称性：dist(xi,xj)=dist(xj,xi)（4）直递性：dist(xi,xj)<=dist(xi,xk)+dist(xk,xj)

通常我们是基于某种形式的距离来定义“相似度度量”，距离越大相似度越小，距离越小越相似。但是用于相似度度量的距离未必一定要满足距离度量的所有基本性质，尤其是直递性。如人马例子：

在讨论距离度量的时候，属性划分“有序属性”和“无序属性”比“连续属性”和“离散属性”更加重要！例如定义域为{1，2，3}这样的属性称为有序属性能直接在属性值上计算距离，例如定义域{飞机，火车，轮船}这样的属性称为无序属性则不能直接在属性值上计算距离。

用于有序属性的常用的是“闵可夫斯基距离”，用于无序属性常用的是VDM距离。

闵可夫斯基距离：,对于p>=1时，满足距离度量的基本性质。

当p=1时，就是曼哈顿距离：

当p=2时，就是欧氏距离：