基于属性关联相似度的中文简称匹配算法研究∗

郭 晖董 源周 钢

（1.海军工程大学电子工程学院计算机工程系 武汉 430033）（2.海军水文气象中心 北京 100000）

1 引言

大数据应用中由于数据来源各异、结构不一，为了提高数据分析性能，需要对不一致、不准确的等脏数据进行数据清洗，或对不同数据源的同一数据进行数据集成［1～2］。字符匹配是指寻找表示实体世界中同一实体的字符串，相互匹配的字符串应对具有同义性，可互换［3］。

在中文语言环境中，对于中文固定名词，如组织机构名等常用简称，如“华中科技大学”简称为“华科大”或“华科”，研究同一名词的“简称”和“全称”两个字符串的匹配算法，其核心在于字符串相似度的度量方法。

本文针对大数据应用特点，以中文固定名词所在数据源为基础，采用基于统计方法，运用数据挖掘技术，提出了基于属性相关度的中文简称匹配算法，该算法通过对匹配名词所处属性的强相关属性的数据范围对比相似度，按照中文简称和全称比量设置置信度，两者乘积得到匹配度。该算法对大数据中保障数据质量，提高数据分析性能具有重要意义。

2 问题背景

中文语言环境中，对于很多固定名词，通常会约定俗成的简短称谓，即为简称。在大数据具体应用中，由于数据采集规范要求不同，数据来源不一，容易出现同一对象有简称和全称两种不同表述，在对数据进行数据清洗或对不同数据源进行数据集成时，需要对中文固定名词的“简称”和“全称”字符串进行有效匹配，是提高数据质量的重要途径。

对中文固定名词简称，通过对中国部分高校简称与全称对比表分析，中文简称具有以下特点规律：一是其长度相对全称要简短很多；二是简称字符串中所有字符在全称中均有出现；三是简称中基本单个字符，有意义词极少出现。

对中文固定名词的“简称”和“全称”进行匹配，本质就是字符串的相似度计算。目前，较具代表性的算法有基于相同字词［4］、基于编辑距离［5］、基于向量空间［6］、基于语义词典［7］、基于统计关联［8］和基于语义依存［9］等方法。前三种方法是基于字符串本身分析，且在英文字符串匹配中有较好应用，但在中文匹配中由于涉及到分词问题，将大幅降低算法准确性，增加执行时间；基于语义词典、基于统计关联依托词典实现，对于中文专属名词中生涩词汇多，简称字符串简短且无意义，基于语义依存对于短中文应用效果较差，所以针对中文固定名词的简称和全称字符匹配问题，由于其分词不明，语义不清，文幅较短特点，已有算法在其上应用存在局限性。

因此，在大数据应用背景下，已拥有大量相关数据基础上，可以考虑使用以统计学为基础，使用数据挖掘技术，提出一种基于属性关联度的中文“简称”和“全称”的匹配算法。

3 基于属性关联度的匹配算法

根据对我国高校部分简称［10］分析中文简称特点，先采用单个字符进行初步匹配，逐步抽取“简称”字符串中的单个字符与“全称”字符串中的所有字符进行逐一比较，并将匹配成功的字符个数与“简称”字符串长度相同，从而判断两者基本匹配。若中文“全称”字符串长度n一般不大，算法的时间复杂度O（nlogn）是非常有限。

但由于存在中文简称指代不明情况，需要做进一步更加准确的匹配，如“南京大学”“南昌大学”均可简称为“南大”。

3.1 算法基本思想

基于属性关联度的匹配算法主要基于某一个属性数据的区分可以由与该属性密切相关属性的区分来发现，即可以通过密切相关属性来辨别某一属性的数据。假设中文“简称”和“全称”匹配的属性为A，算法包括四个步骤：选取A的强关联属性；分别分析“简称”和“全称”在强关联属性的分布相似情况；“简称”和“全称”属相的元组数量确定置信度；以关联相似度同置信度的乘积为匹配度。算法整体框架示意如图1所示。

图1 算法整体框架示意图

3.2 属性关联相似度计算

3.2.1 属性关联度

属性关联度就是数据源中S中属性集合A中任意两个属性间的关联程度，这里主要研究属性集合中各属性同 D 的关联程度。属性关联度计算有基于线性相关性计算或基于贝叶斯分类器进行实现等方法，由于数据源中各属性数据数值型数据较少使用线性相关性不能计算完全，对于贝叶斯分类器方法通过针对决策属性的条件属性调整判断关联度，只能得到条件数据的关联强度定性数据。因此，这里使用基于信息熵理论的互信息度来评价属性关联度。

在数据源中，两个属性间如果相互关联，那么其中一个属性数据变化时，另一个关联属性也会发生相应变化，两属性关联程度越强，那么联动变化越紧密。从信息熵的角度来看，属性间的关联度转化为一个属性的变化引起另一属性变化的互信息度。

苗夺谦在文献［11］中的基本方法，给出了一种计算互信息度的基本方法。该方法以属性D为目标属性，以A’属性集为条件属性，研究A’中各属性和属性D的互信息度。由于D∩A’=Ø，D∪A’=A，那么U在D和A’上的概率分布为

其中，p（Ai）=|Ai|/|U|，根据信息熵的定义，属性集 A’的信息熵可以定义为

那么目标属性D相对于条件属性集A’的条件信息熵为

根据粗糙集理论［12～13］，计算A’中所有支持D的属性集合，即为A’的D核CoreD（A’），记A0=CoreD（A’）。

按照互信息计算方法，依次计算I（D|A0），由于讨论不含D核的互信息没有衡量意义。因此，对于不含D核的集合A’-A0的任意属性Ak的相对D的关联度为

