基于DBSCAN聚類算法的多模式匹配

丁國(guó)輝　許瑩南　郭軍宏

1(沈陽(yáng)航空航天大學(xué)　遼寧 沈陽(yáng) 110136)

2(沈陽(yáng)炮兵學(xué)院　遼寧 沈陽(yáng) 110136)

?

基于DBSCAN聚類算法的多模式匹配

丁國(guó)輝1許瑩南1郭軍宏2

1(沈陽(yáng)航空航天大學(xué)遼寧 沈陽(yáng) 110136)

2(沈陽(yáng)炮兵學(xué)院遼寧 沈陽(yáng) 110136)

摘要模式匹配在很多數(shù)據(jù)庫(kù)相關(guān)領(lǐng)域中有著廣泛的應(yīng)用，例如數(shù)據(jù)集成、數(shù)據(jù)空間以及數(shù)據(jù)倉(cāng)庫(kù)。傳統(tǒng)的匹配技術(shù)主要研究?jī)蓚€(gè)屬性之間的匹配任務(wù)，而忽略了多個(gè)屬性間的匹配任務(wù)。針對(duì)這一問題，提出一種基于DBSCAN聚類算法的多模式集成技術(shù)。該方法將關(guān)注多個(gè)屬性之間語(yǔ)義對(duì)應(yīng)關(guān)系的發(fā)現(xiàn)，相對(duì)于兩個(gè)屬性之間對(duì)應(yīng)關(guān)系的發(fā)現(xiàn)，這將是一個(gè)更加復(fù)雜的問題。主要研究思路是將每個(gè)屬性看成向量空間中的一個(gè)點(diǎn)，然后利用聚類技術(shù)將這些屬性劃分到不同的集合中，在同一個(gè)聚類中的屬性具有相似的語(yǔ)義。同時(shí)，利用Web結(jié)構(gòu)信息源來提高模式匹配結(jié)果的質(zhì)量。最后，通過大量的實(shí)驗(yàn)來驗(yàn)證該方法是有效的并具有較好的性能。

關(guān)鍵詞模式匹配語(yǔ)義對(duì)應(yīng)關(guān)系結(jié)構(gòu)化信息聚類技術(shù)

MULTI-SCHEMA MATCHING BASED ON DBSCAN CLUSTERING ALGORITHM

Ding Guohui1Xu Yingnan1Guo Junhong21

(Shenyang Aerospace University,Shenyang 110136,Liaoning,China)2(Shenyang Institute of Artillery,Shenyang 110136,Liaoning,China)

AbstractSchema matching has wide application in many database correlated fields, such as data integration, data space and data warehouse. Matching task between only two attributes is what the traditional matching techniques study, but the matching task between multiple attributes is ignored. With respect to this problem, we proposed a multi-schema integration technique in this paper, which is based on DBSCAN (density-based spatial clustering of applications with noise) clustering algorithm. The proposed approach focus on the discovery of semantic correspondence among multiple attributes, which is a more complex issue relative to discovering the pairwise-attribute correspondence. Our main study idea is to deem every attribute as a point in the vector space, and then to partition these attributes into different sets by clustering technique. The attributes within same cluster have similar semantics. Meanwhile, we utilised the information sources of Web structure to improve the quality of schema matching results. At last, we performed extensive experimental research to verify the approach, and the experimental results showed that our approach was effective and had good performance.

KeywordsSchema matchingSemantic correspondenceStructured informationClustering technique

0引言

數(shù)據(jù)集成是數(shù)據(jù)庫(kù)領(lǐng)域中一個(gè)重要研究?jī)?nèi)容。數(shù)據(jù)集成的目標(biāo)是為多個(gè)不同的數(shù)據(jù)源提供統(tǒng)一的查詢結(jié)構(gòu)以及在多個(gè)信息系統(tǒng)之間提供共享數(shù)據(jù)的能力。通過統(tǒng)一的查詢接口，用戶不需要定位所有數(shù)據(jù)源、不需要單獨(dú)與每個(gè)數(shù)據(jù)源進(jìn)行交互，最后以手動(dòng)方式將這些結(jié)果進(jìn)行合并。在包含大量數(shù)據(jù)源的大企業(yè)中，數(shù)據(jù)集成是十分重要的，主要表現(xiàn)在以下方面：大規(guī)模的科研項(xiàng)目的推進(jìn)過程，這些項(xiàng)目中的數(shù)據(jù)集往往由不同的研究人員產(chǎn)生；為了政府機(jī)構(gòu)之間更好地合作，需要集成來自不同機(jī)構(gòu)的數(shù)據(jù)源；在互聯(lián)網(wǎng)上成千上萬的結(jié)構(gòu)數(shù)據(jù)源之間進(jìn)行搜索時(shí)，提供更好的搜索質(zhì)量[1]。異構(gòu)數(shù)據(jù)源之間的數(shù)據(jù)集成將會(huì)碰到很多技術(shù)上、結(jié)構(gòu)上和語(yǔ)義特性上的難題[1,2]。

