顧　頎，朱　燦，曹　?。?上海交通大學(xué)電子信息與電氣工程學(xué)院，上海200240；2.南通大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇南通22609）

互聯(lián)網(wǎng)商品匹配算法

顧頎1，2，朱燦1，曹健1
（1.上海交通大學(xué)電子信息與電氣工程學(xué)院，上海200240；2.南通大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇南通226019）

實(shí)體解析是指識(shí)別同一實(shí)體的不同描述形式的過程，旨在保障數(shù)據(jù)質(zhì)量，是數(shù)據(jù)清理、數(shù)據(jù)集成及數(shù)據(jù)挖掘中的關(guān)鍵技術(shù).隨著電子商務(wù)的不斷發(fā)展和成熟，商品的多樣性和消費(fèi)者靈活的購買方式，使得對網(wǎng)絡(luò)商品的精確識(shí)別和匹配成為大數(shù)據(jù)時(shí)代亟待解決的問題.與傳統(tǒng)實(shí)體解析主要針對結(jié)構(gòu)化數(shù)據(jù)不同，網(wǎng)絡(luò)數(shù)據(jù)具有非結(jié)構(gòu)化、異構(gòu)和海量的特性，為此設(shè)計(jì)了綜合相似度算法（synthesized similarity method，SSM）來計(jì)算網(wǎng)絡(luò)商品數(shù)據(jù)間的相似度，同時(shí)引入凝聚的層次聚類框架，以匹配來自不同數(shù)據(jù)源的異構(gòu)商品.此外，為了解決大數(shù)據(jù)環(huán)境下對執(zhí)行效率的要求，從字符串相似度緩存、約束知識(shí)庫和分塊策略三個(gè)方面對SSM進(jìn)行優(yōu)化，基于真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果驗(yàn)證了SSM的執(zhí)行效率和有效性.

實(shí)體解析；大數(shù)據(jù)；非結(jié)構(gòu)化數(shù)據(jù)；商品匹配

電子商務(wù)的持續(xù)發(fā)展給人們帶來了龐大的數(shù)據(jù)總量以及復(fù)雜的數(shù)據(jù)形式，數(shù)據(jù)的關(guān)聯(lián)形態(tài)正在發(fā)生變化，這些都給數(shù)據(jù)處理帶來了極大的挑戰(zhàn).以互聯(lián)網(wǎng)環(huán)境下豐富的網(wǎng)絡(luò)商品為例，隨著商品多樣性的提升，同一網(wǎng)絡(luò)商品在不同網(wǎng)絡(luò)平臺(tái)往往以各種形式存在著，相似商品信息散落在各個(gè)網(wǎng)絡(luò)平臺(tái)，網(wǎng)絡(luò)商品的搜索空間不斷增加，使得消費(fèi)者在感興趣的商品信息的搜索與整合上耗費(fèi)了大量精力.如將散落在各個(gè)網(wǎng)絡(luò)平臺(tái)的商品信息關(guān)聯(lián)起來，勢必有利于商品信息的搜索與整合，從而免去消費(fèi)者繁重的搜索工作.而為了將來自不同網(wǎng)絡(luò)平臺(tái)的商品信息進(jìn)行關(guān)聯(lián)，首要任務(wù)是完成商品的匹配，即從不同網(wǎng)絡(luò)平臺(tái)中找出同一網(wǎng)絡(luò)商品的不同表述，將這一過程稱為實(shí)體解析（entity resolution）［1］，或稱為記錄連接（record linkage）、對象匹配（object matching）、重復(fù)檢測（duplicate detection）等［2］.

實(shí)體解析是以數(shù)據(jù)為中心的各項(xiàng)工作（如數(shù)據(jù)清理、數(shù)據(jù)集成、數(shù)據(jù)挖掘等）中至關(guān)重要的步驟，是數(shù)據(jù)質(zhì)量的保障.不同網(wǎng)絡(luò)平臺(tái)（數(shù)據(jù)提供方）對同一網(wǎng)絡(luò)商品（實(shí)體）可能會(huì)有不同的描述，如數(shù)據(jù)格式、表示方法等.將實(shí)體的描述稱為實(shí)體的引用，實(shí)體解析是指從引用集合中解析并映射到現(xiàn)實(shí)世界中實(shí)體的過程.傳統(tǒng)的實(shí)體解析方法可以分為成對實(shí)體解析［3］、集合實(shí)體解析［4］和時(shí)態(tài)實(shí)體解析［5］.這三種實(shí)體解析方法適用于結(jié)構(gòu)化數(shù)據(jù)的解析，例如一般關(guān)系數(shù)據(jù)庫中的元組.事實(shí)上，在真實(shí)的網(wǎng)絡(luò)商品匹配中，需處理的數(shù)據(jù)沒有統(tǒng)一的模式，也沒有預(yù)定義的“鍵”和“值”，將這樣的數(shù)據(jù)稱為非結(jié)構(gòu)化數(shù)據(jù)，其匹配策略與傳統(tǒng)的面向結(jié)構(gòu)化數(shù)據(jù)的解析方法相比有很大差別.本研究正是以此為切入點(diǎn)，對現(xiàn)有商品匹配算法存在的不足進(jìn)行了深入剖析，并提出了有效的解決方案.

