基于稳定性语义聚类的相关模型估计

孙芯宇 吴江 蒲强

摘要：针对由不稳定聚类估计的相关模型影响检索性能的问题，提出了基于稳定性语义聚类的相关模型（SSRM）。首先利用初始查询前N个结果文档构成反馈数据集；然后探测数据集中稳定的语义类别数量；接着从稳定性语义聚类中选择与用户查询最相似的语义类别估计SSRM；最后通过实验对模型的检索性能进行了验证。对TREC数据集5个子集的实验结果显示，SSRM相比相关模型（RM）、语义相关模型（SRM），平均准确率（MAP）性能最少提高了32.11%和0.41%；相比基于聚类的文档模型（CBDM）、基于LDA的文档模型（LBDM）和Resampling等基于聚类的检索方法，MAP性能最少提高了23.64%，19.59%和8.03%。实验结果表明，SSRM有利于改善检索性能。

关键词：信息检索；语义聚类；稳定性验证；独立分量分析；相关模型估计

中图分类号：TP391.3 文献标志码：A

Abstract：To solve the problem of relevance model based on unstable clustering estination and its effect on retrieval performance， a new Stable Semantic Relevance Model （SSRM） was proposed. The feedback data set was first formed by using the top N documents from user initial query， after the stable number of semantic clusters had been detected， SSRM was estimated by those stable semantic clusters selected according to higher userquery similarity. Finally， the SSRM retrieval performance was verified by experiments. Compared with Relevance Model （RM）， Semantic Relevance Model （SRM） and the clusteringbased retrieval methods including ClusterBased Document Model （CBDM）， LDABased Document Model （LBDM） and Resampling， SSRM has improvement of MAP by at least 32.11%， 0.41%， 23.64%，19.59%， 8.03% respectively. The experimental results show that retrieval performance can benefit from SSRM.

Key words：information retrieval； semantic clustering； stability validation； Independent Component Analysis （ICA）； relevance model estimation

0 引言

信息检索研究中常用伪相关反馈方法估计相关模型，改善用户查询，更准确获取用户信息需求。相关模型的估计需要用到伪相关反馈技术，通常假设用户初始查询的前N个结果文档是查询相关的，但大多数情况下这个假设并不成立。全部N个文档参与反馈必将带入不相关噪声，使得相关模型估计偏离用户查询[1-2]。

聚类技术可将N个查询结果文档形成的数据集划分成若干类别，只选择与用户查询最相似的聚类中的文档估计语言模型，可以减少模型估计中不相关文档带来的噪声。已有研究[3-4]表明，语义聚类技术相比传统聚类技术在聚类效果上有显著改善。语义聚类指在未知数据类别的潜在语义空间上的聚类操作，语义空间以多个数据主题为基张成。语义聚类通常借助本体[4]或利用统计[5-6]的方法进行。本体WordNet可以判断文档间的关联，决定文档是否划分到相同的语义聚类。虽然借助本体的语义聚类效果有所改善，但是规则式的语义聚类方法不能灵活适应各种数据。潜在语义索引（Latent Semantic Indexing，LSI）[5]、独立分量分析（Independent Component Analysis，ICA）[6]采用统计方法分离语义主题，为典型的语义聚类技术。LSI技术将最大方差投影方向定义为语义类别，但最大方差投影方向并不总是表示数据的真实语义类别[6]。ICA技术具有在任意方向上分离出数据中独立分量的能力，分量间不要求一定满足正交关系。相比LSI定义的最大方差投影方向，ICA的任意方向上分离的独立分量更能表示数据中真实存在的语义类别，因此本文采用ICA进行语义聚类。ICA算法分离出的每一个独立分量代表数据中的一个语义类别，以每个独立分量为基可张成ICA语义空间。

