将对象实例的属性规则化为特征的方法和设备

摘要

本发明实施例提供一种将对象实例的属性规则化为特征的方法，包括：对象实例获取步骤，基于给定的领域获取该领域的对象实例；属性池建立步骤，提取所获取的对象实例中的属性，基于所提取的属性建立属性池；属性相似度计算步骤，基于属性池中任何两个属性之间的相似度，建立相似度矩阵；属性整合步骤，根据属性池中属性的相似度矩阵，将属性聚类为特征。本发明实施例还相应地提供一种将对象实例的属性规则化为特征的设备。

说明书

技术领域

本发明涉及一种将对象实例的属性规则化为特征的方法和将对象实例的 属性规则化为特征的设备。

背景技术

随着计算机及网络技术的发展，对从网络资源中查找有用信息的需求也 越来越大。产品的评论、排序以及描述页面在因特网上大量存在，然而，由 于信息量过大，分布于各种各样的网站中，且各个网站对同一种产品的描述 方式也不同，呈现为网络资源中关于同一产品存在大量的异构 (heterogeneous)网页，因而需要从庞杂的网络资源中提取特定领域(domain) 的对象(object)的特征(feature)。

网络中存在的大量网页包含诸如产品说明网页的对象属性值信息。目前 已经存在信息提取技术来从网络中提取网页数据，并自动构建对象数据库。 但是，异构网页的存在造成以不同的方式提供产品信息，所谓不同的方式例 如不同的用语、不同的架构(schema)结构、及不同的观点等等。目前，对 于从网络资源中提取目标对象的描述以及相关技术领域已经有了以下一些现 有技术。

非专利文件1(T.Wong，L.Bing，and W.Lam，″Normalizing web product  attributes and discovering domain ontology with minimal effort″，in Proc.WSDM， 2011，pp.805-814)公开了一种规则化(normalize)网络中的产品属性(attribute) 并发现领域本体(domain ontology)的技术。其考虑到了属性名称及属性值 二者的文本片段，来构建规则化网络上的产品属性的框架；然后，利用所提 取并规则化的属性来构建领域本体。

非专利文件2(H.L.Guo，H.J.Zhu and et al，″Product Feature Categorization  with Multilevel Latent Semantic Association，″Proc.CIKM，2009，pp.1087-1096) 公开了一种通过多层潜在的语义关系来进行产品特征分类的技术。其基于同 时存在关系来对产品特征的片段进行分组，通过多层的语义关系来进行无监 督的产品特征分类，以从评论中提取产品属性并分组。

专利文件1(US 20070244690A1)提出了一种文本聚类技术，用于文本 文档的结构化及语言模型的训练。其方法将文本聚类为代表不同语义含义的 文本聚类；并且给予对目标函数进行再聚类的过程来包含最优化过程，其中 目标函数表示文本单元与聚类之间的相关性。

非专利文件3(Fausto Giunchiglia，Pavel Shvaiko，Mikalai Yatskevich： “Semantic Schema Matching”.OTM Conferences(1)2005：347-365)提出了一种 语义架构匹配技术。其提供了一种结构级别架构匹配方法，即使用字网 (WordNet)来计算术语之间的距离，然后，使用可满足性问题解决器(SAT  solver)来推导映射关系。其中，特别是在存在大量难以提取语义相似性的值 表达及解释段落的情况下，字网对于实例(instance)级别的架构匹配没有帮 助。

专利文件2(US 7249135B2)提出了一种对网络数据库进行架构匹配的 方法和系统。其应用属性-属性匹配及值-值匹配，但是未采用属性-值匹配； 此外，其针对字符串型数据而设计，没有针对数值型数据的特别方案。

非专利文件4(Zhongwu Zhai，Bing Liu，Hua Xu，Peifa Jia：“Clustering  product features for opinion mining”.WSDM 2011：347-354)提出了一种对产品 特征进行聚类以用于观点挖掘(opinion mining)的技术。其提供了一种基于 预先存在的知识资源和分布性质的半监督(semi-supervised)聚类方法。

现有技术的方法涉及与领域有关的信息，针对特定领域来进行处理，然 而领域信息难以收集，并且需要巨大的人力介入，或者要通过训练，而这会 导致发生过度拟合(over fitting)。

发明内容

鉴于现有技术中存在的上述问题而做出本发明。本发明总体上涉及将对 象实例的属性规则化为特征的方法和设备，首先提取产品对象的属性值信息， 然后识别出不同对象实例中的对应关系，再将异构的实例整合到一个架构， 也就是进行属性规则化，包括属性的匹配和属性的整合。

根据本发明实施例的一个方面，提出了一种将对象实例的属性规则化为 特征的方法，包括：对象实例获取步骤，基于给定的领域获取该领域的对象 实例；属性池建立步骤，提取所获取的对象实例中的属性，基于所提取的属 性建立属性池；属性相似度计算步骤，基于属性池中任何两个属性之间的相 似度，建立相似度矩阵；属性整合步骤，根据属性池中属性的相似度矩阵， 将属性聚类为特征。

根据本发明实施例的另一个方面，提出了一种将对象实例的属性规则化 为特征的设备，包括：对象实例获取装置，基于给定的领域获取该领域的对 象实例；属性池建立装置，提取所获取的对象实例中的属性，基于所提取的 属性建立属性池；属性相似度计算装置，基于属性池中任何两个属性之间的 相似度，建立相似度矩阵；属性整合装置，根据属性池中属性的相似度矩阵， 将属性聚类为特征。

通过阅读结合附图考虑的以下本发明的优选实施例的详细描述，将更好 地理解本发明的以上和其他目标、特征、优点和技术及工业重要性。

附图说明

图1示出按照本发明实施例的将对象实例的属性规则化为特征的方法的 总体流程图。

图2包括图2A和图2B，分别示出了同一对象示例的不同实例。