目前常用的面向網(wǎng)絡(luò)商品匹配的算法主要有WHIRL（word-based heterogeneous information retrieval logic）算法［6］和TMWM（title model words method）［7］.WHIRL算法主要采用TF-IDF以及向量空間模型對商品引用進(jìn)行建模，并計(jì)算商品之間的相似度；TMWM結(jié)合了商品名稱間的歸一化編輯距離，以及從名稱中抽取的“模式詞”集合之間的相似度.WHIRL算法和TMWM存在以下兩個(gè)缺陷：①網(wǎng)絡(luò)商品往往遍布于不同的網(wǎng)絡(luò)平臺(tái)，算法只能處理來自兩個(gè)數(shù)據(jù)提供方的商品數(shù)據(jù)，而無法處理來自多個(gè)網(wǎng)絡(luò)平臺(tái)的商品數(shù)據(jù)；②網(wǎng)絡(luò)商品數(shù)據(jù)具有非結(jié)構(gòu)化、異構(gòu)性等特征，算法只能針對結(jié)構(gòu)化數(shù)據(jù)進(jìn)行商品名稱的比對，而無法對非結(jié)構(gòu)化商品數(shù)據(jù)計(jì)算相似度.

為了應(yīng)對網(wǎng)絡(luò)商品數(shù)據(jù)給商品匹配帶來的挑戰(zhàn)，本研究提出了一種基于凝聚層次聚類框架的商品匹配方法，使用綜合相似度算法（synthesized similarity method，SSM）計(jì)算商品之間的相似度.SSM將從商品名稱中獲取的信息以及從商品屬性的鍵值對中獲取的信息有效結(jié)合起來，構(gòu)造綜合的相似度計(jì)算方法，最終根據(jù)相似度的值確定商品是否匹配.引入的凝聚層次聚類（agglomerate hierarchical clustering，AHC）框架可以在不影響匹配準(zhǔn)確度的前提下實(shí)現(xiàn)多源商品數(shù)據(jù)匹配.為了解決大數(shù)據(jù)對執(zhí)行效率的要求，從以下三個(gè)方面對所提出算法進(jìn)行了優(yōu)化：使用字符串相似度緩存、添加約束知識(shí)庫以及應(yīng)用分塊策略.最后，基于真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果驗(yàn)證了所提出算法的執(zhí)行效率和有效性.

本研究的主要工作及貢獻(xiàn)可總結(jié)如下.

（1）提出了基于凝聚層次聚類的商品匹配框架，解決了傳統(tǒng)算法無法處理多源商品匹配的問題.

（2）基于非結(jié)構(gòu)化網(wǎng)絡(luò)商品數(shù)據(jù)設(shè)計(jì)開發(fā)了綜合相似度算法，將商品的有效信息充分結(jié)合起來，提高了商品匹配的準(zhǔn)確度.

（3）為了適應(yīng)大數(shù)據(jù)環(huán)境下對執(zhí)行效率的要求，從三個(gè)方面對所提出算法進(jìn)行優(yōu)化，通過大量實(shí)驗(yàn)表明了所提出算法在性能上有明顯提升.

1　相關(guān)工作

1.1實(shí)體解析概念

1946年，Dunn［8］提出了記錄鏈接（record linkage）的概念；其后，Newcombe等［9］在1959年提出了實(shí)體解析的概念；之后，F(xiàn)ellegi等［10］將這個(gè)問題規(guī)范化并進(jìn)行深入研究.經(jīng)過幾十年的發(fā)展，實(shí)體解析技術(shù)已經(jīng)廣泛應(yīng)用于國民醫(yī)療系統(tǒng)、人口普查、多媒體數(shù)據(jù)庫整合以及銀行信貸系統(tǒng)等各個(gè)領(lǐng)域.常用的實(shí)體解析方法包括成對實(shí)體解析、集合實(shí)體解析以及時(shí)態(tài)實(shí)體解析.