由于数据中未知的语义类别数量和ICA算法的随机性，多次运行ICA算法分离的独立分量是不同的[7]，因此得到的数据语义聚类也不一样，也就是语义聚类是不稳定的。数据本来具有隐含的固定数量的语义主题，在不稳定的语义聚类上估计相关模型必定存在主题偏差。文献[8-9]利用语义聚类估计了相关模型，并提升了检索性能，但没有考虑语义聚类的稳定性。

如果能够预先探测数据中隐含语义类别的个数，那么ICA算法根据此类别数量才能分离出接近真实可靠的语义聚类稳定性语义聚类。探测数据集中的聚类个数通常使用多个k值重复运行包含随机性的聚类算法，并利用聚类稳定性指标计算不同k值下的聚类稳定性，选择聚类稳定性最高的k值作为最合适的聚类个数[10]。

针对基于稳定聚类的语言模型估计对检索性能的影响等研究工作较少，本文提出一种基于稳定性语义聚类估计的相关模型（Stable Semantic Relevance Model， SSRM），通过探测前N个查询结果文档构成的数据集中存在的稳定语义类别数量来验证语义聚类的稳定性。本文认为在稳定性验证后的语义聚类中，选择与用户查询最相似的语义类别估计的相关模型，能够获取比现有方法更好的检索性能。

由于ICA算法的随机性，在微小差别条件下多次运行ICA算法可以解决单次运行分离独立分量的不可靠问题。假设数据集中存在从1到n的语义类别数量，通过如下方法保证稳定性语义聚类：探测1到n的类别数量，在同一数据集上使用Bootstrapping方法微小改变运行条件，多次运行ICA算法，并聚类得到的一组独立分量。将聚类质量得分最高对应的探测类别数量作为数据集中稳定的语义聚类数量。

本文研究工作将解决如下问题：如何验证语义聚类稳定性；如何选择参与相关模型估计的稳定性语义聚类；如何估计基于稳定性语义聚类的相关模型；如何利用稳定性语义聚类估计的相关模型进行检索实验，并将检索结果在纵向和横向上同已有典型算法详细比较，以证明基于稳定性语义聚类估计的相关模型能够带来检索性能上的提升。

1 相关模型和潜在语义聚类的关系

信息检索中，通过相关文档的反馈可以改善用户查询，研究表明检索性能改善效果明显[11]。用户查询已知，相关文档未知的情况下使得相关模型估计变得困难。文献[11]提出一种在相关文档未知情况下，利用用户查询和初始查询结果前面若干文档估计相关模型的理论方法。方法假设用户查询和文档之间存在一个隐含的相关模型，因此可观察的用户查询和文档是由隐含的相关模型随机采样词条生成的。这样，用户查询和文档通过相关模型联系起来。

利用查询和初始查询结果的前面若干文档作为相关反馈文档，可以近似估计相关模型。有两种经典的相关模型估计方法[11]：一种假设由反馈文档估计的文档模型独立生成查询词条和文档词条，查询词条和文档词条间无关联关系；另一种假设查询词条由文档模型独立生成，但各查询词条保持和文档词条关联，关联度高的词条在相关模型估计中拥有较高的权重。

相关模型的估计通常采用基于聚类的方法[1-2，8-9，12]，好处在于可以先对初始查询结果文档聚类，然后只选择用户查询最相似的某个类别中的文档参与估计相关模型。基于聚类的方法估计相关模型的基本思想是：借助聚类选择，过滤掉与用户查询相似度不高的文档带来的噪声。

ICA算法已被证明是一种有效的语义聚类方法[8-9]，和文献[8-9]不同的是，本文重点考虑了ICA算法的随机性造成在同一数据集上多次运行ICA算法分离的独立分量结果不唯一性，也就是语义聚类数量的不唯一问题，因此有必要验证ICA算法在不同数据类别数量上分离独立分量的稳定性。本文认为在稳定的语义聚类中选择和用户查询最相似的语义类别估计的相关模型能够改善检索性能。验证的基本思想是，假设数据集中存在L个语义类别，利用重采样方法[7，13]，在同一数据集上分别按1至L个类别，多次运行ICA算法，并将每次得到的一组独立分量进行聚类。如果在某个数量m上的语义类别稳定，那么独立分量应接近聚类中心而远离其他聚类，这时可将分离的独立分量数量m作为数据集中的语义类别数量。

