周晓光，谭春桥，张强.基于Vague集的决策理论与方法[M].北京：科学出版社，2009
Atanassov.K.Intuitionistic fuzzy sets [J].Fuzzy Sets and Systems，1986，20： 87-96
A Method for Fuzzy Multi-Criteria Decision
Making Based on Vague Sets
XIE NingZHANG QiangMENG Fan-yong
（School of Management & Economics，Beijing Institute of Technology，
Beijing 100081.China）
Abstract： According to its promising advantage in dealing with fuzzy values，vague sets has been widely applied in multi-criteria decision making problems.However，the traditional aggregation operators of vague values assumed that criterias are independent，which in some circumstances can’t reflect the real decision behaviors precisely.Therefore，this paper make use of Choquet integral and vague sets，representing a new aggregation operator-Vague-Choquet integral operator，and compared it with traditional aggregation operators of vague values to illustrate its superiority.At last，an example is provided to verify the process of the new method.
Keywords： Vague Sets； Vague-Choquet Integral Operator； Fuzzy Multi-Criteria Decision Making
一种基于Rough集的中文LINGO算法
陈书炫、熊孟英
（北京理工大学管理与经济学院，北京100081）
摘要：随着互联网络的发展，网络时代的信息量在爆炸性的增长，用户如何从中准确而迅速的找到自己想要的信息，通过对Web搜索结果进行聚类是一种有效的方式。在中文环境下，本文采用一种广义的Rough集——容错关系来描述Web搜索结果，并采用LINGO算法聚类。实验表明它在时间性能、类标识质量以及正确率上都优于传统的K-Means算法。
关键词：Web搜索结果；聚类；Rough集；LINGO算法
中图分类号：TP301.6.文献标识码：A
0.引言
随着Internet/Web技术的快速普及和迅猛发展，各种信息资源可以从网络上很容易地获得，人们正享受着互联网所带来的好处，而且互联网正渐渐地成为人们工作生活中的一部分。同时随着互联网络的发展，网络时代的信息量在爆炸性地增长。这就给用户出了一道难题，如何从浩如烟海的Web信息资源中迅速而准确地寻找到自己所需的信息。
虽然现在有搜索引擎来为我们解决这个问题，但是搜索引擎还是有不尽如人意的地方，有很多用户找到自己真正需要的信息仍然非常困难。特别是对于用户不能清晰表达自己需要的查询，比如，我们在用“苹果”这个词在搜索引擎上搜索的时候，我们可以看到搜索引擎提供了一个按照与这个查询词的相关度从高到低排成的Web搜索结果列表，像很多的查询词一样，搜索结果中包含了很多的信息：有关于苹果公司介绍的，苹果公司的各种产品信息，iPod，iPhone（手机），iPad（平板电脑），MacBook（超薄笔记本）等，也有关于电影《青苹果》的，还有的是关于水果苹果的信息，等等。搜索引擎将这些信息混在一起，用户需要仔细浏览查询结果列表，排除不相关的内容，才有可能找到自己想要的信息。
针对这一情况，本文结合现有的Web搜索结果聚类研究，在中文环境下，设计了一种基于Rough集的中文Web搜索结果的LINGO算法。由于很多时候搜索结果的标题及文摘不能有效地反映所指向的网页的本身的内容，通过采用一种广义的Rough集——容错关系来表示Web搜索结果，从而丰富了对Web搜索结果的描述，并将其应用于LINGO算法中。从实验数据可知，这种算法在时间性能、类标识质量以及正确率上都优于传统的基于Rough集的K-Means算法。
本文其余部分组织如下：第1节介绍容错Rough集的概念；第2节介绍Web搜索结果表示的容错Rough集模型；第3节具体描述基于容错Rough集的中文Web搜索结果的LINGO算法；第4节在Google的搜索结果基础上进行了实验，并同基于Rough集的K-Means进行比较；第5节总结全文。
1.容错Rough集
经典Rough集合理论中近似空间的概念提供了在没有足够的可用信息条件下将属于某一特定全域的对象进行完全分类的一种近似分类分析方法。近似空间中对象的分类是基于等价关系的近似分类，这样的分类过于注重对象之间的差异，忽略了对象之间的相似性。为此Skowron A和Stepaniuk J提出了利用对象之间的一个容错关系(tolerance relation)进行近似分类的广义近似空间的概念。
2.Web搜索结果表示的容错Rough集模型
我们将每个Web搜索结果记为一个文档，对于Web搜索结果的集合，从D中取出M个特征词，运用向量空间模型，每个文档由一个权重向量表示，其中表示为在第i个文档中第j个特征词的权重。所有特征词组成的集合为。
3.基于容错Rough集的中文LINGO算法
由Stanislaw Osinski于2003年首次提出的LINGO算法是一个强调聚类描述质量的在线搜索结果聚类算法。该算法产生聚类过程与传统的产生聚类过程相比有一个明显的不同，即它先根据所给文档集，识别出文档集中的所有抽象概念，然后为每个抽象概念选取最合适的单词元（由单个词组成）或者短语（多个词的有序序列）作为对抽象概念的描述。然后根据这些聚类描述，从文档集中指派一些文档给聚类描述所代表的聚类。LINGO算法的先产生聚类描述，然后再指定聚类内容的思路，可以避免传统的聚类过程在最后产生的聚类描述中存在着语义上无法理解的现象。按照这一思想，本文设计了基于容错Rough集的中文LINGO算法，其过程大致如下：
3.1.构造“特征词-文档”矩阵
针对中文的特点，放弃了原来LINGO算法建立“字-文档”矩阵，而用“特征词-文档”矩阵来代替，这样能有效地提高效率。构造“特征词-文档”矩阵需要包括以下三个步骤：
（1）Web搜索结果的预处理和特征词选择
由于从主流搜索引擎上返回的搜索结果很可能有HTML标记，那么就需要对获得的Web网页去除HTML标记，转化为纯文本。然后对其分词，并通过一定的规则进行特征词选择，如：①搜索中的查询词忽略，因为返回结果一般都会包含的；②出现的文档频率小于一定阙值的词忽略；③在文档中出现频率小于一定阙值的词忽略；④适当控制词的总数；⑤数词忽略，如时间，价格等；⑥结合词的长度和词性进行适当控制（如对词的长度为1且不为名词的词忽略）。经过率选后生成了文档的词频矩阵TF，同时在计算频率时，考虑到在网页文件中标题(Title)相对于摘要(Summary)的重要性，置其不同的权重。
（2）建立特征词的容错关系矩阵
对于任意的两个特征词和，如果其在Web搜索结果集中共现的文档频率达到一定的阙值，则特征词和存在容错关系，即TOL[i，j]=1，否则TOL[i，j]=0，其中矩阵TOL是矩阵，M为特征词的个数。
（3）计算Web搜索结果文摘特征词权重
结合词频矩阵TF和容错矩阵TOL，利用上近似集合来计算每篇Web搜索结果的特征词权重。权重算法不仅需要处理文档中的特征词，还要处理文档上近似特征词(它可能不出现在文档中或不出现在下近似集中)。
3.2.抽象概念发现
对于抽象概念发现，使用的是隐含语义分析 (Latent Semantic Indexing，LSI)的方法，并借助矩阵的奇异值分解 (SVD)方法来实现，利用SVD 方法结果中的U 矩阵来获取文档的抽象概念。由上面得到的“特征词-文档”矩阵进行奇异值分解以获得列向量的正交基(Orthogonal basis)，但并不是所有U矩阵的列向量被用来生成类标识，我们只选择前K个列向量，为了计算这个K值，我们使用一种基于F范式(Frobenius norms)的方法来计算“特征词-文档”矩阵和它的K阶近似矩阵的相似度。
3.3.聚类标识生成
首先，利用SuffixArray和LCP(最长公共前缀)，结合关于完整短语的算法，得到Web搜索结果集的关键短语。同上文中得到的特征词，构造矩阵P，这是一个“特征词-（关键短语+特征词）”矩阵，构造的思路是把关键短语+特征词看成是伪文档，而特征词看成是索引项，利用上文中构造“特征词-文档”矩阵的方法来计算权重。则经过计算将第i个抽象概念中分值最高的特征词或者关键短语作为该抽象概念的描述提取出来，同时此分值作为该聚类标识的得分。对于每一个抽象概念我们尽量使用一个关键短语进行描述，而且尽量避免使用字，优先选择词语来作为聚类标识。最后一步是通过对候选聚类标识的进行合并，以得到最终的聚类标识。在里我们合并那些在对抽象概念描述上重叠的候选聚类标识。在矩阵P中，对得到的候选聚类标识两两之间计算相似度。当2个候选聚类标识的相似度大于一定的阈值时，只保留得分更高的那一个候选聚类标识而将另外一个舍弃；同样我们在得分相同的情况下，优先选择词语而淘汰字。
3.4.生成聚类内容
在已经得到聚类标识的情况下，按照LINGO算法先标识后聚类的思想，下一步的工作则是将Web搜索结果按照与聚类标识之间的相似度，将其分配到相应的聚类标识下从而完成聚类过程。在这里，我们遵循以下两个原则：依照软聚类的思想，允许类与类之间有重叠的内容，即只要大于一定的阈值即可，所以一个Web搜索结果可以同时分配到多个聚类标识下；设立一个标识名为“Other”的类，Web搜索结果对于所有的聚类标识的相似度都低于一定的阈值就分配到这一类中。
按照以上两个原则，参考LINGO算法，聚类内容生成过程的大致如下：(1)利用“特征词-（关键短语+特征词）”矩阵P，将聚类标识表示成“特征词-聚类标识”矩阵Q；(2)按照公式计算出矩阵C，则表示第i个聚类标识与第j个文档之间的相似度；(3)只要文档和某一聚类标识的相似度大于一定的阈值，则将此文档分配到该聚类标识下；(4)如果文档和所有聚类标识的相似度都小于一定的阈值，即发生失配，则将此文档分配到“Other”类中。
4.实验对比
聚类结果的有效性是衡量聚类算法优劣的标准。由于缺乏测试集合，为了对基于Rough集的K-Means和LINGO算法进行比较，我们主要从以下三个方面：时间性能、类标识质量（指有用的类的个数占类的总个数的百分比）和准确率。为了便于测试实验结果，使用查询词“苹果”，从Google上分别选取返回结果的文档数目为50篇、100篇、200篇，其中对于时间的测试是进行多次的测试，计算其平均值，类标识质量和正确率使用人工判断的方法。实验环境为：Visual Studio 2008编程，Vista操作系统，酷睿双核5750，内存2G。
实验结果表明，相对于基于Rough集的K-Means算法，基于Rough集的LINGO算法在时间性能上，类标识质量以及正确率上，都会更好。其主要是因为LINGO聚类算法是一个强调聚类描述质量的在线聚类，先产生聚类标识，然后再决定其聚类内容，所以LINGO算法能产生比较好的类标识质量以及正确率。
5.总结
本文设计与实现了基于Rough集的LINGO算法对中文Web搜索结果的聚类，通过对Web搜索结果自动聚类，可以帮助用户导航浏览，使用户能在更高的主题层次上来查看搜索引擎返回的结果，快速准确地查找到自己感兴趣的信息，从而可大大缩小所需浏览的搜索结果数量以及缩短查询所需要的时间。