图3示意性地示出本发明实施例的总体过程。

图4示出按照本发明实施例的属性整合步骤的总体流程图。

图5示出按照本发明实施例的初步聚类步骤的流程图。

图6示出按照本发明实施例的将对象实例的属性规则化为特征的设备的 总体框图。

图7是示出按照本发明实施例的将对象实例的属性规则化为特征的系统 的总体框图。

图8示出实施本发明实施例所输出的特征的一个示例。

图9示出本发明实施例所得的特征提供给用户的一种方式。

具体实施方式

下面结合附图描述本发明实施例。

图1示出按照本发明实施例的将对象实例的属性规则化为特征的方法的 总体流程图。如图1所示，将对象实例的属性规则化为特征的方法包括：对 象实例获取步骤S100，可以基于给定的领域获取该领域的对象实例；属性池 建立步骤S200，可以提取所获取的对象实例中的属性，基于所提取的属性建 立属性池；属性相似度计算步骤S300，可以基于属性池中任何两个属性之间 的相似度，建立相似度矩阵；属性整合步骤S400，可以根据属性池中属性的 相似度矩阵，将属性聚类为特征。

在对象实例获取步骤S100，可以基于给定的领域获取该领域的对象实例。 特定的领域可以由用户给定，例如，用户可以以本领域中任何一种惯用的手 段输入特定的领域，诸如“数码相机”、“汽车”等等。针对所读入的所给定 的领域，对象实例获取步骤S100可以以现有的任意一种公知技术获取该领域 的对象实例(object instance)。在此，对象指真实世界的对象，诸如某种电子 产品(领域)的某种型号(对象)，例如，领域为“数码相机”的“Ricoh CX5” 型号。现实中，很可能有多个网站描述同一款产品，而不同网站对同一产品 的描述方式不同，因而，对象“Ricoh CX5”可以具有多个异构的实例。

图2包括图2A和图2B，分别示出了同一对象“Ricoh CX5”的不同实例。 例如，在图2A所示的第一个实例中，在属性“top(顶级)”的下级是“Camera (相机)”和“General(总体)”两个属性，在属性“Camera”的下级包括表 示光学传感器的属性“Optical sensor”，表示像素数目的属性“Megapixels” 等等，而在属性“General”的下级列有分别表示照相机类型、尺寸、重量的 属性“Camera Type”、“Dimension”、“Weight”。例如，在图2B所示的第二 个实例中，诸如“Camera type”、“Megapixels”等等的各个属性处于同一级 别，均列于顶级属性“top”之下。两个实例关于属性的层级结构不同，是异 构的。

对象实例中属性与属性值通常成对出现，例如，在图2A所示的实例中， 属性“Optical sensor”的值为“CMOS”，属性“Megapixels”的值为“10 megapixels”等等，然而，属性值也可能为空。属性可以表示对象的物理或功 能性质。属性值是属性的详细描述。对象“Ricoh CX5”还可以有其它实例， 例如还可能具有诸如“Effective Pixels(有效像素)”-“Approximately 10.00 million pixels(大约1千万像素)”及“Weight(重量)”-“Approx.197g(大 约197克)”等等的属性-值对。

在此顺便提及，本发明实施例中的另一概念“特征(feature)”是语义类 似的一些对象属性的整合。例如，特征“Resolution(分辨率)”可以代表名 称为“Resolution(分辨率)”、“Effective pixels(有效像素)”、“Megapixels(兆 像素)”等等的属性，对于同一特征，不同的实例可能采用不同的属性名称， 然而其含义实质上相同或类似。

对于给定的特定领域，例如以数字照相机或者说数码相机为例，在此领 域中有多种对象(产品)，诸如“Ricoh CX5”、“Canon 5D Mark II”等等。对于 每种对象(产品)，网络资源中可能有多种实例。实例是数据结构，描述对象 的性质。实例可以采用不同的结构、不同的用语及风格，称为异构。

图3示意性地示出本发明实施例的总体过程。如图3所示，特定领域下 包括多个对象实例，而每个对象实例包含成对的属性与值，本发明的实施例 将对象实例的属性规则化为该特定领域下的多个特征，每个特征包含整合的 语义上类似的多个属性。

在属性池建立步骤S200，可以采用本领域任意一种惯用手段，从所获取 的对象实例中提取对象属性，所提取的对象属性可以构成所谓的“属性池 (attribute pool)”。将基于给定的领域而获取的可能是多个对象实例的属性均 置于一个属性池中，然而，每个属性仍然可以保留诸如其所源自的对象实例、 其在相应对象实例中的级别、及其上一级属性的名称等等的信息。然而，由 于非底层的属性通常不具有属性值，因此可以不提取非底层的上级属性(亲 属性)来构成属性池，或者说属性池仅由具有属性值的底层属性构成，现有 公知技术手段能够判断并提取对象实例中的底层属性。在根据所给定的领域 获得其属性池之后，本发明实施例将对象属性规则化(normalize)到该特定 领域的特征。

规则化的过程大体上可以分为两个步骤，即上述的属性相似度计算步骤 S300和属性整合步骤S400。属性相似度计算步骤S300总体上计算属性池中 每个属性与其它所有属性的属性相似度，从而可以构成相似度矩阵；而属性 整合步骤S400基于相似度矩阵将相似属性聚类为该特定领域的特征。

为了减轻规则化过程的负担，在属性池建立步骤S200中，可以基于给定 的属性性质，在属性池中排除不符合所给定属性性质的属性。具体地，可以 进一步接受用户所输入的属性性质，或者默认设置缺省的属性性质。例如， 可以设置缺省的属性性质关于对象的物理或功能方面，从而，可以在属性池 中排除不符合所给定属性性质的属性，诸如随着时间流逝而会发生变化的属 性，例如发布信息、评价信息、价格信息等等。此排除过程可以通过现有的 规则表达式匹配手段而实现。通过排除不符合所给定属性性质的属性，可以 减小属性池的规模，降低此后规则化处理过程的负担；并且，如果是用户指 定的属性性质，此排除过程还可以使最终结果准确性更高，即更符合用户的 真实意图。

