数据挖掘：概念与技术（第三版）之第十一章的学习记录
在传统的聚类分析中，对象被互斥地指派到一个簇中。然后在许多应用中，需要以模糊或概率方式把一个对象指派到一个或多个簇。本章将讨论允许一个对象属于多个簇的聚类主题。
基于概率模型的聚类
我们先从讨论模糊簇的概念开始，然后在推广到基于概率模型的簇。
模糊簇
要引入模糊簇就不得不说模糊集
书上P324页，11.1.1先给出了有关模糊集的数学定义，然后例11.3给出了一个例子 ，并且谈到了隶属度。然后，由模糊集推广到模糊簇。这些概念都很好理解。
这里稍微有点混淆的是 模糊集，模糊簇，聚类这三个概念的关系，我们来理清一下。
1、模糊集应当很好理解；
2、模糊簇是模糊集在聚类上的推广，即一个簇就是对象的一个模糊集；
3、一个聚类包含多个模糊簇。
OK，理解这三条，应该就没有问题了。
然后在说说前面谈到的隶属度。
隶属度这个概念很好理解，就是属于哪个簇的“概率”是多少。（记得我们这里谈的是基于概率模型的聚类）
然后，为了记录方便，引出了划分矩阵
P325，例11.4给出了涉及隶属度，划分矩阵和模糊聚类的例子。
在见识过 模糊聚类之后，我们如何度量该聚类的质量呢？？
参考第10章讨论过的，对象与其被指派到簇的中心之间（这个中心可以是均值也可以是代表对象）距离（相似度）可以用来度量该对象属于簇的程度。基于这个思想，我们用聚类的SSE来度量模糊聚类对数据集的拟合程度（即质量，或者可以参考下散度的定义）
OK，我们现在应该已经了解了一个模糊聚类了，那么我们如何去计算一个模糊聚类呢？
实际上，这个算法我们是熟悉的，因为k-均值聚类是模糊聚类的一种特例。因此，计算模糊聚类的EM算法基本上也是这个流程，它的具体操作流程是这样的：
1、选定K个初始的簇中心；
2、然后计算每个对象属于每个簇的隶属度；
3、把每个对象都分配到簇中心离该对象最近的簇。
4、重新计算簇的中心（优化度量值）；
5、迭代3,4,5步直至稳定（稳定的话意味着簇中心变动很小了/或者可以人为的设定一个阀值）。
P328页，例11.7给出了计算一个模糊聚类的详细过程。在这个例子中，我们可以通过划分矩阵很清楚看到整个算法的执行过程。
接下来，我们对模糊聚类进行推广。
基于概率模型的聚类
模糊簇是提供了一种灵活性，允许一个对象属于多个簇。其实从上面我们说到的隶属度就可以引申到这里。
基于概率模型的聚类实质上是提供了一个一般框架，在这个框架中对象可以用概率 的方法参与多个簇。
我们回想一下，聚类分析的目标是发现隐藏的类别。作为聚类分析主题的数据集可以看作隐藏的类别的可能的实例的一个样本，但是没有类标号。这句话可以说是非常重要的，因为它体现了一种思路。我们再来重新细细看一下这句话，它的意思是把我们手上的数据集当作一个样本而已。我们在这个样本中进行聚类分析，然后尽量找出隐藏的类别。
这有点禅或者道的意味儿。我们观察分析一个细微的东西，比如说一张叶子，一块石头，然后发现了天地大道，世间万物无不遵循此道。
呵呵，扯得有点玄了。不过，大家可以从这个角度去体会下。
OK，说正经的。在统计学领域，在数据集中隐藏的类别我们称之为“概率簇”。现在我们的目的就是找出在数据集D中隐藏的k个概率簇。那我们怎么做呢？套用一句话，“不忘初心，方得始终。”我们不妨从如何形成这个数据集开始。
假设我们现在这里有一个数据集D，这个数据集有n个对象，这个数据集里有k个簇（这可以当作先验条件吧）。
那个这个数据集D是咋形成的的？
很简单，简单来说就两三步
1、选一个簇；
2、选簇里的一个对象；
3、迭代。
OK，就是这样，不过这是简单的说法了。
往深了想。在这个数据集里面，我们是有k个簇的，那么第一步我们选中哪个簇了？在选中的那个簇里，我们是有很多个对象的，那么我们第二步选中那个对象了？？
所以，很明显，我们需要额外的参数来完善这个过程。而这些额外的参数的引入就自然而然涉及到了概率论。具体来说第一步引入了权重参数（这个应该很好理解），第二步是引入了概率密度函数（这个不理解的建议回头看看书，或者参考下这篇文章。概率密度函数在某一点的值有什么意义？）
那么这个流程就变成这样了
1、根据簇的概率选择一个概率簇；
2、根据选定簇的概率密度函数选择一个样本；
3、迭代。
OK，这样做迭代n次就能搞成这个数据集D了。
这个过程在P327页，公式11.6被归纳成了一个公式。
然后现在想一想我们做这个的目的是什么？我们的目的是推导出/使用/以上/数据产生过程中/最可能产生D的/k个概率簇。
所以，我们的目的始终是推导出（或者说聚类）k个概率簇。这是不是又回到了我们的主题了？？
所以，关注下最可能这三个字，结合公式11.6。我们的聚类目的就自然转换成了一个求最值的过程，更准确的说我们是转换成了求最优化参数的过程。
整个过程若采用公式进行推导的话就如下所示：
而我们想要的就是P(D|C)最大化。我们看公式11.6，发现里面设计了权重wj,，以及概率密度函数fj。权重都还好说，但是我们知道概率密度函数fj是可以任意复杂的。这就意味着，我们的最大化之路会异常难行。所以，为了使基于概率模型的聚类是计算可行的，我们通常假定概率密度函数是一个参数分布。
至此，我们权重wj好计算，我们又假定了概率密度函数服从某一个参数分布。那么最大化P(D|C)就可以进行计算了。
而继续往后推导，我们可以很容易的想到，由于我们假定概率密度函数是一个参数分布，因此到最后，整个问题就转变成了这样：
使用参数概率分布模型，基于概率模型的聚类分析任务是推导出最大化式子的参数集
那么，如何进行具体操作呢？这里就引出了EM算法的框架。你可以在书上看到，用EM算法来不断调整参数集，最后得到聚类的。
其实，要理清这个问题说简单也简单，说复杂也真的很复杂。因为这里涉及到的很多东西，其内在精髓是思想，是数学公式的推导。因此，目前我也是不奢望能说得很清楚了，毕竟自己的水平还没达到那个地步=。=
建议不明白的同学，去看看极大似然估计。
OK，剩下了书上的阐述已经很明确了。我在这里的阐述只是用来理清思路，省略了一些东西。
其实啊，在第十章的时候（P304页），我们在谈概率层次聚类的时候，就已经提到过这么一种看待聚类的方法，即把待聚类的数据对象看作要分析的基础/数据生成机制/的一个样本（生成模型）。而聚类的任务就是使用待聚类的观测数据对象，尽可能准确地估计该样本（模型）。
而在实践中，我们可以假定该数据的生成模型（就是样本）是采用常见的分布函数，如正态分布或伯努利分布，它们由参数确定。于是，学习生成模型的任务就归结为找出使得模型最佳拟合观测数据集的参数值。
聚类高维数据
当数据的维度特别高时，传统的聚类方法效果已经很不好了。
譬如传统聚类方法通常使用的距离度量在高维数据空间就基本上没效果了。
因此，我们需要针对高维数据找到特定聚类方法。
首先，我们要明白高维数据是什么样的？
一般来说，高维数据容易出现在超市，商场等等企业的数据仓库中。
这类数据一般的特点是数据量特多（交易量大），数据维数特多（商品总类多）。
其次，我们要明白我们想要的聚类是什么样的？
我想，这些企业对数据分析通常都是为了KDD或者BI。
对于这些企业来说，高维数据上什么样的簇才是有意义的呢？
是小属性集，或者说是精准的聚集。想一想会员服务，精准化推荐。
P330，11.2.1。
高维数据聚类方法主要有两类：子空间聚类方法和维归约方法。
子空间聚类方法
子空间聚类方法分为3类：
1、子空间搜索方法；
2、基于相关性的聚类方法；
3、双聚类方法。
这里着重考察双聚类方法。
在某些应用中，我们希望同时聚类对象和属性。结果簇是所谓的双簇，满足如下要求：
1、只有一个小对象参与一个簇；(少量数据)
2、一个簇只涉及少数属性；（少量属性）
3、一个对象可以参与多个簇，或完全不参与任何簇；
4、一个属性可以被多个簇涉及，或完全不被任何簇涉及。
在实际应用中，对这类数据进行聚类的话，就涉及到了搜索矩阵，这是双聚类技术的本质。
P332,11.2.3给出了双聚类的应用实例，包括在生物基因领域上的应用和在推荐系统中的应用。好好看看这两个例子，应该能对双聚类的认识加深不少。
其实，你可以这样来理解。把数据想象成一个巨大的矩阵，而我们进行双聚类的目的就是要在这个巨大的矩阵上进行数据的分析处理和聚类，挖掘出满足需要的簇或者说子矩阵。而这个簇通常被我们称为双簇。而这个簇通常有具有上面我说的那些特点。
OK，把双簇理解成一个子矩阵，这个子矩阵的形式是比较固定的（通常一行代表一条数据，而一列代表一种属性）。、
因此，基于这种构造，子矩阵一般都是下面这几种：
1、子矩阵是一个具有常数值的双簇；
2、子矩阵是一个行上具有常数值的双簇；
3、子矩阵是一个列上具有常数值的双簇；
4、子矩阵是一个具有相干值的双簇；
5、子矩阵是一个行上具有相干演变的双簇；
6、子矩阵是一个列上具有相干演变的双簇。
然而，值得注意的是，上面的的子矩阵类型定义只考虑了理想情况。但是在实际的数据中，这6类完美的双簇很罕见。只要原因是有噪声数据的存在。因此，在实际上，我们找矩阵的时候不能完全比照着这6种固定的模式。所以，对于这种情况来说，我们通常需要引入一个参考值，具有最高参考值的子矩阵被识别为双簇。
OK，那我们要怎么去挖掘双簇呢？
在含噪声的数据中发现双簇的方法主要有两类：
1、基于最优化的方法执行迭代搜素；
2、使用枚举方法进行枚举。
P335页解释了这两种方法。其中第一类方法比较好理解，第二类的Maple方法，书上讲得比较笼统，算法的更多细节我目前也不是太清楚。
维归约方法
上面讲的子空间聚类方法试图在原数据空间的子空间中发现簇。
然而在某些情况下，构造一个新的空间，而不是使用原数据空间的子空间，效果更好。
基于这个思想，维归约方法被提了出来。
在这里，我们重点介绍谱聚类方法中的NJW算法。
书上P337下方，详细介绍了谱聚类方法的一般框架，然后再具体谈了谈NJW算法。
这个算法比较有意义，书上介绍得也很不错。如果有看不懂的同学，我建议去复习在线性代数中有关求特征值和特征向量这一块儿。然后在参考下这篇文章吧。
谱聚类（NJW算法 Matlab代码）
其他的
本章节，P339,11.3节所述的聚类图和网络数据比较好理解，书上说得也还比较清楚 。
但是，其中simrank阐述的不是太好。建议同学们自己在网上看下。
后面的SCAN算法是用于图 聚类算法，P345的表中把算法流程已经列出来了。多看下，仔细分析下，应该没问题。
最后面的处理有约束的多维聚类也是看看书就行了。