为对象分类的自动确定显著特点的方法和装置

摘要

提供了为对象分类而自动确定显著特点的方法和装置。根据一个实施例，从第一内容对象组中提取一个或多个独特特点以形成第一特点列表，再从第二非内容对象组中提取一个或多个独特特点以形成第二特点列表。然后在第一特点列表的独特特点和第二特点列表的独特特点间采用统计区分法产生一分级特点列表。然后从所得的分级特点列表中识别出显著特点集。

说明书

发明背景

1.发明领域

本发明涉及数据处理领域。更具体说，本发明涉及用于将对象分组的对象特点的自动选择。

2.背景信息

万维网提供了重要的信息源，估计已可在线阅览下载数十亿页的信息。但为了有效的利用此信息，必需要有一切合实际的方法用于指引此海量数据。

在互联网冲浪的初期，发展了两种基本方法用于网上搜索。在第一种方法里，根据由自动搜索引擎收集在一起的网页内容产生索引数据，搜索引擎在网上“爬行以寻找新的独特的页面。然后，此数据库可用各种质询技术搜索，而且通常数据可根据质询形式的相似性分级。在第二个方法中，网页分组成一分层结构，往往以一棵树的形式呈现。然后当顺着此分层结构下行时，使用者便作出一系列的选择，在代表决定点之下的子树之间显著区别的每一级别上作出两个或更多的选择，最终达至包含文本和/或多媒体内容页面的叶节点。

例如，图1说明一典型的现有技术分层结构102，其中多个决定节点(下称“节点”)130-136分层排列成多个父/或子节点，每一节点均与一独特的学科类别相联系。例如，节点130为节点131与132的父节点，而节点131与132则为节点130的子节点。因为节点131与132都是同一节点(节点130)的子节点，节点131与132互为兄弟。在102学科分层结构中其他的兄弟对包括节点133与134，还有节点135与136。由图1可见，节点130形成学科分层结构102的第一级137，而节点131-132形成学科分层结构102的第二级138。节点133-136则形成学科分层结构102的第三级139。此外，节点130被认为是学科分层结构102的根节点，因为它不是其他任何节点的子节点。

将网页分层分类的过程面临多重挑战。首先，分层结构的性质必须界定。通常这是由专门学科领域中的专家人工完成的，有点像为图书馆做杜威十进制系统的分类。然后这些类别加上说明标签提交出来，以便使用者和分类者在指向此分层结构时能作出适当的决定。然后，例如，以个别电子文档形式呈现的内容可用在分类系统中人工搜索的方法放进多个类别中去。

近年来人们的注意力已转向这一过程各个阶段的自动化。现已存在从批量文档中将文档自动分类的系统。例如，某些系统应用与文档有联系的关系字将相似文档自动集合成组群。这些组群又能多次反复组成超级组群，从而产生分层结构，然而，这些系统需要人工插入关键字，产生的是一个没有系统性结构的分层结构。如果此分层结构用于人工搜索，就必须人工检查子节点或叶文档以识别公共特点，从而对分层结构的节点贴上标签。

许多分类系统应用字列表将文档分类，通常，显著字可以预先界定，也可从正在处理的文档中选择，以便更为准确地表征文档。一般这些显著字列表是用对一组文档中的每一个文档数全部字的出现频率来产生。然后根据一个或多个判据将字从字列表中移出。往往，在一批文档中出现次数太少的字被剔除，因为这些字用得太少不足以可靠地区分类别，但出现得太频繁的字也要剔除，因为在各类文档中都要出现。

再者，“无用字”与词干也往往从特点列表中剔除以更利于显著特点的确定。无用字包括语言中的普通字，诸如“a”，“the”，“his”与“and”，这些字让人感觉并不具有语义学内容，词干则指诸如“-ing”，“-is”与“-able”等词尾。可惜，生成无用字列表与词干列表是一项语言专业性的任务，要求有语法、文档和习语方面的专业知识，而这些又是会随时间变化的。因此，就要求有一个更为灵巧的方法来确定显著特定。

附图简要说明

本发明将通过示例性实施例来描述，但并无限制，并用附图说明，其中相同的标号表示相似的要素，附图中：

图1说明一包括多个决定节点的示例性现有技术分层结构；

图2(A-C)根据本发明的一个实施例说明显著特点确定功能的操作流程；