下面详细描述对对象属性进行规则化的过程，首先是属性相似度计算步 骤S300，此步骤将计算得到属性池中属性对之间的属性相似度，构成相似度 矩阵。

在属性相似度计算步骤S300中，可以分别计算属性池中任何两个属性之 间的名称相似度、属性值相似度、及交叉相似度，将该名称相似度、属性值 相似度、及交叉相似度加权相加，作为该两个属性之间的属性相似度。

匹配过程中属性的必要信息可以包括例如属性名称、属性值、上级属性 (也可以称“亲属性”)名称、对象索引、实例索引、及在实例中的位置。在 此，对象索引体现属性所来自的对象，是对象的固有唯一标识符，可以用于 标识属性是否属于同一对象。类似地，实例索引也体现属性的来源，是实例 的固有唯一标识符，可以用于标识属性是否属于同一实例。另外，实例中位 置表示该属性出现在相应实例中的自然顺序位置。实例可以认为是属性-值对 的列表，从而列表中的元素具有自然顺序。例如，实例中第i个元素可以认 为其位置为i，在此，i为索引值，从1而不是0开始。

可以理解，如果计算属性池中任何两个属性之间的属性相似度，则可以 得到维度为属性池中属性数目的二维矩阵(方阵)，此矩阵可以称为相似度矩 阵simScore[n][n]，n为属性池中的属性数目。相似度矩阵中的元素simScore[i][j] 表示属性i与属性j之间的属性相似度，属性相似度可以是大于等于0且小于 等于1的实数。该属性相似度的分值可以是名称相似度、属性值相似度、及 交叉相似度加权和。名称相似度用来度量属性名称之间的文本相似度；属性 值相似度用来度量属性值之间的文本或数值相似度；而交叉相似度可以通过 比较属性名称与属性值，来挖掘出更多的匹配情况。

名称相似度的计算可以简单地通过把名称视为字符串，然后利用现有的 计算字符串之间相似度的手段来实现；然而，在本发明的实施例中，还可以 进一步考虑该属性上一级的亲属性的名称。属性i和属性j之间的名称相似度 nameScore[i][j]的计算可以使用字符串相似度度量，可采用各种编辑距离度量， 例如Levenshtein距离、SmithWaterman距离、Dice距离等等，现有的开源软 件即可以实现上述字符串之间距离的计算。属性自身文本的相似度可以表示 为texSim[i][j]，其各自的亲属性之间的文本相似度可以表示为parentSim[i][j]， 则属性i与属性j之间的名称相似度nameScore[i][j]可以通过以下公式(1)计 算：

nameScore[i][j]＝w_ttexSim[i][j]+w_pparentSim[i][j]      (1)

其中，权重w_t和w_p均为大于等于0小于等于1的实数，且w_t+w_p＝1。

权重w_t和w_p可以通过考虑以下情况来确定。如果texSim[i][j]＞ε₁且 parentSim[i][j]＜ε₂，当自身名称文本相似度很高而亲属性名称文本相似度很低 时，例如属性名称为“type”的两个属性，而其亲属性分别为“Flash”和 “Battery”，ε₁和ε₂的取值范围例如可以是0.8≤ε₁≤1且0≤ε₂≤0.2，说明两个属 性本身名称相似度不高，在此情况下可以设w_t＝0，w_p＝1。如果texSim[i][j]＞ε₃且 parentSim[i][j]＜ε₄，当自身名称文本相似度不是很高而亲属性名称文本相似度 不是很低时，ε₃和ε₄的取值范围例如可以是0.5≤ε₃≤1且0≤ε₄≤0.5，说明两个 属性本身名称相似度可能很高，在此情况下可以设w_t＝1，w_p＝0。在其余情况， 可以设w_t≥0.5≥w_p。

通过上述方式，可以得到属性池中任意属性i与属性j之间的名称相似度 nameScore[i][j]。

属性i与属性j之间的属性值相似度的计算取决于值的规则化，例如，如 果值包括数值和度量单位，则表示其不应被考虑为字符串。如果度量单位是 可以相互转换的，表示二者可以相互比较，例如kg(千克)和oz(盎司)， 从而，诸如1.5kg和52oz的两个属性值可以经过单位转换后相互比较，如果 二者基本相同，即差值在根据经验而设定的一定阈值范围内，则属性值相似 度valueScore[i][j]为1，否则为0。如果度量单位是不可以相互转换的，例如 mm(毫米)和ms(毫秒)，表示二者不可以相互比较，属性值相似度 valueScore[i][j]为0。如果属性值仍然为字符串，则可以按照上述计算属性名称 相似度的方式来计算属性值之间的相似度。

在本发明的实施例中，可以进一步考虑交叉相似度crossScore[i][j]来发现 更多的通过一般相似度计算难以发现的隐藏关系，例如，属性i“Pixels： 18000000”(1千8百万像素)和属性j“Resolution:18megapixels”(分辨率18 兆像素)，无论通过比较属性名称还是属性值均难以发现其间的关联关系。然 而，通过度量属性i的名称“Pixels”与属性j的值“18megapixels”之间的 文本相似度、及属性j的名称“Resolution”与属性i的值“18000000”之间 的文本相似度，将此两个文本相似度取平均，作为属性i和j之间的交叉相似 度crossScore[i][j]。

因此，属性i与属性j之间的属性相似度simScore[i][j]可以通过以下公式 (2)计算：

simScore[i][j]＝w₁nameScore[i][j]+w₂valueScore[i][j]+w₃crossScore[i][j] (2)