2 ICA语义聚类及稳定性验证

2.1 ICA语义聚类

如果将语义空间看成一组相互独立的隐含主题为基构成的空间，那么混合了隐含主题的一组文档在语义空间上张成用户可观察的文档集合[14]。已知混合主题的文档集合，利用ICA技术可分离其中的隐含主题，即将文档集表示为独立分量的线性组合[6]。本文将独立分量表示的相互独立的隐含主题定义为文档集中的语义类别。ICA模型如式（1）：

2.2 语义聚类的稳定性验证

多次利用随机性和无监督的ICA算法分离的语义类别是不同的。如果能事先验证数据中存在的稳定类别数量，那么通过ICA算法得到的语义类别才可靠并接近数据类别的真实情况。在尽可能接近真实可靠的语义聚类上估计的相关模型应该能够提升检索性能，本文实验部分将验证这一猜测。

语义聚类的稳定性验证的基本过程是：假设数据集中存在不同的独立分量数量，即语义类别数量。遍历每个类别数量，多次运行ICA算法，将得到的独立分量进行聚类；然后考察聚类质量，将聚类质量最高情况下对应的独立分量个数作为数据集中稳定的语义聚类数量。

3 基于稳定性语义聚类的相关模型估计

已知用户查询的情况下，利用前N个初始查询结果文档作为伪相关反馈可以估计相关模型。例如，已知用户查询Q和前N个结果文档构成的文档集D，相关模型R的估计为p（D|Q，R）=∏Ni=1p（di|Q，R）。p（di|Q，R）为假设已知相关模型R和用户查询Q的条件下，生成文档di的条件概率。

由于前N个查询结果文档并非都与用户查询相关，将N个结果文档全部参与反馈估计相关模型必定带入不相关的噪声，导致估计的相关模型偏离用户查询主题。这里提出利用基于稳定性语义聚类估计相关模型（SSRM）的方法，期望估计的相关模型比已有方法更好地改善检索性能。SSRM估计过程包括两个阶段：1）选择参与相关模型估计的稳定性语义聚类；2）基于稳定性语义聚类估计相关模型。

3.1 筛选稳定性语义聚类

语义聚类稳定性验证后得到的一组独立分量将作为数据集中稳定的语义聚类，对应多个语义类别。稳定性语义聚类选择的目的是，选取稳定性语义聚类中适合度高于阈值的一组语义类别参与相关模型的估计。语义聚类的适合度采用KL散度计算，基本思想是将语义聚类和用户查询的相似度距离作为语义聚类的适合度，离用户查询相似度距离最小的语义聚类适合度最高。语义聚类的适合度按照语义聚类模型和查询模型间的相似度计算，并筛选出适合度高于阈值的语义聚类。计算如式（7）：

如果语义聚类模型和用户查询模型生成词条w的概率越接近，那么这两种模型的词条分布越相似。适合度高于阈值的语义聚类下的文档将用来估计相关模型，期待缓解使用全部前N个查询结果文档估计相关模型带入的不相关噪声，造成相关模型估计出现主题偏移的问题。

3.2 估计相关模型

假设用户查询词条q1，q2，…，qk间相互独立，与文档词条w保持某种程度的关联。通过式（7）选择的稳定性语义聚类将在相关模型估计过程中发挥桥梁作用，它将用户查询和语义聚类中文档词条关联起来。使用稳定性语义聚类后，在已知用户查询Q的情况下，相关模型p（w | Q， R）的估计转化为计算文档词条w和用户查询q在稳定性语义聚类中的同现概率，如式（8）：

4 实验结果与分析

4.1 实验设计

