根据单词相关度识别单词聚类

摘要

本发明涉及根据单词相关度识别单词聚类。在一种实施方式中，识别单词聚类包括访问记录了相关度的记录。第一单词和第二单词之间的相关度描述了第一单词和第二单词之间的定量关系。根据相关度识别单词聚类。聚类包括彼此具有足够相关的单词。如果第一单词和第二单词之间的相关度满足一种或多种相关度判据则第一单词与第二单词足够相关。利用聚类进行聚类分析。

说明书

技术领域

本发明总体上涉及词典(lexigraphical)分析，更具体地说，涉及根据单词相关度识别单词聚类。

背景技术

一组数据可以包含大量信息，然而查找到相关信息却可能比较困难。关键词搜索是查找信息的主要技术。然而，在特定情况下关键词搜索在定位信息时并不有效。

发明内容

附图说明

图1例示了根据语言的单词之间的相关度来生成语言本体的系统的一种实施方式；

图2例示了可与图1的系统一起使用的相关度模块的一种实施方式；

图3例示了记录基本相关度的相关度矩阵的实施例；

图4例示了记录有向相关度的相关度矩阵的实施例；

图5例示了记录平均相关度的相关度矩阵的实施例；

图6例示了相关度图的实施例；以及

图7例示了可与图1所示的系统一起使用的聚类模块的一种实施方式。

具体实施方式

概述

在一种实施方式中，识别单词聚类包括访问记录相关度的记录。第一单词和第二单词之间的相关度描述了第一单词和第二单词之间的定量关系。单词聚类是根据近似度识别的。聚类中包括彼此足够相关的单词。如果第一单词和第二单词之间的相关度满足一个或更多个相关度判据则第一单词与第二单词足够相关。利用聚类进行聚类分析。

示例实施方式

在具体实施方式中，领域本体的创建及查询包括以下步骤：

1、收集领域中的文档。在具体实施方式中，文档是词条的集合。文档包括可读文本，例如，书《新约》。文档不需要包括叙述性形式的文本，例如，文档可以包括用户输入的一组标注(tag)，其单独及共同地描述了图像的内容。文档的集合可称为“领域文集(domain corpus)”。

2、识别该领域中感兴趣的词条(“词典词条”)。词条的实施例包括单词(诸如“树”)、短语(诸如“图形算法”)、命名实体(诸如“纽约”)等。词条(或概念)可具有不同的形式。在特定情况下，不同的单词用于同一概念，例如，“kidney stones(肾结石)”和“kidney calculi(肾结石)”是指同一概念，即“肾结石”。在其它情况下，词干可具有多种词形变化(inflected varian)，例如，词干“tree”具有词形变化“tree”和“trees”。在具体实施方式中，同一词条的各种形式可处理为映射到同一词条。词典词条的任意适当形式可出现在文档中，但是具体词典词条不一定出现在任意文档中。

识别词典词条的方法的实施例包括利用用于特定领域的人造词典，例如，医学词典。在具体实施方式中，可根据文档集中的一组文本串自动地生成词典词条的列表。可以按照频度对这些串进行索引及分类，并且可选择频度大于阈值的串。可使用其它合适的统计方法来确定词条。在具体实施方式中，“单词”可与“词条”及“词典词条”互换。

3、计算给定的共现上下文中词典词条的共现(co-occurrence)数量。如果两个词条中的每一个都在同一共现上下文(co-occurrence context)中至少出现一次，则这两个词条共现。共现上下文的实施例包括文档和段落。

4、创建包括该领域本体的有向加权图(directed weighted graph)。该有向加权图包括作为节点的词典词条以及作为边权重的相关度。“有向加权图”可以用作可由任意合适的数据结构(例如，矩阵、二值判决图、或二值判决图的集合)代表的同一信息的实际表达。

5、应用查询该有向加权图的流程。给定一个或更多个词典词条作为输入，该流程输出与输入的词典词条有关的一个或更多个词典词条。例如，该流程可输出一个或更多个词条的分类列表，所述一个或更多个词条针对一个或更多个输入词条具有最高的差分有向相关度(如下所述)。在这种情况下，就该本体涉及的领域而言，该输出包括较接近输入词条的词条。