其中，w₁+w₂+w₃＝1，并且w₁，w₂，w₃均为[0，1]区间内的实数，名称相似度 nameScore[i][j]，值相似度valueScore[i][j]，及交叉相似度crossScore[i][j]均为大于 等于0且小于等于1的实数。

由此，可以计算得到属性池中任意两个属性i和j之间的属性相似度，从 而构建出属性池的相似度矩阵。

在此，可以进一步考虑，取决于属性是否来自于同一对象，而对名称相 似度、属性值相似度、及交叉相似度赋予不同的权重。也就是，对于属性i 和属性j来自同一对象的情况和属性i和属性j来自不同对象的情况(可以简 单地通过前述对象索引来判断)，可以采用不同的标准来匹配。

进一步地，考虑到来自于同一对象的属性更有可能具有类似的值，而来 自于不同对象的属性更有可能具有不同的值。因此，对于两个待匹配属性来 自同一对象的情况，属性值的相似度更为重要，而对于两个待匹配属性来自 不同对象的情况，属性相似度可能更依赖于属性的名称。因此，属性来自于 同一对象的情况下名称相似度的权重小于属性来自于不同对象的情况下的权 重，属性来自于同一对象的情况下属性值相似度的权重大于属性来自于不同 对象的情况下的权重。具体地可以按照以下方式确定。

如果属性i和属性j之间的名称相似度、值相似度和交叉相似度中的最大 值大于某阈值，即max(nameSim[i][j]，valueSim[i][j]，crossSim[i][j])＞ε₀，其中ε₀的取 值例如可以是0.8≤ε₀≤1，则可以设 simScore[i][j]＝max(nameSim[i][j]，valueSim[i][j]，crossSim[i][j])。

当属性i和j属于同一对象时，设名称相似度、值相似度和交叉相似度的 权重参数分别为w₁′，w₂′，w₃′；当属性i和j属于不同对象时，设名称相似度、 值相似度和交叉相似度的权重参数分别为w₁″，w₂″，w₃″。原则是设定为 w₁′≤w₁″，w₂′≥w₂″，w₃′＝w₃″。

在属性i和j属于同一对象的情况下，如果nameSim[i][j]＜ε₅且 valueSim[i][j]＞ε₆，值相似度很高而名称相似度很低，在此情况下，可以设 0≤ε₅≤0.4且0.7≤ε₆≤1，表明两个属性相似度很高，因此可以设 w₁′＝0，w₂′＝1，w₃′＝0。而在属性i和j属于不同对象的情况下，如果 nameSim[i][j]＞ε₆且valueSim[i][j]＜ε₅时，即名称相似度很高而值相似度很低，表 明两个属性相似度很高，因此可以设w₁″＝1，w₂″＝0，w₃″＝0。另外，如果 nameSim[i][j]+valueSim[i][j]＞1，即名称相似度和值相似度都较高或不低，则原 则仍然是w₁′≤w₁″，w₂′≥w₂″，具体则例如可以设w₁′≥0.7，w₂′≤0.3，w₃′＝0， w₁″≥0.85，w₂″≤0.15，w₃″＝0。如果nameSim[i][j]+valueSim[i][j]≤1，即名称相似度和 值相似度都不高，则原则仍然是w₁′≤w₁″，w₂′≥w₂″，具体则例如可以设 w₁′≥0.45，w₂′≤0.25，w₃′＝0.3，w₁″≥0.5，w₂″≤0.2，w₃″＝0.3。

通过以上处理过程，属性相似度计算步骤S300可以计算出属性池中任意 两个属性之间的属性相似度，构建相似度矩阵。然后，在属性整合步骤S400， 可以根据所构建的相似度矩阵，将属性整合到特征。

图4示出按照本发明实施例的属性整合步骤S400的总体流程图。如图4 所示，属性整合步骤S400可以包括：初选步骤S410，可以选定预定数目的 属性作为初始的中心属性；以及循环执行以下步骤S420-S480，直至特征符合 第一预定优化条件：初步聚类步骤S420，可以基于中心属性，根据属性的相 似度矩阵，将属性池中的属性聚类为各个初步特征；特征排序步骤S440，可 以分别计算各个初步特征的分值，依据分值对各个初步特征进行排序；特征 过滤步骤S460，可以基于初步特征的次序，按照预定过滤规则对初步特征进 行过滤；第一判断步骤S480，可以判断经过过滤的特征是否符合第一预定优 化条件，如果经过过滤的特征符合第一预定优化条件，则将经过过滤的特征 作为属性聚类的结果，否则确定经过过滤的特征的中心属性，返回所述初步 聚类步骤S420。

如上所述，输入到属性整合步骤S400的是表示属性池的属性之间的属性 相似度(也可以称为“距离”)的相似度矩阵。属性整合步骤S400的输出是 符合一定条件的特征，此特征也是实施本发明实施例的将对象实例的属性规 则化为特征的方法所得的输出。为了与后文将要描述的另一条件相区别，在 此该条件称为“第一预定优化条件”。

聚类过程总体上围绕一定数目的中心属性而进行，其它属性根据与其的 属性相似度来决定是否归入该中心属性，中心属性并未恒定不变，而是随着 聚类的过程而调整变动。聚类的过程总体上是循环迭代的过程，因而需要“起 点”，在此，“起点”的确定通过初选步骤S410实现，在此初选步骤S410， 可以选定预定数目的属性作为初始的中心属性。其中，中心属性的预定数目 K也就是最终要聚类得到的特征的数目，K可以通过多种方式确定，例如可 以通过用户指定，也可以设定默认值，还可以把实例的尺度(属性元素的数 目)的平均确定为K值，此外，还可以把实例的最大尺度确定为K值。其中 初始中心属性的选定可以是随机的，或者也可以将属性池中的目前位于一定 位置的某K个属性确定为初始中心属性。此后，将从初始中心属性开始，通 过循环迭代来得到符合条件的特征。