图3根据一个实施例说明本发明显著特定确定设备的应用实例；

图4根据本发明的一个实施例说明图3的分类器训练服务的功能框图；

图5根据本发明的一个实施例举例说明适于用作确定显著特点的计算系统。

发明的详细描述

下文将描述本发明的各个方面。然而，本领域的技术人员可以清楚，本发明可以仅用其某些或全部方面而实施。为便于解释，专门的数字、材料与结构均予以阐明以便提供对本发明的透彻了解。然而，本领域的技术人员也清楚，本发明无需这些细节也可实施。在其他情形，众所周知的特点予以忽略或简化，以免说不清楚本发明。

描述的有些部分以用基于处理器的设备实施的操作表达，使用诸如数据，存贮、选择、确定、计算等术语，与本领域技术人员通常使用的相符，以便将他们工作的基本内容传给本领域的其它技术人员。本领域的技术人员可以理解，数量可取能贮存，传输或者通过基于处理器的设备中的机械及电学元件操控的电学、磁学或光学信号的形式；而这里处理器一词包括微处理器、微控制器、数字信号处理器等，可以是独立的，也可以是辅助的或嵌入式的。

各个操作按各个分立步骤依次描述，以便最有助于了解本发明，然而，描述的顺序不应理解为意味着这些操作必与顺序相关。实际上，这些操作无须按所呈现的顺序执行。再者，描述反复使用短语“在一个实施例中”，但并不一定都指同一实施例，虽然可以如此。

根据本发明的一个实施例，从第一个对象组中提取一个或多个独特的特点以形成第一特点集，再从第二个对象组中提取一个或多个独特特点以形成第二特点集。然后在第一特定集的独特特点与第二特点集的独特特点间采用统计区分法产生一分级特点列表。然后，从这样得到的分级特定列表中即可识别出一组显著特点。

在一个实施例中，显著特点的确定有利于对数据对象的有效分类，对象包括(但不限于)文本文档、图象文档、音频序与视频序列，在甚大规模的分层分类树中，也在诸如平坦文档的非分级数据结构中这些数据对象既包括专利格式也包括非专利格式。例如在一文本文档中，特点可取字的形式，而术语“字”通常理解为在给定的语言中代表一组字母，具有某种语义学的意义。更一般地说，一个特点可以是一个N-标记语法(N-token gram)，一个标记就是语言的一个微小元素，例如，包括英语中的N-字母语法和N-字语法，也包括亚洲语言中的N-表意符语法。又如在音频序列中，音调、速度、音延、音高、音量以及诸如此类都可用作对声音分类的特点，而在视频序列与静止图像中，各个像素属性，诸如角度和亮度级即可用作特点。根据本发明的一个实施例，一旦一个特点组从一组(比如说)电子文档中被识别出来，然后就可确定出这些特点的一个子集对于给定数据对象组的分类而言是显著的。本文中的术语“电子文档”广泛用于描述一族数据对象，诸如以上所描述的包括一个或多个构成特点的那一些。虽然电子文档可包括文本，也同样可包括音频和/或视频内容，即可取代文本，也可附加于文本。

特点选择的判据一经确定(就是说哪些不同文本/音频/视频的属性在数据对象集中用作确定性特点)，本发明的显著特点确定过程即可实施。显著特点确定过程一开始，所考虑的数据对象分成两组。然后对这两组数据对象应用代表“实用可能性”的方程(见方程1)，这里0(d)代表一给定数据对象作为第一数据对象组之成员的可能性，P(R|d)代表此数据对象作为此第一组成员的概率，而P(R′|d)则代表此数据对象作为第二组成员的概率。

$$ >>O>>(>d>)>>=>>>P>>(>R>|>d>)>>>>P>>(>>R>\prime >>|>d>)>>>>->->->>(>1>)>>>$$

因为数据对象的人工分组并不提供用于计算实用可能性的概率，方程(1)便可充分利用来估计此值。相应的，对数函数连同Baye公式可一起应用于方程(1)的两边，给出方程(2)：

logO(d)＝logP(d|R)-logP(d|R′)+logP(R)-logP(R′)         (2)

如此，一数据对象假设由一组特点{F_j}组成；并且X_i要么是1要么是0，分别代表给定特点f_i在或者不在一数据对象内，则

