基于控制词集的中文信息动态自动聚类研究，本文主要内容关键词为：中文论文,动态论文,信息论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
1 导言
动态自动聚类，是一种在用户检索提问的基础上，对检索返回的结果进行多层次自动聚类的新型检索优化技术。这一方式结合检索排序技术，可以有效揭示检索返回资源的主题内容，是自动聚类技术在网络环境下的一种应用。国外不少网络检索工具，如Vivisimo[1] 等就使用了这一技术。
动态自动聚类技术的发展，是网络关键词检索系统实用需要的结果，同时也是对海量数字信息环境下新分类法形式的一种探索。随着研究的深入，它必然可以与海量数字信息环境下的各种应用，如知识挖掘、数据分析等结合，成为信息资源开发利用的利器，具有巨大发展潜力，值得引起重视。为了探索动态有限环境下中文信息聚类的规律，发展适用于中文使用的动态自动聚类方法系统，我们建立一个专用实验数据库（CDCS），该库收入约2万条经济领域期刊资源的基本数据， 以及一定数量以网页资源为对象的检索返回数据，在此基础上对中文动态自动聚类方法进行了试验。根据中文系统的特点，系统直接以收录基本概念为基础的词及词组的专用词典作为切分工具；引入词汇控制的方法，并结合规则系统优化聚类结果；试图通过试验，建立起一种以概念为基础的、具有主题分类特点的、中文动态自动聚类的方法系统，从而推进中文信息动态自动聚类实践的发展。
2 相关工作
最早将聚类方法引入文献检索，改进检索有效性的是Salton（1968）[2]。1973年，S.E.Preece[3] 首次提出将倒排文档检出的文献集作为聚类对象，为文献自动聚类研究提出了一个新的思路。进入上世纪90年代后，随着网络的使用和检索优化的需要，动态自动聚类方法逐步受到重视。1993年，R.B.Allen,P.Obry和M.Littman[4] 采用Scatter／Gather方法，通过在检索过程中与用户交互，结合使用动态聚类，用以改进检索效果。其后，许多学者对基于检索返回结果的聚类技术进行了一系列探讨。比较典型的如，1996年M.A.Hearst和J.O.Pedersen[5]，A.V.Leouski和W.B.Croft[6] 等对动态聚类方法以及聚类结果有效性的探讨；2001年Anastasios Tombros、Robert Villa、C.J.Van Rijsbergen等[7] 对传统聚类方法在动态环境下应用效果的研究；1998、1999年O.Zamir和O.Etzioni[8][9] 以及2004年我国学者曾华军（音译）等[10] 对适合英文文献的新的聚类依据、聚类策略的探索等。
文献聚类研究多数以文献中的词汇作为测度依据。传统测度是将文献作为词集对待，结合考虑词频、词位等因素，通过计算两文献之间词汇的重叠程度，衡量资源的相似性。影响较大的一种相似性测量方法是余弦系数测量，该测量将每篇文献看作由n个关键词构成的n维空间向量。通过计算两文献向量夹角的余弦，作为确定文献之间相似度的系数。常用的相似性测量公式还有Dice系数和Jaccard系数等。试验表明，不同测量算法可能影响聚类结果，但学界对何种系数更优并无一致意见，有学者认为通常可依据其中最简单、适合的系数进行处理[11]。一种在动态聚类研究中逐步受到重视的新的相似性测量方式，则是直接将专指性短语作为揭示类目相似性的依据，并通过多种方法加以优化。这类测量不计算文献的整体相似度，只计算文献之间作为聚类依据的短语这一变量的相似度。它有利于改进对文献主题内容的揭示，是近年来出现的一种在有限对象环境中使用的相似性测量方式。
在聚类策略上， 传统聚类方式重视在资源对象相似性基础上采用贪婪法（greedy）聚类，其中尤以等级聚合聚类法（agglomerative hierarchical clustering（AHC）algorithms）使用最多，最常用的有单链法、近邻法等。这些聚类策略可以根据文献相似性建立起一个系统类图，使所有文献按相似性关系组织，且十分稳定。其不足是，计算开销较大，如以O表示聚类文献数，n表示文献中词数，则单链法的计算复杂性为O（n[2]），全链法为O（n[3]）；同时，使用这一方法，一种资源通常只能归入一个对应类，对多主题文献揭示有一定局限性；此外，由于不是以主题内容为中心聚类的，聚类结果并不必然符合主题检索的特点。与传统聚类方式对应的是线性聚类方式。常用的有单遍法（single-pass）、K-means 法、Buck-shot和Fractation[12] 法、后缀树聚类法[13] 等。前几种方法的不足是，它们同样不是以主题为中心的，同时存在一定程度的次序或选择依赖。后缀树法则本质上是以n-gram法的方式，通过在文本中发现的短语聚类，有利于以主题短语为中心聚类，但仅使用这一方式较难将聚类操作上升到语义层面，无法充分结合词汇控制进行各种处理。目前西方使用动态自动聚类的英文搜索引擎，如Vivisimo、iboogie[14]、Mooter[15]等，因其商业性原因，未对聚类算法加以说明。但就其聚类结果看，多数是以线性方式进行聚类的。
比较而言，国内由于中文特点等原因，对中文信息的自动聚类研究较少。直到近年来，才出现了少量以中文文献为对象的动态自动聚类研究和探索。比较典型的有，2001年王爱华等的PCCS部分聚类分类研究试验[16]，2004年孙学刚等基于主题的文档聚类研究[17] 等。这些研究采用借鉴国外方法并加以改进的方式，重视将主题因素引入聚类，力图优化处理效果。两个系统基本上都将聚类过程分解为两个阶段，第一阶段进行简单聚类和主题发现，第二阶段再依据相应算法聚类，方法类似K-means；在中文词汇的识别上，均以通用切分词典为工具。但算法复杂度仍较高，同时，使用通用性切分词典，在类名表达效果上受到一定影响。
国内外的研究表明，动态环境下的自动聚类应根据其自动聚类条件的变化，选择适用的方法进行，同时，中文系统还应对切词方法作出选择。通过分析，我们决定直接以专用词典为切分工具，以专指词汇为中心聚类，同时引入词汇控制的方法，结合规则系统优化聚类结果。
3 控制词集的建立
本系统中控制词集的主要功能为：①切分工具。代替普通切分词典，直接从文献中抽取表达文献主题内容的语词，并通过一定的控制对语词切分加以优化。②聚类依据。由于专业词汇，特别是专用词组往往能在一定程度上反映文献的内容，因此可以在词典的基础上，直接依据收入的词汇聚类。③对聚类结果加以优化。结合控制词集，对一词多义、多词一义现象，词汇中存在的等级关系等进行必要的控制，从而将知识结构引入系统，改进聚类效果。④类名表达。与一般切分词典中的词相比，它们能更加专指、确切地揭示类目的主题含义，同时还可以通过词表中的等同控制机制，选择通用、科学、规范的语词进行表达。
与归类系统使用的控制词集不同，本词集不受任何预先建立的分类系统影响。根据动态聚类处理的需要，控制词典编制过程中，在依据多个来源对词汇进行收集和预处理的同时，还对词汇进行了同义处理、等级处理等。本词集具有以下特点：
3.1 词汇收集充分，重视自然语言词汇的收集。
除收入各种来源的主题词、关键词外，还根据抽词需要收入了大量文本语词形式，包括：①收入自然语言中各种常见词汇和概念表达形式，并建立起其与相应语词的对应关系，以便为同义关系处理提供条件。如收入“国土资源大调整”，并标注“国土资源调整”。②收入一部分必要的错误词汇形式，同时标注对应的规范词，以便提高词表“容错”能力。如“供应琏”应为“供应链”。③保留部分具有一定长度，且存在交叉概念关系的词组。如“管理规范化和科学化”的确切含义为“管理规范化”、“管理科学化”，但一般切词方案只能切出“管理规范化”和“科学化”，不能准确反映其完整含义。保留这类词，有助于解决这类词组中包含概念的充分揭示问题。④收入一定数量的英文词汇。包括具有特定内涵的缩略语和使用频率较高的英文单词，如GIS、Internet等。此外， 剔除没有检索价值的词或语义含糊的词，如“敏捷”、“显著”等。
3.2 结合文本处理的需要进行等同关系处理
进行等同关系控制的目的，是避免将同一主题的文献分散在不同的词下，以便在概念基础上聚类。综合考虑各方面情况，本系统将等同控制的对象，主要确定为同义词、反义词两类，近义词暂不收入，等级关系词则在等级关系表中解决。本系统中同义关系与传统词表的不同之处在于，作为一种文本抽词工具，需要结合自然语言词汇中各种表达形式进行处理，比传统词表的同义控制类型更为多样。除传统控制词表的各种同义词类型，如语义同义词、学名与俗称、新称与旧称等以外，还包括：文本表述与相应概念的词汇之间，如“技术成果的产业化”与“技术成果产业化”；不同数字年代之间，如“1999”与“一九九九”；部分英文大小写之间，如“WTO”与“wto”；部分包含常见错别字的词与规范词之间，如“供应琏”与“供应链”；部分具有交叉概念关系的词组与对应概念的词汇之间，如“中小民营企业信息化”与“中小民营企业”、“企业信息化”；多个对应分称与统称词之间，如“黑龙江、吉林、辽宁”与“东北地区”等。这类方式是文本抽取的需要决定的，有助于增强词表在聚类过程中的语词识别和容错能力。系统采用多种方式解决同义词识别问题，包括结合字面相似算法进行识别，结合各种词汇特征进行识别，结合相关工具识别等。为避免在同义词识别中出现歧义，对可能引起误解的词不予处理，并根据显示需要选择合适的规范词。
3.3 按照分类系统特点进行等级关系控制
基本做法是：①根据分类法中上下位类涉及的关系类型确定等级控制范围。本词集等级关系控制的对象除从属关系、整部关系词汇外，还包括事物与方面关系的词汇。如“资源”与“资源开发”、“资源利用”等，均作为等级关系处理。②一词可同时与两个或多个词建立等级关系。如“西部旅游资源”同时从属于“西部资源”和“旅游资源”。③进行多个等级层次的揭示，但在显示时，只反映邻近词之间的上下位关系。如资源、旅游资源、西部资源、西部旅游资源这组存在多个层次等级关系的词汇，在控制词集中只建立“资源——西部资源”，“资源——旅游资源”，“旅游资源——西部旅游资源”等显示形式，而“资源——西部旅游资源”这一非直接等级关系则通过推导产生。对等级关系的处理根据许多等级关系词汇中存在的字面包含关系现象，采用人机结合的方式处理，并结合多种方式补充。
3.4 根据聚类的需要，对词汇进行必要的识别处理
主要是对通用词进行标注。所谓通用词，是指没有独立检索意义，只起辅助检索作用的词，如“问题”、“方法”等。这类词虽然具有限制检索范围的作用，但由于使用范围广，组配能力强，容易出现歧义或搭配错位。因此，需要对这类词加以标注，以期结合聚类算法合理应用。
根据收词特点和计算机环境下词汇控制的需要，本控制词集由关键词表、等同控制词表、等级词表等一系列词表组成，并通过相应程序一体化使用。图1 为等级词表的样例。其中“Keywords”为关键词；“dengji”为等级词，收录关键词的上位类词。通过这一方式，来揭示相关词之间的等级关系。
4 聚类方法
动态自动聚类有别于传统的以全局性资源为对象的静态聚类，是一种在动态有限环境中进行的实时聚类，其主要特征为：①聚类是动态进行的，是在检索返回基础上进行的实时操作。②每次聚类处理的数量有限，通常只处理检索返回时排列在前的一定数量文献。③参与聚类的资源在整个资源集合中的分布不是固定的，没有预先设定的类目框架可以套用。④虽然本系统的每一次聚类都是以有限资源为对象的，但作为一种聚类方法，应能适用于各种可能出现的情况，具备根据不同对象、特点随时进行聚类的能力。
为了满足上述特点，本系统使用的聚类方案为：①采用以主题为中心的聚类方式。依据相应语词聚类，方便对特定主题对象的揭示，使聚类结果揭示充分，同时结合同义控制等措施，实现在概念层次上聚类。②采用等级聚类形式。这种形式有利于有层次地展示资源的内容，方便用户浏览。③多维聚类、重复反映。以便充分揭示文献主题以及类目之间的关系，使得多主题文献能够在相应门类得到重复揭示，同时在各个层次的类目下，所有子类或资源都能够得到完整显示。④类名规范，能确切表达类目的含义。通过控制词集中对词汇的选择和处理，使类名准确、适合使用。⑤较强的聚类灵活性。即要求聚类算法能根据情况的变化，对聚类条件适当进行调整，以改进聚类的适用性。⑥优化聚类算法。选用计算开销较小的算法聚类，简化聚类操作，使聚类时间保持在可以接受的范围内。
本系统直接依据专用词典抽词，选择逆向最大匹配单次切分法进行切分。系统的加权策略，主要采用词频加权法、词位加权法和反文献频率法等。聚类处理分为基本聚类操作和结合控制词集对聚类进行优化两个方面。
其中，基本聚类操作的步骤为：①首先将含有同一个词的文献看作一个初始类；②对初始类文献进行删选，排除类词权重低于阈值的文献；③设定类目文献数量范围，确定设类起始数量，并依据反文献频率等限定聚类最大文献值；④根据权值确定类目排列次序。对二级类的再次聚类，可重复这一过程。聚类层次限定为三级。
上述基本聚类步骤，处理简单、易于操作，并具有算法开销小、聚类时间短、形成类目结果稳定等特点，但同时也存在明显不足，主要是：①未进行等同关系控制，因而会出现相同主题文献分散的现象。②有可能出现逻辑关系混乱的现象。按主题中心聚类虽然并不十分强调聚类结果的系统性，但类目之间的等级关系是客观存在的，如不加必要的控制，有可能在类目之间出现违背基本逻辑关系的现象。③一些以通用词为中心形成的类目，内容对象往往比较分散。④对不同主题类目之间存在的文献交叉、重合现象，也有必要加以适当的控制。
对于上述各种可能出现的问题，本系统在依据控制词集的同时，结合使用相应算法予以解决，包括：
4.1 等同关系控制
主要解决缺乏同义控制等造成的相同主题文献的离散问题，实现在概念基础上聚类。系统主要通过控制词集予以解决，包括使用等同控制和结合使用等级控制两种情况。对一般的等同关系控制，系统直接依据其中的等同控制词表进行，在使用词典完成抽词后，将所有抽出的关键词转换为对应的规范词，并统一按规范词计算权重，在这一基础上实施聚类。对涉及组配关系的对应词，则同时按指定的分解词分别进行聚类操作，方法类似一般的同义词。至于等级关系词在一定条件下按等同关系处理的问题，系统则结合等级词表，在等级关系控制的过程中根据资源情况动态解决。
4.2 等级关系控制
如前所述，本系统的聚类结构，基本上是一种以语词（概念）为中心建立的具有主题分类特点的等级分类结构。在这一系统中，类目之间主要存在着包括并列关系和等级关系两种关系类型。一般情况下，以这一方式建立的类目体系中，类目设置的限制较少。并列类可以由同一个主题类下多种主题关系的类目构成，包括各个不同层面、不同角度的类、相关概念类等；在上下位类中，则基本上是一种组配关系，可以是等级关系，也可以是十分松散的关系，如相关关系，甚至不相关关系等。但也有一些基本的逻辑关系仍不应违背。常见的应予控制的等级关系情况包括：上、下位概念颠倒现象，同位类中同时，出现具有等级关系含义的类目等。后者如，在同位类中同时出现“市场经济”和“社会主义市场经济”这样两个概念上存在包含关系的类目。此外，还存在着专指词不能聚类的情况下，依据其上级概念词动态聚类，以增强系统聚类能力等问题。在人工建立的系统中，这类控制通常是一个根据资源情况的变化，进行动态调整的过程。因此要在动态聚类中有效处理好等级关系，一般需根据聚类过程中资源的情况，按照控制词集中的等级结构，结合相应的算法加以处理。
本系统中对等级关系控制的基本规则可以描述为：
如果 上级类词下的资源数量大于类数量的下限
则下级类并入该类
否则 如果上级类词资源和所有下级类词资源数量均小于类数量的下限
则该下级类词参加上级类词的聚类
按照这一处理规则，为避免在同位类中同时出现具有等级关系含义的类目，当上位概念词类和下位概念词类作为同位类出现，且两者都符合聚类条件时，将下位概念类合并入上位概念类下；当上位概念词、下位概念词均小于聚类标准时，则将下位概念词并入上位概念词，以增强上位概念词的聚类能力。通过这一处理，就可以动态、灵活地解决聚类过程中的逻辑控制和等级调整的问题。
系统同时并为聚类过程中出现多级概念词类和跨级概念词类等情况制订了相应规则。
4.3 合并重合度高的类
这是由于一篇文献往往同时涉及多个主题概念的情况造成的。合理解决交叉类，有利于通过合并多属性类，减少类目的数量，增加聚类的整体性。重合度阈值设置时考虑的因素，通常应包括合并处理后类的质量以及重合带来的类目数量的影响。重合度阈值设置过低，会使同类文献相对分散；重合度阈值设置过高，则会使总体类目数量过多，影响类目体系的整体性，因此通常应根据试错法确定。同时，在进行合并处理时，还应根据情况对类名进行必要的调整，如适当使用相应词并列显示。
此外，系统还依据通用词形成的类独立检索意义相对比较小，与相应上位主题对象联系的强度较低的特点，对通用词的聚类条件作出相应控制。
5 系统设计
根据实验系统的需要，系统首先建立期刊资源、网页资源的文本检索试验库，编制抽词词表和控制词表，而后在库中进行检索和动态聚类试验，改进算法。系统使用Visual Foxpro 6.0实现，用表存储各种数据，通过建立过程，使用VFP内部函数、临时表等实现切分、检索、聚类等算法。利用VFP可视化的界面设计工具，VFP自带控件和ActiveX控件等完成用户界面。
根据动态聚类的操作流程，系统整体分为检索、切分、聚类三个模块。其中检索部分采用加权布尔检索。抽词以专用词典为工具，采用逆向最大匹配切分法。聚类模块是系统的核心，由一级聚类、二级聚类、三级聚类、等级处理和合并处理5个子模块组成。其中一、二、三级聚类主要实现以词为中心的基本聚类算法和同义词控制，建立等级结构。等级处理、合并处理子模块是一、二、三级聚类的共用模块。等级处理模块依据控制词集对等级结构进行优化，合并处理子模块对重合度高的同位类进行合并处理。系统还在实验过程中根据需要设置了检索界面、聚类界面、聚类结果显示界面、相关信息显示界面等，以便对数据进行试验调整。图2即为本系统聚类模块程序的流程图。
图2 聚类模块流程图
6 评价与展望
本项目使用国外典型的评价函数和统计方法，选择涉及系统的基本性能指标和相关因素，结合使用期刊资源和网络资源两种资源类型，对系统聚类效果、类目分布、类目覆盖范围、多重聚类与多维揭示程度、基于词汇控制的聚类优化功能、二三次聚类效果、类目有效性与类名表达等，进行了统计分析和研究。从实验结果可以看出，系统整体上聚类功能良好，聚类的全面性、准确性、区分度、综合效果等各项指标达到了较好的水平，类目揭示充分，分布合理，覆盖范围广，取得了较好的效果。
实验显示：依据主题概念为中心建立的分类主题形式，适应性强，有利于充分揭示返回文献的主题，符合动态聚类的需要；使用经过控制的专用词集作为抽词工具，有利于提高抽词的有效性，改进切分的效果；依据控制词集进行词汇控制，有助于通过等同关系控制、等级关系控制等，显著改进聚类效果；结合动态环境中聚类文献数量的变化，对等级关系词表进行动态应用，可以在一定程度上改进系统的聚全率和聚准率；等级聚类、多维揭示的方法，有助于类目体系的展开更为完备；采用线性聚类算法，聚类速度快，基本上可以满足中文自动聚类的需要。
图3 动态自动聚类实验系统界面
除了需要不断完善已有技术方法外，在本项目研究的基础上可以进一步研究的问题包括：①将本研究扩大到其他领域，探索在超越特定专业领域的情况下，词汇控制的规律和方法。②进一步将近义词、相关词纳入词汇控制的范围，探索近义词相关词识别和处理的方法，研究其在动态有限环境下自动聚类的特点与规律，发展相应的规则系统，以改进自动聚类的灵活处理能力。③探索在动态聚类过程中引入既有知识系统的可能性。目前在知识组织研究中形成了多种知识组织系统，包括分类法、ontology等，如何将这类智力成果引入动态自动聚类系统，用于改进聚类效果，是今后动态自动聚类研究应当考虑的课题。
收稿日期：2006年3月1日