在初步聚类步骤S420，基于中心属性，根据属性的相似度矩阵，将属性 池中的属性聚类为各个初步特征。图5示出按照本发明实施例的初步聚类步 骤S420的流程图。如图5所示，初步聚类步骤S420也是循环过程，包括循 环执行以下步骤S422至S426，直至各个特征符合第二预定优化条件：属性 分配步骤S422，可以基于中心属性，根据属性的相似度矩阵，把属性池中的 属性分配到各个中心属性，各个属性集合作为特征；中心属性计算步骤S424， 可以计算各个特征的中心属性；第二判断步骤S426，可以根据各个特征的中 心属性判断各个特征是否符合第二预定优化条件，如果符合第二预定优化条 件，则将各个特征作为初步聚类所得的初步特征，否则将各个特征的中心属 性代入所述属性分配步骤。

初步聚类步骤S420可以采用任何现有的聚类算法及优化器。在此，例如 可以采用k均值算法(k-means)，k均值算法例如在 http://croce.ggf.br/dados/K％20mean％20Clustering1.pdf或 http://en.wikipedia.org/wiki/K-means_clustering中均有描述。本发明实施例的初步聚 类步骤S420可以利用现有的k均值算法，采用现有技术部分的细节不再赘述。

初步聚类步骤S420的输入，也即属性分配步骤S422的输入为尺度为n*n 的相似度矩阵simScore[n][n](n为属性池中的属性数目)、聚类数目K、以及当 时的K个中心属性。

在属性分配步骤S422，根据属性的相似度矩阵所体现的各个属性之间的 属性相似度(距离)，来把除当前的中心属性之外的各个属性分别分配到与之 属性相似度最高(距离最近)的中心属性，从而，可以基于各个中心属性而 形成相应的属性集合。

然后，在中心属性计算步骤S424，计算各个属性集合的中心属性，例如， 可以通过以下公式(3)来计算第k个当前聚类cluster(k)(属性集合)的中心 属性：

$c_k=\left\{i\right|\underset{i\in \mathrm{cluster}\left(k\right)}{\max }\left(\underset{j\in \mathrm{cluster}\left(k\right)}{\Sigma }\mathrm{simScore}\right[i\left]\right[j\left]\right)\}---\left(3\right)$

其中c_k是计算得到的聚类k(表示为cluster(k))的中心属性，取代此前此聚类 (属性集合)的中心属性，k∈[1，K]，i和j是聚类k中的属性，simScore[i][j]是 属性i和j的相似度值。此公式(3)表明，所得到的新的中心属性c_k是这样 的聚类k中的属性i，其与聚类k中所有属性的属性相似度之和在聚类k的所 有属性中最大。

然后，在第二判断步骤S426，判断各个特征的中心属性是否符合第二预 定优化条件。作为一种迭代手段，判断是否符合第二预定优化条件可以理解 为判断当前迭代聚类结果(初步聚类)是否收敛，如果收敛，则迭代结束， 否则重复执行之前的步骤S422-S424。

有多种方式判断初步聚类的结果是否收敛，一种可以采用的原则是，判 断此次计算得到的中心属性与上次迭代的结果是否相同，如果该聚类的中心 属性不再变化，则认为该聚类已经收敛。或者，还可以采用以下公式(4)所 体现的第二优化函数：

$J2=\underset{k=1}{\overset{K}{\Sigma }}\underset{i\in \mathrm{cluster}\left(k\right)}{\Sigma }{\left(\mathrm{simScore}\right[i\left]\right[c_k\left]\right)}^2---\left(4\right)$

其中，与上述公式(3)中相同的参数的含义与公式(3)中相同，simScore[i][c_k] 表示聚类cluster(k)中属性i与中心属性c_k之间的属性相似度。

在此情况下，第二预定优化条件具体则是第二优化函数值J2最小化，最 小化的具体方法可以是设定某经验阈值ε″，当两次迭代的第二优化函数值J2 的差小于该阈值ε″，即判定达到最小化。

如果初步聚类的结果符合所设置的第二预定优化条件，则可以将各个当 前所得聚类、或者说属性集合，作为特征代入此后的处理过程，由于在此所 得的特征并非最终结果，因此可以称为初步特征。如果初步聚类的结果不符 合所设置的第二预定优化条件，则将各个中心属性代入属性分配步骤S422， 再次进行循环过程。

初步聚类步骤S420得到的初步特征在特征排序步骤S440中进行排序。 可以考虑多种方式来计算初步特征的分值，从而使得能够依据分值对各个初 步特征进行排序。

例如，可以考虑度量初步特征的重要性，将重要性的度量值作为其分值。 一种度量重要性的方法可以是以初步特征所包含的属性与中心属性的属性相 似度之和来进行度量，初步特征所包含的属性与中心属性的属性相似度之和 越高则其重要性分值越高。在此情况下，初步特征k的重要性分值可以定义 为：

$\underset{i\in \mathrm{cluster}\left(k\right)}{\Sigma }\mathrm{simScore}\left[i\right]\left[c_k\right]$

其中，与前述公式中相同的参数具有与之相同的含义。

或者，例如，可以考虑度量初步特征中属性在原对象实例中的位置，总 体原则是，特征中属性越多，属性在原实例中的位置越靠前，分值越高。在 此情况下，初步特征k的位置分值可以定义为：

$\frac{n_k}{\underset{i\in \mathrm{cluster}\left(k\right)}{\Sigma }i.\mathrm{position}}$

其中，与前述公式中相同的参数具有与之相同的含义，n_k表示初步特征k(聚 类k)的尺度，可以是其所包含的属性的数目，i.position表示聚类k中属性i 在原对象实例中的位置，可以考虑实例中最底层(通常是具有属性值的一层) 的属性，而不考虑属性所处的层次，将最底层属性从上至下视为一个列表， 则每个属性具有其在实例中的排序位置，此排序可以从1而非0开始。

