聚类--《Programing Collective Intelligence》读书笔记

聚类

聚类就是根据对象的相似度将对象归类。相似度的计算可以参考（相似度评价）.

分级聚类（P33）

此方法的计算过程如下：

1. 选取两两距离（相似度）较小的元素进行合
2. 计算组合元素的位置，组合出来的组合元素的位置在组合前的元素的两点之间。
3. 判断是否所有的元素都存在分组，若否，则重复执行1.

缺点：复杂度极高，每次迭代都要遍历所有的对象，并计算两两的距离值。复杂度O(n^2)

可视化形式：分级聚类的树状图（P34）

采用二叉树的方法，每次两个对象合并为一个对象，则新对象是两个对象的父亲节点。算法执行完成后，所有的对象在构成一颗二叉树。 二叉树上，两个顶点间的距离能够判断相似度的大小。

K-Means聚类（P42）

K-Means，K是将对象集合分成K份。 迭代过程如下：

1. 空间上随机选取K个点，作为中心点。
2. 遍历所有对象，确定每个对象与哪个中心点最接近，则将其归类为最近的中心点的对象。
3. 根据中心点的归类，确定这一归类下所有对象的中心位置，新的中心点位置。
4. 判断所有中心点是否有移动，若有，则回到2过程。

优点：相比于分级聚类来说，此方法的时间复杂度较低，为O(nK)。其中K << n。

多维缩放（P49）

由于对象与对象间的评价是多维的，将对象根据相似度绘制在平面图上，以二维形式展现数据，使人们能够很直观的了解对象之间联系的紧密程度。

平面图上，相似度越大的对象，靠的越近。之前将对象随机分布（或是按照一定规律分布）。迭代过程中，若是远了，就近一点 ，若是近了，就远一点。通过不断迭代调整顶点间的距离，使得所有对象间的距离都趋近于合适。即：总体误差较小。