以聚类为核心的聚合优化方案

聚类是无监督学习的一种最普遍形式，是一种允许相似的事物根据其普遍特征聚集在一起的技术。聚类方法被广泛应用在数据挖掘和信息检索的不同检索过程任务中，针对的对象也不同(例如文档、作者、索引词)。被聚类的特征可以包括资源中的特征词汇和它们共现的现象，如果关注点是索引款目或链接(例如网页之间的超链接、引文关系、文档中出现的共被引)等，资源本身也可以直接作为聚类的样本。信息检索中的聚类作用主要在于检索到文档进行评估，并且揭示出对象之间明显的关联，并发现那些潜在的关联。

正如上文提到的，如何最好地匹配用户的查询和集合中的文档迄今为止仍是信息检索面临的一个基础挑战。许多数学模型被开发出来用于进行匹配处理，匹配处理的细节一般情况下对于终端用户来说都是不可见的，只是表现为不同的最终输出结果。一旦候选的文档集合被识别出来，就会被系统直接返回给用户。传统的处理流程主要依赖线性的文档有序列表，其依据是计算得到的结果和查询之间的相关性或者是其他测序标准(例如日期、按字母顺序排列的标题或作者)，也就是说，这种线性列表方式展现的结果主要体现的是文档和查询之间的关联，而非文档本身之间的关联。聚类技术则可以通过创建文档(或其他有价值的对象)的集合，更有效地检索或评估检索结果的集合来克服这种局限^[16]。

早期的信息检索系统就开始使用聚类的思想，例如Salton的SMART系统^[17]的文档聚类是通过定义一个向量空间来表示相关文档的快速定位集合；贾德尼和罗杰斯博格则将聚类应用的基本原理正式定义为聚类假说^[18]，这个假说认为与同一个查询有关的文档之间的相似性高于与不同查询有关的文档对象，这种关系的不同可以通过多种形式表现出来，例如文档集合，近年来兴起的关系的可视化和多维空间中结果的相似性^[19]。

常规的聚类分析技术主要包括层次聚类(或系统聚类)和非层次聚类两种类型。非层次聚类方法例如k-means聚类等需要一个最终获得聚类的数量和性质先验假设；层次聚类的结果一般用骨干结构可视化表达出来，在不同的聚类步数上获得的类的数目有所不同。在层次聚类中，各类之间的距离越近说明类间的关联越紧密，其相似程度也就越高。作为一种探索性的研究方法，目前层次聚类的算法有很多，但其步骤基本上是类似的：首先，对象之间相似性被计算出来作为逐个比较的基础，一般来说，常用的衡量样本之间的相似性测度包括欧式距离、余弦系数、Jaccard系数、切比雪夫距离等。然后，选择不同的聚类方法实施聚类，常用的方法包括类间平均法、类内平均法等，每种方法的算法各不相同，最终得到的聚类数量也不同，利用不同的聚类方法进行重复试验可以在比较的基础上获得最佳的结果。

从层次的角度进行的聚合方式主要包括两种方法：分裂式层次聚类和凝聚式层次聚类。层次角度的聚合有助于从不同的粒度分析检验最终的聚合，其基本思想是根据网络的拓扑结构建立层次性的聚合结构。

(1)距离和相似性

聚类实施的基本依据是对象之间的距离或者相似性程度，这种思想和上一小节中提及的以节点为中心的资源集合发现有一定相似的地方。距离的测量最常见的方法为欧式距离。假设vik是某个资源实体i所具有的第k个属性，每个资源实体测量了p个属性，那么资源实体vi和vj之间的欧式距离为：

欧式距离常被用于数据密集的情况，当所有的节点都有属性值，属性值量级相对重要的情况下，欧式距离比较合适。

常见的相关性系数算法主要包括Person相关系数和Cosine相关系数(夹角余弦相似度)。Person相关系数算法源于线性回归模型，要求被测量的数据符合线性回归的基本假设，比如变量间是线性的，服从均值为0、方差为常数的概率分布。两个观测对象X和Y的Person相关系数r的计算公式为：(www.xing528.com)