实验目的是为了验证基于稳定性语义聚类估计的相关模型（SSRM）更接近用户的查询需求，比已有的相关模型和基于聚类的检索方法在检索性能上有所改善。

实验将在TREC数据集上测试SSRM的检索性能。实验中，TREC标题用来模拟用户查询，并删除了无相关结果文档的查询。数据集使用Porter进行词干处理，同时删除了停止词。实验使用Indri5.0建立数据集索引。查询编号51～150的美联社（Associated Press Newswire，AP）数据集作为训练集，查询编号151～200的AP数据集、华尔街日报（Wall Street Journal，WSJ）、圣何塞水星报（San Jose Mercury News，SJMN）、查询编号301～400的金融时报（Financial Times，FT）和洛杉矶时报（Los Angeles Times，LA）等数据集作为测试集。

估计SSRM实验步骤包括：1）使用基本的查询似然模型得到初始查询结果文档；2）使用DTU工具箱[14]255中的ICA算法对前50个用户查询结果文档进行语义聚类；3）稳定性语义聚类验证。首先假设前50个文档形成的数据集中存在20个语义类别，然后使用Bootstapping方法运行FastICA算法[6]154930次，探测数据集中存在的稳定语义类别；4）通过式（7）选择适合度高于阈值的稳定性语义聚类。适合度阈值设定为0.3，即选择KL散度值由高到低排列的前面30%的稳定性聚类参与相关模型的估计；5）利用选择的稳定性语义聚类进行相关模型估计。估计中，选择稳定性语义聚类生成词条的概率值大于阈值0.3的词条作为语义聚类的关键词。

为了验证SSRM的检索性能高于其他相关模型和基于聚类的方法，实验在查询平均准确率均值（Mean Average Precision， MAP）上纵向和横向比较了SSRM和其他模型的检索性能。纵向比较的模型包括：1）基线相关模型（Relevance Model， RM）：Indri实现Lavarenko的相关模型[11]122-123作为检索性能比较基线；2）在无稳定性验证的ICA语义聚类上估计的语义相关模型（Semantic Relevance Model， SRM）。横向比较的方法包括：基于聚类的方法（ClusterBased Document Model， CBDM）[1]、基于LDA的文档模型（LDABased Document Model， LBDM）[15]和重采样（Resampling）方法[2]。

4.2 三种相关模型性能纵向比较

表1给出了SSRM在测试集上的MAP性能相比RM、SRM的MAP性能的提升情况。“%chg”表示SSRM相对RM和SRM在MAP性能上提高的百分比。表中值的上标α、β、γ分别表示RM、SRM和SSRM三种模型在置信度为95%的情况下，MAP值在Wilcoxon检验下显著性提高。“Upper”列中的值为MAP性能上界。性能上界值计算方法：首先手动选取前50个查询结果文档中真正查询相关的文档，然后将这些真实相关的文档作为反馈估计语义相关模型（SRM）并检索得到MAP值。之所以利用SRM计算检索性能上界，主要考虑SRM没有消耗额外的时间验证语义聚类的稳定性。

表1纵向比较的结果显示，SSRM在所有测试集上得到的MAP值均高于RM和SRM，MAP性能最少提高了32.11%和0.41%。例如在AP测试集，使用SSRM得到的MAP值为0.3431，相对RM的MAP值0.25，在性能上提升了37.24%；相对SRM的MAP值0.3345，在性能上提升了2.57%。

表1中SSRMMAP值的提高验证了经过稳定性验证的语义聚类更好过滤了用户查询无关的噪声，因而估计的相关模型更接近用户查询的实际需求，从而提高了MAP性能。同时也观察到，并非所有MAP值都是显著性提高的。例如对于AP测试集，SSRMMAP值提高只对RM是显著性提高，而对SRM的提高是非显著的；但是对于SJMN和FT测试集，SSRM相对RM和SRM在MAP值上的提升都是显著性的。这说明SJMN和FT测试集中主题噪声影响了相关模型的估计，但SSRM能够有效过滤这两种测试集中的噪声，因而带来的MAP提升是显著性的。