數(shù)據(jù)集成的本質(zhì)是模式匹配，在數(shù)據(jù)集成領(lǐng)域，這一直是一個(gè)重要，但又很困難的問題。隨著信息系統(tǒng)的劇增，針對(duì)模式匹配解決方案的需求也變得更加突出。隨著互聯(lián)網(wǎng)的發(fā)展，數(shù)據(jù)共享和數(shù)據(jù)交換問題也亟待解決。這些問題的實(shí)質(zhì)都是模式匹配，因此，針對(duì)模式匹配解決方案的需求將會(huì)進(jìn)一步增加。模式匹配問題的本質(zhì)是發(fā)現(xiàn)源模式和目標(biāo)模式的屬性之間的語(yǔ)義對(duì)應(yīng)關(guān)系，即匹配。在某些具體的應(yīng)用背景下，一個(gè)匹配中的兩個(gè)屬性實(shí)際上具有相同或者相似的語(yǔ)義。從集合的角度來看，找到的匹配可以被看成兩個(gè)模式之間的映射。模式匹配領(lǐng)域存在大量的匹配技術(shù)，例如文獻(xiàn)[3-14]所述。

現(xiàn)存的匹配技術(shù)也被稱為匹配器。最初，匹配任務(wù)都是領(lǐng)域?qū)＜沂止ね瓿?，這種手工的解決方案耗時(shí)耗力。因此，人們開始研究自動(dòng)的匹配技術(shù)，以提高匹配的效率。文獻(xiàn)[14]對(duì)現(xiàn)存的自動(dòng)和半自動(dòng)的模式匹配技術(shù)進(jìn)行了綜述。他們提出的分類涵蓋了大部分現(xiàn)存的方法。其中，一個(gè)主要的分類是基于模式信息的匹配方法和基于數(shù)據(jù)實(shí)例信息的匹配方法。雖然該領(lǐng)域存在大量的工作，但是不存在完美的能夠返回100%正確匹配結(jié)果的技術(shù)。因此，模式匹配問題還需要更多的研究。本文研究的重點(diǎn)是自動(dòng)的模式匹配技術(shù)，并提出一種自動(dòng)的基于DBSCAN(Density-Based Spatial Clustering of Applications with Noise)[15]聚類技術(shù)的多模式匹配技術(shù)。傳統(tǒng)的匹配技術(shù)主要研究?jī)蓚€(gè)屬性之間語(yǔ)義對(duì)應(yīng)關(guān)系的發(fā)現(xiàn)問題。例如，給定兩個(gè)數(shù)據(jù)庫(kù)關(guān)系表“Movie(title, director, running_time, release_date)”和“Film(fName, fDirector, fRunningTime, fReleaseDate)”，現(xiàn)存匹配技術(shù)的目標(biāo)是尋找成對(duì)的屬性對(duì)應(yīng)關(guān)系，例如(title, fName), (director, fDirector)等。這些屬性對(duì)將被輸出作為最后的匹配結(jié)果，每個(gè)屬性對(duì)被稱為一個(gè)匹配。然而，大部分情況下，實(shí)際應(yīng)用需要的是多模式匹配，也就是尋找多個(gè)屬性之間的語(yǔ)義對(duì)應(yīng)關(guān)系。因此，針對(duì)多模式匹配技術(shù)的研究是有意義的。如果直接使用現(xiàn)有的匹配技術(shù)去處理多模式匹配問題，將會(huì)出現(xiàn)一些問題(在后面進(jìn)行介紹)。

因此，本文提出通過聚類技術(shù)解決多個(gè)屬性間語(yǔ)義對(duì)應(yīng)關(guān)系的發(fā)現(xiàn)問題。給定一個(gè)待匹配的屬性集合，本文的主要思路是將每個(gè)屬性看成一個(gè)空間中的點(diǎn)(實(shí)際上是一個(gè)向量)。然后，利用聚類技術(shù)將屬性劃分到不同的聚類中，每個(gè)聚類則代表一種語(yǔ)義，在同一個(gè)聚類中的屬性則具有相同或者相似的語(yǔ)義。在這個(gè)過程中，本文利用文獻(xiàn)[16]中的TFIDF(Term Frequency-Inverse Document Frequency)加權(quán)機(jī)制將每個(gè)輸入屬性轉(zhuǎn)換成空間中的點(diǎn)，進(jìn)而應(yīng)用聚類技術(shù)。

互聯(lián)網(wǎng)上存在大量的信息源，可以利用他們來輔助解決模式匹配問題。根據(jù)文獻(xiàn)[17]的調(diào)查，在互聯(lián)網(wǎng)的Deep Web中存在約96 000個(gè)搜索站點(diǎn)和5500億個(gè)隱藏的頁(yè)面。據(jù)網(wǎng)景公司統(tǒng)計(jì)，截止2008年，互聯(lián)網(wǎng)上存在1.6億個(gè)網(wǎng)站。文獻(xiàn)[17]經(jīng)過研究發(fā)現(xiàn)了Web數(shù)據(jù)源的兩個(gè)非常有用的特性。第一，隨著Web規(guī)模的擴(kuò)大，存在豐富的數(shù)據(jù)源提供同一領(lǐng)域內(nèi)的結(jié)構(gòu)信息。第二，隨著數(shù)據(jù)源的擴(kuò)大，它們的模式詞匯總和傾向收斂于一個(gè)較小的規(guī)模。他們研究了四個(gè)領(lǐng)域的信息源：電子圖書、在線音樂、電影和手機(jī)，然后獲得統(tǒng)計(jì)數(shù)據(jù)。對(duì)于每個(gè)領(lǐng)域的任意數(shù)據(jù)源，其使用的所有屬性的全部詞匯量在40到60之間。因此，本文利用從Web結(jié)構(gòu)信息源中抓取的模式詞匯來進(jìn)一步提高模式匹配的質(zhì)量。

1向量空間模型中模式屬性的轉(zhuǎn)換方法