可使用任意适当的相关度定义。在具体的实施方式中，可使用以下定义：

1、基本相关度

a.词条A与B之间的基本相关度(A)可定义为包括词条A和B这两者的共现上下文的数量与包括词条A或B的共现上下文的数量的比值：

A(A，B)＝|AB|/|A or B|

b.词条A与B之间的基本相关度(A)还可定义为包括词条A和B这两者的共现上下文的数量与包括A的共现上下文的数量或包括B的共现上下文的数量中的最大值的比值：

A(A，B)＝|AB|/max(|A|，|B|)

2、有向相关度

词条A与B之间的有向相关度(DAff)可定义为在假定共现上下文中观察到了A的情况下观察到B的条件概率：

DAff(A，B)＝|AB|/|A|

也就是说，有向相关度可以是包括词条A和B这两者的共现上下文的数量与包括词条A的共现上下文的数量的比值。通常，DAff(A，B)与DAff(B，A)不同。

3、差分有向相关度

词条A和B之间的差分有向相关度(DiffDAff)可定义为：词条A与B之间的有向相关度减去考虑了该文集中的词条B的常见程度(common-ness)的参数。在该文集中的词条B的常见程度可以是词条B与该文集中的其它词条的基本相关度或有向相关度值的统计值。在具体实施方式中，该文集中的词条B的常见程度可以是词条B的平均相关度(AA)，这得到以下差分有向相关度的定义：

DiffDAff(A，B)＝DA(A，B)-AA(B)

词条B的平均相关度(AA)或平均有向相关度可定义为：

AA(B)＝AVERAGE_x DAff(x，B)

也就是说，平均相关度是共现上下文中的词条B与其他词条的有向相关度的平均值。

图1示出了识别单词的聚类的系统10的一种实施方式。在特定实施方式中，系统10根据单词之间的相关度识别单词的聚类。聚类中包括彼此足够相关的单词，其中足够的相关度是根据一个或更多个相关度判据确定的。在具体实施方式中，系统10进行聚类分析。聚类分析的实施例包括根据页面的聚类对页面分类，根据文集的聚类确定文档集的特性，以及基于用户的文档中的聚类分析用户。

在特定实施方式中，对于给定的单词子集和词典D，可以基于特定的反向索引II计算有向相关度，其中索引II例如包括针对单词w_i和w_j的条目I(w_i)和I(w_j)。一般而言，反向索引是存储从词条到它的位置(即词条出现的共现上下文)的映射的索引数据结构。对于D中的每对单词w_i和w_j，DA(i，j)可以被定义为II中的条目I(w_i)和I(w_j)的合取值除以I(w_i)的数目值。一般而言，DA(i，j)不必等于DA(j，i)。结果可以以任意合适的方式例如以行方式存储，其中D(1，i)被存储，然后D(2，j)被存储，依此类推。对于每行i，可以存储|I(w_i)|，接着是与w_j的合取的基数。

在特定实施方式中，可以在三个阶段中计算有向相关度。在这些实施方式中，每个词典词条被指派以唯一的整数标识符。反向索引的条目对应于整数标识符。在阶段0，对应于D的II条目被读取。对于参数(s，o)，仅形式ks+o的元素标识符被保留。值ks+o定义了将被检验的II条目的子集。以这样的方式，可以并行地计算有向相关度。作为示例，来自参数s，o(1，0)的结果相当于对参数(3，0)、(3，1)、(3，2)的计算进行合并获得的结果。该步骤允许计算用于很大反向索引的DA表。

在阶段1内，仅仅针对DA(i，j)以行的方式进行合取运算。在阶段2内，读取计算出的上三角形UT DA阵列。据此获得作为UT置换的下三角形部分。在特定的实施方式中，可以将多个维数相同的DA阵列并成单个阵列。可以以(s，i)为参数按照sum_{i＝0...(s-1)}DA来计算与大II相关的DA数组。可以将附加信息与计算的合取存储起来，以便可以计算有向相关度。在一定的情况中，可以存储II条目的基数。