1.1.1成對實(shí)體解析

成對實(shí)體解析通過計(jì)算一對記錄各屬性間的相似度衡量記錄是否匹配.衡量方法包括基于規(guī)則、基于屬性權(quán)重以及基于機(jī)器學(xué)習(xí)（包括決策樹、支持向量機(jī)、嵌套分類器、條件隨機(jī)場等）.成對實(shí)體解析適用于對數(shù)據(jù)庫內(nèi)重復(fù)記錄的檢測以及數(shù)據(jù)庫間的記錄匹配.

1.1.2集合實(shí)體解析

成對實(shí)體解析通過引入領(lǐng)域知識(shí)、機(jī)器學(xué)習(xí)等方法提高了匹配準(zhǔn)確度，然而獨(dú)立的求解過程無法區(qū)別不同實(shí)體擁有相同屬性這一情形.集合實(shí)體解析使得求解過程不再獨(dú)立完成，而是借助關(guān)系的引入，使得更多關(guān)聯(lián)信息被用于解析過程中.

1.1.3時(shí)態(tài)實(shí)體解析

傳統(tǒng)的實(shí)體解析方法往往忽略了時(shí)態(tài)信息，而實(shí)際數(shù)據(jù)記錄中常用時(shí)間戳描述現(xiàn)實(shí)世界實(shí)體在特定時(shí)間的狀態(tài).時(shí)態(tài)實(shí)體解析通過定義與時(shí)間間隔相關(guān)的“衰變率”，來減少對高相似的獎(jiǎng)勵(lì)和對低相似的懲罰，從而利用時(shí)態(tài)信息為實(shí)體解析提供更多的“證據(jù)”.

1.2商品匹配算法

隨著網(wǎng)絡(luò)商品數(shù)據(jù)的急速累積，網(wǎng)絡(luò)商品的搜索空間不斷增加，商品匹配變得愈發(fā)重要.目前，常用的網(wǎng)絡(luò)商品匹配算法主要有WHIRL算法和TMWM.

1.2.1WHIRL算法

WHIRL算法由Cohen［6］于1998年提出，該算法利用向量空間模型對商品信息進(jìn)行建模，并計(jì)算商品之間的相似度.在向量空間模型中，現(xiàn)實(shí)世界中商品的自然語言描述可以用詞項(xiàng)構(gòu)成的文本向量表示.向量中的成分對應(yīng)文本中的某個(gè)詞項(xiàng)，成分值與該詞項(xiàng)在文檔中的“重要性”相關(guān)聯(lián)，詞項(xiàng)越重要?jiǎng)t對應(yīng)的成分值越大.如果兩個(gè)文檔具有很多相同的“重要性”相近的詞項(xiàng)，則可以認(rèn)為它們是相似的.對詞項(xiàng)賦予權(quán)重的方法有很多，其中TF-IDF（term frequency-inverse document frequency）方法經(jīng)過改進(jìn)后可以很方便地在向量空間模型中引用［6］.盡管文本向量通常很長也很稀疏，但已有很多方法可以高效處理稀疏向量.

1.2.2TMWM

TMWM由Vandic等［7］于2012年提出，該算法結(jié)合了商品名稱間的歸一化編輯距離以及從名稱中抽取的“模式詞”集合之間的相似度.編輯距離是指將一個(gè)字符串轉(zhuǎn)換成另一個(gè)字符串所需進(jìn)行的最少操作數(shù)，已廣泛應(yīng)用于字符串相似度或差異度的計(jì)算中.由于未考慮字符串的長度，這樣的編輯距離也稱為絕對編輯距離.通過對絕對編輯距離進(jìn)行歸一化，可以處理長度較短的字符串.首先，計(jì)算兩個(gè)商品名稱間的余弦相似度，若相似度值高于閾值α，表明兩個(gè)商品為同一商品，返回“true”；若相似度低于閾值α，則分別提取兩個(gè)商品的模式詞形成相應(yīng)的模式詞集合，再將兩個(gè)集合中的模式詞對進(jìn)行逐一比較，如果存在一個(gè)模式詞對的非數(shù)字字符近似而數(shù)字字符不同，那么這兩個(gè)商品為不同商品，返回“false”，如果非數(shù)字字符和數(shù)字字符都一致，則更新兩個(gè)商品名稱之間的相似度，即求出兩個(gè)商品名稱的余弦相似度和兩個(gè)商品名稱所產(chǎn)生的兩個(gè)模式詞集合間的平均編輯距離相似度的加權(quán)和，最終相似度如果大于預(yù)設(shè)的閾值ε，則兩個(gè)商品為同一商品，返回“true”.