實(shí)踐中，待集成的數(shù)據(jù)源往往多于兩個(gè)，例如，Deep Web中需要被整合的數(shù)據(jù)源往往是大量的，社交網(wǎng)絡(luò)中需要被分享的數(shù)據(jù)源也不僅僅是兩個(gè)。因此，多模式集成還需大量的研究工作。這一節(jié)將討論如何利用聚類技術(shù)完成多模式匹配工作。

如果直接利用傳統(tǒng)技術(shù)發(fā)現(xiàn)多屬性間的匹配，那么將會(huì)產(chǎn)生一些潛在的問題。傳統(tǒng)技術(shù)一般利用相似性分值和閾值來尋找匹配。一般通過計(jì)算兩個(gè)屬性間的相似性來作為它們的分值，例如字符串相似性，來自數(shù)據(jù)實(shí)例的統(tǒng)計(jì)信息的相似性等等。給定兩個(gè)屬性a1和b1，如果它們之間的相似性超過某個(gè)給定閾值，那么a1和b1被認(rèn)為是相似的，即他們具有相似的語(yǔ)義。最后，屬性對(duì)(a1,b1)被輸出作為最后的匹配結(jié)果，習(xí)慣上稱為匹配。

然而，如果考慮三個(gè)給定屬性a1、b1和c1的匹配任務(wù)，那么一系列的問題將會(huì)出現(xiàn)。如果a1和b1之間的相似性分值以及a1和c1之間的相似性分值都大于給定閾值，那么我們可以得出結(jié)論a1和b1是相似的，同時(shí)a1和c1之間也是相似的，可進(jìn)一步推斷出b1和c1也是相似的。這里，存在一個(gè)潛在的關(guān)于b1和c1之間的相似性問題。如果b1和c1之間的真實(shí)的相似性分值大于給定閾值，那么所得出的結(jié)論是正確的，相反，如果它們之間的分值小于這個(gè)閾值，將會(huì)得到一個(gè)矛盾：輸出一個(gè)小于給定閾值的匹配結(jié)果。

基于上面的分析，可以看出傳統(tǒng)的匹配技術(shù)不能用來完成多屬性間的語(yǔ)義對(duì)應(yīng)關(guān)系發(fā)現(xiàn)工作。在本文的方法中，利用聚類技術(shù)解決這一問題。本文的方法分為三個(gè)階段。首先，利用信息檢索領(lǐng)域中被廣泛應(yīng)用的向量空間模型[17]將所有的輸入屬性轉(zhuǎn)換成空間中的一個(gè)點(diǎn)。其次，利用DBSCAN聚類算法發(fā)現(xiàn)多屬性間的匹配。最后，利用Web上的結(jié)構(gòu)信息源進(jìn)一步提高模式匹配質(zhì)量。

在向量空間模型中，文本被轉(zhuǎn)換成相關(guān)的向量，然后關(guān)于文本的處理工作就轉(zhuǎn)換成對(duì)向量的處理任務(wù)。具體地，給定一個(gè)字符串s，s被表示成一個(gè)向量，向量的每一維代表一個(gè)詞匯對(duì)應(yīng)的項(xiàng)的權(quán)重。利用基于token[16]的方法將一個(gè)字符串解釋成一個(gè)項(xiàng)的集合。給定一個(gè)字符串的集合，所有字符串的項(xiàng)集則組成了全局的詞匯表。實(shí)際上，一個(gè)token是指一個(gè)字符串中的具有固定長(zhǎng)度的片段(子串)，也稱為詞項(xiàng)。例如，字符串“conference”的長(zhǎng)度為3的詞項(xiàng)集合是{“con”, “onf”, “nfe”, “fer”, “ere”, “ren”, “enc”, “nce”}。在本文的討論中，使用屬性的名字(字符串)作為屬性的表示。因此，實(shí)際上是利用屬性名字中包含的這種信息進(jìn)行模式匹配。在下面的描述中，在不出現(xiàn)混淆的情況下，一個(gè)屬性就代表一個(gè)字符串。每個(gè)屬性都可以被轉(zhuǎn)換成一個(gè)詞項(xiàng)集合。令ST為所有詞項(xiàng)的集合，即全局詞匯。基于ST，每個(gè)屬性被表示成一個(gè)向量，向量的每一維表示一個(gè)詞項(xiàng)t的權(quán)重，其中t∈ST。這個(gè)權(quán)重表示一個(gè)詞項(xiàng)在一個(gè)屬性名中的相對(duì)重要性。給定一個(gè)屬性a，如果一個(gè)詞項(xiàng)t沒有在屬性a中出現(xiàn)，那么詞項(xiàng)t在屬性a所對(duì)應(yīng)的向量中的權(quán)重為0，本文將通過TFIDF來計(jì)算詞項(xiàng)權(quán)重。TFIDF是IR(Information Retrieval)和文本挖掘領(lǐng)域中經(jīng)常用到的加權(quán)方式。給定一個(gè)文檔集合，其利用統(tǒng)計(jì)數(shù)據(jù)來反應(yīng)一個(gè)詞在該集合中的文檔中的重要性， TFIDF加權(quán)模式考慮了兩方面內(nèi)容。第一個(gè)是詞項(xiàng)在文檔中出現(xiàn)的頻率(TF)，也就是詞項(xiàng)的TF越高，該詞項(xiàng)越重要。第二個(gè)是一個(gè)詞項(xiàng)在所有文檔中的出現(xiàn)頻率(DF)，也就是一個(gè)詞項(xiàng)的DF越高，則其重要性越低。原因是類似“within”、“based”、“usually”等常見的詞匯會(huì)經(jīng)常出現(xiàn)在大部分文檔中，所以具有較高的DF。然而，這些常見的普通的詞匯對(duì)于文檔主題的表示來說是不重要的，因此，具有較高DF的詞將會(huì)被分配較低的權(quán)重。下面將給出屬性向量的每一維權(quán)重的具體計(jì)算方法。