在特定的实施方式中，可以以行的方式存储DA，所以AA条目的计算可以与DA条目的计算并行地进行。具体地，可以通过在从盘中读取DA时对DA的行进行求和，最后通过词典条目的数量进行归一化而生成AA。

在示出的实施方式中，系统10包括客户端20、服务器22和存储器24。客户端20允许用户与服务器22通信以便生成语言本体。客户端20可以将用户输入发送到服务器22，并且可以将服务器输出提供(例如显示或打印)给用户。服务器系统24管理用于生成语言本体的应用。存储器24存储服务器系统24使用的数据。

在示出的实施方式中，存储器24存储页面50和记录54。页面50(或文档或共现上下文)可以指文字集合。页面50的例子包括一个或更多个文档页面、一个或更多个文档、一本或更多本书、一个或更多个网页、信件(例如电子邮件或即时消息)和/或其它文字集合。可以通过页面识别符识别页面50。可以将页面50电子地存储中一个或更多个有形计算机可读媒介中。页面50可以与任何适当的内容例如文本(例如字符、文字和/或数字)、图像(例如图形、像片或视频)、音频(例如录音或计算机生成的声音)和/或软件程序相联系。在特定的实施方式中，一组页面50可以属于一个文集。该文集可以与具体的主题、社区、组织或其它实体相联系。

记录54描述了页面50。在该实施方式中，记录54包括索引58、反向索引62、本体66以及聚类67。索引58包括索引列表，其中，页面50的索引列表指示页面50的单词。反向索引62包括反向索引列表，其中，单词(或单词集)的反向索引列表指示包括所述单词(或所述单词集)的页面50。在一个实施例中，列表W_i包括包含有单词w_i的页面50的页面标识符。列表W_i&W_j包括合取页面50(其包含单词w_i和w_j这两者)的页面标识符。列表W_i+W_j包括分取(disjunction)页面50(其包含单词w_i或w_j)的页面标识符。P(W_i)是W_i中页面50的数量，即，包括单词w_i的页面50的数量。

在一种实施方式中，列表(诸如索引列表或反向索引列表)可被存储为二值判决图(BDD)。在一个实施例中，集合W_i的二值判决图BDD(W_i)代表具有单词w_i的页面50。BDD(W_i)的满足指定计数(satisfyingassignment count)Satisf(BDD(W_i))得到具有单词w_i的页面50的数量P(W_i)：

P(W_i)＝Satisf(BDD(W_i))

因此，

P(W_i&W_j)＝Satisf(BDD(W_i)AND BDD(W_j))

P(W_i+W_j)＝Satisf(BDD(W_i)OR BDD(W_j))

本体66代表语言的单词以及这些单词之间的关系。在一种实施方式中，本体66代表单词之间的相关度。在例示的实施例中，本体66包括相关度矩阵和相关度图。参照图3到图5来描述相关度矩阵的实施例。参照图6来描述相关度图的实施例。聚类67记录彼此相关的词的聚类。参照图7更详细地描述这些聚类。

在示出的实施方式中，服务器22包括相关度模块30和聚类模块31。相关度模块30可以计算单词对的相关度、记录相关度矩阵中的相关度和/或报告相关度矩阵。相关度模块30还可以产生相关度图。将参照图2更详细地描述相关度模块30。

在特定实施方式中，聚类模块31可以通过识别数据集中相关元素的聚类发现数据集中的模式(pattern)。在特定实施方式中，聚类模块31可以识别一组单词(例如，一种语言或一组页面50)的聚类。一般而言，聚类单词彼此高度相关，但是不与聚类外的单词高度相关。单词聚类可以指示单词集的主题(或题目)。在特定实施方式中，聚类模块31根据单词之间的相关度识别相关单词的聚类。在这些实施方式中，聚类单词彼此高度相关，但是不与聚类外的单词高度相关。将参照图7更详细地描述聚类模块31。

