SVD

实例中的数据是在学术会议ACM SIGIR 2001：The 24^th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (http://www.sigir2001.org/)上发表的一些论文的标题，我们希望对之进行聚类。

按照会议组织者的安排，各个论文应根据各自的主题属于不同的部分(paper session)，分别在不同的时间进行讨论。我们选择了其中的4个部分共12篇论文为例。这些论文是关于两个主题的：摘要(summarization) 和语言模型(language model)。我们将对这些论文的标题进行正交聚类，并与会议组织者人为划分的结果进行比较。

 

Paper Session IA: Summarization 1

D1: Applying Summarization Techniques for Term Selection in Relevance Feedback

D2: Temporal Summaries of News Topics

D3: Generic Text Summarization Using Relevance Measure and Latent Semantic Analysis

D4: A New Approach to Unsupervised Text Summarization

Paper Session 3: Language Model

D5: Document Language Models, Query Models, and Risk Minimization for Information Retrieval

D6: Relevance-based Language Models

Paper Session 5A: Summarization 2

D7: Generic Summaries for Indexing in Information Retrieval

D8: Automatic Generation of Concise Summaries of Spoken Dialogues in Unrestricted Domains

D9: Enhanced Topic Distillation using Text, Markup Tags, and Hyperlinks

Paper Session 8A: Language Models 2

D10: A Study of Smoothing Methods for Language Models Applied to ad hoc Information Retrieval

D11: Topic Segmentation with an Aspect Hidden Markov Model

D12: Finding Topic Words for Hierarchical Summarization

 

表4 .1 ACM SIGIR 2001 会议上的一些论文的标题

 

将这些论文的标题作为“文档”，记为D1，D2，...，D12。首先找出在这些文档中出现过两次以上的单词作为关键词，在表4.1中以斜体表示。在此过程中，同一个词根(stem)不同后缀形式的单词被认为是相等的，如summarize和summarization。关键词中不包括of，for等常用词。另外，因为这个会议的总的主题是信息检索(Information Retrieval)，Information和Retrieval这两个单词在论文中出现很频繁，所以关键词中也不包括它们。然后，就可以构造词语-文档关系矩阵(term-document matrix)，矩阵的各个行表示各个关键词，矩阵的各个列表示各个文档，矩阵第i行第j列的元素表示第i个关键词是否在第j个文档中出现，如表4.2所示。

 

 

	D1	D2	D3	D4	D5	D6	D7	D8	D9	D10	D11	D12
Summarization	1	1	1	1	0	0	1	1	0	0	0	1
Relevance	1	0	1	0	0	1	0	0	0	0	0	0
Topic	0	1	0	0	0	0	0	0	1	0	1	1
Generic	0	0	1	0	0	0	1	0	0	0	0	0
Text	0	0	1	1	0	0	0	0	1	0	0	0
Language	0	0	0	0	1	1	0	0	0	1	0	0
Model	0	0	0	0	1	1	0	0	0	1	1	0

 

表 4.2 对应于表4 .1中数据的词语-文档关系矩阵

 

易见合理的类数k=2，或者说将这些论文分成两类。

根据矩阵A的奇异值分解，得到正交聚类的结果，矩阵A的行的前2个类向量(即矩阵A的前2个左奇异向量)是

 

X1=(0.76, 0.33, 0.32, 0.26, 0.33, 0.11, 0.15)^T,

X2=(-0.25, 0.17, 0.04, -0.09, -0.10, 0.61, 0.72)^T;

 

矩阵A的列的前2个类向量(即矩阵A的前2个右奇异向量)是

Y1=( 0.34, 0.34, 0.52, 0.34, 0.08, 0.18, 0.32, 0.24, 0.20, 0.08, 0.15, 0.34)^T,

Y2= (-0.03, -0.08, -0.10, -0.13, 0.51, 0.57, -0.13, -0.10, -0.02, 0.51, 0.29, -0.08)^T。

如果在这个正交聚类的结果的基础之上，构造划分型聚类。那么这些论文将被分成两类：

(1)     V1={D1, D2 , D3, D4, D7, D8, D9, D1 2}，

相应的关键词U1={ Summarization, Relevance, Topic, Generic, Text}，

(其中关键词Summarization的权重最大)：

(2)     V2={D5, D6, D10, D11}，

相应的关键词U2={Language, Model}。

这个结果与ACM SIGIR 2001会议组织者人为划分的结果(见表4.1)基本吻合，只是D12的类别有所不同。从论文D12的标题(Finding Topic Words for Hierarchical Summarization)与内容来看，正交聚类将论文D12划分到主题是摘要(summarization)的类V1也是很自然的。如果在这个正交聚类的结果的基础之上，取程度临界值X Threshold = 0.15构造覆盖型聚类，那么论文D6与D12将同时属于两个类，即D6和D12与两个主题都不同程度地相关。

 

参考：万维网信息聚类研究