对于D核集合A0中的属性则不作单独讨论，认为RD（A0）=I（D|A0）。因此得到了A’相对于D的所有属性关联度。

3.2.2 属性相似度

属性相似度主要研究的是属性D上d1，d2对应的关联属性集合A’D中各属性上数据分布的相似程度。在大数据应用中，代表中文固定名词的“简称”和“全称”的数据如果指代相同，由于参与统计数据量大，那么其相关属性上的数据分布应当近似。

对于大数据应用中的具体业务数据源，除基本的数值类型数据外，其余文本型、非结构化数据等可以通过聚集、分类等技术转化为离散型数值，重点对离散型数据进行分析研究，对于连续型数据可以按照隶属函数的方法转化为离散型数值。

分析关联属性中离散型数据进而分析其分布近似情况。对于关联属性Ak中离散型数据在U上的集合｛a1，a2，…an｝，主要统计各数据点分布数据个数集合Ck=｛c1，c2，…cn｝，分别计算 d1，d2对应的统计分布集合为 C1k=｛c11，c12，…c1n｝，C2k=｛c21，c22，…c2n｝，那么属性D中d1，d2相对关联属性A的差异体现在Ak同一数据ai的统计数占总比值的差值，则两者在离散数据类型属性Ak相似度表示是100%减去差异度，即为

当属性D取d1，d2对应在关联属性Ak上的数据集在各离散点分布情况完全相同，即认为d1，d2本质上完全相同的，那么式（6）的后半部分为0，此时相似度为1，即100%。

3.2.3 属性关联相似度

属性关联相似度作为判断中文固定名词所在属性D中两个数值“简称”和“全称”的d1，d2的相似程度，对与属性D相关联属性A’进行相似分析得到无当量相似度SEAi（d1，d2）。在判断d1，d2的匹配程度时，考虑所有关联属性A’，那么以关联属性集合A’中各属性权重可以用与属性D的关联度表示。

因此，首先对 A’中的所有属性 A0+｛A1，A2，…Am｝，其中A0为属性D的核其中包括n-m个属性，并对A’-A0的非核属性进行重新编号，通过归一化方法得到各属性或属性集的权重矩阵为

那么，可以得到属性D上d1，d2的关联相似度RS（d1，d2）为W和 A’中各属性相似度的对应乘积和，是一个小于100%的无量纲数值，即

3.3 置信度的引入及匹配度计算

由于关联相似度的计算主要基于统计学的，需要大量基础数据作为支撑。但同时要注意，作为数据源S上属性D=d1，D=d2所对应的数据集元组数量足够多且相当，否则，当D=d1，D=d2数据量有限且不相当时，即便关联相似度较高，可以认为是偶然因素导致，不具备普遍意义。样本量数据与结果置信度密切相关［14］，因此，需要在关联相似度基础上引入置信度。

根据置信度与样本量的密切关系，使用频繁共现熵方法［15］分析置信度，假设D=d1，D=d2对应数据量为C1，C2，当 C1，C2不是足够大时，那么 d1在属性D对应的全样本空间分布概率为p（d1）=C1/（C1+C2），同理可得 p(d2)的值。

那么频繁共现熵 f(D)值为

由式（9）得到置信度c(D)为

由式（8）和（10）得到 d1，d2的匹配度为

4 实验分析及效果评价

根据数据堂提供的我国15万在售小区信息数据集，数据集包含数据项：小区id、城市、小区名称、均价、小区地址、所在区域、周边学校、邮编、竣工时间、总户数、停车位、绿化率、容积率、物业费，以及停车位信息包含停车场方式、价格车位数等方面信息。由于数据源来自网络，数据规范性较差，在周边学校数据项中出现比较多的高校名称简称，主要研究该属性中高校简称匹配问题。

大数据应用中，对数据集进行数据预处理，主要先完成“周边学校”其他属性，如将均价按千元，物业费按1元划分区间等级，“周边学校”属性按标点划分开来。按照基于属性关联度方法对高校名称进行匹配，以数据项“周边学校”为目标属性D，得到属性D的核CoreD为A0=｛均价，所在区域，邮编｝，按照式（5）得到其余属性的关联度（忽略值＜0.01的属性），那么通过式（7）归一化处理得到属性集合｛均价，所在区域，邮编，物业费，城市｝的相对“周边学校”属性D关联度权重为

这里对属性D中的d1=“华中科技大学”进行分析，通过单字匹配方法进行初步匹配得到d2=“华科大”，d3=“华科”，d4=“科大”，d5=“中科大”，以 d1为基准，计算关联属性集｛均价，所在区域，邮编，物业费，城市｝的相似度为

表1 关联属性集的相似度

根据式（8）得到 d2，d3，d4，d5相对属性D的值 d1的匹配关联度为

认为d2，d3同全称d1的匹配度高，且匹配度均超过75%，判断与d1为同一指向，d4，d5与d1的匹配度均没有达到35%，不认为匹配。根据现实简称情况，该匹配算法结果符合实际情况。

5 结语

该匹配算法主要运用于大数据具体分析及应用之前，对于匹配算法结果匹配度不高时候，采用关联属性方法会导致后续的关联分析存在效能增强的情况，因此对于涉及各属性关联情况的主因分析等大数据应用时，应谨慎使用本算法。

在大数据应用中，为解决数据清洗或数据集成中中文固定名词的简称和全称匹配问题，提出一种基于属性关联度的匹配算法。该算法在单词匹配基础上，通过其他属性同匹配目标属性间的关联度，及“简称”和“全称”对应关联属性上的数据分布相似度得到各属性的关联相似度，并结合“简称”和“全称”的数据量得到置信度，并结合关联相似度得到匹配度。该算法应用于小区数据集，发现该算法匹配度高，结果符合实际情况，算法匹配效果好。