系统10的组件可以包括接口、逻辑、存储器和/或其他合适的元件。接口接收输入、发送输出，处理输入和/或输出，和/或执行其他合适的操作。接口可以包括硬件和/或软件。

逻辑执行组件的操作，例如，执行指令以根据输入产生输出。逻辑可以包括硬件、软件和/或其他逻辑。逻辑可以在一个或更多个有形介质中编码且当被计算机执行时可以进行操作。某些逻辑，例如，处理器，可以管理组件的操作。处理器的实施例包括一个或更多个计算机、一个或更多个微处理器、一个或更多个应用和/或其他逻辑。

存储器存储信息。存储器可以包括一个或更多个有形的、计算机可读的和/或计算机可执行的存储介质。存储器的示例包括计算机存储器(例如，随机存取存储器(RAM)或只读存储器(ROM)，)、海量存储介质(例如，硬盘)、可移动存储介质(光盘(CD)或数字视频光盘(DVD))、数据库和/或网络存储器(例如，服务器)以及/或其他计算机可读介质。

可以对系统10做出修改、添加或省略而不偏离本发明的范围。系统10的组件可以是集成的或分立的。而且，系统10的操作可以通过更多或更少或其他组件实施。例如，生成器42和46的操作可以通过一个组件执行，或者相关度计算器34的操作可以通过多于一个的组件执行。另外，系统10的操作可以使用任意合适的逻辑实施，包括软件、硬件和/或其他逻辑。当在本文中使用时，“各个”表示集中的各个成员或集的子集中的各个成员。

可以对矩阵的实施例做出修改、添加或省略而不偏离本发明的范围。矩阵可以包括更多的、更少的或其他的值。另外，矩阵的值可以以任意合适的顺序布置。

图2示出了可以与图1的系统10一起使用的相关度模块30的一种实施方式。相关度模块30可以为单词对计算相关度、在相关度矩阵中记录相关度以及/或者报告相关度矩阵。相关度模块30还产生相关度图。

在所示出的实施方式中，相关度模块30包括相关度计算器34、本体生成器38和单词推荐器48。相关度计算器34为单词w_i或包括第一单词w_i和第二单词w_j的单词对计算任意类型的相关度。相关度的实施例包括基本相关度、有向相关度、平均相关度、差分相关度和/或其他相关度。

在一种实施方式中，单词推荐器48接收种单词且识别与该种单词之间的相关度大于阈值相关度的单词。阈值相关度可以具有任何适当的值，诸如大于或等于0.25、0.5、0.75或0.95。阈值相关度可以被预编程或由用户设定。

基本相关度可以根据包括单词w_i和/或w_j的页面50的数量(例如，数目)计算。合取页面数量代表包括单词w_i和单词w_j两者的页面50的数量。分取页面数量代表包括w_i或w_j的页面50的数量。通过将合取页面数量除以分取页面数量，可以给出基本相关度。在一个实施例中，合取页面数表示包括单词w_i和单词w_j的页面数，而分取页面数表示包括单词w_i或w_j的页面数。通过将合取页面数除以分取页面数可以给出基本相关度：

Affinity(w_i，w_j)＝P(W_i&W_j)/P(W_i+W_j)

图3例示了记录基本相关度的相关度矩阵110的实施例。在所例示的实施例中，相关度矩阵110记录单词w₁，...，w₅的逐对相关度。根据相关度矩阵110，单词w₀与w₁之间的相关度是0.003，单词w₀与w₂之间的相关度是0.005，以此类推。

返回参照图1，相关度组包括彼此具有高相关度的单词对，并可用于针对页面内容而获得单词w₁和w₂之间的关系。较高的相关度可指定为大于相关度组阈值的相关度。阈值可以设定为任意合适的值，例如大于或等于0.50，0.60，0.75，0.90或0.95。一个单词可属于多于一个的相关度组。在一种实施方式中，相关度组可表示为BDD。用于该BDD的指针可与该组的各个单词一起存储在反向索引62中。

