[背景音乐] 翻译: RyukaSuu |审阅: 19waa Coursera Global Translator Community
最后 我们通过一些凝聚聚类的细节来总结一下本单元
一个值得讨论的问题是，
在做凝聚聚类时，我们应当做什么样的选择？
一是 在计算两点时间的距离是 应当选择什么样的
"度量方法"
另一个是 我们应当选择什么样的"链接方程" 去
计算两聚类之间的距离
对于单链接方式，这个“链接方程”就是用于计算
两数据点之间的最短距离 这两个数据点分别属于两个不同的聚类
最后 还有一个重要的问题就是
我们如果去切割树状图
一个问法是 我们应该把这条水平切割线放在哪里
但是还有一点就是 我们并不是只能做水平的切割，
我们还可以对这棵树做一些奇怪的切割。
这正是这种切割技艺派上用场的时候
经常 你必须用到许多应用相关的信息
去考虑如何去切割树状图
如果你在一些数据可视化任务里 你用到层次聚类
生成较少数量的聚类 通常是一个合适的选择
那就定义了你将怎样却切树状图
但相反 如果你要做类似于异常检测 也就是
你想检测出哪些数据点与其他数据点差异较大
那你就得想想其他办法去确定聚类的个数
同样 也是确定如何切割树状图
在这种情况下 你可以使用距离阈值
我们在上一节里介绍了同样的方法
或者你可以做一些更加复杂的东西 比如"不一致参数"
你要做的是 把任一给定"合并聚类"的高度与这一
数据点下面所有"合并聚类"的平均高度相比较
如果这一高度比平均高度高出很多
那就说明这个"合并聚类"所合并的聚类距离比较远
对比这个数据点下面其他"合并聚类"而言
所以那有可能是一个合理的切合树状图的点 并且
把那些聚类保持为不同的聚类
我们来看一个简单的图形化说明
或许我们有一些相对之间距离相当远的数据点
我们有还有一个有一些非常紧凑的数据点组成的聚类，
附近还有一个同样紧凑的聚类
如果我们仅仅根据阈值来决定如何切割树状图
你可能会把这两个紧凑的聚类划分为一个聚类
但相反 根据图示的结构 你所期待的
应该是把这两个紧凑的聚类划分为两个不同的聚类
因为这两个聚类内部的数据点之间的距离非常非常小
而这个两个红色的聚类所组成的聚类 其内部数据点之间的距离
要比单独的红色聚类内部数据点之间的距离大的多
所以这样的树状图切割就形成这样的图示状态
需要清楚的是 没有哪一种切割方法是任何情况下都正确的切割方法
然而 向我们以前说的
许多应用相关的直觉或信息会起到很重要的作用
而且很多根据经验的方法通常会用于决定如何切割树状图
层次聚类方法所的到的结果
不管所输出的聚类如何
都会对你所使用的切割方法非常敏感
使用这种方法 你所得到的结果可能会差异很大
所以你必须仔细思考一下这个方法
然而 你可以把层次聚类看做是一种
生成各种不同的聚类的方法 你可以通过变化阈值 或者
你可以利用不同的切割树状图的方法 来实现这个目标
当我们运用层次聚类方法时 我们还应当考虑到一些非常重要的有关计算效率
的问题
对于凝聚聚类 当我们需要计算聚类之间的距离时
我们必须计算任意一对数据点之间的距离
这个计算开销非常大
类似于我们在检索问题中学习的"最近邻"算法
你可以发现 凝聚聚类的brute-force算法
的时间复杂度是O(N^2 *logN) 这里N是数据点个数
在介绍“最近邻”算法的时候 我们讲了KD树和
和删减搜索空间的高效方法
在这儿 我们可以考虑用"三角形公理"
去删减一些潜在的合并动作
如果你可以做一些非常复杂的事情 实现层次聚类的最出名的算法
的时间复杂度可以达到O(N^2)
而不是O(N^2 *logN) 但是 如果N非常大的话 这个算法效率仍然不高
根据你的数据的结构特点 仍然可以考虑一些提高效率的方式
比如 "单链接"方法可能遇到的一个问题就是
"长链"问题 也就是你得到一长列的数据点 这些点之间
距离非常小 所以这些点都被合并为一个聚类
但是 如果你观察这个聚类 你会发现这个聚类里的有些点之间
的距离非常非常远。
在许多实际应用中 这种形状的聚类是很不理想的
所以 有一种方法可以帮助解决这个"长链"问题
就是重新考虑其他的"链接方程"
你可以看一个叫做"完全链接"的方法
在我们之前的方法里 我们计算的是两个聚类
数据点间的最短距离 在这个新方法里 我们计算最大距离
这样的话 如果我们看这个"长链"形聚类里最大距离
我们就不会合并生成这样的聚类
因为这个最大距离会非常大
链接方程还有另外一种可选择 是一种叫做"Ward Criterion"的方法
它考察聚类内部数据点的方差
本质上 这两种链接方程都隐含地
约束了生成聚类的形状
所以它确实能帮助解决"长链"问题 但是你又回到了
类似于"米歇尔或高斯类型反转"的问题
也就是 你首先假定一种你的聚类将要形成的具体形状
本质上 有点像去排除一些其他形状
的聚类
所以 你有几个不同的选择 而且
这些选择也有对应的隐含条件
当你确定如何完成层次聚类的时候
你应该仔细考虑。
总之 层次聚类一个非常强有力的工具
它可以完成多种"粒度"的聚类
在这个过程中 你可以得到非常有描述性的聚类结果
[背景音乐] 翻译: RyukaSuu |审阅: 19waa Coursera Global Translator Community