前言

“最近在学习层次聚类的算法的过程中发现算法中某一步存在疑问, 查阅相关资料, 原来还是自己读书少, 只知其一不知其二, 找到原因之后记录于此”

问题

今天在看以前从网上抄的层次聚类代码的时候, 发现如果距离函数选用最小距离, 层次聚类的结果似乎不是稳定的.

层次聚类的原理就是找到最近的两个簇 $C_i$ , $C_j$ , 将簇 $C_j$ 的类别设置为和簇 $C_i$ 一致, 然后删除其中一个簇, 但是为什么是删除那个较大的呢(或者为什么删除其中那一个而不是另一个呢), 而且删除不同的数对接下来的计算是有影响的:

考虑从 (1, 2, 4, 8, 14) 中选出两类.如果删除较小的,最后的结果就是(1, 2, 4, 8; 14),删除较大的最后的结果就是(1, 2, 4; 8, 14).

关键

问题的关键在于距离函数, 在计算同一样本空间中的集合 $X$ 和集合 $Z$ (而不是单个点)之间的距离的时候不应使用欧氏距离, 而应当使用豪斯多夫距离(Hausdorff distance)计算:

$$ dist_H (X , Z) = \max (dist_h (X , Z) , dist_h (Z , X)) $$

其中

$$ dist_h ( X , Z) = \max_{x \in X} \min_{z \in Z} |x - z|_2 $$

其他

在看书或者是查阅资料的时候, 不能想当然, 并且看书一定要看全看仔细, 对于每个细节都要好好推敲清楚.

顺便说一句, 在 hexo 中的 markdown 会把 _ 转义, 因此在写公式的时候要注意用 \_ 替代, *, \ 同理. (17.08.28更新: 已经将markdown的渲染方式更改为hexo-render-pandoc, 除了公式中本身需要转义表达的符号, 例如 {, 其他的特殊符号不再需要转义)

还有在 markdown 表格中如果要输入 | 符号, 可以使用 |, 也就是 Vertical bar 的 HTML 实体替代, 不要忘记分号呦~

主要参考文献:

周志华. 机器学习 : = Machine learning[M]. 清华大学出版社, 2016.