有向相关度可用于测量单词w_i对于w_j的重要性。相关度计算器34根据包括单词w_i和w_j的页面50的数量(例如，数目)来计算单词w_i与给定单词w_j的有向相关度。单词w_j页面数量表示包括单词w_i的页面50的数量。单词w_i与给定单词w_j的有向相关度可通过合取页面数量除以单词w_j页面数量得到。例如，单词w_j页面的数量指示包括单词w_i的页面50的数量。单词w_i与给定单词w_j的有向相关度可通过合取页面50的数量除以单词w_i页面50的数量得到：

DAffinity(w_i，w_j)＝P(W_i & W_j)/P(W_i)

DAffinity(w_i，w_j)与DAffinity(w_j，w_i)不同。单词w_i与w_j之间的高有向相关度DAffinity(w_i，w_j)指示在页面50包括单词w_j的情况下页面50包括单词w_i的概率较高。在一个实施例中，页面[1 2 3 4 5 6]包括单词w_i，而页面[42]包括单词w_j。包括单词w_j的页面也包括单词w_i，因此从单词w_j的角度，单词w_i具有较高的重要性。包括单词w_i的页面中仅有三分之一的页面也包括单词w_j，因此从单词w_i的角度，单词w_j具有较低的重要性。

图4例示了记录单词w₀，...，w₅的有向相关度的相关度矩阵120。在该实施例中，单词124是A单词，而单词128是B单词。矩阵120的各行记录了B单词与给定A单词的相关度，而矩阵120的各列记录了A单词与给定B单词的相关度。

返回参照图1，针对其它单词w_j来计算单词w_i的平均相关度。在一种实施方式中，平均相关度可以是单词w_i与其它各个单词w_j之间的相关度的平均。N个单词中的单词w_i的平均相关度可由下式给出：

$\mathrm{AveAff}\left(w_i\right)=\frac{1}{N}{\Sigma }_{j=1}^{N}P\left(w_i\right|w_j)$

图5例示了记录平均相关度的相关度矩阵140的实施例。行142记录单词1到单词50,000的基本相关度。行144记录单词1到单词50,000的平均相关度。

返回参照图1，单词的平均相关度可指示该单词的深度(depth)。具有较低平均相关度的单词可认为是较深的单词，而具有较高平均相关度的单词可认为是较浅的单词。较深的单词倾向于更技术、更具体和更精确。较深单词的百分比较高的页面50可被认为是较深的页面，而较深单词的百分比较低的页面50可被认为是较浅的页面。在一种实施方式中，用户可指定要提取的单词和/或页面50的深度。

页面50的较深的单词可形成具有高度相关单词的一个或更多个聚类(cluster)。聚类可表示共同思想或主题。页面50的主题的数量可指示页面50的特异性。具有较少主题的页面50可被认为是较特殊的，而具有较多主题的页面50可被认为是较不特殊的。

单词w_i相对单词w_j的差分相关度是单词w_i与单词w_j之间的有向相关度减去单词w_i相对其它全部单词的平均相关度。差分相关度可表示为：

DiffAff(w_i，w_j)＝DAffinity(w_i，w_j)-AveAff(w_j)

差分相关度排除了由单词w_i在页面50中出现的一般趋势而造成的偏差(bias)。在具体情况下，差分相关度可提供针对给定了页面包括单词w_j情况下该页面包括单词w_i的概率的更精确指示。

差分相关度可用于多种应用。在一个实施例中，人名之间的差分相关度可用于研究社会网络。在另一实施例中，语言元素之间的差分相关度可用于研究自然语言处理。在另一实施例中，产品之间的差分相关度可用于研究营销。

相关度计算器34可使用任意合适的技术来搜索反向索引列表，以计算相关度。例如，为了识别包括单词w_i和单词w_j这两者的页面，相关度计算器34可搜索单词w_i的列表W_i以及单词w_j的列表W_j，以获得公共元素，即公共页面标识符。