定義1令A(yù)為所有輸入模式的屬性的全集，Ut為A中所有屬性的詞項(xiàng)的全集。令s為A中任意屬性對(duì)應(yīng)的字符串，t為Ut中任意的詞項(xiàng)。則詞項(xiàng)t在字符串s中的權(quán)重w(s,t)被定義為：

(1)

式中，tfs,t表示詞項(xiàng)t在s中出現(xiàn)的頻率TF，|A|為A中屬性的數(shù)量，dft為t在A中出現(xiàn)的屬性的數(shù)量。通過上述方法，可以將每個(gè)輸入模式的屬性轉(zhuǎn)化成空間中的點(diǎn)，然后利用聚類技術(shù)對(duì)這些點(diǎn)進(jìn)行劃分，處于同一個(gè)聚類中的屬性則具有相似的語(yǔ)義。

2基于聚類技術(shù)的語(yǔ)義對(duì)應(yīng)關(guān)系發(fā)現(xiàn)

當(dāng)將每個(gè)屬性看成空間中的點(diǎn)后， 點(diǎn)之間的距離則暗含了屬性之間的相似性，相似的點(diǎn)的集合則表示了某個(gè)語(yǔ)義，因此，采用聚類技術(shù)對(duì)空間中的點(diǎn)進(jìn)行聚類?；诿芏鹊木垲惙椒ㄒ悦芏茸鳛榫垲愰g差異性的度量，將聚類看作是數(shù)據(jù)空間中被低密度區(qū)域分隔開的高密度對(duì)象區(qū)域。對(duì)給定聚類中某個(gè)數(shù)據(jù)點(diǎn)，在該數(shù)據(jù)點(diǎn)的一定范圍的區(qū)域中必須至少包含某個(gè)數(shù)目的點(diǎn)?；诿芏鹊木垲惙椒梢杂脕磉^濾噪聲或孤立點(diǎn)，可以發(fā)現(xiàn)任意形狀的聚類。這種聚類算法對(duì)數(shù)據(jù)集合中的聚類形狀以及聚類中的數(shù)據(jù)分布不敏感。DBSCAN[15]算法是經(jīng)典的基于密度的聚類算法，由Ester等人在1996年提出，其基本思想是：搜索核心對(duì)象，然后利用密度可達(dá)特性對(duì)數(shù)據(jù)對(duì)象進(jìn)行聚類。所謂核心對(duì)象是指滿足某個(gè)數(shù)量要求的某個(gè)鄰域內(nèi)的一個(gè)對(duì)象。該算法利用“某個(gè)聚類可以由其內(nèi)部的任一核心對(duì)象確定”這一性質(zhì)來產(chǎn)生最后的聚類。DBSCAN算法具有基于密度聚類方法的典型特征，即DBSCAN可以挖掘任意形狀的聚類、聚類過程與數(shù)據(jù)的輸入順序無關(guān)，并且具有處理異常點(diǎn)的能力。與K-Means方法相比，DBSCAN不需要事先知道要形成的聚類的數(shù)量，DBSCAN可以發(fā)現(xiàn)任意形狀的聚類，DBSCAN能夠識(shí)別出噪聲點(diǎn)，同時(shí)DBSCAN對(duì)于數(shù)據(jù)的輸入順序不敏感，因此本文采用DBSCAN算法來對(duì)空間中的屬性點(diǎn)進(jìn)行聚類。下面將給出DBSCAN算法的一些概念和定義。

定義2令p為一給定數(shù)據(jù)點(diǎn)、e為給定半徑，則稱以p為中心，以e為半徑的領(lǐng)域?yàn)閜的e領(lǐng)域。

定義3令D為數(shù)據(jù)對(duì)象集合，即空間中的數(shù)據(jù)點(diǎn)的集合，且p∈D，那么稱p的e鄰域內(nèi)的數(shù)據(jù)對(duì)象的數(shù)量為p的密度。

定義4給定一個(gè)點(diǎn)p，如果點(diǎn)p的密度超過某一給定的閾值Minpts，則稱p為核心對(duì)象。

定義5給定數(shù)據(jù)對(duì)象集合D，p、q是D中任意的數(shù)據(jù)對(duì)象，如果p是核心對(duì)象，且q在p的e鄰域內(nèi)，則稱點(diǎn)q從點(diǎn)p直接密度可達(dá)。

定義6給定數(shù)據(jù)對(duì)象集合D，{p1, p2, …, pi, …, pn}是D中任意的數(shù)據(jù)對(duì)象，如果pi+1從pi關(guān)于e和Minpts直接密度可達(dá)，其中1≤i≤n-1，則稱pn從p1關(guān)于e和Minpts密度可達(dá)。