2　基于凝聚層次聚類的商品匹配框架

2.1凝聚層次聚類（AHC）方法

WHIRL算法和TMWM適用于分析兩個(gè)網(wǎng)絡(luò)商店的商品（假設(shè)同一網(wǎng)絡(luò)商店內(nèi)沒有重復(fù)商品）.事實(shí)上，商品搜索往往涉及多個(gè)數(shù)據(jù)源，為此需要將算法的輸出從兩個(gè)商品間的相似度變?yōu)榇鎯?chǔ)不同商品間的距離，或稱為相似度矩陣，在該矩陣上運(yùn)行聚類算法.k-means算法和層次聚類算法是最常用的聚類算法.k-means算法將全部集中的個(gè)體分成k個(gè)子集，但在網(wǎng)絡(luò)商品搜索的應(yīng)用背景下，無法預(yù)知確切的k值；層次聚類算法則不需要額外的先驗(yàn)知識(shí).傳統(tǒng)的層次聚類算法主要分為兩大類：①分離（自頂向下）的層次聚類，即初始時(shí)將所有的點(diǎn)視為一個(gè)簇，之后將簇的一部分分離出來形成一個(gè)新簇，重復(fù)這一過程直至每個(gè)簇中只包含單獨(dú)的點(diǎn)，此類算法需要確定哪個(gè)簇應(yīng)該被分離以及如何被分離；②凝聚（自底向上）的層次聚類，即初始時(shí)將每個(gè)點(diǎn)作為單獨(dú)的簇，之后合并最相鄰的兩個(gè)簇，重復(fù)這一過程直至最后只剩下一個(gè)簇，此類算法需要預(yù)先定義簇之間的距離，以此作為簇合并的依據(jù).這兩種層次聚類方法中凝聚的層次聚類較為常用.

凝聚層次聚類中的關(guān)鍵問題是簇間距離的計(jì)算.不同的簇間距離計(jì)算方法又將凝聚層次聚類分為以下三種模式：單鏈模式（MIN）、全鏈模式（MAX）和組平均（group average）模式.單鏈模式又稱最小值模式，簇間距離等于簇中成員間的最短距離.這種策略容易造成“Chaining”效應(yīng)，即兩個(gè)實(shí)際離得較遠(yuǎn)的簇由于簇中個(gè)別距離較近的點(diǎn)而合并，使得離得較遠(yuǎn)的點(diǎn)因?yàn)槿舾呻x得較近的“中介點(diǎn)”而被鏈接起來，并且這種效應(yīng)可能會(huì)逐漸擴(kuò)大.全鏈模式又稱最大值模式，簇間距離等于簇中成員間的最遠(yuǎn)距離，與單鏈模式相反，全鏈模式中離得較近的簇可能因?yàn)槠渲袀€(gè)別離得較遠(yuǎn)的點(diǎn)而無法合并.組平均模式是單鏈模式和全鏈模式的折中策略.本研究使用基于組平均策略的凝聚層次聚類作為商品匹配算法的框架.

2.2綜合相似度算法（SSM）

TMWM通過分析商品名稱判斷商品是否匹配，該算法要求將商品名稱以某種特定的方式進(jìn)行編碼，盡可能將有辨別性的信息體現(xiàn)在商品名稱中.然而這一要求對真實(shí)數(shù)據(jù)卻過于嚴(yán)苛，在大多數(shù)情況下真實(shí)數(shù)據(jù)的商品名稱只提供商品的型號信息.顯然，在實(shí)驗(yàn)數(shù)據(jù)集上僅僅利用商品名稱信息進(jìn)行匹配，結(jié)果并不能讓人滿意.因此，本研究提出了綜合相似度算法（synthesized similarity method，SSM），也可將其看作是對TMWM的改進(jìn)，即添加了更具體更詳細(xì)的商品信息比對，如商品屬性等.以相機(jī)為例，添加了相機(jī)的一系列參數(shù)比如相機(jī)像素、顯示屏尺寸、傳感器尺寸、光學(xué)變焦、感光元件類型等.顯然，相比單純利用商品名稱信息，這些額外信息能夠獲得更好的匹配結(jié)果.

所有商品屬性可以以鍵值對（key-value pair，KVP）的形式來表示，如“相機(jī)像素”、“2 000萬”.將從商品名稱中獲取的信息以及從商品屬性的鍵值對中獲取的信息結(jié)合起來，得到綜合相似度