可以选择上述任意一种分值作为对初步特征进行排序的依据，然而，在 特征排序步骤S440中，也可以计算各个初步特征的重要性分值和位置分值， 将重要性分值和位置分值加权相加，作为相应初步特征的分值。在此情况下， 初步特征k的分值可以通过以下公式(5)计算得到：

${\mathrm{Score}}_{\mathrm{feat}\left(k\right)}=w_{\mathrm{sim}}\underset{i\in \mathrm{cluster}\left(k\right)}{\Sigma }\mathrm{simScore}\left[i\right]\left[c_k\right]+w_{\mathrm{position}}\frac{n_k}{\underset{i\in \mathrm{cluster}\left(k\right)}{\Sigma }i.\mathrm{position}}---\left(5\right)$

其中，Score_feat(k)表示初步特征k的分值，w_sim和w_position分别表示重要性分值和 位置分值的权重，w_sim+w_position＝1，且w_sim＞w_position。

对每个初步特征均计算得到其分值之后，可以据此对初步特征进行排序， 分值越高越靠前，从而每个特征均具有由其排序位置所表示的位置值，在此， 可以设排序从1而非0开始。

特征排序步骤S440所得的具有次序的初步特征的序列进入特征过滤步 骤S460进行处理。在特征过滤步骤S460，基于初步特征的次序，可以对初 步特征进行合并、拆分、及去除，得到经过过滤的特征。

可以首先考虑将初步特征序列中相似的特征合并，此过程可以基于初步 特征的次序来进行。一种可以选择的方式是，先依次判断第一个初步特征与 其后的初步特征是否能够合并，如果能够合并则立即合并，然后再判断能否 与此后的初步特征合并；在先的初步特征与其后的所有特征判断能否合并之 后，下一初步特征再以相同方式进行合并判断。本领域技术人员可以认识到， 判断初步特征是否合并的方式不限于此，也可以先判断任意两个初步特征之 间能否合并，然后再合并符合合并标准的初步特征；此外，还可以采用其它 方式。

对于任意两个初步特征p和q，可以通过以下方式计算其耦合值 coupling(p，q)，如果耦合值大于一预定阈值，则初步特征p和q合并，由前文 描述可知，初步特征p和q分别对应于属性聚类p和q，因此初步特征p和q 合并也即聚类p和q的属性归在一起，在此，可以以前文所述的方式，例如 中心属性计算步骤S424中所采用的方式，计算合并的新特征的聚类中心属 性。

例如，可以通过以下公式(6)来计算初步特征p和q的耦合值 coupling(p，q)：

$\mathrm{coupling}(p,q)=\max \left(\mathrm{simScore}\right[c_p\left]\right[c_q],\frac{1}{2}\underset{i\in \mathrm{cluster}\left(p\right)}{\Sigma }\mathrm{simScore}[i\left]\right[c_q]+\frac{1}{2}\underset{j\in \mathrm{cluster}\left(q\right)}{\Sigma }\mathrm{simScore}[c_p\left]\right[j\left]\right)---\left(6\right)$

其中，c_p和c_q分别表示初步特征p和q所对应的聚类p和q的中心属性， simScore[c_p][c_q]表示中心属性c_p和c_q的属性相似度； 表示聚类p中所有属性与中心属性c_q的属性相似度之和； 表示聚类q中所有属性与中心属性c_p的属性相似度之和。

公式(6)表示，coupling(p，q)的取值为中心属性c_p和c_q的属性相似度与 和的平均值中的最大值。

与耦合值coupling(p，q)相比较的阈值的取值范围为[0，1]，可以根据经验设 定其中的区间，例如，该阈值的取值范围可设定为大于等于0.1小于等于0.3。 如果耦合值coupling(p，q)大于或大于等于该阈值，则将两个聚类合并为一个聚 类，并为其重新计算中心。合并后的聚类可以继续与其它聚类计算耦合值， 以判断是否继续与其它聚类进行合并。

经过合并判断之后的特征仍然为一序列，可以基于此时的序列及其各初 步特征的次序，对各个初步特征进行拆分判断，以将聚类中的不相似的属性 拆分到不同的新的聚类，以确保拆分后的聚类(特征)中属性的相似性。

例如，可以计算初步特征k的一致性值cohesion(k)，判断其是否小于或小 于等于一预定阈值，如果初步特征k的一致性值cohesion(k)小于或小于等于该 预定阈值，则将该初步特征k对应的聚类k拆分为多个聚类。

例如可以通过以下公式(7)计算一致性值cohesion(k)：

$\mathrm{cohesion}\left(k\right)=\underset{i\in \mathrm{cluster}\left(k\right)}{\Sigma }\mathrm{simScore}\left[i\right]\left[c_k\right]---\left(7\right)$

其中，各参数含义通过前文描述可知。

在通过公式(7)确定聚类的一致性值的情况下，该预定阈值的取值范围 可以是大于等于0.3小于等于0.4的区间，如果一致性值cohesion(k)小于或小 于等于该预定阈值，则确定要对该聚类(初步特征)进行拆分。

聚类可以拆分为2个或2个以上的新聚类。拆分为2个聚类的方式可以 是：选择聚类中其间属性相似度最小的两个属性分别作为中心属性，然后可 以(i)将聚类中的其它属性根据与中心属性的属性相似度而分配到两个中心 属性中距离更近的中心属性，从而形成两个新的聚类，或(ii)设定某阈值， 令与聚类中心属性相似度值小于该阈值的属性构成新的聚类。

以此类推，拆分为2个以上聚类的方法可以是选择多个彼此属性相似度 值小于某阈值的属性分别作为中心属性，将聚类中的其它属性根据与中心属 性的属性相似度而分配到距离最近的新的中心属性。

