聚类(番外篇)——贪心算法
在之前对层次聚类的介绍中提到了贪心算法。在这里我也简单的谈谈贪心算法是什么吧。转载此文请注明出处：http://blog.csdn.net/jiang1st2010/article/details/8432627
贪心算法又叫做贪婪算法，最大的特点就是，它在每一步做出的选择，是就当前情况而言，是最优的选择。换句话说，有可能尽管当前情况下的选择是最优的，却没有从整体的角度考虑，因此不一定是全局最优解。所以这个算法叫贪婪。
就我们而言，当然希望贪婪算法求得的解是全局最优解。那么在满足什么条件下能用贪婪算法求解呢？这篇博客中总结了两个重要性质：贪心选择性质和最优子结构性质。
所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。而对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
而最优子结构性质是指，当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。
其实这两条性质总结起来就是一个意思，就是一个问题的最优解，一定包含了贪心策略中存在的子问题的最优解。
好像还是没解释清楚。还是用具体的例子来说吧。以经典的背包问题为例。
给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。
与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1 <= i <= n。
对于最优子结构性质，我们做如下解释：两个问题中背包的重量是Wi，假设最优解中装的物品分别为a1,a2,a3……an等，那么对于子问题“背包的重量是Wi-ai”来说，最优解一定就是a1,a2….ai-1,ai+1……an了（反证法，如果是其他的组合最优，那么对于最优解来说一定是这个新的组合加上ai，而不是现在这个a1,a2,…..an了）。让人迷惑的也许是这个“子问题”。这个子问题如果说是贪心策略的每一步形成的子问题，那个两个背包问题都满足最优子结构性质（这一特点满足了动态规划的求解基础）。而对于原问题的任一子问题来说，0-1背包问题并不能满足（而背包问题能够满足）。按照这点解释，0-1背包问题不能用贪心算法求解是一个原因。
对于背包问题，其策略是每一步都选择单位重量价值最高的物品装入背包，直到装满为止。在这个策略下，如果最终能将背包填满，是满足贪心选择性质的，因此背包问题能用贪心算法求解。对于0-1背包问题，在最优解下，背包不一定能够填满。这样导致填背包的物品的单位重量的价值降低了，而不是原策略下的那个单位价值。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。对于这种情况，就应该使用动态规划求解。
回到层次聚类的问题中，自顶向下的聚类方法每一步都合并最近的两个类，直到所有的类都不再靠近。这显然是贪心算法。但是这里每一步都合并了最近的两个类，也就是说每一步合并后都将合并后的新类当做一个整体进行判断。这一策略应该是满足最优子结构性质的，和0-1背包问题相似，如果剔除某个类的所有点，其余的所有点的划分情况不会改变。而合并过程的每一步并不能导致问题的整体最优解，很显然是因为每次合并都以整体为单位，被划分为某类的样本不可能再被划分出去，所以，这个过程不一定能得到最优解。
转载此文请注明出处：http://blog.csdn.net/jiang1st2010/article/details/8432627
