著录项信息
专利名称 | 聚类方法及装置 |
申请号 | CN200910089176.8 | 申请日期 | 2009-08-03 |
法律状态 | 授权 | 申报国家 | 中国 |
公开/公告日 | 2011-03-23 | 公开/公告号 | CN101989281A |
优先权 | 暂无 | 优先权号 | 暂无 |
主分类号 | G06F17/30 | IPC分类号 | G;0;6;F;1;7;/;3;0查看分类表>
|
申请人 | 中国移动通信集团公司 | 申请人地址 | 北京市西城区金融大街29号
变更
专利地址、主体等相关变化,请及时变更,防止失效 |
权利人 | 中国移动通信集团公司 | 当前权利人 | 中国移动通信集团公司 |
发明人 | 孙宏伟;胡珉;罗治国 |
代理机构 | 北京同达信恒知识产权代理有限公司 | 代理人 | 郭润湘 |
摘要
本发明公开了一种聚类方法,用以解决现有技术提供的检索结果聚类方法难以生成可读性较好的聚类标签的缺陷,该方法包括:根据预设的选取策略,从待聚类的各个文档中选取第一候选字串集合;针对第一候选字串集合中的各字串,根据与该字串相关的参数,从第一候选字串集合中选取第二候选字串,所述与该字串相关的参数为该字串出现在待聚类的所有文档中的总次数、该字串出现在指定文档中的总次数、该字串包含的字符个数以及待聚类的文档中包含该各字串的文档个数中的至少一个参数;将第二候选字串确定为对所述待聚类的各个文档进行聚类的聚类标签,并将待聚类的各个文档分别归类到与所述聚类标签对应的簇中。本发明还公开了一种聚类装置。
1.一种聚类方法,其特征在于,包括:
根据预设的选取策略,从待聚类的各个文档中选取第一候选字串集合;
针对所述第一候选字串集合中的各字串,根据与该字串相关的参数,从所述第一候选字串集合中选取第二候选字串,所述与该字串相关的参数为该字串出现在所述待聚类的所有文档中的总次数、该字串出现在指定文档中的总次数、该字串包含的字符个数以及所述待聚类的文档中包含该各字串的文档个数中的至少一个参数;
将所述第二候选字串确定为对所述待聚类的各个文档进行聚类的聚类标签,并将所述待聚类的各个文档分别归类到与所述聚类标签对应的簇中;
其中,根据预设的选取策略,从待聚类的各个文档中选取第一候选字串集合具体包括:
从待聚类的各个文档所包含的字串中,选取字串包含的字符个数与预设的第一字符个数阈值一致的字串;
从所述选取的字串中选取符合预设规则的第一候选字串集合,所述预设规则为以下规则中的任意一种或为以下规则的任意组合:
针对所述第一候选字串集合中的各字串,包含该字串的所述待聚类的文档的个数不小于预设的第一阈值;
针对所述第一候选字串集合中的各字串,在所述待聚类的各个文档中,与该字串相邻、位于该字串之前、且包含的字符数目与预设的第二字符个数阈值一致的不同字串的个数不小于预设的第二阈值;
针对所述第一候选字串集合中的各字串,在所述待聚类的各个文档中,与该字串相邻、位于该字串之后、且包含的字符数目与预设的第二字符个数阈值一致的不同字串的个数不小于预设的第三阈值;
针对所述第一候选字串集合中的各字串,该字串出现在所述待聚类的所有文档中的总次数除以该字串包含的各字符出现在所述待聚类的所有文档中的总次数所得的数值不小于预设的第四阈值。
2.如权利要求1所述的方法,其特征在于,针对所述第一候选字串集合中的各字串,根据与该字串相关的参数,从所述第一候选字串集合中选取第二候选字串具体包括:
针对所述第一候选字串集合中的各字串,根据该字串出现在所述待聚类的所有文档中的总次数、该字串出现在指定文档中的总次数、该字串包含的字符个数以及所述待聚类的文档中包含该各字串的文档个数,采用下述公式计算该字串的重要度Score:
其中,word.tf为该字串出现在所述待聚类的各个文档中的总次数,word.normtf为该字串出现在所述指定文档中的总次数,word.df为包含该字串的所述待聚类的文档个数,word.length为该字串包含的字符个数;
在计算出所述第一候选字串集合中各字串的重要度Score后,根据所述重要度Score,从所述第一候选字串集合中选取第二候选字串。
3.如权利要求2所述的方法,其特征在于,还包括:
按照所述确定的聚类标签的重要度Score由大至小的顺序,对所述确定的聚类标签进行对应排列。
4.如权利要求1或2所述的方法,其特征在于,采用多模式匹配的方法,将所述待聚类的各个文档分别归类到与所述聚类标签对应的簇中。
5.如权利要求1或2所述的方法,其特征在于,还包括:
针对所述确定的聚类标签中的各聚类标签,确定该聚类标签出现在所述待聚类的所有文档中的总次数,并按照各个所述确定的总次数由多至少的顺序,对所述确定的聚类标签进行对应排列;或
针对所述确定的聚类标签中的各聚类标签,确定包含有该聚类标签的所述待聚类的文档个数,并按照各个所述确定的文档个数由多至少的顺序,对所述确定的聚类标签进行对应排列;或
按照所述确定的聚类标签分别被用作搜索引擎所使用的查询词的频率由高至低的顺序,对所述确定的聚类标签进行对应排列,其中,所述待聚类的文档为通过搜索引擎搜索到的搜索结果。
6.一种聚类装置,其特征在于,包括:
第一选取单元,用于根据预设的选取策略,从待聚类的各个文档中选取第一候选字串集合;
第二选取单元,用于针对第一选取单元选取的第一候选字串集合中的各字串,根据与该字串相关的参数,从所述第一候选字串集合中选取第二候选字串,所述与该字串相关的参数为该字串出现在所述待聚类的所有文档中的总次数、该字串出现在指定文档中的总次数、该字串包含的字符个数以及所述待聚类的文档中包含该各字串的文档个数中的至少一个参数;
标签确定单元,用于将第二选取单元选取的第二候选字串确定为对所述待聚类的各个文档进行聚类的聚类标签;
归类单元,用于将所述待聚类的各个文档分别归类到与所述标签确定单元确定的聚类标签对应的簇中;
其中,所述第一选取单元具体包括:
第一选取模块,用于从所述待聚类的各个文档所包含的字串中,选取字串包含的字符个数与预设的第一字符个数阈值一致的字串;
第二选取模块,用于从第一选取模块选取的字串中选取符合预设规则的第一候选字串集合,所述预设规则为以下规则中的任意一种或为以下规则的任意组合:
针对所述第一候选字串集合中的各字串,包含该字串的所述待聚类的文档的个数不小于预设的第一阈值;
针对所述第一候选字串集合中的各字串,在所述待聚类的各个文档中,与该字串相邻、位于该字串之前、且包含的字符数目与预设的第二字符个数阈值一致的不同字串的个数不小于预设的第二阈值;
针对所述第一候选字串集合中的各字串,在所述待聚类的各个文档中,与该字串相邻、位于该字串之后、且包含的字符数目与预设的第二字符个数阈值一致的不同字串的个数不小于预设的第三阈值;
针对所述第一候选字串集合中的各字串,该字串出现在所述待聚类的所有文档中的总次数除以该字串包含的各字符出现在所述待聚类的所有文档中的总次数所得的数值不小于预设的第四阈值。
7.如权利要求6所述的装置,其特征在于,所述第二选取单元具体包括:
计算模块,用于针对所述第一候选字串集合中的各字串,根据该字串出现在所述待聚类的所有文档中的总次数、该字串出现在指定文档中的总次数、该字串包含的字符个数以及所述待聚类的文档中包含该各字串的文档个数,采用下述公式计算该字串的重要度Score:
其中,word.tf为该字串出现在所述待聚类的各个文档中的总次数,word.normtf为该字串出现在所述指定文档中的总次数,word.df为包含该字串的所述待聚类的文档个数,word.length为该字串包含的字符个数;
选取模块,用于在计算模块计算出所述第一候选字串集合中各字串的重要度Score时,根据所述重要度Score,从所述第一候选字串集合中选取第二候选字串。
8.如权利要求6或7所述的装置,其特征在于,还包括:
次数确定单元,用于分别针对标签确定单元确定的聚类标签中的各聚类标签,确定该聚类标签出现在所述待聚类的所有文档中的总次数;
标签排列单元,用于按照次数确定单元分别确定的各个总次数由多至少的顺序,对所述确定的聚类标签进行对应排列;或者
还包括:文档个数确定单元,用于针对标签确定单元确定的聚类标签中的各聚类标签,确定包含有该聚类标签的所述待聚类的文档个数;
标签排列单元,用于按照文档个数确定单元确定的各个文档个数由多至少的顺序,对所述确定的聚类标签进行对应排列;或者
还包括:标签排列单元,用于按照标签确定单元确定的聚类标签分别被用作搜索引擎所使用的查询词的频率由高至低的顺序,对所述确定的聚类标签进行对应排列,其中,所述待聚类的文档为通过搜索引擎搜索到的搜索结果。
聚类方法及装置\n技术领域\n[0001] 本发明涉及信息检索领域,尤其涉及一种聚类方法及装置。\n背景技术\n[0002] 检索结果聚类,是指将搜索引擎搜索到的检索结果中类似的搜索结果聚集成簇的过程,其中,簇是一组彼此相似的检索结果的集合,相同簇中的检索结果彼此相似,而不同簇中的检索结果则往往彼此相异。检索结果聚类能够帮助用户更好的使用搜索引擎,比如,能够帮助用户更加快速的定位到需要的信息,或者能够帮助用户获取更加全面的信息等。\n[0003] 在现有技术中,已有的检索结果聚类方法主要分为两类:一类被称为基于文档(Documents-Based)的方法;而另一类被称为基于标签(Label-Based)的方法。所谓基于文档的方法是指首先通过传统的文档聚类方法,把文档聚集成多个类别,然后再从各类别中分别抽取出合适的聚类标签来标注各个类别,由于采用基于文档的方法往往不能生成可读性较好的聚类标签,不同聚类标签之间区分性较小,从而用户难以从区分性较小的各聚类标签中找到符合自己需求的检索结果,因此这一类方法只是在早期的检索结果聚类工作中使用较多;而基于标签的方法则是指首先从文档中抽取一些有代表性的词语,然后对抽取的词语进行合理的评价与筛选,并将经过评价和筛选处理后得到的不同词语作为对应于不同类别文档的聚类标签,从而后续可以以该不同类别的聚类标签为基础,进一步实现对文档的分类,在这类方法中,聚类标签的选取很关键,但按照现有技术中提供的聚类标签选取方式,同样很难得到可读性较好的聚类标签。\n[0004] 由上述可知,现有技术采用的各类检索结果聚类方法都存在着难以生成可读性较好的聚类标签,从而使得用户难以按照聚类标签找到符合自己需求的检索结果的缺陷。\n发明内容\n[0005] 本发明实施例提供一种聚类方法及装置,用以解决按照现有技术提供的检索结果聚类方法难以生成可读性较好的聚类标签的缺陷。\n[0006] 为此,本发明实施例采用以下技术方案:\n[0007] 一种聚类方法,包括:根据预设的选取策略,从待聚类的各个文档中选取第一候选字串集合;针对所述第一候选字串集合中的各字串,根据与该字串相关的参数,从所述第一候选字串集合中选取第二候选字串,所述与该字串相关的参数为该字串出现在所述待聚类的所有文档中的总次数、该字串出现在指定文档中的总次数、该字串包含的字符个数以及所述待聚类的文档中包含该各字串的文档个数中的至少一个参数;将所述第二候选字串确定为对所述待聚类的各个文档进行聚类的聚类标签,并将所述待聚类的各个文档分别归类到与所述聚类标签对应的簇中。\n[0008] 较佳地,针对所述第一候选字串集合中的各字串,根据与该字串相关的参数,从所述第一候选字串集合中选取第二候选字串具体包括:针对所述第一候选字串集合中的各字串,根据该字串出现在所述待聚类的所有文档中的总次数、该字串出现在指定文档中的总次数、该字串包含的字符个数以及所述待聚类的文档中包含该各字串的文档个数,采用下述公式计算该字串的重要度Score:\n[0009] \n[0010] 其中,word.tf为该字串出现在所述待聚类的各个文档中的总次数,word.normtf为该字串出现在所述指定文档中的总次数,word.df为包含该字串的所述待聚类的文档个数,word.length为该字串包含的字符个数;\n[0011] 在计算出所述第一候选字串集合中各字串的重要度Score时,根据所述重要度Score,从所述第一候选字串集合中选取第二候选字串。\n[0012] 较佳地,所述方法还包括:按照所述确定的聚类标签的重要度Score由大至小的顺序,对所述确定的聚类标签进行对应排列。\n[0013] 较佳地,根据预设的选取策略,从待聚类的各个文档中选取第一候选字串集合具体包括:从待聚类的各个文档所包含的字串中,选取字串包含的字符个数与预设的第一字符个数阈值一致的字串;从所述选取的字串中选取符合预设规则的第一候选字串集合,所述预设规则为以下规则中的任意一种或为以下规则的任意组合:针对所述第一候选字串集合中的各字串,包含该字串的所述待聚类的文档的个数不小于预设的第一阈值;针对所述第一候选字串集合中的各字串,在所述待聚类的各个文档中,与该字串相邻、位于该字串之前、且包含的字符数目与预设的第二字符个数阈值一致的不同字串的个数不小于预设的第二阈值;针对所述第一候选字串集合中的各字串,在所述待聚类的各个文档中,与该字串相邻、位于该字串之后、且包含的字符数目与预设的第二字符个数阈值一致的不同字串的个数不小于预设的第三阈值;针对所述第一候选字串集合中的各字串,该字串出现在所述待聚类的所有文档中的总次数除以该字串包含的各字符出现在所述待聚类的所有文档中的总次数所得的数值不小于预设的第四阈值。\n[0014] 较佳地,采用多模式匹配的方法,将所述待聚类的各个文档分别归类到与所述聚类标签对应的簇中。\n[0015] 较佳地,所述方法还包括:\n[0016] 针对所述确定的聚类标签中的各聚类标签,确定该聚类标签出现在所述待聚类的所有文档中的总次数,并按照各个所述确定的总次数由多至少的顺序,对所述确定的聚类标签进行对应排列;或针对所述确定的聚类标签中的各聚类标签,确定包含有该聚类标签的所述待聚类的文档个数,并按照各个所述确定的文档个数由多至少的顺序,对所述确定的聚类标签进行对应排列;或按照所述确定的聚类标签分别被用作搜索引擎所使用的查询词的频率由高至低的顺序,对所述确定的聚类标签进行对应排列,其中,所述待聚类的文档为通过搜索引擎搜索到的搜索结果。\n[0017] 一种聚类装置,包括:第一选取单元,用于根据预设的选取策略,从待聚类的各个文档中选取第一候选字串集合;第二选取单元,用于针对第一选取单元选取的第一候选字串集合中的各字串,根据与该字串相关的参数,从所述第一候选字串集合中选取第二候选字串,所述与该字串相关的参数为该字串出现在所述待聚类的所有文档中的总次数、该字串出现在指定文档中的总次数、该字串包含的字符个数以及所述待聚类的文档中包含该各字串的文档个数中的至少一个参数;标签确定单元,用于将第二选取单元选取的第二候选字串确定为对所述待聚类的各个文档进行聚类的聚类标签;归类单元,用于将所述待聚类的各个文档分别归类到与所述标签确定单元确定的聚类标签对应的簇中。\n[0018] 本发明实施例提供的一种聚类方案通过先根据预设的选取策略,从待聚类的各个文档所包含的字串中,选取第一候选字串集合;再针对该第一候选字串集合中的各字串,根据能够反映该字串出现在待聚类的所有文档中的频率、该字串的文档类别代表性等的相关参数,从第一候选字串集合中选取第二候选字串,其中,这些参数包括该字串分别出现在所述待聚类的所有文档中的总次数、该字串分别出现在指定文档中的总次数、该字串包含的字符个数以及待聚类的各个文档中包含该各字串的文档个数中的至少一个;将选取到的第二候选字串确定为对所述待聚类的各个文档进行聚类的聚类标签,并将所述待聚类的各个文档分别归类到与所述聚类标签对应的簇中,从而实现对聚类标签的确定以及对文档的聚类。由于本发明实施例在对聚类标签进行选取的过程中,针对该第一候选字串集合中的各字串,综合考虑了能够反映该字串出现在待聚类的各个文档中的频率以及该字串的文档类别代表性等的相关参数,使生成的聚类标签能够充分体现待聚类文档的类别,从而使确定的聚类标签具有较好的可读性。\n附图说明\n[0019] 图1为本发明实施例提供的一种聚类方法的具体流程示意图;\n[0020] 图2为将本发明实施例提供的一种聚类方法应用到对检索结果进行聚类的过程中的具体流程示意图;\n[0021] 图3为本发明实施例中搜索引擎所得到两个检索结果的具体示意图;\n[0022] 图4为本发明实施例提供的一种聚类装置的具体结构示意图。\n具体实施方式\n[0023] 本发明实施例提供了一种聚类方案,通过按照预设的选取策略以及能够反映字串出现在待聚类的所有文档中的频率和字串的文档类别代表性等的相关参数,从待聚类的各个文档所包含的字串中,选取作为对待聚类的各个文档进行聚类的聚类标签,从而使生成的聚类标签能够充分体现待聚类文档的类别,达到较好的可读性。\n[0024] 下面结合各个附图对本发明实施例技术方案的主要实现原理、具体实施方式及其对应能够达到的有益效果进行详细的阐述。\n[0025] 本发明实施例首先提供一种聚类方法,该方法的具体流程示意图如图1所示,包括以下步骤:\n[0026] 步骤11,根据预设的选取策略,从待聚类的各个文档中选取第一候选字串集合;\n[0027] 步骤12,针对第一候选字串集合中的各字串,根据与该字串相关的参数,从第一候选字串集合中选取第二候选字串,其中,与该字串相关的参数为该字串出现在待聚类的所有文档中的总次数、该字串出现在指定文档中的总次数、该字串分别包含的字符个数以及待聚类的各个文档中包含有该各字串的文档个数中的至少一个,需要解释的是,以对互联网中使用的搜索引擎得到的搜索结果进行聚类为例,上述的“指定文档”可以是指互联网中任意的网页,一般地,该指定文档可以是任意的十万或二十万个或其他数量(这里的数量一般较大)的网页,在该情况下,字串出现在该指定网页中的总次数越大,则说明该字串可能是网页中常用的字串;\n[0028] 步骤13,将选取的第二候选字串确定为对待聚类的各个文档进行聚类的聚类标签,并将待聚类的各个文档分别归类到与所述聚类标签对应的簇中。\n[0029] 针对上述步骤11,可以采用如下的步骤来实现根据预设的选取策略,从待聚类的各个文档中选取第一候选字串集合:\n[0030] 首先,从待聚类的各个文档所包含的字串中,选取字串包含的字符个数与预设的第一字符个数阈值一致的字串,针对汉语,若将汉语中的一个字看做是本发明实施例中所说的一个“字符”,则可以将上述第一字符个数阈值设置为2~6个,以符合汉语的语言习惯,而针对英文,若将一个词语看做是本发明实施例中所说的一个“字符”,则也可以将上述第一字符个数阈值设置为1~4个;\n[0031] 然后,再从上述选取到的字串中选取满足预设规则的第一候选字串集合,其中这里的预设规则可以但不限于为以下四种规则中的任意一种或任意多种的组合:\n[0032] 规则一:针对第一候选字串集合中的各字串,包含该字串的待聚类的文档的个数不小于预设的第一阈值,该规则一用于从上述选取到的字串中选取出字串出现频率较高从而具有较强的文档类别代表性的第一候选字串集合;\n[0033] 规则二:针对第一候选字串集合中的各字串,在待聚类的各个文档中,与该字串相邻、位于该字串之前、且包含的字符数目与预设的第二字符个数阈值一致的不同字串的个数不小于预设的第二阈值,若将上述的与该字串相邻、位于该字串之前、且包含的字符数目与预设的第二字符个数阈值一致的字串称为相邻前字串,则该规则二的作用在于选取出与该相邻前字串的相关性较低的字串作为第一候选字串集合;\n[0034] 规则三:针对第一候选字串集合中的各字串,在待聚类的各个文档中,与该字串相邻、位于该字串之后、且包含的字符数目与预设的第二字符个数阈值一致的不同字串的个数不小于预设的第三阈值,若将上述的与该字串相邻、位于该字串之前、且包含的字符数目与预设的第三字符个数阈值一致的字串称为相邻后字串,则该规则三的作用在于选取出与该相邻后字串的相关性较低的字串作为第一候选字串集合;\n[0035] 规则四:针对第一候选字串集合中的各字串,该字串出现在待聚类的所有文档中的总次数除以该字串包含的各字符出现在待聚类的所有文档中的总次数所得的数值不小于预设的第四阈值,该规则四的作用在于选取出字串包含的字符个数较少,且具有较强的文档类别代表性的第一候选字串集合。\n[0036] 较佳地,在本发明实施例中的步骤13中可以但不限于采用多模式匹配的方法,将待聚类的各个文档分别归类到与所述聚类标签对应的簇中,该多模式匹配的方法的具体执行过程为针对待聚类的文档中的各个文档,首先通过对该文档进行扫描确定出该文档中包含的聚类标签,然后再根据确定出的该文档包含的聚类标签,把该文档分别归类到不同的聚类标签对应的簇中。\n[0037] 此外,由于同一篇文档有可能会归入到不同聚类标签所对应的不同簇中,因此,为了能够方便地从某一聚类标签对应的簇中查找到需要的文档,可以考虑按照聚类标签的文档类别代表性来对聚类标签进行排序,具体地,本发明实施例可以进一步采用以下步骤对确定的各聚类标签进行排列:\n[0038] 首先,针对确定的聚类标签中的各聚类标签,确定该聚类标签出现在待聚类的所有文档中的总次数;\n[0039] 由于聚类标签在文档中出现的次数越多,越能表明该聚类标签具有较强的文档类别代表性,因此,可以按照确定的各个总次数由多至少的顺序,对确定的聚类标签进行对应排列。\n[0040] 或者,本发明实施例也可以进一步采用以下步骤对确定的各聚类标签进行排列:\n[0041] 首先,针对确定的聚类标签中的各聚类标签,确定该聚类标签的重要度Score;\n[0042] 由于聚类标签的重要度Score越大,越能表明该聚类标签具有较高的出现频率,且具有较强的文档类别代表性,因此,可以按照确定的各个重要度Score由大至小的顺序,对确定的聚类标签进行对应排列。\n[0043] 或者,本发明实施例还可以进一步采用以下步骤对确定的各聚类标签进行排列:\n[0044] 首先,针对确定的聚类标签中的各聚类标签,确定包含有该聚类标签的待聚类的文档个数;\n[0045] 由于包含有该聚类标签的待聚类的文档个数越多,说明该聚类标签具有较高的出现频率,因此可以按照各个确定的文档个数由多至少的顺序,对确定的聚类标签进行对应排列。\n[0046] 由于本发明实施例提供的该方案可以应用到对通过搜索引擎搜索到的搜索结果进行聚类的过程中,因此,本发明实施例提供的该方案既可以采用上述的任一排列方式对确定的聚类标签进行排列,也可以采用按照确定的聚类标签分别被用作搜索引擎所使用的查询词的频率由高至低的顺序,对确定的聚类标签进行排列的方式,从而使得使用搜索引擎的用户能够方便地按照聚类标签找到自己需要的检索结果。\n[0047] 以下以本发明实施例提供的上述方案在实际中的应用为例,详细说明该方案的实施流程:\n[0048] 如图2所示,为将本发明实施例提供的该方案应用到对搜索引擎搜索到的检索结果进行聚类的过程中的具体流程示意图,在该具体实施例中,以检索结果为汉语网页为例来说明本方案,但若将本方案应用到对英文或其他语言网页进行聚类的过程,则对应的方案也在本发明的保护范围之内,具体地,图2所示的流程图包括以下步骤:\n[0049] 步骤21,从待聚类的检索结果中选取候选字串,其中,该选取到的候选字串包含的字符个数与预设的第一字符个数阈值一致,在本发明实施例中,这里的待聚类的检索结果可以指搜索引擎搜索到的网页,也可以指该搜索到的网页所对应的摘要和/或标题,并且,可以根据需要对待聚类的检索结果的个数进行设定,本实施例中可以将待聚类的检索结果个数设置为200个,由于汉语中的词语一般包含至少两个字符(这里的两个字符即是指汉语中的两个字),因此,在本实施例的该步骤21中,若将第一字符个数阈值设定为2~6个,则需要将摘要或标题中符合字符个数为2~6个的字串都选取出来作为候选字串,如果两个检索结果如附图3所示,则可以从第一个检索结果的标题“东风honda汽车CRV”中选取得到以下候选字串,其中,将小写字母构成的一个英文词语“honda”当作一个字符,而将大写字母构成的英文词语“CRV”按照一个字母为一个字符的方式进行统计,但是这3个字符不可分;\n[0050] \n[0051] 步骤22,从选取到的候选字串中去除“噪音候选字串”,一般地,在通过步骤21选取到的汉字候选字串中有大量的“噪音候选字串”,这些“噪音候选字串”特指字串本身不是一个有意义的短语的候选字串,比如上面的“风honda汽”、“honda汽”等,由于这些“噪音候选字串”本身没有什么意义,不适合作为聚类标签,因此需要把这些“噪音候选字串”过滤掉,可以采用下述方式过滤掉“噪音候选字串”:首先,如果某一候选字串在待聚类的检索结果中的出现频率小于一个阈值f1,就将该候选字串确定为“噪音候选字串”,并将其过滤掉,在本发明实施例中,可以将该f1设置为3;其次,如果与某一候选字串相邻,且位于该候选字串之后的不同的汉字的个数小于一个阈值f2,就将该候选字串确定为“噪音候选字串”,并将其过滤掉,在本发明实施例中,可以将f2设置为5,根据该过滤方式,例如在待聚类的检索结果中,由于“东风honda汽”这个候选字串后面的汉字通常只有“车”字,因此“东风honda汽”很可能会被过滤掉,类似地,“风honda”、“风honda汽”也有可能因为相同的原因被过滤掉,而从如图3所示的第二个检索结果中可以看到“东风标致...”的字样,因此“东风”这一候选字串后面的汉字除了“honda”外,还有可能是“标”字,因此“东风”就有可能不是“噪音候选字串”,当然仅有两个不同的字“honda”、“标”还不足以说明该“东风”不会被过滤掉,“东风”后不同字的个数必须达到5个才能够确定该“东风”不会被过滤掉;而如果与某一候选字串相邻,且位于该候选字串之前的的不同汉字的个数小于一个阈值f3,就将该候选字串确定为“噪音候选字串”,并将其过滤掉,在本发明实施例中,可以将该f3设置为5,根据该过滤方式,例如“风honda汽车”、“风honda汽”等很有可能会被过滤掉,因为这些候选字串前面的汉字通常只有“东”字;此外,如果某一候选字串出现在待聚类的所有检索结果中的总次数除以该候选字串中每个汉字单独出现在所有待聚类的检索结果中的总次数之和小于一个阈值f4,就将该候选字串确定为“噪音候选字串”,并将其过滤掉,在本发明中可以将f4设置为0.1,为了便于描述,以下将进行了“噪音候选字串”过滤后得到的候选字串所构成的字串集合称为第一候选字串集合;\n[0052] 步骤23,计算第一候选字串集合中各候选字串的重要度Score,由于经过以上两个步骤21、21处理后得到的第一候选字串集合中包含的候选字串的数量仍然很多,为了进一步从第一候选字串集合中选取出可读性更好的聚类标签,因此需要进一步采用以下的计算公式(1)分别计算第一候选字串集合中各候选字串的重要度Score:\n[0053] \n[0054] 其中,word表示第一候选字串集合中的任一候选字串,word.tf为该任一候选字串出现在待聚类的所有检索结果中的总次数,word.normtf为该任一候选字串出现在指定检索结果中的总次数,word.df为包含该任一候选字串的检索结果个数,word.length为该任一候选字串包含的字符个数,其中,指定检索结果可以是大量任意的普通网页,而word.normtf用以体现该任一候选字串在该大量任意的普通网页中出现的频率,公式(1)中各参数的含义分别如下:\n[0055] 这一项体现了第一候选字串集合中任一候选字串的重要度Score\n与该任一候选字串出现在待聚类的检索结果的频率成正比,而与该任一候选字串出现在大量任意的普通网页所展现的语言环境下的频率成反比,其含义是用于衡量该任一候选字串的检索结果类别代表性;\n[0056] word.df这一项体现了第一候选字串集合中任一候选字串的重要度Score与该任一候选字串出现在待聚类的各个检索结果中的总次数成正比,其物理含义为该任一候选字串出现在待聚类的各个检索结果中的频率,若该任一候选字串出现在待聚类的检索结果中的次数太少,那么该候选字串也不具有检索结果类别代表性,不适宜作为聚类标签;\n[0057] log(word.length)这一项体现了候选字串所包含的字符个数应该为一个适当的值,因为相对来说,包含字符个数较多的候选字串的word.tf值一般要小于包含字符个数较少的候选字串的word.tf值,因此,在本发明实施例所使用的公式(1)中需要考虑到候选字串所包含的字符个数word.length这一因素,由于该因素对重要度Score的影响过大,因此公式(1)中通过对word.length进行取对数的操作,以减少候选字串所包含的字符个数这一因素对Score的影响;\n[0058] 在本发明实施例中,针对图3所示的两个检索结果,经过上述步骤21、22处理后得到的第一候选字串集合中的各字串及与第一候选字串集合中的各字串对应的参数如下表1所示,将表1中各参数的具体值对应代入公式(1)中,即可分别计算得到第一候选字串集合中各候选字串的重要度Score:\n[0059] 表1:\n[0060] \n 第一候选字串集\n word.tf word.normtf word.df word.length score\n 合中的各字串\n 汽车 95 3500 52 2 0.42\n 东风 82 4300 46 2 0.26\n 标致 43 2000 32 2 0.20\n[0061] \n 标致207 40 1300 32 4 0.59\n 一个 92 10500 78 2 0.2\n 不断 88 8300 67 2 0.21\n[0062] 需要说明的是,只要能体现出各字串的重要度与上述各参数之间在数值大小变化上的对应关系(比如根据上述各参数的含义可知,重要度由大至小的变化是与word.df由大至小的变化相对应的,而重要度由大至小的变化与word.normtf由小至大的变化也是相对应的),则本发明实施例也可以但不限于采用下述公式(2)来计算各字串的重要度Score1:\n[0063] \n[0064] 或者,也可以采用下述公式(3)~(5)来分别对应计算各字串的重要度Score2~Score4:\n[0065] \n[0066] Score3=word.df(4)\n[0067] Score4=log(word.length)(5)\n[0068] 上述Score1~Score4同样可以作为衡量第一候选字串集合中各候选字串的重要度的参数。\n[0069] 步骤24,在计算出第一候选字串集合中各字串的重要度Score时,从第一候选字串集合中选取第二候选字串,比如,可以按照第一候选字串集合中的各字串的重要度Score由大至小的选择顺序,从第一候选字串集合中选取满足预设数目的第二候选字串,在本发明实施例中,可以设置该预设数目为20个,则本步骤24中需要从第一候选字串集合中选取\n20个第二候选字串,若第一候选字串集合中的候选字串个数不足20个,则可以直接将第一候选字串集合中所有的候选字串都选取作为第二候选字串,此外,还可以设定一个重要度阈值,并规定只从第一候选字串集合中选取重要度Score大于重要度阈值的候选字串作为第二候选字串,在本发明实施例中,根据步骤21~24的实施,最终选取到的第二候选字串为最后“标致207”、“汽车”、“东风”等;\n[0070] 步骤25,将第二候选字串确定为对待聚类的检索结果进行聚类的聚类标签;\n[0071] 步骤26,采用多模式串匹配的方法,将各个待聚类的检索结果分别归类到与各个聚类标签对应的簇中,比如,将包含“标致207”的检索结果都归入聚类标签为“标致207”的簇中,将包含“汽车”的检索结果都归入到聚类标签为“汽车”的簇中,将包含“东风”的检索结果都归入聚类标签为“东风”的簇中;\n[0072] 步骤27,根据聚类标签分别被用作搜索引擎所使用的查询词的频率(以下简称使用频率)由高至低的顺序,对聚类标签进行对应排列,比如可以按照阅读习惯,将具有最高使用频率的聚类标签放置在排列有聚类标签的页面的最左边(或最上面),相应地将具有最低使用频率的聚类标签对应放置在排列有聚类标签的页面的最右边(或最下面)。\n[0073] 相应地,本发明实施例还提供了一种聚类装置,用以使利用该聚类装置确定出的聚类标签能够充分体现待聚类文档的类别,达到较好的可读性,具体地,该装置的结构示意图如图4所示,包括以下功能单元:\n[0074] 第一选取单元41,用于根据预设的选取策略,从待聚类的各个文档中选取第一候选字串集合;\n[0075] 第二选取单元42,用于针对第一选取单元41选取的第一候选字串集合中的各字串,根据与该字串相关的参数,从第一候选字串集合中选取第二候选字串,其中,与该字串相关的参数为该字串出现在待聚类的所有文档中的总次数、该字串出现在指定文档中的总次数、该字串包含的字符个数以及待聚类的文档中包含该各字串的文档个数中的至少一个参数;\n[0076] 标签确定单元43,用于将第二选取单元42选取的第二候选字串确定为对待聚类的各个文档进行聚类的聚类标签;\n[0077] 归类单元44,用于将待聚类的各个文档分别归类到与标签确定单元43确定的聚类标签对应的簇中。\n[0078] 较佳地,针对上述第一选取单元41功能的一种实现方式,可以将上述第一选取单元41进一步划分为以下功能模块:\n[0079] 第一选取模块,用于从待聚类的各个文档所包含的字串中,选取字串包含的字符个数与预设的第一字符个数阈值一致的字串;\n[0080] 第二选取模块,用于从第一选取模块选取的字串中选取符合预设规则的第一候选字串集合,其中,这里的预设规则为以下规则中的任意一种或为以下规则的任意组合:\n[0081] 规则一:针对第一候选字串集合中的各字串,包含该字串的待聚类的文档的个数不小于预设的第一阈值;\n[0082] 规则二:针对第一候选字串集合中的各字串,在待聚类的各个文档中,与该字串相邻、位于该字串之前、且包含的字符数目与预设的第二字符个数阈值一致的不同字串的个数不小于预设的第二阈值;\n[0083] 规则三:针对第一候选字串集合中的各字串,在待聚类的各个文档中,与该字串相邻、位于该字串之后、且包含的字符数目与预设的第二字符个数阈值一致的不同字串的个数不小于预设的第三阈值;\n[0084] 规则四:针对第一候选字串集合中的各字串,该字串出现在待聚类的所有文档中的总次数除以该字串包含的各字符出现在待聚类的所有文档中的总次数所得的数值不小于预设的第四阈值。\n[0085] 针对上述第一选取单元41被划分为上述各模块的情况,本发明实施例提供的该装置还可以进一步包含:\n[0086] 重要度Score确定单元,用于针对标签确定单元43确定的聚类标签中的各聚类标签,确定该聚类标签的重要度Score;以及标签排列单元,用于按照重要度Score确定单元确定的各个重要度Score由大至小的顺序,对所述确定的聚类标签进行对应排列。\n[0087] 较佳地,针对上述第二选取单元42功能的一种实现方式,可以将上述第二选取单元42进一步划分为以下功能模块:\n[0088] 计算模块,用于针对第一候选字串集合中的各字串,采用下述公式计算该字串的重要度Score:\n[0089] \n[0090] 其中,word.tf为该字串出现在待聚类的各个文档中的总次数,word.normtf为该字串出现在指定文档中的总次数,word.df为包含该字串的待检索的文档的个数,word.length为该字串包含的字符个数;\n[0091] 选取模块,用于在计算模块计算出第一候选字串集合中各字串的重要度Score时,根据所述重要度Score,从第一候选字串集合中选取第二候选字串,其中,在计算出第一候选字串集合中各字串的重要度Score时,可以按照第一候选字串集合中的各字串的重要度Score由大至小的选择顺序,从第一候选字串集合中选取满足预设数目的第二候选字串,也可以设定一个重要度阈值,并规定只选取重要度Score大于重要度阈值的第一候选字串集合作为第二候选字串。\n[0092] 较佳地,上述归类单元44可以采用多模式匹配的方法,将待聚类的各个文档分别归类到与标签确定单元43确定的聚类标签所对应的簇中。\n[0093] 此外,由于同一篇文档有可能会归入到不同聚类标签所对应的不同簇中,因此,为了能够方便地从某一聚类标签对应的簇中查找到需要的文档,可以考虑按照聚类标签的文档类别代表性来对聚类标签进行排序,具体地,本发明实施例提供的该装置还可以进一步包括:\n[0094] 次数确定单元45,用于分别针对标签确定单元43确定的聚类标签中的各聚类标签,确定该聚类标签出现在待聚类的所有文档中的总次数;\n[0095] 标签排列单元46,用于按照次数确定单元45分别确定的各个总次数由多至少的顺序,对标签确定单元43确定的聚类标签进行对应排列。\n[0096] 此外,还可以考虑按照聚类标签在待聚类的文档中的出现频率,来对聚类标签进行排序,具体地,本发明实施例提供的该装置还可以进一步包括:\n[0097] 文档个数确定单元,用于针对标签确定单元确定的聚类标签中的各聚类标签,确定包含有该聚类标签的待聚类的文档个数;\n[0098] 标签排列单元,用于按照文档个数确定单元确定的各个文档个数由多至少的顺序,对确定的聚类标签进行对应排列。\n[0099] 需要说明的是,当本发明实施例提供的该装置应用到对通过搜索引擎搜索到的搜索结果进行聚类的过程中时,本发明实施例提供的该装置还可以包含另一标签排列单元,可以用于按照标签确定单元43确定的聚类标签分别被用作搜索引擎所使用的查询词的频率由高至低的顺序,对标签确定单元43确定的聚类标签进行对应排列,从而使得使用搜索引擎的用户能够方便地按照聚类标签找到自己需要的检索结果。\n[0100] 显然,本领域的技术人员可以对本发明进行各种改动和变型而不脱离本发明的精神和范围。这样,倘若本发明的这些修改和变型属于本发明权利要求及其等同技术的范围之内,则本发明也意图包含这些改动和变型在内。
法律信息
- 2022-07-15
未缴年费专利权终止
IPC(主分类): G06F 17/30
专利号: ZL 200910089176.8
申请日: 2009.08.03
授权公告日: 2012.06.27
- 2012-06-27
- 2011-05-04
实质审查的生效
IPC(主分类): G06F 17/30
专利申请号: 200910089176.8
申请日: 2009.08.03
- 2011-03-23
引用专利(该专利引用了哪些专利)
序号 | 公开(公告)号 | 公开(公告)日 | 申请日 | 专利名称 | 申请人 |
1
| |
1997-09-03
|
1996-12-31
| | |
2
| |
2009-06-17
|
2008-12-05
| | |
被引用专利(该专利被哪些专利引用)
序号 | 公开(公告)号 | 公开(公告)日 | 申请日 | 专利名称 | 申请人 | 该专利没有被任何外部专利所引用! |