测试集FT和LA每个主题对应的真实相关文档在TREC五个数据集中最少[8]，但SSRM在这两个测试集上相对其他三个测试集的MAP性能提升最大。这进一步验证了SSRM能够较好过滤数据集中用户查询不相关噪声，使稳定性语义聚类中的文档查询相关，并远离查询不相关主题。在AP和WSJ两个测试集上，SSRM对MAP性能的提升有限，其原因可能是两个数据集中的文档包含多个语义主题，使用ICA算法很难将多语义主题文档划分到合适的语义类别中。这说明利用ICA算法进行稳定性语义聚类，对于多个语义主题的文档效果有限。由表1还可以观察到，SSRM的MAP值离性能上界还存在不小差距，说明基于稳定性语义聚类估计出的相关模型在MAP性能上还有改进空间。

4.3 四种聚类方法性能横向比较

横向比较的三种基于聚类的方法为：基于聚类方法（CBDM）、基于LDA的方法（LBDM）和重采样（Resampling）方法。比较的原因是：这三种方法是信息检索中比较典型的方法，同时三种方法没有作稳定性聚类验证工作，可以对比验证SSRM的性能。表2中三种基于聚类的方法的MAP值均来源于文献[1-2，15]的数据。

表2显示，SSRM在测试集上相比三种基于聚类方法的MAP性能改善明显。相比三种基于聚类的检索方法，MAP性能至少提高了23.64%，19.59%和8.03%。由于SSRM采用ICA算法进行语义聚类，并对语义聚类进行了稳定性验证，这说明ICA算法相比其他三种聚类方法在语义聚类上的效果更好，特别是经过语义聚类稳定性验证后估计的相关模型，在语义上更接近用户查询，是提升MAP性能的主要原因。

图1显示了SSRM、RM、SRM三种相关模型和检索上界UP在AP训练集和5个测试集上检索的准确率召回率曲线的比较情况。可以看出，无论在训练阶段还是在测试阶段，SSRM总是获得比RM明显好的检索性能。通常情况下，SSRM也能得到相对SRM好的检索性能。检索性能的改善证明了语义聚类经过稳定性验证后，更好地将查询相关的文档聚在一起，因此SSRM方法较SRM方法使用更多的真实相关文档参与相关模型估计，而RM方法直接使用前N个查询结果文档估计相关模型，带入了较多的不相关噪声。

图1显示，在WSJ和FT测试集上，在高召回率一端，SSRM比RM的检索性能稍差；同时，SSRM在AP和WSJ测试集上相比SRM提升的检索性能有限，甚至在低召回率一端，SSRM的检索性能比SRM还差。显示表明，SSRM在召回率的中前段对检索性能的提升最明显。

图1中SSRM的检索性能同性能上界有很大差距。由于性能上界由真实的相关文档估计的相关模型得到，这个差距说明通过数据聚类的方法不能完全获取相关模型估计需要的真实相关的反馈文档，同时也说明SSRM方法有较大的提升空间。一个解决思路是如何更好地选择主题相关文档，将聚类粒度放到段落或句子层次而不是整个文档上。

5 结语

本文研究了ICA语义聚类稳定性验证对相关模型估计的影响及其对检索性能的改善效果。研究发现，语义聚类经过稳定性验证后，能够更好地将查询相关的文档聚在一起。

利用语义聚类的适合度筛选出和用户查询最相似的语义聚类，并以筛选出的语义聚类为文档和查询间的桥梁，估计出的稳定性语义聚类模型（SSRM）能够改善检索性能。由于不相关噪声会使相关模型估计中出现偏离用户查询主题的问题，SSRM有效利用了稳定性语义聚类的噪声过滤功能，因而SSRM更接近用户的查询需求。另外，SSRM相比基于聚类方法的检索性能提升，也说明ICA算法是一种适合的语义聚类算法。