式中，α+β+γ=1.綜合相似度算法共分三部分：titleSim，mKVPSim，nmPerc，其中第一部分titleSim是兩個(gè)商品名稱間的相似度，該相似度取自TMWM；第二部分mKVPSim和第三部分nmPerc是針對商品屬性鍵值對計(jì)算的相似度.SSM中的符號注釋如表1所示.

表1　算法符號注釋Table 1　Algorithm notations

SSM假設(shè)同一網(wǎng)絡(luò)平臺(tái)沒有重復(fù)商品，若兩個(gè)商品來自同一平臺(tái)，則它們之間的距離disti，j為∞；否則，繼續(xù)比較商品的屬性鍵值對.為了利用屬性鍵值對信息，選擇q-gram算法［11］衡量相似度，該算法能很好地應(yīng)對拼寫錯(cuò)誤，并且不需要額外的標(biāo)簽.q-gram算法設(shè)置了一個(gè)大小為q個(gè)字符的滑動(dòng)窗口，這些長度為q的子串構(gòu)成一個(gè)子串集合，然后比較兩個(gè)字符串生成的子串集合的相似度：假設(shè)字符串s1和s2相應(yīng)的子串集合分別為C1和C2，則s1和s2的q-gram相似度為

根據(jù)calSim的定義可以看出，即使是部分匹配也會(huì)為最后的相似度作出貢獻(xiàn)，這在處理拼寫錯(cuò)誤以及縮寫時(shí)很有優(yōu)勢.應(yīng)用calSim計(jì)算相似度后，如果兩個(gè)鍵的相似度大于閾值μ，則計(jì)算這兩個(gè)鍵對應(yīng)值的相似度：假設(shè)商品i和j的鍵值對集合分別為Ki和Kj，則Ki和Kj的相似度為

找出所有鍵匹配的鍵值對并計(jì)算相似度后，分析剩余的未匹配鍵值對.此時(shí)忽略這些鍵值對的鍵，分別抽取商品屬性值中的所有模式詞生成模式詞集合，接下來計(jì)算這兩個(gè)集合中匹配的模式詞所占比例為

由式（3）和（4）計(jì)算得到mKVPSim和nmPerc后，再采用TMWM計(jì)算商品名稱間的相似度titleSim.接著，按照式（1）計(jì)算得到綜合相似度，并將相似度轉(zhuǎn)換成距離.最后，使用凝聚層次聚類方法求得聚合后的簇集合.算法1總結(jié)了完整的構(gòu)造過程.

3　實(shí)驗(yàn)結(jié)果與分析

3.1實(shí)驗(yàn)設(shè)置

3.2商品匹配實(shí)驗(yàn)結(jié)果分析

3.2.1SSM結(jié)果分析

SSM共有3個(gè)參數(shù)μ，γ和ε需要訓(xùn)練，使用網(wǎng)格搜索訓(xùn)練ε的最佳值，范圍為0.1～0.9，步長為0.1.在50個(gè)訓(xùn)練集上，μ，γ和ε最佳值的平均值為0.792，0.638和0.612，將其應(yīng)用于測試集后得到平均Precision為0.627，平均Recall為0.583，平均F1-measure為0.609.與WHIRL和TMWM兩個(gè)算法相比較可知：改進(jìn)后的SSM在各方面效果都有所提升，詳細(xì)的算法性能比較如表2所示.

表2　3種算法的評價(jià)指標(biāo)對比Table 2　Performance metrics of three different algorithms

3.2.2基于字符相似度緩存的算法實(shí)驗(yàn)結(jié)果分析

WHIRL算法，TMWM和SSM的復(fù)雜度主要都集中在字符串間相似度的計(jì)算上，實(shí)驗(yàn)中令每種算法在同一個(gè)數(shù)據(jù)集上運(yùn)行50次，每個(gè)樣本都將數(shù)據(jù)集劃分為不同的訓(xùn)練集和測試集.如果每次運(yùn)行新樣本都要重新計(jì)算所有字符串間的相似度，顯然這會(huì)浪費(fèi)大量的時(shí)間.因此，預(yù)先計(jì)算所有字符串間的相似度并保存在一個(gè)global cache中，之后每次運(yùn)行時(shí)直接從global cache中讀取所需相似度，將會(huì)大大提高運(yùn)行效率.為了預(yù)防系統(tǒng)崩潰或者重復(fù)測試，還可將global cache中的數(shù)據(jù)格式化地存儲(chǔ)在硬盤當(dāng)中.在實(shí)驗(yàn)數(shù)據(jù)集上應(yīng)用此方法后，總運(yùn)行時(shí)間從35 h 37 min減少到了6 h 19 min，速度為原來的5.63倍，可見添加global cache之后大大縮短了算法的運(yùn)行時(shí)間，尤其是重復(fù)在同一數(shù)據(jù)集上運(yùn)行時(shí)其優(yōu)勢更加明顯.