在特定实施方式中，本体生成器38产生语言的本体66，诸如相关度矩阵或相关度图。本体可以根据任意合适的相关度产生，诸如根据基本相关度、有向相关度、平均相关度、差分相关度和/或其他相关度产生。本体66可以以任意方式根据从语言中选出的单词产生。例如，可以选择来自于语言的普遍使用部分的单词或涉及一个或更多个特定主题领域的单词。

在所示出的实施方式中，本体生成器38包括相关度矩阵生成器42和相关度图生成器46。相关度矩阵生成器42产生相关度矩阵，该相关度矩阵记录单词之间的相关度。相关度图生成器46产生相关度图，该相关度图代表单词之间的相关度。在相关度图中，节点代表单词，节点之间的有向边的权重代表节点代表的单词之间的相关度。相关度图可以具有任意适当大小的维数。

图6示出了相关度图150的示例。相关度图150包括节点154和链路158。节点154代表单词。在该实施例中，节点154a代表单词“二进制”。节点154之间的节点有向边的权重代表节点154代表的单词之间的相关度。例如，较大的权重代表较大的相关度。节点之间的链路158表示节点154代表的单词之间的相关度大于相关度阈值。相关度阈值可以具有任意合适的值，例如，大于或等于0.25、0.5、0.75或0.95。

图7示出了可以与图1的系统10一起使用的聚类模块31的一种实施方式。在特定实施方式中，聚类模块31通过识别数据集中的相关元素的聚类发现数据集中的图案。在特定实施方式中，聚类模块31可以识别一组单词(例如，语言或一组页面50)的聚类。一般而言，聚类单词彼此高度相关，但是不与聚类之外的单词高度相关。单词的聚类可以指示该组单词的主题(或题目)。

在特定实施方式中，聚类模块31根据单词之间的相关度识别相关单词的聚类。在该实施方式中，聚类的单词彼此高度相关，但是不与聚类外的单词高度相关。在一种实施方式中，如果单词足够相关，它们可以被认为高度相关。如果单词满足一个或更多个相关度标准(例如阈值)，单词可以足够相关，标准的实施例在下面提供。

任意合适的相关度都可用于识别聚类。在特定实施方式中，聚类模块31使用有向相关度。单词相对其他单词的有向相关度表征了单词的共现。聚类包括具有相似共现的单词。在特定实施方式中，聚类模块31使用差分相关度。差分相关度旨在去除单词在页面50中出现的一般趋势导致的偏差。

在所示出的实施方式中，聚类模块31包括聚类引擎210和聚类分析器214。聚类引擎210根据相关度识别单词的聚类，且聚类分析器214应用相关度聚类以分析各种情况。

聚类引擎210可以以任意合适方式根据相关度识别单词的聚类。用于识别聚类的方法的三个实施例为：根据一组单词建立聚类，将单词分入聚类，以及比较单词的相关度向量。在一种实施方式中，聚类引擎210根据一组单词建立聚类。在一种实施方式中，聚类引擎210根据具有相关度^*Aff(w_i，w_j)的单词{w_i}的集W建立聚类S。相关度值^*Aff(w_i，w_j)代表单词w_i相对于w_j的任意合适类型的相关度，诸如有向相关度DAffinity(w_i，w_j)或差分相关度DiffAff(w_i，w_j)。这里提供的相关度值的某些实施例可以被认为是归一化值。在该实施例中，Aff_for(w_i，w_j)代表前向相关度，且Aff_back(w_j，w_i)代表后向相关度。

在该实施例中，聚类S开始于种单词w_q。当前单词w_x代表在当前迭代中与来自集W的单词比较的聚类S的单词。最初，当前单词w_x被设置为种单词w_q。

在迭代中，当前单词w_x被设置为聚类S的单词。集W的单词w_i根据它们与当前单词w_x的前向聚类Aff_for(w_i，w_x)分类。从分类集W的起点开始，识别满足相关度标准的候选单词w_c。相关度标准可以包括与当前单词w_x的前向相关度标准：

Aff_for(w_c，w_x)＞Th_cf

以及与种单词w_q的后向相关度标准：