研究发现对于多主题文档，文档级别上的语义聚类很难将其划分到合适的类别中。将来的工作考虑段落或者句子粒度上的聚类，并做聚类的稳定性验证工作。另外，如何根据不同数据集学习适合数据集的训练参数，也是一个值得研究的问题。

参考文献：

[1]LIU X， CROFT W B. Clusterbased retrieval using language models[C]// Proceedings of the 27th International Conference on Research and Development in Information Retrieval. New York： ACM， 2004：186-193.

[2]LEE K S， CROFT W B， ALLAN J. A clusterbased resampling method for pseudorelevance feedback[C]// Proceedings of the 31st International Conference on Research and Development in Information Retrieval. New York： ACM， 2008：235-242.

[3]NASIR J A， VARLAMIS I， KARIM A， et al. Semantic smoothing for text clustering[J]. KnowledgeBased Systems， 2013， 54（4）： 216-229.

[4]ALSULAMI B S， ABULKHAIR M F， ESSA F A. Semantic clustering approach based multiAgent system for information retrieval on Web[J]. International Journal of Computer Science & Network Security， 2012， 12（1）：41-44.

[5]HOFMANN T. Probabilistic latent semantic indexing[C]// Proceedings of the 22nd International Conference on Research and Development in Information Retrieval. New York： ACM， 1999：56-73.

[6]HYVARINEN A. Survey on independent component analysis[J]. Neural Computing Surveys， 1999， 2（7）：1527-1558.

[7]HIMBERG J， HYVARINEN A， ESPOSITO F. Validating the independent components of neuroimaging timeseries via clustering and visualization[J]. Neuroimage， 2004， 22（3）： 1214-1222.

[8]PU Q， HE D. Pseudo relevance feedback using semantic clustering in relevance language model[C]// Proceedings of the 18th ACM International Conference on Information and Knowledge Management. New York： ACM， 2009：1931-1934.

[9]蒲强，何大庆，杨国纬.一种基于统计语义聚类的查询语言模型估计[J].计算机研究与发展，2011，48（2）：224-231.（PU Q， HE D Q， YANG G W. An estimation of query language model based on statistical semantic clustering [J]. Journal of Computer Research and Development， 2011， 48（2）： 224-231.）

[10]刘家辰， 苗启广， 宋建锋. 使用聚类稳定性分析方法增强单类学习算法[J]. 西安电子科技大学学报（自然科学版）， 2015， 2（2）：58-64. （LIU J C， MIAO Q G， SONG J F. Enhanced oneclass learning based on clustering stability analysis[J]. Journal of Xidian University （Natural Science）， 2015， 42（2）： 58-64.）

[11]LAVRENKO V， CROFT W B. Relevancebased language models[C]// Proceedings of the 24th International Conference on Research and Development in Information Retrieval. New York： ACM， 2001：120-127.

[12]刘铭，刘秉权，刘远超.面向信息检索的快速聚类算法[J].计算机研究与发展，2013，50（7）： 1452-1463.（LIU M， LIU B Q， LIU Y C. A fast clustering algorithm for information retrieval [J]. Journal of Computer Research and Development， 2013， 50（7）：1452-1463.）

[13]张永，浮盼盼，张玉婷.基于分层聚类及重采样的大规模数据分类[J].计算机应用， 2013， 33（10）： 2801-2803.（ZHANG Y， FU P P， ZHANG Y T. Largescale data classification based on hierarchical clustering and resampling[J]. Journal of Computer Applications， 2013， 33（10）： 2801-2803.）

[14]KOLENDA T， HANSEN L K， SIGURDSSON S. Independent components in text[J]. Perspectives in Neural Computing， 2000， 32： 235-256.

[15]WEI X， CROFT W B. LDAbased document models for Ad Hoc retrieval[C]// Proceedings of the 29th International Conference on Research and Development in Information Retrieval. New York： ACM， 2006：178-185.