2019, Vol. 40
2. 哈尔滨工业大学 计算机科学与技术学院, 黑龙江 哈尔滨 150001
2. School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China
基于Web2.0的电子商务网站，如淘宝网、ebay等得到了广泛的应用。这些电子商务网站有大量用户的参与销售，商品的数量非常巨大，这为用户购买商品带来了便利。但由于存在不同用户发布信息，对同一商品可能有不同的描述，这为用户检索商品带来了困难。特别是在商品数量巨大的情况下，用户检索出来的信息可能包含着大量同一商品的不同描述，这大大降低了用户挑选和购买商品的效率，影响了用户购买商品时的体验。
为了提高用户的检索效率，使用户检索出来的结果以实体为单位，需要对这些电子商务系统中的商品进行实体识别，即将系统商品进行分类，使得同一类中的商品指代现实中的同一实体。每一类描述同一个实体，基于这个结果，用户就可以根据自己的需求以实体为单位选择感兴趣的商品进行浏览和比价，提高了检索的效率和体验。尽管当前有一些实体方法提出[1-2]，但是这些方法并不适用于Web2.0电子商务系统中的实体识别，主要原因是效率和实体识别依据信息的问题。因而当前的实体识别方法难以直接应用到商品信息的实体识别上。
因而，利用商品名进行快速有效地实体识别也带来了如下技术上的挑战：1)商品名识别需要高效的处理算法；2)商品名中经常包含与商品本身无关的词；3)商品名中的词权重不同。
为了利用商品名信息有效地进行实体识别，本文提出了一种基于Jaccard相似性的实体识别方法，首先对商品名信息进行分词，将商品信息转化成为关键字的集合，然后利用关键字集合的加权Jaccard相似性对商品名信息进行分类。为了有效地确定关键字的权重，本文设计了基于词频的关键字权重设置方法。并利用用户的相关反馈修改关键字权重，达到有效进行实体识别的目的。本文提出的方法可以在用户检索或者在商品信息预处理时进行使用。
1 商品名实体识别基本方法考虑到Web2.0电子商务网站中商品名描述的复杂性，需要对商品名进行分词，分词方法可以采用现有的自然语言处理中的分词方法，形成每个商品名对应的关键词集合。商品名中的一些无用单词，如在关键词集合中将这些无用单词删除后，形成商品名对应的有效关键字集合。基于相似性对关键字集合进行划分，使得划分得到的每个类中的商品指代同一实体。
1.1 基于商品名的实体识别模型通过将商品名划分为关键词，基于商品名的实体识别结果是一个对应商品名集合S={s1, s2, …, sk}的关键字集合超集，KS={Ks1, Ks2, …, Ksk}，对于给定阈值θ，如果sim(si, sj)=Jaccard(Ksi, Ksj)>θ，则si和sj描述同一实体。根据此关系，一个商品名集合S可以建模成数据对象关系图GS=(VS, ES)，其中v∈VS对应sv∈S，若sim(sv, su)>θ，则(sv, su)∈ES。则商品名集合的实体识别对应VS的一个划分，并且满足同类点的内聚度尽可能高、而不同类点之间度尽可能低。因此，本文基于数据对象关系图定义实体识别问题如下：
问题1 给定一个图G=(V, E)和密度阈值δ，将V划分为若干类V1, V2, …, Vk，使得对于每个vi(1≤i≤k)，在Vi对应的生成子图G[Vi]中，v∈Vi, deg(v)>δ(|Vi|-1)，并且
在该定义中，密度阈值δ表示内聚程度，δ=1则表示每个生成子图要求是团。
1.2 商品名实体识别算法可以证明，问题1是同NP完全问题，不存在多项式时间算法，因此提出多项式时间的近似算法。该近似算法的基本思想是通过二分图匹配将图中的点集合划分为点对，将点集建模成图G′，使得G′中的每个点v对应一个点集Sv，G′中存在边(u, v)，则Su和Sv合并之后得到的结果满足内聚度约束，求得G′中的最大匹配，再将每个匹配的点对(u, v)对应的点集Su和Sv合并，重复以上过程，直到求得的G′中不存在边。
算法1 Resolution(G, δ)
输入:待划分的图G，内聚度阈值δ
输出:满足条件的划分图M
得到G的最大匹配M
M′=M
while G≠Ø do
G′=Ø
for M中的每个连通分量C do
将点nC加入VG′中
RnC=VC
| $ S_{n c}=\left\{v| |\left\{n_{i} | v \in \text { neigbour }\left(n_{i}\right)\right\}|\geqslant \delta| R_{n c} |\right\} $ |
for ∀v′∈VG do
if ∀n′∈Rv, n′∈SnC and n″∈RnC, n″∈Sv then
将边(nC, n′)加入EG′
得到G′的最大匹配M′
for M′中的每对匹配的节点(v1, v2)∈M′ do
for 每个节点n1∈Rv1 do
for 每个节点n2∈Rv2 do
将边(n1, n2)加入EM中
return M
可以证明，该算法的时间复杂性是O(n3.5)，近似比是n+[logn]，其中n是G中的节点个数。在具体实现时，无需构造整个图，在进行最大图匹配时可使用近似连接[27]实现。
2 词权重的设置方法由于大多数商品名较长且其对应关键词集合中关键字的重要程度并不相同，如“货到付款”是很多商品都有的词，它不能很好地表示商品特征，所以权重应该设的低一些，而像“NIKE”就能很好地表示商品的品牌特征，所以权重应该设得高一些。
考虑到这种权重的不同，对商品生成的词的集合中每个词设置权重，则用加权Jaccard距离可以更加准确地计算商品名的相似性，从而使分类更加合理，提高实体识别的准确率。由于商品名较短，大多数单词仅出现一次，而多数词仅出现在很少的商品名中，因此传统的TF-IDF模型不适用于商品名集合。
2.1 词权重设置模型如果2件商品是同一类商品，他们对应关键词集合交集的大小应当较大；如果2件商品不是同一类商品，则这2件商品对应关键词集合交集大小应当较小。因此本文提出如下词权重设制模型。
对于一个关键词，如果它存在于属于同一类的2个商品的共有词的次数为y1，而同一类存在次数最多的词为max1；它存在于不属于同一类商品的共有次数为y2，而不在同一类存在次数最多的词为max2，则这个词权重设置为1+y1/max1-y2/max2。
2.2 词权重计算方法由于上述词权重需要预先商品名的实体识别结果，而该识别结果需要单词的权重，因此本文提出了迭代确定词权重的方法。将所有词权重初始化为1.0，依据此权重进行分类，并按照这个分类结果修改单词权重，再根据此权重重新进行分类，这个过程迭代进行，直到分类结果的差别小于某个阈值为止。具体如算法2所示。
算法2 Weight1(S, n)
输入:待划分超集S={S1, S2, …, Sk}，循环次数n
输出:
设每个key∈∪Si的权重wkey=1.0
while 循环次数大于n or所有词权重不发生变化 do 对于每个key∈∪Si，设ckey=0, dkey=0, ctotal=-1, dtotal=-1
对S进行实体识别，得到结果T
for 每对集合Si, Sj∈S do
if Si和Sj在T中属于同一类then
for key∈Si∩Sj do
ckey=ckey+1
if ctotal < ckey then
ctotal=ckey
else
for key∈Si∩Sj do
dkey=dkey+1
if dtotal < dkey then
dtotal=dkey
wkey=wkey+ckey/ctotal-dkey/dtotal
为了加速算法，本文根据单词，用倒排表的形式组织单词，每次分类后可根据每个单词将倒排表中单词按照其分类排序，则在每次迭代中对每个单词的分组号扫描1次即可以确定ckey和dkey，另建一个有序的多重集合R保存每对集合交集的值，用于计算ctotal和dtotal，一次计算实际权值。具体如算法3所示。
算法3 Weight2(S, n)
输入:待划分超集S={S1, S2, …, Sk}，循环次数n
输出:
for 每对集合S1, S2∈S do
R[S1∩S2]={S1, S2}
设每个key∈∪Si的权重wkey=1.0
while 循环次数大于n or所有词权重不发生变化do
对于每个key∈∪Si，设ckey=0, dkey=-1
对S进行实体识别，得到结果T
for 每个key∈∪Si do
total=0
将Lkey按照T中的分组排序
for Lkey的每个分组i do
num[i]=Lkey中包含分组i的数量
ckey=ckey+num[i](num[i]-1)/2
dkey=|Lkey| (|Lkey|-1)/2-ckey
if ctotal < ckey then
ctotal=ckey
if dtotal < dkey then
dtotal=dkey
for 每个key∈∪Si do
wkey=wkey+ckey/ctotal-dkey/dtotal
按照标号从大到小扫描R，找到首次扫描到的在T中同组的集合标号是ctotal和不同组的集合的标号是dtotal，设置wkey=1+ckey/ctotal-dkey/dtotal。
算法3中每次迭代中在不考虑实体识别时间的情况下最坏情况下时间复杂性是O(|∪Si|Lkey+|S|2)，其中|∪Si|Lkey是扫描倒排表的代价，|S|2是R的大小，即扫描R所需的代价。在现实中由于大多数集合没有交集，因而扫描R所需的代价远小于|S|2。
3 基于反馈的阈值确定方法在实体识别过程中，阈值起着至关重要的作用，过大的阈值会导致很多描述同一实体的商品名被分到多个类别中，而过小的阈值会导致同一个类中有很多描述不同实体的商品名。考虑到不同的用户对精度和召回率有不同的要求，为了增强识别的整体效果，本文提出了一种基于反馈的阈值确定方法，利用用户的反馈确定识别所需要的阈值。本节用到的用户反馈信息包括2种：1)假阴性，即描述同一实体的商品没有被分到同一类；2)假阳性，即描述不同实体的商品被分到同一类。
反馈算法的基本思想是首先随机生成阈值，然后根据用户反馈结果逐步缩小范围。初始输入阈值的范围为[0, 1]，0表示2件商品完全不相同，1表示2件商品完全相同。人为查看识别的结果，如果存在2件商品本不是同一类却被分到了同一类，说明区分程度不够，如果2件商品的相似性为y1，则要求输入相似性的范围大于y1才能区分开这2件商品；相反，如果2件商品的是同一类商品却没有分到同一类，如果这2件商品的相似性为y2，则要求输入的相似性的范围小于y2，才能保证这2件商品分到同一类。一种特殊情况是存在用户认为相同商品相似性小于用户认为不同商品相似性，导致这2种情况原因如下：1)是用户的误判; 2)由于方法本身不适用区分商品，如词的权重不合适或商品名字的用词不足以区分商品。本方法中将这种情况看做噪声，对于这种情况可通过修改关键词权重或者增加其他信息等方法来解决。
算法4 实体识别的反馈算法
随机生成[0, 1]区间的数θ，执行实体识别
p=Ø
n=Ø
x=0, y=1
while 用户存在反馈 do
for 每对用户反馈的相同商品集合(o1, o2) do
将sim(o1, o2)插入P
for 每对用户反馈的不相同商品集合(o1, o2) do
将sim(o1, o2)插入N
if P[1]>N[1] then
a=N[1], b=P[1]
else
x=P中最小的大于N[1]元素的下标
y=N中最小的大于P[1]元素的下标
a=P[x], b=N[y]
θ为[a, b]之间的一个随机数
以θ为阈值执行实体识别并展示结果接受用户反馈
算法4中P是按照从小到大顺序排列，N是按照从大到小顺序排列，如果使用红黑树来实现P和N，则在不考虑实体识别时间的情况下反馈算法的时间复杂性是O(nlogn)，其中n是用户输入反馈的个数。
4 扩展实验扩展实验运行在计算机奔腾1 G CPU，512 M内存，320 G硬盘。本文的系统采取根据不同的商品种类选择关键词，在线提取淘宝网(www.taobao.com)的数据进行测试。注意本文没有采取特别的语料库，仅根据观察网站选择了100个可以去除的无用词汇。
4.1 运行效率实验运行实验测试在线提取商品数据和实体识别的运行时间之和，以页为处理单位，每页100个商品，提取1~20个网页进行测试，提取的页数与运行时间如图 1所示，从实验结果可以看出，运行时间和页数，即商品数量成线性管理，这说明本文提出的方法具有良好的可扩展性。
|
Download:
|
| 图 1 系统运行时间 Fig. 1 Run time of the system | |
本文用查准率和查全率来描述分类结果的精度。分类结果分为以下3种情况：
1) A、B是同一类商品，但未分到同一类的商品对数为A；
2) A、B是同一类商品，且分到同一类的商品对数为B；
3) A、B不是同一类商品，但分到同一类的商品对数为C。
其中查准率表示分到同一类的商品中应属于同一类的比例；查全率表示应当分到同一类的商品分到同一类的比例。
4.2.1 测试查准率以及查全率为了检测分类结果的有效性，选取4组不同类关键词，对每组关键词的检索结果提取100条的商品信息，求出分类结果的查全率及查准率。
测试1 以“篮球训练服背心网”为搜索关键字，分类结果随阈值变化的结果如图 2(a)所示。
|
Download:
|
| 图 2 测试1~4上的识别精度 Fig. 2 Resolution accuracy on test set 1~4 | |
测试2 以“童装外贸男孩”为搜索关键字，分类结果如图 2(b)所示。
测试3 以“羽毛球拍正品特价”为搜索关键字，分类结果如图 2(c)所示。
测试4 以“巧克力礼盒生日”为搜索关键字分类结果如图 2(d)所示。
从这些实验结果可以看出，随着阈值的增加，查准率逐步提高，而查全率逐步降低，只要选取合适的阈值，查准率和查全率都可以达到0.7以上，可以看出合适阈值选择的必要性。
4.2.2 反馈过程的实验结果为了测试本文提出反馈方法的效率和有效性，我们在搜索出来的100件商品对4组测试数据进行了反馈的测试，直到结果稳定为止，初始输入阈值为[0, 1]，阈值变化序列如下：
测试1 [0, 1]→[0, 0.6]→[0.4, 0.6]→[0.45, 0.6]→[0.45, 0.52]。
测试2 [0, 1]→[0.4, 1]→[0.4, 0.6]→[0.51, 0.6]→[0.51, 0.55]
测试3 [0, 1]→[0.46, 1]→[0.46, 0.6]→[0.46, 0.49]
测试4 [0, 1]→[0.4, 1]→[0.4, 0.51]→[0.45, 0.48]
从实验结果可以看出，输入的阈值范围不断收敛，且在5轮之内就可以收敛到稳定状态，说明本文提出反馈方法效率较高，如图 3中的实验结果所示，在得到的阈值上查准率和查全率达到相交的状态，查准率和查全率都可以达到0.7以上，说明本文提出反馈策略的有效性。
|
Download:
|
| 图 3 测试1~4上设置权重后识别精度 Fig. 3 Resolution accuracy after setting weights on test set 1~4 | |
为了测试权重调整策略的有效性，本文分别在4组测试结果上测试，检索出来的100条结果进行权重测试，结果如图 4所示，根据此结果可以看出，经过词权重调整，查准率和查全率有显著提高。
|
Download:
|
| 图 4 设置权重前后的查准率和查全率的比较 Fig. 4 Comparison of precision and recall ratio after setting weights | |
对于在不同雅克比基准的查全率和查准率，为了测试权重调整策略的有效性，分别在4组测试结果上测试，检索出来的100条结果在未设置权重和设置权重的平均查准率和平均查全率进行权重测试，结果如图 4所示，从实验结果中可以看出，在给定阈值的情况下权重的设置可以将查准率和查全率提高10%左右。
5 结语1) 本文提出的方法可以快速有效地实现对商品的实体识别。
2) 本文提出了阈值设定算法和词权重设定方法，实验结果表明对改进实体识别有显著的效果。
未来的工作包括利用知识库和自然语言处理技术提高实体识别的效果、利用云计算和索引技术提高实体识别的效率等。
| [1] |
CHRISTEN P. A survey of indexing techniques for scalable record linkage and deduplication[J]. IEEE transactions on knowledge and data engineering, 2012, 24(9): 1537-1555. DOI:10.1109/TKDE.2011.127 (  0)
|
| [2] |
ELMAGARMID A K, IPEIROTIS P G, VERYKIOS V S. Duplicate record detection:a survey[J]. IEEE transactions on knowledge and data engineering, 2007, 19(1): 1-16. DOI:10.1109/TKDE.2007.250581 ( 0)
|
| [3] |
WANG Sibo, XIAO Xiaokui, LEE C H. Crowd-based deduplication: an adaptive approach[C]//Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. Melbourne, Victoria, Australia, 2015: 1263-1277.
( 0)
|
| [4] |
GOKHALE C, DAS S, DOAN A, et al. Corleone: hands-off crowdsourcing for entity matching[C]//Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. Snowbird, Utah, USA, 2014: 601-612.
( 0)
|
| [5] |
VERROIOS V, GARCIA-MOLINA H. Entity Resolution with crowd errors[C]//Proceedings of 2015 IEEE 31st International Conference on Data Engineering. Seoul, South Korea, 2015: 219-230.
( 0)
|
| [6] |
VESDAPUNT N, BELLARE K, DALVI N. Crowdsourcing algorithms for entity resolution[J]. Proceedings of the VLDB endowment, 2014, 7(12): 1071-1082. ( 0)
|
| [7] |
WHANG S E, LOFGREN P, GARCIA-MOLINA H. Question selection for crowd entity resolution[J]. Proceedings of the VLDB endowment, 2013, 6(6): 349-360. DOI:10.14778/2536336 ( 0)
|
| [8] |
HUA Wen, ZHENG Kai, ZHOU Xiaofang. Microblog entity linking with social temporal context[C]//Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. Melbourne, Victoria, Australia, 2015: 1761-1775.
( 0)
|
| [9] |
SHEN Wei, HAN Jiawei, WANG Jianyong. A probabilistic model for linking named entities in web text with heterogeneous infor mation networks[C]//Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. Snowbird, Utah, USA, 2014: 1199-1210.
( 0)
|
| [10] |
ZHU Xiaochen, SONG Shaoxu, LIAN Xiang, et al. Matching heterogeneous event data[C]//Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. Snowbird, Utah, USA, 2014: 1211-1222.
( 0)
|
| [11] |
CHIANG Y H, DOAN A, NAUGHTON J F. Modeling entity evolution for temporal record matching[C]//Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. Snowbird, Utah, USA, 2014: 1175-1186.
( 0)
|
| [12] |
WHANG S E, GARCIA-MOLINA H. Incremental entity resolution on rules and data[J]. The VLDB journal, 2014, 23(1): 77-102. DOI:10.1007/s00778-013-0315-0 ( 0)
|
| [13] |
GRUENHEID A, DONG X L, SRIVASTAVA D. Incremental record linkage[J]. Proceedings of the VLDB endowment, 2014, 7(9): 697-708. DOI:10.14778/2732939 ( 0)
|
| [14] |
WILDANI A, MILLER E L, RODEH O. HANDS: a heuristically arranged non-backup in-line deduplication system[C]//Proceedings of 2013 IEEE 29th International Conference on Data Engineering. Brisbane, QLD, Australia, 2013: 446-457.
( 0)
|
| [15] |
LI Xian, DONG Luna, LYONS K B, et al. Scaling up copy detection[C]//Proceedings of 2015 IEEE 31st International Conference on Data Engineering. Seoul, South Korea, 2015: 89-100.
( 0)
|
| [16] |
WHANG S E, MARMAROS D, GARCIA-MOLINA H. Pay-as-you-go entity resolution[J]. IEEE transactions on knowledge and data engineering, 2013, 25(5): 1111-1124. DOI:10.1109/TKDE.2012.43 ( 0)
|
| [17] |
LI Lingli, LI Jianzhong, WANG Hongzhi, et al. Context-based entity description rule for entity resolution[C]//Proceedings of the 20th ACM International Conference on Infor mation and Knowledge Management. Glasgow, Scotland, UK, 2011: 1725-1730.
( 0)
|
| [18] |
LI Lingli, LI Jianzhong, GAO Hong. Rule-based method for entity resolution[J]. IEEE transactions on knowledge and data engineering, 2015, 27(1): 250-263. DOI:10.1109/TKDE.2014.2320713 ( 0)
|
| [19] |
WANG Fangda, WANG Hongzhi, LI Jianzhong, et al. Graph-based reference table construction to facilitate entity matching[J]. Journal of systems and software, 2013, 86(6): 1679-1688. DOI:10.1016/j.jss.2013.02.026 ( 0)
|
| [20] |
ALTOWIM Y, KALASHNIKOV D V, MEHROTRA S. Progressive approach to relational entity resolution[J]. Proceedings of the VLDB endowment, 2014, 7(11): 999-1010. DOI:10.14778/2732967 ( 0)
|
| [21] |
ALTWAIJRY H, KALASHNIKOV D V, MEHROTRA S. Query-driven approach to entity resolution[J]. Proceedings of the VLDB endowment, 2013, 6(14): 1846-1857. DOI:10.14778/2556549 ( 0)
|
| [22] |
WANG Hongzhi, LI Jianzhong, GAO Hong. Efficient entity resolution based on subgraph cohesion[J]. Knowledge and infor mation systems, 2016, 46(2): 285-314. DOI:10.1007/s10115-015-0818-7 ( 0)
|
| [23] |
LI Qi, LI Yaliang, GAO Jing, et al. A confidence-aware approach for truth discovery on long-tail data[J]. Proceedings of the VLDB endowment, 2014, 8(4): 425-436. DOI:10.14778/2735496 ( 0)
|
| [24] |
PROKOSHYNA N, SZLICHTA J, CHIANG F, et al. Combining quantitative and logical data cleaning[J]. Proceedings of the VLDB endowment, 2015, 9(4): 300-311. DOI:10.14778/2856318 ( 0)
|
| [25] |
ZHAO Zhou, CHENG J, NG W. Truth discovery in data streams: A single-pass probabilistic approach[C]//Proceedings of the 23rd ACM International Conference on Conference on Infor mation and Knowledge Management. Shanghai, 2014: 1589-1598.
( 0)
|
| [26] |
INTERLANDI M, TANG Nan. Proof positive and negative in data cleaning[C]//Proceedings of 2015 IEEE 31st International Conference on Data Engineering. Seoul, South Korea, 2015: 18-29.
( 0)
|
| [27] |
XIAO Chuan, WANG Wei, LIN Xuemin, et al. Top-k set similarity joins[C]//Proceedings of the 25th International Conference on Data Engineering. Shanghai, China, 2009: 916-927.
( 0)
|