Aff_back(w_q，w_c)＞Th_cb

其中Th_cf代表候选单词的前向阈值，Th_cb代表候选单词的后向阈值。候选单词{w_c}的有序集的第一单词被添加到聚类S，添加的单词数由参数Size_c给出。阈值Th_cf和Th_cb可以为范围从最小值到最大值的任何适当值的浮点参数。在特定的实施例中，阈值Th_cf和Th_cb的适当值可以根据实际相关度的等级列表确定。例如，可以使用列表的第200个值。参数Size_c可以是具有任意合适值的整数参数。合适的值的实施例包括缺省值1、2、3或4。在特定实施方式中，参数可以在特定迭代处变化。

可以执行任意合适数目的迭代。在一个实施例中，可以在方法启动之前设计迭代数目。在另一实施例中，可以在方法的执行过程中计算次数。例如，可以根据聚类S的尺寸的生长速度计算次数。

在另一实施方式中，聚类引擎210通过将一组单词中的单词分类成聚类来识别聚类。在一个实施例中，集W的单词{w_i}根据相关度^*Aff(w_i，w_j)(诸如差分相关度或有向相关度)分类。在另一实施例中，单词{w_i}根据聚集函数分类，例如，根据单词w_i的与单词分离集Q中的各个成员的相关度之和分类。集W可以以任意合适的方式选择。例如，集W可以是与查询最相关的X个单词，其中X可以是任意合适的值，诸如从10至100，100至200或等于或大于200的值。

在该实施例中，聚类最初为空。集W的第一单词w_i被放置在聚类中。在每次迭代，当前单词w_x从集W中选择。如果^*Aff(w_x，w_f)满足相关度阈值Th给出的相关度标准，则当前单词w_x被放入到聚类，其中w_f代表聚类中放置的第一单词。阈值Th可以具有任意合适的值，例如，0.1至0.5范围的值(最小值为0.0和最大值为1.0)。如果^*Aff(w_x，w_f)不满足阈值Th，则当前单词w_x被置于空聚类。针对集W中的每个单词重复该迭代。

在处理了集W的单词之后，小聚类可以被消除。例如，可以消除具有少于Y个单词的聚类。Y可以具有任意合适的值，诸如3至5、5至10、10至25、25至50，或大于等于50的范围中的值。

如果聚类的数目不在满意的范围内，可以使用不同的阈值Th重复该处理，该不同的阈值Th给出了针对在聚类中进行放置的较严格或较松的标准。满意的范围可以由具有任意合适值的聚类数目最小值和聚类数目最大值给出。合适值的实施例包括针对最小值的1至5、5至10或大于或等于10范围的值，以及针对最大值的10至15、15至20或大于或等于20的范围中的值。可以增加阈值Th的值以增加聚类的数目，且可以减小阈值Th的值以减小聚类数目。

在另一实施方式中，聚类引擎210通过比较单词的相关度向量识别聚类。在特定实施方式中，相关度矩阵的行和列可以得出相关度向量<w_i，^*Aff(w_i，w_l)，...，^*Aff(w_i，w_j)，...，^*Aff(w_i，w_n)>，这代表单词w_i相对于单词w_j的相关度，j＝1，...，n。相关度值^*Aff(w_i，w_j)代表单词w_i相对于单词w_j的任意合适类型的相关度，例如，有向相关度或差分相关度。

在特定实施方式中，具有相似相关度值的相关度向量可以表示聚类。仅用于描述目的，相关度向量可以被认为是相关度空间中单词的相关度的坐标。即，每个相关度值^*Aff(w_i，w_j)可以被认为是特定维数的坐标。具有相似相关度值的相关度向量表示这些向量与之相关的单词在相关度空间彼此靠近。即，这些向量表示这些单词与其他单词具有类似相关度关系，且因而可以适用于相同聚类中的成员关系。

如合适的距离函数所确定的，如果一个相关度向量接近另一相关度向量，则这些相关度向量相似。距离函数可以基于相关度向量定义为例如针对给定尺寸的向量的标准欧几里得距离，或者给定尺寸的向量的余弦。距离函数可以通过聚类引擎210或通过用户指定。