3.2.3基于添加知識(shí)約束的算法實(shí)驗(yàn)結(jié)果分析

為提高算法準(zhǔn)確性并避免多余計(jì)算，本研究為算法添加了根據(jù)常識(shí)或統(tǒng)計(jì)數(shù)據(jù)建立的約束庫，也稱知識(shí)庫.知識(shí)庫作為額外組件可靈活地參與到運(yùn)算中，也可以根據(jù)新的數(shù)據(jù)和知識(shí)進(jìn)行更新（擴(kuò)充和改進(jìn)），將參與到運(yùn)算中的數(shù)據(jù)和知識(shí)統(tǒng)稱為知識(shí)約束（knowledge constraints，KC）.在計(jì)算一對引用間的相似度之前，可以先使用約束知識(shí)庫的相關(guān)條目對目標(biāo)引用對進(jìn)行核查，若不符合其中任意一條約束，則終止比較，從而避免多余計(jì)算，縮短算法的運(yùn)行時(shí)間.表3給出了應(yīng)用于算法的知識(shí)庫中的幾個(gè)例子.

約束知識(shí)庫能為算法提供更多的信息，或者說是證據(jù).這些信息不同于字符串相似度，它們更直接也更可信.尤其值得注意的是，約束知識(shí)庫給出的通常是一些必要條件，即不滿足條件的引用對絕不可能指向相同的實(shí)體，應(yīng)用這些知識(shí)約束可以篩除一些潛在的FP結(jié)果，從而提高算法的Precision.表4給出了SSM添加約束知識(shí)庫前后的性能對比.

表3　知識(shí)約束類型和例子Table 3　Types and examples of knowledge constraints

表4　SSM添加KC前后的性能對比Table 4　Performance comparison between SSM without and with KC

從表4可以看出，知識(shí)約束對算法的貢獻(xiàn)主要體現(xiàn)在Precision上.盡管添加約束知識(shí)庫后SSM的效率和性能均得到了提升，但不可否認(rèn)的是，知識(shí)庫依賴于領(lǐng)域知識(shí).由于不太可能復(fù)用跨領(lǐng)域的知識(shí)庫，不嚴(yán)謹(jǐn)或是過于嚴(yán)苛的約束又無疑將對算法產(chǎn)生負(fù)面影響（例如過于嚴(yán)苛的約束可能會(huì)增加FN的數(shù)目并影響Recall，從表3中可以看出Recall有輕微下降），因此領(lǐng)域知識(shí)庫的建立需要領(lǐng)域?qū)＜业膮⑴c.

3.2.4基于分塊策略的算法實(shí)驗(yàn)結(jié)果分析

本研究采用的真實(shí)實(shí)驗(yàn)數(shù)據(jù)集共有1 933條相機(jī)數(shù)據(jù)，計(jì)算規(guī)模（主要指字符串比較）已經(jīng)達(dá)到了千萬數(shù)量級，不難想象在大數(shù)據(jù)集上應(yīng)用算法時(shí)將會(huì)面臨效率問題.為此引入分塊技術(shù)（block technique）對數(shù)據(jù)進(jìn)行預(yù)處理，即根據(jù)某種知識(shí)或規(guī)則將數(shù)據(jù)集分成規(guī)模更小的數(shù)據(jù)塊（block），在數(shù)據(jù)塊里再進(jìn)行商品匹配.

（1）基于hash函數(shù)的分塊.

定義一個(gè)關(guān)于商品的一項(xiàng)或多項(xiàng)屬性的hash函數(shù)，每個(gè)塊都有一個(gè)hash值標(biāo)識(shí)，將所有商品按照屬性求hash值后歸入互不相交的塊中，商品匹配在塊內(nèi)完成.hash函數(shù)的種類多種多樣，往往需要量身定制，可以將簡單的規(guī)則合并以滿足復(fù)雜的需求.minHash算法［12］就是基于多種hash鍵值進(jìn)行分塊的算法.根據(jù)實(shí)驗(yàn)數(shù)據(jù)集的特點(diǎn)，本研究選取品牌、像素以及顯示屏尺寸三個(gè)參數(shù)作為minHash算法的鍵值列表.表5為應(yīng)用minHash算法進(jìn)行分塊前后的SSM性能比較.

表5　SSM應(yīng)用minHash算法進(jìn)行分塊前后的性能對比Table 5　Performance comparison between SSM without and with minHash algorithm