根據(jù)上述概念，現(xiàn)給出基于密度聚類的概念。對(duì)于給定的閾值Minpts和鄰域半徑e，一個(gè)聚類就是可以密度相連的所有數(shù)據(jù)對(duì)象的集合。密度相連具有傳遞性，因此一個(gè)聚類可以被其中的任意一個(gè)核心對(duì)象唯一確定。所以數(shù)據(jù)的輸入順序?qū)BSCAN算法沒有影響。DBSCAN算法的基本思想是：不斷地從數(shù)據(jù)集D中的某一點(diǎn)出發(fā)，查找D中所有關(guān)于閾值Minpts和鄰域半徑e的從該點(diǎn)密度可達(dá)的點(diǎn)，直至D中所有點(diǎn)都被遍歷。若從p點(diǎn)出發(fā)，且p是核心對(duì)象，則其鄰域內(nèi)的所有點(diǎn)和p同屬于一個(gè)聚類，同時(shí)，這些點(diǎn)將作為下一次迭代遍歷的對(duì)象，依次從這些點(diǎn)出發(fā)，尋找從它們密度可達(dá)的點(diǎn)，重復(fù)這一過程直至所有密度可達(dá)的點(diǎn)都被找到，這個(gè)過程中發(fā)現(xiàn)的點(diǎn)則形成一個(gè)聚類。若p不是核心點(diǎn)，即沒有對(duì)象從p密度可達(dá)，則p被暫時(shí)標(biāo)注為噪聲。然后，算法從D中的下一個(gè)沒有被遍歷過的點(diǎn)開始，重復(fù)上述過程直至D中所有數(shù)據(jù)對(duì)象都被遍歷，并將形成的聚類進(jìn)行輸出，此時(shí)，若存在不屬于任何一個(gè)聚類的點(diǎn)，那么這些點(diǎn)將作為噪聲輸出。具體流程如算法1所示。

算法1基于密度聚類的多屬性匹配發(fā)現(xiàn)算法

輸入：A={a1,…,an}，屬性集合;

e，鄰域半徑;

Minpts，密度閾值;

輸出：C，聚類結(jié)果;

1: for each unvisited aiin D do

2:visited(ai);

//將ai標(biāo)記為已訪問

3:N=getNeighbours(ai,e);

//ai的e鄰域內(nèi)的點(diǎn)集