拆分出新的聚类之后，可以通过前述方式计算新聚类的中心属性。并且， 拆分所得的新的聚类可以以前述方式计算其相应的特征分值，根据分值进行 排序。

经过拆分处理的初步特征仍然为一序列，可以基于此时的序列及其各初 步特征的次序，对各个初步特征进行去除判断。

可以考虑多种方式来去除初步特征序列中意义不大的初步特征。例如， 可以去除其中属性数目比较少的初步特征，例如，如果某个初步特征具有的 属性数目小于等于3，则对其进行去除。或者，可以计算各个初步特征的一 致性值cohesion(k)，在采用前述公式(7)的情况下，如果一致性值cohesion(k) 小于或小于等于某个预定阈值，则去除该初步特征，此处的预定阈值的取值 范围仍然可以是大于等于0.3小于等于0.4的区间。

本领域技术人员可以认识到，上述对初步特征进行合并、拆分、及去除 的过程不必按照上述方式依次进行，而是可以以任意选择其中全部或部分过 程，以任意顺序进行。

经过过滤处理的特征然后进入第一判断步骤S480进行判断，即判断经过 过滤的特征是否符合第一预定优化条件。

在第一判断步骤S480，判断属性整合步骤S400的循环迭代过程是否已 经收敛，收敛的标准是符合第一预定优化条件。

第一预定优化条件可以采用多种方式，例如，第一预定优化条件可以是 各个特征相应的聚类中心属性与上次迭代结果相同。

或者，还可以采用以下公式(8)所体现的第一优化函数：

$J1=\frac{\underset{k=1}{\overset{K}{\Sigma }}{n}_k\mathrm{simScore}\left[c_k\right]\left[c\right]}{\underset{k=1}{\overset{K}{\Sigma }}\frac{1}{n_k}\underset{i\in \mathrm{cluster}\left(k\right)}{\Sigma }\mathrm{simScore}\left[i\right]\left[c_k\right]}---\left(8\right)$

其中，与前述公式中相同的参数具有与在之前公式中相同的含义，c是将当前 所有属性视为构成一个聚类的中心属性，可以通过前述中心属性计算步骤 S424的处理过程计算，c_k是聚类k的中心属性，n_k是聚类k中的属性数目， simScore[c_k][c]是属性c_k与属性c之间的属性相似度。

公式(8)的第一优化函数的分母体现特征(聚类)内属性的一致性，分 子体现特征(聚类)之间的耦合度，优化的方向应是特征(聚类)内属性的 一致性越大越好，而(聚类)之间的耦合度越小越好，也就是，希望第一优 化函数值最小化。因此，在此情况下，第一预定优化条件可以是设定某阈值ε′， 当两次迭代的第一优化函数值的差小于该阈值ε′，即判定达到最小化。

如果经过过滤的特征满足收敛条件，则迭代结束，将经过过滤的特征作 为属性聚类的结果，也即本发明实施例的结果来输出；否则，可以以例如前 述的中心属性计算步骤S424的方式，确定经过过滤的特征的中心属性，返回 所述初步聚类步骤S420，进行下一轮迭代。

符合第一判断步骤S480的第一预定优化条件而输出的特征也是本发明 实施例的对象实例的属性规则化为特征的方法的输出结果。

本发明还可以实施为一种将对象实例的属性规则化为特征的设备，可以 用来执行前述的将对象实例的属性规则化为特征的方法。图6示出按照本发 明实施例的将对象实例的属性规则化为特征的设备的总体框图。如图6所示， 本发明实施例的将对象实例的属性规则化为特征的设备包括：对象实例获取 装置100，可以用来执行前述的对象实例获取步骤S100，以基于给定的领域 获取该领域的对象实例；属性池建立装置200，可以用来执行前述的属性池 建立步骤S200，以提取所获取的对象实例中的属性，基于所提取的属性建立 属性池；属性相似度计算装置300，可以用来执行前述的属性相似度计算步 骤S300，以基于属性池中任何两个属性之间的相似度，建立相似度矩阵；属 性整合装置400，可以用来执行前述的属性整合步骤S400，以根据属性池中 属性的相似度矩阵，将属性聚类为特征。

其中，所述属性池建立装置200可以基于给定的属性性质，在属性池中 排除不符合所给定属性性质的属性。

其中，所述属性相似度计算装置300可以分别计算属性池中任何两个属 性之间的名称相似度、属性值相似度、及交叉相似度，将该名称相似度、属 性值相似度、及交叉相似度加权相加，作为该两个属性之间的相似度。

而且，所述属性相似度计算装置300可以取决于属性是否来自于同一对 象，而对名称相似度、属性值相似度、及交叉相似度赋予不同的权重。

而且，所述属性相似度计算装置300可以按照以下原则来赋予权重：属 性来自于同一对象的情况下名称相似度的权重小于属性来自于不同对象的情 况下的权重，属性来自于同一对象的情况下属性值相似度的权重大于属性来 自于不同对象的情况下的权重。

其中，所述属性整合装置400可以包括：初选装置，可以用来执行前述 的初选步骤S410，选定预定数目的属性作为初始的中心属性；以及初步聚类 装置，可以用来执行前述的初步聚类步骤S420，基于中心属性，根据属性的 相似度矩阵，将属性池中的属性聚类为各个初步特征；特征排序装置，可以 用来执行前述的特征排序步骤S440，分别计算各个初步特征的分值，依据分 值对各个初步特征进行排序；特征过滤装置，可以用来执行前述的特征过滤 步骤S460，基于初步特征的次序，按照预定过滤规则对初步特征进行过滤； 第一判断装置，可以用来执行前述的第一判断步骤S480，判断经过过滤的特 征是否符合第一预定优化条件，如果经过过滤的特征符合第一预定优化条件， 则将经过过滤的特征作为属性聚类的结果，否则确定经过过滤的特征的中心 属性，将该经过过滤的特征的中心属性输出到所述初步聚类装置，进行下一 循环的处理。