應(yīng)用minHash算法進(jìn)行分塊后，算法運(yùn)行速度從5.7 h縮短到3.5 h，提高了62.3%，但在Precision，Recall以及F1-measure三個(gè)性能指標(biāo)上都有不同程度的降低.性能下降可能是由分塊錯(cuò)誤造成的，即同一商品被分到不同塊中.在實(shí)驗(yàn)數(shù)據(jù)集上，運(yùn)行時(shí)間尚在可承受范圍之內(nèi)，但若是面對極其龐大的數(shù)據(jù)集，這種性能與速度之間的權(quán)衡將至關(guān)重要.

（2）基于相似度與距離的分塊.

McCallum等［13］提出Canopy算法來加速重復(fù)檢測的過程.Canopy算法的基本思想是利用一些計(jì)算簡便的參數(shù)為依據(jù)，將所有引用劃分成互相部分重疊的簇（Canopies）.將引用集合中的每一條引用都映射到空間中的一點(diǎn)，再根據(jù)空間中各點(diǎn)的位置將聚集的點(diǎn)劃分到一個(gè)塊中.應(yīng)用Canopy算法前需要預(yù)先設(shè)計(jì)一個(gè)距離函數(shù)，如果使用之前計(jì)算的商品相似度作為分塊依據(jù)，則函數(shù)代價(jià)太大，不妨以部分相似度或一些簡單參數(shù)為依據(jù)，因此選擇商品名稱的q-gram相似度作為分塊依據(jù)（q=3）.實(shí)驗(yàn)中選擇k-means算法以及凝聚層次聚類方法.表6給出了應(yīng)用k-means算法進(jìn)行分塊前后的SSM性能比較.

表6　SSM應(yīng)用k-means算法進(jìn)行分塊前后的性能對比Table 6　Performance comparison between SSM without and with k-means algorithm

從表6可以看出，隨著k值（簇的個(gè)數(shù)）的增大，Precision的變化呈現(xiàn)波形（當(dāng)k=75時(shí)達(dá)到最大值），并且波形的前半段上升比較平緩，而后半段下滑明顯加劇.這可能是由于選取商品名稱的相似度作為分塊依據(jù)在實(shí)驗(yàn)數(shù)據(jù)集上有較好區(qū)分度，并且在k=75時(shí)恰好與應(yīng)該劃分的簇個(gè)數(shù)等同.另一方面，當(dāng)k=100及125時(shí)，由于簇的個(gè)數(shù)超出理想簇個(gè)數(shù)過多，聚類的過程變得不穩(wěn)定，從而產(chǎn)生一系列連鎖反應(yīng)，導(dǎo)致產(chǎn)生很多FP.隨著k值的增大，Recall逐漸下降并且趨于穩(wěn)定，這是由于隨著簇個(gè)數(shù)的增加，兩個(gè)應(yīng)該指向同一實(shí)體的引用被劃分到同一個(gè)簇中的可能性減小，從而導(dǎo)致算法產(chǎn)生的FN逐漸增多，Recall逐漸減小.綜合Precision與Recall，F(xiàn)1-measure的變化也呈現(xiàn)波形.因此，在利用k-means算法進(jìn)行分塊時(shí)，簇個(gè)數(shù)的設(shè)定需要根據(jù)數(shù)據(jù)集的特點(diǎn)以及對算法運(yùn)行時(shí)間的要求進(jìn)行權(quán)衡.不同分塊策略的性能比較如圖1所示.

圖1　不同SSM應(yīng)用AHC后的評價(jià)指標(biāo)比較Fig.1　Performance metrics of different SSM with AHC

從圖1可以看出，在總體表現(xiàn)上，使用AHC算法進(jìn)行分塊的效果優(yōu)于minHash算法，而與k-means算法相當(dāng).AHC算法相對于k-means算法的優(yōu)勢在于其通用性，一方面，AHC算法無需指定k值而且比k-means算法更穩(wěn)定；但是另一方面，如果事先確定了k值，則使用k-means算法可能會(huì)得到更好的效果.

4　總結(jié)與展望

實(shí)體解析是數(shù)據(jù)預(yù)處理過程中的重要步驟，為了解決網(wǎng)絡(luò)環(huán)境下非結(jié)構(gòu)化商品數(shù)據(jù)的匹配問題，本研究提出了基于凝聚層次聚類框架的綜合相似度算法，以識(shí)別不同網(wǎng)絡(luò)平臺(tái)的同一商品，本算法適用于非結(jié)構(gòu)、多來源的商品匹配.同時(shí)，引入字符串處理、添加約束及分塊策略的優(yōu)化方法，目的是在現(xiàn)有方法的基礎(chǔ)上提高大數(shù)據(jù)環(huán)境下商品匹配的執(zhí)行效率.在大量真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證了本算法的有效性.