在特定实施方式中，聚类引擎210应用聚类算法以识别值彼此接近的相关度向量。聚类算法的示例包括直接算法、重复二等分算法、聚合算法、偏差聚合算法和/或其它适当算法。在一个实施例中，聚类引擎210可以包括聚类软件，诸如CLUTO。

聚类分析器214可以在任意合适的应用中使用相关度聚类以用于分析。在一种实施方式中，聚类分析器214可以使用相关度聚类对页面50进行分类。类可以与聚类标识符或一个或更多个聚类成员相关。在一个实施例中，页面50的聚类被识别，然后可以根据聚类对页面50进行分类。在另一实施例中，可以选择页面50的重要单词，然后定位包括该单词的聚类。然后根据定位的聚类对页面50进行分类。

在一种实施方式中，聚类分析器214可以使用相关度聚类来分析页面50的文集。文集可以与特定主题、一个或更多个个体的社团、组织或它们的实体相关。在一个实施例中，聚类分析器214可以识别文集的聚类且根据聚类确定文集的文集特性。文集特性可以表示与实体(所述实体与文集相关)相关的单词。如果一个或更多的页面50具有文集特征的聚类，则页面50可以与该实体相关。

在一种实施方式中，针对搜索查询歧义消除和扩展，聚类分析器214可以使用相关度聚类。在该实施方式中，聚类分析器214识别包括给定搜索查询的搜索词条的聚类。聚类提供与给定搜索查询相关的另选单词和/或分类。在一个实施例中，来自于聚类的单词可以被报告给搜索者以帮助下一次搜索查询。在另一实施例中，聚类分析器214可以从聚类选择单词且自动地形成一个或更多个新的搜索查询。聚类分析器214可以顺序地或并行地运行新的查询。

在一种实施方式中，聚类分析器214可以使用相关度聚类来研究社会网络。在一个实施例中，页面50可以提供社会网络的洞察。这种页面的实施例包括信件(诸如信、电子邮件和即时消息)、备忘录、文章和会议记录。这些页面50可以包括包含社会网络的中的人的用户标识符(诸如名字)的单词。可以识别名字的聚类以分析该网络中的人之间的关系。在一个实施例中，差分相关度聚类可用于过滤页面50中的出现最多的名字，而不提供诸如系统管理员的名字之类的信息。

在特定实施方式中，聚类分析器214可以通过组合和/或比较数据集的聚类来分析数据集。在一种实施方式中，比较交叠数据集的聚类。一个数据集的聚类可以映射到其他数据集的聚类，这可以提供两个数据集之间的关系的洞察。例如，数据集可以来自于对一组同事的文档的分析且来自于该组的社会网络研究。社会网络聚类可以映射到文档主题聚类以分析社会网络和主题之间的关系。

本发明的某些实施方式可以提供一个或更多的技术优点。一种实施方式的技术优点是可以根据从单词之间的相关度识别单词的聚类。聚类包括彼此足够相关的单词，其中足够的相关度是根据一种或更多种相关度判据确定的。一种实施方式的另一技术优点可以是可进行聚类分析。聚类分析的实施例包括根据页面的聚类对页面分类，根据文集的聚类确定文集特性，并且基于用户的文档中的聚类分析用户。本发明的特定实施方式可包括零个、一些或全部上述技术优点。对于本领域技术人员而言，从这里所包括的附图、说明书以及权利要求得到一项或更多项其它技术优点是明显的。

尽管已经根据某些实施方式描述了本公开，但这些实施方式的变型和改变对于本领域技术人员而言是显见的。因此，实施方式的上述描述并不限制本公开。在不偏离所附权利要求限定的本发明的精神和范围的情况下，可以做出其他变型、替代和变更。

本申请要求David(nmi)Marvit等人于2007年10月5日提交的题为“WORD CLUSTERING BASED ON AFFINITY”的美国临时申请第60/977,811号(律所案号：073338.0550)的优先权。