4:if(|N|

//將ai標(biāo)記為噪聲

5:else

6:insert aito c;

//c為一個(gè)聚類

7:for each biin N do

8:visited(bi);

9:O = getNeighbours(bi,e);

10:if(|O|>=Minpts) then N=N O;

11:end if

12:if bi? any cxthen insert bito c;

13:end if

//cx為已存在的某個(gè)聚類

14:end for

15:insert c to C;

16:end if

17:end for

3利用Web信息源改進(jìn)模式匹配質(zhì)量

本節(jié)將會(huì)介紹如何利用Web上的結(jié)構(gòu)信息源來提高最終聚類結(jié)果的質(zhì)量。如上所述，互聯(lián)網(wǎng)上存在大量的結(jié)構(gòu)信息源。據(jù)網(wǎng)景公司調(diào)查，截止2010年底，互聯(lián)網(wǎng)上存在超過1.6億個(gè)網(wǎng)站，而且這個(gè)數(shù)字還在不斷地增長(zhǎng)。文獻(xiàn)[17]調(diào)查發(fā)現(xiàn)隨著數(shù)據(jù)源數(shù)量的增長(zhǎng)，它們的詞匯總和傾向收斂于一個(gè)較小的數(shù)量規(guī)模。本文將利用這一特點(diǎn)來提高聚類結(jié)果的質(zhì)量。

文獻(xiàn)[17]總結(jié)的特點(diǎn)可被解釋成可以從互聯(lián)網(wǎng)的結(jié)構(gòu)信息源中為每個(gè)領(lǐng)域抽取一個(gè)規(guī)模較小的模式詞匯集合。這個(gè)小的模式詞匯集合可以被稱為某個(gè)領(lǐng)域的模式詞匯。本文的主要思想是利用這個(gè)詞匯集合來提高聚類結(jié)果的質(zhì)量。待匹配的輸入模式一般來自相同或者相似的領(lǐng)域。給定一個(gè)來自領(lǐng)域H的輸入模式的集合，為輸入模式從領(lǐng)域H的頁(yè)面的結(jié)構(gòu)信息源中抽取一個(gè)詞匯表G，然后，將G劃分成不同的集合{G1,…,Gi,…,Gq}。在同一個(gè)集合Gi中的模式元素的詞匯具有相似的語(yǔ)義。

本文以兩種方式使用詞匯表G，首先介紹第一種方式。在最終的聚類結(jié)果中，具有相似語(yǔ)義、不同表示方法的屬性經(jīng)常被劃分到不同的聚類中，例如“book-Name”和“bookTitle”。本文利用詞匯表G解決這一問題。令a1和a2為最終聚類結(jié)果中屬于不同聚類的兩個(gè)屬性。如果存在Gi使得|v(a1)-v(b1)|<β∩|v(a2)-v(b2)|<β，其中b1,b2∈G1，b1≠b2，v()表示屬性對(duì)應(yīng)的特征向量，β設(shè)置為0.1，那么將a2替換為a1，也就是從a2所在的聚類θi中將a2移除，并將a1加入聚類θi。目的是利用一個(gè)屬性表示多個(gè)語(yǔ)義相似的屬性以提高聚類結(jié)果的質(zhì)量。其次，令a1為聚類θi中的一個(gè)屬性，如果在任意的一個(gè)集合Gi中，存在一個(gè)屬性b1，使得|v(a1)-v(b1)|<γ，其中γ被置為0.2，那么用b1替換a1。這里，將相似性閾值進(jìn)行放寬意在使得輸入屬性更加標(biāo)準(zhǔn)和完整，例如，用“title”替換“bTitle”。當(dāng)屬性替換結(jié)束后，重新運(yùn)行聚類過程以得到更好的聚類結(jié)果。實(shí)驗(yàn)中，我們對(duì)比了改進(jìn)后的方法和原始方法。

4實(shí)驗(yàn)

本節(jié)首先介紹實(shí)驗(yàn)所用數(shù)據(jù)集。其次，給出關(guān)于多模式匹配算法性能的實(shí)驗(yàn)結(jié)果，同時(shí)將改進(jìn)后的算法與原始算法進(jìn)行對(duì)比。為簡(jiǎn)便起見，將原始算法記為DA，將改進(jìn)后的算法記為IA。實(shí)驗(yàn)利用信息檢索領(lǐng)域中經(jīng)典的度量標(biāo)準(zhǔn)F-Measure作為最后匹配結(jié)果的準(zhǔn)確性評(píng)價(jià)方法，該標(biāo)準(zhǔn)在模式匹配領(lǐng)域也得到了廣泛的應(yīng)用。以人工得到的匹配作為標(biāo)準(zhǔn)結(jié)果，通過和標(biāo)準(zhǔn)結(jié)果進(jìn)行對(duì)比來評(píng)估最后算法的有效性。算法采用C++語(yǔ)言實(shí)現(xiàn)，在PC機(jī)上運(yùn)行，PC機(jī)器配置為Intel Core I5處理器，主頻3.10 GHz，4 GB內(nèi)存，Win7操作系統(tǒng)。

通過三個(gè)不同人員開發(fā)的在線書店系統(tǒng)來產(chǎn)生實(shí)驗(yàn)數(shù)據(jù)。本次實(shí)驗(yàn)只考慮書目信息表，即數(shù)據(jù)庫(kù)表“book”。每個(gè)表包含16~20個(gè)字段。利用原始的三個(gè)真實(shí)的數(shù)據(jù)庫(kù)表產(chǎn)生32個(gè)合成的數(shù)據(jù)庫(kù)表作為實(shí)驗(yàn)數(shù)據(jù)集。利用加前綴或者后綴的方式通過原有字段生成新表中的字段(例如，“t_”、“table_”、“book_”等)。主要目的是模擬實(shí)際應(yīng)用中的真實(shí)情況。本文以人工的方式從“亞馬遜”和“當(dāng)當(dāng)”等網(wǎng)站抽取與書目相關(guān)的詞匯表G。G中包含大約30個(gè)模式詞匯。從生成的表集合中隨機(jī)地選擇子集作為每次實(shí)驗(yàn)的數(shù)據(jù)集。

圖1給出了第一個(gè)實(shí)驗(yàn)結(jié)果，該實(shí)驗(yàn)測(cè)試了鄰域半徑的變化對(duì)算法性能的影響，橫坐標(biāo)e則表示聚類過程中用到的鄰域半徑，e的取值范圍為[1.0, 3.0]?？梢钥闯霰疚牡姆椒ň哂休^好的準(zhǔn)確性，如圖1(a)所示，最好的結(jié)果接近90%。隨著e的增加算法的有效性逐漸增加，當(dāng)e超過區(qū)間[1.6, 2.0]后，算法的性能開始下降，主要原因是當(dāng)e超過某一范圍時(shí)，密度相連的范圍變大，即原本不是密度相連的點(diǎn)開始密度相連，從而導(dǎo)致多個(gè)聚類的合并，使算法的有效性降低。通過實(shí)驗(yàn)，本文選定e的值為1.8。同時(shí)，可以看出引入的詞匯表改善了匹配結(jié)果的質(zhì)量，即IA優(yōu)于沒有引入詞匯表的原始算法DA。

圖1　鄰域半徑對(duì)匹配結(jié)果的影響

下面實(shí)驗(yàn)研究了核心對(duì)象閾值Minpts的變化對(duì)算法性能的影響，實(shí)驗(yàn)結(jié)果如圖2所示，Minpts從2增加至20?？梢钥闯觯S著Minpts的增加，算法的性能先升高后降低。這是由于較小的閾值使得點(diǎn)之間的密度相連的難度降低，使得不屬于同一個(gè)聚類的點(diǎn)被劃分到同一個(gè)聚類中，即最后的聚類增大。當(dāng)Minpts較大時(shí)，情況相反，此時(shí)的密度相連難度增加，最終得到的聚類的數(shù)量增多，但是每個(gè)聚類的體積減小(包含的點(diǎn)的數(shù)量減少)。通過實(shí)驗(yàn)，本文選定Minpts的值為12。同時(shí)，改進(jìn)后的算法要優(yōu)于原始算法，這與上面實(shí)驗(yàn)相符。

圖2　核心對(duì)象密度閾值的影響

最后，對(duì)輸入模式的數(shù)量對(duì)算法性能的影響進(jìn)行了測(cè)試，實(shí)驗(yàn)結(jié)果如圖3所示?？梢钥闯鲭S著輸入模式的增加，除去輕微的局部上升趨勢(shì)之外，本文方法的準(zhǔn)確率基本保持不變，這說明在一定的范圍內(nèi)基于密度的聚類方法不受輸入模式數(shù)量的影響。同時(shí)，在圖3(b)中，由于鄰域半徑為3.0，匹配結(jié)果的準(zhǔn)確性大幅度下降，這與圖1中的實(shí)驗(yàn)結(jié)果相符。

圖3　輸入模式數(shù)量的影響

5相關(guān)工作

模式匹配是一個(gè)長(zhǎng)期的且比較受關(guān)注的研究問題[12-23]。文獻(xiàn)[14]給出一個(gè)自動(dòng)模式匹配方法的綜述。他們將現(xiàn)存的匹配技術(shù)看成匹配器，并將它們分為基于模式信息的匹配方法和基于實(shí)例信息的匹配方法?；谀Ｊ降钠ヅ淦髦豢紤]模式自身的信息，例如模式的名稱、描述、類型等?；趯?shí)例的信息則主要探測(cè)了依賴模式而存在的數(shù)據(jù)的特性，特別是當(dāng)模式信息不可用時(shí)，此種方法顯得尤為重要。

