参考资料：周志华著《机器学习》
基础知识
在“无监督学习”(unsupervised learning)中,训练样本的标记信息是未知的,目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律,为进一步的数据分析提供基础.此类学习任务中研究最多、应用最广的是“聚类”(clustering)。聚类既能作为一个单独过程,用于找寻数据内在的分布结构，也可作为分类等其他学习任务的前驱过程
聚类算法的性能度量指标
聚类性能度量大致有两类.一类是将聚类结果与某个“参考模型”(reference model)进行比较,称为“外部指标”(external index);另一类是直接考察聚类结果而不利用任何参考模型,称为“内部指标”(internalindex)
外部指标
内部指标
距离计算
对函数 dist(·,·),若它是一个“距离度量”(distance measure),则需满足一些基本性质:
连续变量
分类变量
我们常将属性划分为“连续属性”(continuous attribute)和“离散属性”(categorical attribute),前者在定义域上有无穷多个可能的取值,后者在定义域上是有限个取值.然而,在讨论距离计算时,属性上是否定义了“序”关系更为重要.例如定义域为{1,2,3}的离散属性与连续属性的性质更接近一些能直接在属性值上计算距离:“1”与“2”比较接近、与“3”比较远,这样的属性称为“有序属性”(ordinal attribute);而定义域为{飞机,火车,轮船}这样的离散属性则不能直接在属性值上计算距离,称为“无序属性”(non-ordinalattribute).显然,闵可夫斯基距离可用于有序属性。
对无序属性可采用VDM(Value Diference Metric)[Stanfll and Waltz,1986].令 mu,a表示在属性u上取值为a的样本数,mu,a,i表示在第i个样本簇中在属性u上取值为a的样本数,k为样本数,则属性u上两个离散值a与b之间的 VDM 距离为
混合变量
非度量距离
有必要基于数据样本来确定合适的距离计算式,这可通过“距离度量学习”(distance metric learning)来实现.
聚类算法
k均值算法
是一种原型聚类算法，原型聚类亦称“基于原型的聚类”(prototype-based clustering),此类算法假设聚类结构能通过一组原型刻画,在现实聚类任务中极为常用。
迭代求解算法流程
学习向量量化
与k均值算法类似,“学习向量量化”(Learning Vector Quantization,简称 IVQ)也是试图找到一组原型向量来刻画聚类结构,但与一般聚类算法不同的是,LVQ 假设数据样本带有类别标记,学习过程利用样本的这些监督信息来辅助聚类.
算法流程
高斯混合聚类
与k均值、IVQ用原型向量来刻画聚类结构不同,高斯混合(Mixture-ofGaussian)聚类采用概率模型来表达聚类原型.
EM方法求解算法流程
密度聚类
密度聚类亦称“基于密度的聚类”(density-based clustering),此类算法假设聚类结构能通过样本分布的紧密程度确定.通常情形下,密度聚类算法从样本密度的角度来考察样本之间的可连接性,并基于可连接样本不断扩展聚类簇以获得最终的聚类结果。
算法流程
层次聚类
层次聚类(hierarchical clustering)试图在不同层次对数据集进行划分,从而形成树形的聚类结构.数据集的划分可采用“自底向上”的聚合策略,也可采用“自顶向下”的分拆策略.
AGNES 是一种采用自底向上聚合策略的层次聚类算法.它先将数据集中的每个样本看作一个初始聚类簇,然后在算法运行的每一步中找出距离最近的两个聚类簇进行合并,该过程不断重复,直至达到预设的聚类簇个数.这里的关键是如何计算聚类簇之间的距离.实际上,每个簇是一个样本集合,因此,只需采用关于集合的某种距离即可.例如,给定聚类簇Ci与Cj，可通过下面的式子来计算距离:
显然,最小距离由两个簇的最近样本决定,最大距离由两个簇的最远样本决定而平均距离则由两个簇的所有样本共同决定.当聚类簇距离由dmin、dmax或davg 计算时,AGNES 算法被相应地称为“单链接”(single-linkage)、“全链接”(complete-linkage)或“均链接”(average-linkage)算法。
算法流程