其中，i为每个属性，表示对象X在所有属性上的平均值。

相较而言，Cosine相似性更适用于数据较为稀疏的情况，且目前使用也非常广泛，其基本思想是测量两个向量之间夹角的余弦值作为两个向量的相似性。由于余弦相似测量适用于具有任何维度的空间，因此在信息检索和文本挖掘中被广泛使用，例如针对词和文档的关系，每个词都被表达为一个维度，而文档则用在这些维度上的向量来定义，Cosine相似性提供了一个衡量两个文档在主题上相关有效度量方法^[20]。两个向量A和B的Cosine相似性计算公式如下：

其中，i表示每个维度，Ai表示向量A在维度i上的值。

采取哪种形式的相关性测度在学者中间经过了很长时间的讨论^[21]，且一直没有明确的结果，目前逐渐达成的一个共识是，从数学原理和读者理解两个方面考虑，Cosine相似度要优于Person相关系数^[22]，且Cosine常用于信息检索中。因此，本研究所涉及的相关系数转化统一使用Cosine相关性测度。

(2)聚类方法

分裂式聚类方法首先将网络中的节点划分为不相交的集合，之后将每个集合进一步分解为更小的集合，直到每个集合中包含数量较少或只有一个点。其中的关键方法就是如何将整体网络划分为多个部分。最典型的分裂式聚类方式是通过不断删除网络中最不紧密的边，实现将整个网络分解为不同的集合，一般步骤包括两个部分：第一，在每次迭代后，找到强度最小的关系，这类边常位于两个集合的边缘，是连接两个结合的桥梁。第二，删除该边，然后重新计算新形成的网络中各边的强度。第三，如果通过删除这个边使网络中出现更多的组分，那么每一个组分就被认为是一个聚合。反复迭代1和2的过程以发现更小的聚合。Newman和Girvan在2004年曾经提出了基于边介数来实现分裂式聚类的G-N算法^[23]，且已经有相关的研究将G-N算法进行实践应用^[24]。但相对而言，基于边介数的分裂式聚类算法存在许多的局限，主要表现为两个方面：一方面，计算网络中节点或边的介数时间复杂度很高，算法效率低下；另一方面，每删除网络中的一条边需要重新计算所有的边介数，因此，分裂式聚类算法在大规模网络中的适用性较差。

凝聚式聚类是将每个节点都视作一个类，从最基本的类开始，按照某种标准不断将其集合成更大的类，最终对网络总体结构进行类分析的一种方法。Clauset等人^[25]在2004年曾提出以模块度为标准的凝聚式聚类，其基本思想是：如果两个类合并能够对总体的模块度产生贡献，那么就实施聚类合并，直至总体的模块度不再增加为止。凝聚式聚类其他算法有很多^[26]，例如类间平均法(Betweengroups linkage)和类内平均法(Within-groups linkage)侧重于合并偏差较小的类，最近距离法(Nearest Neighbor)适用于非常离散的资料，最远距离法(Furthest Neighbor)适用于高度压缩的资料，离差平方和法(Ward's method)倾向于得到各类书目接近的分类结果。

凝聚式聚类也存在一定的缺陷，例如会导致不平衡的聚类过程，一个较大的子类和一个较小的子类合并时计算的代价会比较高。因此，对于凝聚式聚类的研究侧重于获得平衡程度高的层次结构来提高算法的效率，例如Blonedl等人在2008年提出的Louvain算法^[27]，该算法将每个节点当做一个类，然后给予模块度来判定哪些相邻的节点应该合并，经过第一次全局遍历之后，实现了一些节点的聚类，然后每个类再次被当成节点，对其关联的信息和度进行计算，能够基于计算结果作进一步合并，这种多层次算法在处理大规模网络时比较有效。本研究中案例分析在使用传统的聚类方法时主要采用凝聚式聚类方法。