周志华《机器学习》课后习题(第九章):聚类

简介: 周志华《机器学习》课后习题(第九章):聚类

9.1 试证明 : image.png时,闵可夫斯基距离满足距离度量的四条基本性质; image.png时,闵可夫斯基距离不满足直递性,但满足非负性、同一性、对称性;P 趋向无穷大时,闵可夫斯基距离等于对应分量的最大绝对距离,即


image.png

答:

非负性、同一性、对称性很显然,关键是直递性了,关于直递性就是闵可夫斯基不等式的证明,具体参考:

https://zh.wikipedia.org/zh-hans/%E9%97%B5%E5%8F%AF%E5%A4%AB%E6%96%AF%E5%9F%BA%E4%B8%8D%E7%AD%89%E5%BC%8F

image.png

image.png


9.3 试析 k 均值算法能否找到最小化式 (9.24) 的最优解.


答:

不能,因为 k 均值本身是 NP 问题,且 9.24 是非凸的(具体证明不太懂.),容易陷入局部最优是 k 均值的一个缺点吧,所以在使用 k 均值时常常多次随机初始化中心点,然后挑选结果最好的一个。


9.4 试编程实现 k 均值算法,设置三组不同的 k 值、三组不同初始中心点,在西瓜数据集 4.0 上进行实验比较,并讨论什么样的初始中心有利于取得好结果.


答:

代码在:

https://github.com/han1057578619/MachineLearning_Zhouzhihua_ProblemSets/tree/master/ch9--%E8%81%9A%E7%B1%BB

暂时先不分析初始化点和结果了。


9.5 基于 DBSCAN 的概念定义,若 x 为核心对象,由 x 密度可达的所有样本构成的集合为 X. 试证明 :X 满足连接性 (9.39)与最大性 (9.40).

答:


image.png


9.6 试析 AGNES 算法使用最小距离和最大距离的区别.


答:

个人理解,不一定正确。使用最小距离合并聚类簇时,最终聚类结果趋于不同类别之间的“空隙”会更大;而最大距离约等于最小距离加上两个类别的离散程度,这里离散程度可理解为方差,方差越大,两个类别的最大距离越大,所以使用最大距离时,会尽量使得类别的方差尽量小,最终聚类结果也趋于类内更集中。

其实类似于线性判别分析中类内方差尽量小,类间距离尽量大。


9.7 聚类结果中若每个簇都有一个凸包(包含簇样本的凸多面体) ,且这些凸包不相交,则称为凸聚类.试析本章介绍的哪些聚类算法只能产生凸聚类,哪些能产生非凸聚类.


答:

若在一个簇的凸包之内,有其他簇的样本,就说明凸包相交。

  • 原型聚类:输出线性分类边界的聚类算法显然都是凸聚类,这样的算法有:K均值,LVQ;而曲线分类边界的也显然是非凸聚类,高斯混合聚类,在簇间方差不同时,其决策边界为弧线,所以高混合聚类为非凸聚类;
  • 密度聚类:DBSCAN,如下图情况,显然当领域参数符合一定条件时,会生成两个簇,其中外簇会包括内簇,所以DBSCAN显然也是非凸聚类;

image.png

  • 层次聚类:AGENS,这个暂时没想明白怎么分析。从书中给出的示例,是凸聚类。


9.8 试设计一个聚类性能度量指标,并与 9.2 节中的指标比较.


答:

参考线性判别分析的优化目标:同类协方差尽量小,异类中心之间距离尽量大。


9.9* 试设计一个能用于混合属性的非度量距离.


答:

image.png

这里的计算其实很简单,就是把连续属性归一化;而离散属性有序时则归一化话再按照连续属性处理,无序时则相等为1,不等为0.

相关文章
|
2月前
|
机器学习/深度学习 数据可视化 算法
机器学习第12天:聚类
机器学习第12天:聚类
|
1月前
|
机器学习/深度学习 数据挖掘
机器学习之聚类——模糊聚类FCM
机器学习之聚类——模糊聚类FCM
28 4
|
1月前
|
机器学习/深度学习 算法 搜索推荐
机器学习中的聚类
**文章摘要:** 本文介绍了聚类算法的基本概念、应用、实现流程和评估方法。聚类是一种无监督学习技术,用于将数据分为相似的组,如K-means、层次聚类、DBSCAN和谱聚类。K-means算法通过迭代优化质心,将数据点分配到最近的簇,直至质心不再变化。模型评估包括误差平方和(SSE)、肘部方法(确定最佳簇数)和轮廓系数法(Silhouette Coefficient),以量化聚类的紧密度和分离度。应用场景涵盖用户画像、广告推荐和图像分割等。在Python的sklearn库中,可以使用KMeans API进行聚类操作。
|
1月前
|
机器学习/深度学习 算法 数据挖掘
机器学习——DBSCAN 聚类算法
【6月更文挑战第8天】DBSCAN是一种基于密度的无监督聚类算法,能处理不规则形状的簇和噪声数据,无需预设簇数量。其优点包括自动发现簇结构和对噪声的鲁棒性。示例代码展示了其基本用法。然而,DBSCAN对参数选择敏感,计算效率受大规模数据影响。为改善这些问题,研究方向包括参数自适应和并行化实现。DBSCAN在图像分析、数据分析等领域有广泛应用,通过持续改进,将在未来保持重要地位。
45 2
|
26天前
|
机器学习/深度学习 分布式计算 算法
在机器学习项目中,选择算法涉及问题类型识别(如回归、分类、聚类、强化学习)
【6月更文挑战第28天】在机器学习项目中,选择算法涉及问题类型识别(如回归、分类、聚类、强化学习)、数据规模与特性(大数据可能适合分布式算法或深度学习)、性能需求(准确性、速度、可解释性)、资源限制(计算与内存)、领域知识应用以及实验验证(交叉验证、模型比较)。迭代过程包括数据探索、模型构建、评估和优化,结合业务需求进行决策。
29 0
|
27天前
|
机器学习/深度学习 算法 数据可视化
技术心得记录:机器学习笔记之聚类算法层次聚类HierarchicalClustering
技术心得记录:机器学习笔记之聚类算法层次聚类HierarchicalClustering
26 0
|
1月前
|
机器学习/深度学习 算法 搜索推荐
机器学习聚类算法
聚类算法是无监督学习技术,用于发现数据集中的自然群体,如用户画像、广告推荐等。常见的聚类算法包括K-Means,它基于距离分配样本至簇,适合球形分布;层次聚类则通过合并或分裂形成簇,能发现任意形状的簇;DBSCAN依据密度来聚类,对噪声鲁棒。KMeans API中`sklearn.cluster.KMeans(n_clusters=8)`用于指定簇的数量。评估聚类效果可使用轮廓系数、SSE等指标,Elbow方法帮助选择合适的K值。
|
1月前
|
机器学习/深度学习 算法 数据挖掘
机器学习之聚类——MeanShift算法和图像矢量量化
机器学习之聚类——MeanShift算法和图像矢量量化
23 0
|
1月前
|
机器学习/深度学习 算法 数据挖掘
机器学习之聚类——从教授的等式到凸聚类
机器学习之聚类——从教授的等式到凸聚类
20 0
|
1月前
|
机器学习/深度学习 存储 算法
机器学习之聚类——双聚类简介及简单案例
机器学习之聚类——双聚类简介及简单案例
11 0