文獻(xiàn)[18]提出一種通用的圖匹配算法，稱為“相似性洪流”。他們的模型有一個(gè)假設(shè)前提，即如果圖中的任意兩個(gè)頂點(diǎn)是相似的，那么它們的鄰居之間相似性也會(huì)被增加。基于這個(gè)假設(shè)，相似性在待匹配的模式屬性之間進(jìn)行傳遞。文獻(xiàn)[19]考慮了模式中的屬性和依賴模式存在的數(shù)據(jù)都比較模糊、難以解釋時(shí)如何進(jìn)行模式匹配的情況。文獻(xiàn)[17]提出一種新的思路：統(tǒng)計(jì)模式匹配。為了進(jìn)一步改善模式匹配的質(zhì)量，上下文信息“context”被文獻(xiàn)[20]引入。所謂的“context”是指數(shù)據(jù)庫(kù)表中具有離散值的分類字段，例如人員信息表中的“性別”字段。他們利用這些分類字段作為約束條件以進(jìn)一步提高匹配的質(zhì)量。

文獻(xiàn)[21]提出一種基于corpus的匹配技術(shù)。所謂的corpus是指一個(gè)包含大量的模式和它們之間映射關(guān)系的實(shí)例集合。他們利用corpus訓(xùn)練多種不同的學(xué)習(xí)機(jī)，利用這些學(xué)習(xí)機(jī)去預(yù)測(cè)給定輸入模式的匹配結(jié)果。文獻(xiàn)[16]提出利用數(shù)據(jù)實(shí)例副本的方式進(jìn)行模式匹配。給定兩個(gè)模式，他們利用字符串比對(duì)領(lǐng)域的技術(shù)來發(fā)現(xiàn)數(shù)據(jù)實(shí)例間的重復(fù)記錄，然后利用這些重復(fù)記錄找出匹配。除上述工作外，文獻(xiàn)[12]利用神經(jīng)網(wǎng)絡(luò)來發(fā)現(xiàn)異構(gòu)數(shù)據(jù)庫(kù)中的屬性對(duì)應(yīng)關(guān)系。

最近，文獻(xiàn)[22]提出一種新的匹配技術(shù)，稱為基于使用信息的匹配技術(shù)。他們的主要思想是利用從查詢?nèi)罩局谐槿∫环N稱為“共同出現(xiàn)模式”的特征來進(jìn)行模式匹配。不同于傳統(tǒng)的匹配方法，文獻(xiàn)[23]提出一個(gè)新的概念“可能映射”。對(duì)于一個(gè)屬性a，“可能映射”則表示a可以被匹配給另外一個(gè)模式的多個(gè)屬性，即每個(gè)映射實(shí)例帶有一個(gè)概率值?！翱赡苡成洹笨梢员挥脕韯?chuàng)建“可能中間模式”以描述一個(gè)查詢的多個(gè)潛在的查詢結(jié)果。然而，不存在完美的可以返回100%正確結(jié)果的匹配器，因此，模式匹配領(lǐng)域仍然需要大量的研究。

6結(jié)語(yǔ)

多個(gè)屬性之間語(yǔ)義對(duì)應(yīng)關(guān)系的發(fā)現(xiàn)工作具有廣泛的應(yīng)用，例如數(shù)據(jù)集成。本文提出一種利用DBSCAN聚類算法發(fā)現(xiàn)模式匹配的方法，利用Web上的結(jié)構(gòu)信息源進(jìn)一步改善模式匹配結(jié)果的質(zhì)量。作為DBSCAN算法的準(zhǔn)備工作，本文利用TFIDF加權(quán)方法將每個(gè)輸入屬性轉(zhuǎn)換為向量空間模型中的一個(gè)點(diǎn)。然后，利用DBSCAN算法將屬性點(diǎn)劃分至不同的聚類中。在同一個(gè)聚類中的屬性具有相似的語(yǔ)義。通過實(shí)驗(yàn)比對(duì)，本文提出的算法具有較好的準(zhǔn)確性。

參考文獻(xiàn)

[1] 李玉坤,孟小峰,張相於.數(shù)據(jù)空間技術(shù)研究[J].軟件學(xué)報(bào),2008,19(8):2018-2031.

[2] 周傲英,金澈清,王國(guó)仁,等.不確定性數(shù)據(jù)管理技術(shù)研究綜述[J].計(jì)算機(jī)學(xué)報(bào),2009,32(1):1-16.

[3] Zhang M,Chakrabarti K.InfoGather+:semantic matching and annotation of numeric and time-varying attributes in web tables[C].SIGMOD 2013:proceedings of Special Interest Group on Management Of Data,NY,USA,June 22-27,2013.New York:ACM,2013.