其中，所述初步聚类装置可以包括：属性分配装置，可以用来执行前述 的属性分配步骤S422，基于中心属性，根据属性的相似度矩阵，把属性池中 的属性分配到各个中心属性，各个属性集合作为特征；中心属性计算装置， 可以用来执行前述的中心属性计算步骤S424，计算各个特征的中心属性；第 二判断装置，可以用来执行前述的第二判断步骤S426，根据各个特征的中心 属性判断各个特征是否符合第二预定优化条件，如果符合第二预定优化条件， 则将各个特征作为初步聚类所得的初步特征，否则将各个特征的中心属性输 出到所述属性分配装置，进行下一循环的处理。

其中，在所述特征排序装置可以计算各个初步特征的重要性分值和位置 分值，将重要性分值和位置分值加权相加，作为相应初步特征的分值。

其中，所述特征过滤装置可以基于初步特征的次序，对初步特征进行合 并、拆分、及去除，得到经过过滤的特征。

本发明还可以通过一种将对象实例的属性规则化为特征的系统来实施。 图7是示出按照本发明实施例的将对象实例的属性规则化为特征的系统1000 的总体框图。如图7所示，将对象实例的属性规则化为特征的系统1000可以 包括：输入设备1100，用于从外部输入将要处理的领域，例如可以包括键盘、 鼠标器、以及通信网络及其所连接的远程输入设备等等；处理设备1200，用 于实施上述的按照本发明实施例的将对象实例的属性规则化为特征的方法， 或者实施为上述的按照本发明实施例的将对象实例的属性规则化为特征的设 备，例如可以包括计算机的中央处理器或其它的具有处理能力的芯片诸如 DSP等等，可以连接到诸如因特网的网络(未示出)，根据处理过程的需要而 从网络获取数据等等；输出设备1300，用于向外部输出实施上述将对象实例 的属性规则化为特征的过程所得的结果，例如可以包括显示器、打印机、以 及通信网络及其所连接的远程输出设备等等；以及存储设备1400，用于以易 失或非易失的方式存储上述将对象实例的属性规则化为特征的过程所涉及的 图像、所得的结果、命令、中间数据等等，例如可以包括随机存取存储器 (RAM)、只读存储器(ROM)、硬盘、或半导体存储器等等的各种易失或非 易失性存储器。

图8示出本发明实施例的将对象实例的属性规则化为特征的方法、设备 及系统所输出的特征的一个示例。如图8所示，特征(Feature)为尺寸 (Dimension)(以聚类的中心属性表示该特征)，则其可以包含以下属性，诸 如Dimension，Dimensions，Dimension(w*h*d)，Size，以上4个属性均可 能出现在不同网络资源中用来表示尺寸，该特征还可以包括诸如Width(宽 度)，Height(高度)，depth(厚度)的属性，此3个属性也可能出现在不同 网络资源中用来表示某一维度的尺寸。

本发明实施例的将对象实例的属性规则化为特征的方法、设备及系统所 输出的结果可以用来以多种方式提供给用户。图9示出本发明实施例所得的 特征提供给用户的一种方式。例如，根据用户所给定的领域而得到的特征可 以以如图9所示的特征矩阵的形式提供给用户。如图9所示的特征矩阵可以 体现出各个特征与各个对象相配合情况下的值，例如，某款相机(对象)的 某一方面(特征)的参数(值)，特别有助于进行不同产品(对象)关于同一 方面(特征)的性能的比较。特征矩阵还可以用于领域本体的建构。

本发明实施例的将对象实例的属性规则化为特征的方法和设备进行了属 性相似度计算，对于来自同一对象及不同对象的属性采用不同的标准来匹配。 例如，匹配来自同一对象的属性时可以更多考虑属性值，而匹配来自不同对 象的属性时可以更多考虑属性名称，因为不同对象的相同属性通常具有不同 的属性值。而且，本发明实施例的方法和设备在计算相似性度量时基本上仅 仅依赖资料库(corpus)中的分布性质，而不是现有的知识资料。

通过本发明实施例，能够实现属性级别的聚类，并将相似属性聚类为特 征，而无需采用任何领域信息。进一步地，本发明实施例可以基于混合的匹 配相似度，进行属性名称、属性值之间的匹配，还可以进行属性名称和属性 值之间的交叉匹配，来对属性进行聚类，此外，在匹配过程中还可以进一步 考虑属性层级，也就是确定属性相似度时考虑上一级属性的相似度，从而可 以挖掘出更多隐藏的匹配属性对。另外，本发明实施例还可以利用迭代手段 对特征进行聚类-排序-过滤，显著地降低了复杂性。

在说明书中说明的一系列操作能够通过硬件、软件、或者硬件与软件的 组合来执行。当由软件执行该一系列操作时，可以把其中的计算机程序安装 到内置于专用硬件的计算机中的存储器中，使得计算机执行该计算机程序。 或者，可以把计算机程序安装到能够执行各种类型的处理的通用计算机中， 使得计算机执行该计算机程序。

例如，可以把计算机程序预先存储到作为记录介质的硬盘或者ROM(只 读存储器)中。或者，可以临时或者永久地存储(记录)计算机程序到可移 动记录介质中，诸如软盘、CD-ROM(光盘只读存储器)、MO(磁光)盘、 DVD(数字多功能盘)、磁盘、或半导体存储器。可以把这样的可移动记录介 质作为封装软件提供。

本发明已经参考具体实施例进行了详细说明。然而，很明显，在不背离 本发明的精神的情况下，本领域技术人员能够对实施例执行更改和替换。换 句话说，本发明用说明的形式公开，而不是被限制地解释。要判断本发明的 要旨，应该考虑所附的权利要求。