周志华《机器学习—西瓜书》九九、聚类以下是按顺序整理的内容1、聚类Clustering无监督学习中研究最多、应用最广的任务。目标将数据样本划分为若干不相交的“簇”。作用单独过程探寻数据内在的分布结构前驱过程辅助分类等其他学习任务。2、 聚类的性能度量亦称为聚类“有效性指标”核心思路簇内相似度高、簇间相似度低。有效性指标分类外部指标将聚类结果与“参考模型”比较如Jaccard系数、FM指数、Rand指数内部指标直接考察聚类结果如DB指数、Dunn指数。3、 距离计算常用形式距离度量的基本性质非负性dist(xi,xj)≥0\text{dist}(\boldsymbol{x}_i, \boldsymbol{x}_j) \geq 0dist(xi,xj)≥0同一性dist(xi,xj)0 ⟺ xixj\text{dist}(\boldsymbol{x}_i, \boldsymbol{x}_j) 0 \iff \boldsymbol{x}_i \boldsymbol{x}_jdist(xi,xj)0⟺xixj对称性dist(xi,xj)dist(xj,xi)\text{dist}(\boldsymbol{x}_i, \boldsymbol{x}_j) \text{dist}(\boldsymbol{x}_j, \boldsymbol{x}_i)dist(xi,xj)dist(xj,xi)直递性dist(xi,xj)≤dist(xi,xk)dist(xk,xj)\text{dist}(\boldsymbol{x}_i, \boldsymbol{x}_j) \leq \text{dist}(\boldsymbol{x}_i, \boldsymbol{x}_k) \text{dist}(\boldsymbol{x}_k, \boldsymbol{x}_j)dist(xi,xj)≤dist(xi,xk)dist(xk,xj)。常用距离闵可夫斯基距离distmk(xi,xj)(∑u1n∣xiu−xju∣p)1p\text{dist}_{\text{mk}}(\boldsymbol{x}_i, \boldsymbol{x}_j) \left( \sum_{u1}^n |x_{iu} - x_{ju}|^p \right)^{\frac{1}{p}}distmk(xi,xj)(∑u1n∣xiu−xju∣p)p1p2p2p2欧氏距离p1p1p1曼哈顿距离。特殊属性的距离计算无序属性用VDMValue Difference MetricVDMp(a,b)∑i1k∣mu,a,imu,a−mu,b,imu,b∣p VDM_p(a, b) \sum_{i1}^k \left| \frac{m_{u,a,i}}{m_{u,a}} - \frac{m_{u,b,i}}{m_{u,b}} \right|^pVDMp(a,b)i1∑kmu,amu,a,i−mu,bmu,b,ipmu,am_{u,a}mu,a是属性uuu取aaa的样本数mu,a,im_{u,a,i}mu,a,i是簇iii中属性uuu取aaa的样本数k为样本簇数则属性u上两个离散值 a 与 b 之间的VDM距离为上述公式混合属性用MinkovDM结合闵可夫斯基距离与VDM可以证明满足距离公式的四个基本性质MinkovDMp(xi,xj)(∑u1nc∣xiu−xju∣p∑unc1nVDMp(xiu,xju))1p \text{MinkovDM}_p(\boldsymbol{x}_i, \boldsymbol{x}_j) \left( \sum_{u1}^{n_c} |x_{iu} - x_{ju}|^p \sum_{un_c1}^n VDM_p(x_{iu}, x_{ju}) \right)^{\frac{1}{p}}MinkovDMp(xi,xj)(u1∑nc∣xiu−xju∣punc1∑nVDMp(xiu,xju))p14、聚类方法概述聚类的核心认知聚类的“好坏”无绝对标准取决于用户的需求即聚类的“标准”由任务场景决定。聚类是新算法出现最多的领域之一总能通过新的“标准”拓展算法边界。对于聚类先确定自己的标准再选择算法故事一则聚类的故事老师拿来苹果和梨让小朋友分成两份。小明把大苹果大梨放一起小个头的放一起老师点头恩体量感。小芳把红苹果挑出来剩下的放一起老师点头颜色感。小武的结果不明白。小武掏出眼镜最新款能看到水果里有几个籽左边这堆单数右边双数。老师很高兴新的聚类算法诞生了。聚类也许是机器学习中中“新算法”出现最多、最快的领域总能找到一个新的“标准”使以往算法对它无能为力常见聚类方法原型聚类假设聚类结构由一组“原型”刻画过程初始化原型→迭代更新代表k均值聚类、LVQ、高斯混合聚类。密度聚类假设聚类由样本分布的紧密程度决定过程基于样本密度扩展簇代表DBSCAN、OPTICS、DENCLUE。层次聚类假设产生不同粒度的树形聚类结构过程分层划分数据集代表AGNES自底向上、DIANA自顶向下。