$$ >>log>O>>(>d>)>>=>>\Sigma >i>>[>log>P>>(>>X>i>>|>R>)>>->log>P>>(>>X>i>>|>>R>\prime >>)>>]>+>log>P>>(>R>)>>->log>P>>(>>R>\prime >>)>>->->->>(>3>)>>>$$

因为logP(R)与logP(R′)都是常数，与数据对象中选作显著的特点无关，便可规定一新量g(d)：

$$ >>g>>(>d>)>>=>>\Sigma >i>>[>log>P>>(>>X>i>>|>R>)>>->log>P>>(>>X>i>>|>>R>\prime >>)>>]>->->->>(>4>)>>>$$

如设p_i＝P(X_i＝1/R)代表一给定特点(f_i)出现在第一数据组中的一个数据对象中的概率，而q_i＝P(x_i＝1/R′)代表给定特点(f_i)出现在第二数据对象组中的一个数据对象中的概率，则经代入化简可得方程(5)：

$$ >>g>>(>d>)>>=>>\Sigma >i>>[>>X>i>>log>>>>p>i>>>(>1>->>q>i>>)>>>>>q>i>>>(>1>->>p>i>>)>>>>+>>\Sigma >i>>[>log>>>1>->>p>i>>>>1>->>q>i>>>>]>->->->>(>5>)>>>$$

因为第二项中的求和并不依赖于特点在数据对象中的出现情形，可将之除去而得方程(6)：

$$ >>log>>>>p>i>>>(>1>->>q>i>>)>>>>>q>i>>>(>1>->>p>i>>)>>>>->->->>(>6>)>>>$$

因为对数函数是单调函数，方程(7)

$$ >>>>>p>i>>>(>1>->>q>i>>)>>>>>q>i>>>(>1>->>p>i>>)>>>>->->->>(>7>)>>>$$

的比值最大化即足以使相应的对数值最大化。根据本发明的一项具体体现，对两组数据对象，对组合特点列表中的每个特点应用方程(7)以利于显著特点的识别。为此，应计算p_i，代表在第一数据对象组中至少包含特点f_i一次的数据对象数除以第一数据对象文档组中数据对象的总数。同样，应计算q_i，q_i代表第二数据对象组中至少包含特点f_i一次的数据对象数除以第二组数据对象组中数据对象的总数。

图2(A-C)根据本发明的一个实施例说明显著特点确定功能的操作流程。一开始，先检查第一集数据对象以产生一特点列表，该列表由出现在至少是来自第一数据对象集的一个或多个数据对象的独特特点组成，见方框210。对每一个识别过的独特特点，应用方程(7)以产生一分组特点列表，见方框220，此分组特点列表中的至少一个子集选作显著特点，见方框230。显著特点可包含由分级特点列表中选出的一个或多个相邻或非相邻的元素组。在一个实施例中，分级特点列表中的前N个元素选作显著的，而N可根据系统的需要而变化。在另一实施例中，分级特点列表中的最后的M个元素选作显著的，而M亦根据系统的需要而变化。

根据本发明的一个实施例，当产生特点列表(见方框210)时，包含在每一个数据对象组中的数据对象的总数得以确定，见方框212，对在至少是第一数据对象组中识别的每一个独特特点，包含此独特特点的数据对象总数亦能确定，见方框214。此外，独特特点列表可根据所需要不同的判据过滤，见方框216。例如，独特特点列表可删减除去那些并未发现为不管怎样出现的次数最少的数据对象的特点，那些短于经确定的某一最小长度的特点，和/或出现的次数比配额少的特点也被去除。

根据本发明的一个实施例，应用统计区分的方法获得分级特点列表，如同就图2A中的方框220描述的那样，还进一步包括在同2C中说明的那些过程。就是说，在应用统计区分法(即如方程(7)所示)时就作出一项决定，即确定在第一个数据对象集中的哪一些经识别的独特特点也出现在第二个数据对象集中，见方框221，同样地确定出在第一数据对象集中的哪一些经识别的独特特点不出现在第二文档集中，见方框222。根据所说明的具体体现，当通过统计区分法(即方程(7))作出决定时，那些确定为只出现在一个数据对象集中而不出现在其他集中的特点便被在分组特定列表中定为较高的相对级别，见方框223，而那些确定为在两个数据对象集中都出现的特点则定为相对较低的级别，见方框224。有时，根据包含每一个相应特点的数据对象的总数，分级特点列表中的特点还可进一步分级。

应用示例

现参见图3，在其中根据一个实施例，以一例示出本发明用于确定显著特点的设备。如图所示，分类器300用来有效地对数据对象分类，诸如在一大类包括甚大规模级别分类树及平坦文档格式的数据结构中的电子文档，包括(但不限于)文本文档，图像文档，音频序列与视频序列，既包含专利性格式也包含非专利性格式。分类器300包括分类器训练服务305，用以为训练分类器300根据从以前已分类过的数据分层结构中提取的分类规则对新的数据对象分类；也包括分类器分类服务315用以对输入进分类器300的新数据对象进行分类。

分类器训练服务305的功能包括聚集功能306，本发明的显著特点确定功能308，以及节点特征化功能309。根据所示的实施例，来自前已分类的数据分层结构的内容在分层结构的每个节点处通过聚集功能306聚焦，以同时形成数据的内容组与非内容组。然后由每个数据组提取特点并用显著特点确定功能308的方法确定那些特点是显著的一个特点子集。节点特征化功能309用来对前已分类过的数据分层结构的每个节点根据显著特点特征化，也用以在数据贮存310中贮存这些分类特征化，例如，以便为分类器分类服务315作进一步使用。

关于包括分类器训练设备305和分类器分类设备315的分类器300的其他资料在与此同时提交的编号为《51026，P004》的美国专利申请书中描述，题为“Very-Large-Scale Automatic Categorizer For Web Content(为网上内容的甚大规模自动分类器)”，共同地转让本申请的受让人，该申请通过引用完全结合于此。

分类器训练服务

图4根据本发明的一个实施例画出图3中的分类训练服务305的功能方框图。如图4所示，前已分类的数据分层结构402用以输入至分类器300的分类训练服务305。前已分类的数据分层结构400代表一个诸如音频、视频和/或文本对象的数据对象集，这些数据对象前已分类并将其归入一主题分层结构(通常由人工完成)。前已分类的数据分层结构402可以代表一个或多个前已经web门户或搜索引擎分类过的电子文档集。

根据业已说明的例子，聚集功能406将来自前已分类的数据分层结构402的内容聚集至内容和非内容组，这样就在分层结构的每个级别的兄弟节点间增加了差别。显著特点确定功能408的作用是从内容与非内容数据组中提取特点并确定哪些提取的特点(409)可被定为显著的(409′)。

此外，根据已说明的例子，图3中的节点特征化功能309的作用是对内容及非内容数据组特征化。在一个实施例中，内容与非内容数据是根据已确定的显著特点而特征化的。在一个实施例中，特征化的结果贮存在数据贮存设备310中，这可以任何种数据结构的形式实施，诸如数据库、目录结构，或是简单的查验列表。在本发明的一个实施例中对每个节点分类器的参数都贮存在一类似于前已分类的数据分层结构的文件结构的级别分类树中。

计算机系统示例

图5说明适于根据本发明的一个实施例用以确定显著特点的一例计算机系统。如图所示，计算机系统500包括一个或多个处理器502及系统存储器504。此外，计算机系统500还包括大容量的存贮设备506(诸如磁盘、硬驱、CDROM等)、输入/输出设备508(诸如键盘、光标控制器等)以及通信接口510(诸如网络接口卡、调制解调器等)。各部分通过系统总线512相互耦合，系统总线可代表一个或多个总线。当系统总线512代表多个总线时，彼此间由一个或多个总线桥(未画出)相连接。

每一个部分都行使本领域中已知的寻常功能。具体来说，系统存储器504与大容量存储设备506用来贮存实施本发明的分类系统的编程指令的一个工作副本和一个永久副本。编程指令的永久性副本可在出厂前即加载入大容量存储设备506中；或在现场载入，如前所述，通过一分配介质(未画出)或通过通信接口510(来自一分配服务器(未画出))加载。这些部分502～512的结构都是已知的，无须进一步描述。

结论和后记

因此，由以上描述可见，用以为对象分类的自动确定显著特点的新方法及装置已描述出来。虽然本发明用上述实施例描述，本领域的技术人员会认识到，本发明并不局限于所描述的实施例。本发明亦可用修改和替换方案来实施，但必须在所附权利要求书的精神和范围之内。因此本描述应认为是关于本发明的说明性而非约束性描述。