目前，雖然商品匹配算法較多，但仍缺少有效的評價(jià)方法，用于測試的大規(guī)模真實(shí)數(shù)據(jù)集的缺失也是目前亟待解決的問題.在接下來的工作中，應(yīng)著重設(shè)計(jì)新的衡量方法或指標(biāo)來減少人工檢測帶來的資源浪費(fèi)，同時(shí)構(gòu)造一個(gè)優(yōu)質(zhì)的大規(guī)模真實(shí)數(shù)據(jù)集，進(jìn)一步提升算法與現(xiàn)實(shí)需求的契合度.

［1］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.

［2］CHRISTEN P.Data matching：concepts and techniques for record linkage，entity resolution，and duplicate detection［M］.Berlin：Springer Science and Business Media，2012.

［3］CHRISTEN P.Automatic record linkage using seeded nearest neighbour and support vector machine classification［C］//Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2008：151-159.

［4］BHATTACHARYA I，GETOOR L.Collective entity resolution in relational data［J］.ACM Transactions on Knowledge Discovery from Data（TKDD），2007，1（1）：5.

［5］LI P，DONG X，MAURINO A，et al.Linking temporal records［J］.Proceedings of the VLDB Endowment，2011，4（11）：956-967.

［6］COHEN W W.Integration of heterogeneous databases without common domains using queries based on textual similarity［C］//ACM SIGMOD Record.1998：201-212.

［7］VANDIC D，VAN DAM J W，F(xiàn)RASINCAR F.Faceted product search powered by the Semantic Web［J］.Decision Support Systems，2012，53（3）：425-437.

［8］DUNN H L.Record linkage［J］.American Journal of Public Health and the Nations Health，1946，36（12）：1412-1416.

［9］NEWCOMBE H B，KENNEDY J M，AxFORD S J，et al.Automatic linkage of vital records computers can be used to extract“follow-up”statistics of families from files of routine records［J］.Science，1959，130（3381）：954-959.

［10］FELLEGI I P，SUNTER A B.A theory for record linkage［J］.Journal of the American Statistical Association，1969，64（328）：1183-1210.

［11］UKKONEN E.Approximate string-matching with q-grams and maximal matches［J］.Theoretical Computer Science，1992，92（1）：191-211.

［12］BRODER A Z，CHARIKAR M，F(xiàn)RIEZE A M，et al.Min-wise independent permutations［J］.Journal of Computer and System Sciences，2000，60（3）：630-659.

［13］MCCALLUM A，NIGAM K，UNGAR L H.Efficient clustering of high-dimensional data sets with application to reference matching［C］//Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2000：169-178.

Product matching based on Internet and its implementation

GU Qi1，2，ZHU Can1，CAO Jian1
（1.School of Electronic Information and Electrical Engineering，Shanghai Jiao Tong University，Shanghai 200240，China；2.School of Computer Science and Technology，Nantong University，Nantong 226019，Jiangsu，China）

Entity resolution identifies entities from different data sources that refer to the same real-world entity.It is an important prerequisite for data cleaning，data integration and data mining，and is a key in ensuring data quality.With the rapid growth of E-commerce，diversity of products and flexible buying patterns of consumers，product identification and matching becomes a long-standing research topic in the big data era.While the traditional entity resolution approaches focus on structured data，the Internet data are neither standardized nor structured.In order to address this problem，this paper presents a synthesized similarity method to calculate similarity between different products.An agglomerate hierarchical clustering method is used to identify products from different sources.Also，the approach is optimized to improve efficiency of execution in three aspects：global cache，knowledge constraints，and blocking strategies.Finally，a series of experiments are performed on real data sets.The experimental results show that the proposed approach has a better performance compared with others.

entity resolution；big data；unstructured data；product matching

TP 391

A

1007-2861（2016）01-0058-11

10.3969/j.issn.1007-2861.2015.04.016

2015-11-30

國家自然科學(xué)基金資助項(xiàng)目（61272438，61472253，61300167）；上海市科委資助項(xiàng)目（15411952502，14511107702）

曹?。?972—），男，教授，博士生導(dǎo)師，博士（后），研究方向?yàn)榉?wù)計(jì)算、網(wǎng)絡(luò)計(jì)算、大數(shù)據(jù)分析.

E-mail:cao-jian@cs.sjtu.edu.cn