[4] Yakout M,Ganjam K,Chakrabarti K,et al.InfoGather: entity augmentation and attribute discovery by holistic matching with web tables[C].SIGMOD 2012:proceedings of Special Interest Group on Management Of Data,AZ,USA,May 20-24,2012.New York:ACM,2012.

[5] Peukert E,Eberius J,Erhard Rahm.A self-configuring schema matching system[C].ICDE 2012:proceedings of International Conference on Data Engineering,DC,USA,April 1-5,2012.Washington:IEEE Computer Society,2012.

[6] Qian L,Cafarella M J,Jagadish H V.Sample-driven schema mapping[C].SIGMOD 2012:proceedings of Special Interest Group on Management of Data,AZ,USA,May 20-24,2012.New York:ACM,2012.

[7] Patricia C Arocena,Boris Glavic,Renee J Miller.Value invention in data exchange[C].SIGMOD 2013:proceedings of Special Interest Group on Management Of Data,NY,USA,June 22-27,2013.New York:ACM,2013.

[8] Nguyen Quoc Viet Hung,Nguyen Thanh Tam,Zoltan Miklos,et al.Pay-as-you-go reconciliation in schema matching networks[C].ICDE 2014:proceedings of International Conference on Data Engineering,Chicago,USA,March 31-April 4,2014.Washington:IEEE Computer Society,2014.

[9] Floris Geerts,Giansalvatore Mecca,Paolo Papotti,et al.Mapping and cleaning[C].ICDE 2014:proceedings of International Conference on Data Engineering,Chicago,USA,March 31-April 4,2014.Washington:IEEE Computer Society,2014.

[10] Xin Luna Dong,Divesh Srivastava.Big data integration[C].ICDE 2013:proceedings of International Conference on Data Engineering,Brisbane,Australia,April 8-12,2013.Washington:IEEE Computer Society,2013.

[11] Franklin M,Halevy A,Maier D.From Databases to Dataspaces:A New Abstraction for Information Management[C].SIGMOD 2005:Proceedings of Special Interest Group on Management of Data,Maryland,USA,June 14-16,2005.New York:ACM,2005.

[12] Li W S,Clifton C.SEMINT:A Tool for Identifying Attribute Correspondences in Heterogeneous Databases Using Neural Networks[J].Data & Knowledge Engineering,2000,33(1):49-84.

[13] Doan A,Domingos P,Halevy A.Reconciling schemas of disparate data sources:A machine-learning approach[C].SIGMOD 2001:proceedings of Special Interest Group on Management Of Data,CA,USA,July 20-24,2001.New York:ACM,2001.

[14] Rahm E,Bernstein P A.A survey of approaches to automatic schema matching[J].Very Large Data Base Journal,2001,10(4):334-350.

[15] Ester Martin,Kriegel HansPete,Sander J?rg,et al.A density-based algorithm for discovering clusters in large spatial databases with noise[C].KDD 1996:proceedings of Discovery and Data Mining,Oregon,USA,August 20-24,1996.New York:ACM,1996.

[16] Bilke A,Naumann F.Schema Matching using Duplicates[C].ICDE 2005:proceedings of International Conference on Data Engineering,Tokyo,Japan,April 5-8,2005.Washington:IEEE Computer Society,2005.

[17] He B,Chang K C.Statistical schema matching across web query interfaces[C].SIGMOD 2003:proceedings of Special Interest Group on Management Of Data,California,USA,June 9-12,2003.New York:ACM,2003.

[18] Melnik S,GarciaMolina H,Rahm E.Similarity flooding: a versatile graph matching algorithm[C].ICDE 2002:proceedings of International Conference on Data Engineering,California,USA,26 February-1 March,2002.Washington:IEEE Computer Society,2002.

[19] Kang J,Naughton J F.On Schema Matching with Opaque Column Names and Data Values[C].SIGMOD 2003:proceedings of Special Interest Group on Management of Data,Wisconsin,USA,June 9-12,2003.New York:ACM,2003.

[20] Bohannon P,Elnahrawy E,Fan W,et al.Putting context into schema matching[C].VLDB 2006:proceedings of Very Large Data Base,Seoul,Korea,September 9-12,2003.New York:ACM,2006.

[21] Madhavan J,Bernstein P,Doan A,et al.Corpus-based schema matching[C].ICDE 2005:proceedings of International Conference on Data Engineering,Tokyo,Japan,April 5-8,2005.Washington:IEEE Computer Society,2005.

[22] Chan C,Elmeleegy H V J H,Ouzzani M,et al.Usage- Based Schema Matching[C].ICDE 2008:proceedings of International Conference on Data Engineering,Cancún,México,April 7-12,2008.Washington:IEEE Computer Society,2008.

[23] Dong X,Halevy A Y,Yu C.Data integration with uncertainty[C].VLDB 2007:proceedings of Very Large Data Base,Vienna,Austria,September 23-27,2003.New York:ACM,2007.

中圖分類號(hào)TP3

文獻(xiàn)標(biāo)識(shí)碼A

DOI:10.3969/j.issn.1000-386x.2016.02.006

收稿日期：2014-07-16。國(guó)家自然科學(xué)基金項(xiàng)目(61303016)；遼寧省教育廳一般項(xiàng)目(L2012045)。丁國(guó)輝，講師，主研領(lǐng)域：數(shù)據(jù)庫(kù)模式匹配。許瑩南，講師。郭軍宏，講師。