HSMA：面向物聯(lián)網(wǎng)異構(gòu)數(shù)據(jù)的模式分層匹配算法

郭 帥 郭忠文 仇志金

(中國海洋大學(xué)信息科學(xué)與工程學(xué)院 山東青島 266100) (guoshuaiouc@163.com)

據(jù)物聯(lián)網(wǎng)行業(yè)統(tǒng)計數(shù)據(jù)顯示，2014年中國物聯(lián)網(wǎng)產(chǎn)業(yè)規(guī)模達(dá)到5 800億元，同比增長18.46%.2015 年全球物聯(lián)網(wǎng)市場規(guī)模達(dá)到 624 億美元，同比增長 29%.到 2018 年全球物聯(lián)網(wǎng)設(shè)備市場規(guī)模有望達(dá)到 1 036 億美元，2019 年新增的物聯(lián)網(wǎng)設(shè)備接入量將從2015 年的16.91 億臺增長到30.54 億臺[1].隨著物聯(lián)網(wǎng)的快速發(fā)展以及物聯(lián)網(wǎng)平臺的逐步成熟，無處不在的末端設(shè)備和設(shè)施，如智能傳感器、移動終端等通過物聯(lián)網(wǎng)連接在一起，萬物互聯(lián)已經(jīng)成為必然趨勢.隨之興起的物聯(lián)網(wǎng)技術(shù)被廣泛應(yīng)用到各個領(lǐng)域，產(chǎn)生了海量的異構(gòu)數(shù)據(jù).Mccrory[2]在2010年提出了“數(shù)據(jù)引力”的概念，將數(shù)據(jù)、軟件應(yīng)用、接口服務(wù)等比作星體，含有各自的質(zhì)量和密度，數(shù)據(jù)質(zhì)量不斷地增加并且遠(yuǎn)大于其他“星體”，而其他“星體”都將被巨大的引力吸引過來并以數(shù)據(jù)“星體”為中心.由此可見，對于物聯(lián)網(wǎng)異構(gòu)數(shù)據(jù)，其處理技術(shù)的發(fā)展將會直接影響整個物聯(lián)網(wǎng)技術(shù)的發(fā)展和進(jìn)步.目前大部分的異構(gòu)數(shù)據(jù)都是獨(dú)立、分散地存儲于各個地區(qū)，形成了大量信息孤島，由結(jié)構(gòu)化數(shù)據(jù)(如關(guān)系型數(shù)據(jù)庫)、半結(jié)構(gòu)化數(shù)據(jù)(如XML，HTML)和非結(jié)構(gòu)化數(shù)據(jù)(如NoSQL數(shù)據(jù)庫、圖片、視頻)等多種形式組成，如何通過“2次采集”將這些信息孤島互聯(lián)起來受到人們的關(guān)注.

模式匹配技術(shù)在數(shù)據(jù)互聯(lián)過程中發(fā)揮著巨大的作用[3]，盡管目前對物聯(lián)網(wǎng)異構(gòu)數(shù)據(jù)可以通過制定統(tǒng)一數(shù)據(jù)接口標(biāo)準(zhǔn)的方式進(jìn)行互聯(lián)，但在實(shí)際應(yīng)用中卻很難實(shí)現(xiàn)，因?yàn)閷τ谝呀?jīng)存在的海量數(shù)據(jù)存儲模式的改造成本是巨大的，可以說數(shù)據(jù)異構(gòu)的問題是不可避免的，數(shù)據(jù)模式匹配技術(shù)為解決以上問題提供了一個良好的解決方案.模式匹配是一個構(gòu)建源模式和目標(biāo)模式中元素間映射關(guān)系的過程，而傳統(tǒng)的模式匹配操作大多都是由IT技術(shù)人員手工完成，隨著數(shù)據(jù)規(guī)模的擴(kuò)大以及模式復(fù)雜度的提升，手工匹配會耗費(fèi)巨大的人力物力，并且容易破壞數(shù)據(jù)的完整性和準(zhǔn)確性.目前已有的研究成果利用元素自身信息、語義信息、數(shù)據(jù)實(shí)例信息和結(jié)構(gòu)信息來挖掘模式正確的元素映射關(guān)系.在之前的工作中，我們構(gòu)建了一個面向物聯(lián)網(wǎng)的異構(gòu)數(shù)據(jù)轉(zhuǎn)換模型，實(shí)現(xiàn)快速高效的物聯(lián)網(wǎng)異構(gòu)數(shù)據(jù)互聯(lián)，然而在互聯(lián)過程中模式匹配過程的人工參與度過高，匹配效率低下.為了解決該問題，我們首先分析了物聯(lián)網(wǎng)異構(gòu)數(shù)據(jù)的特征，即時間序列特征.并以此為切入點(diǎn)，通過解析時間序列數(shù)據(jù)來對物聯(lián)網(wǎng)異構(gòu)數(shù)據(jù)進(jìn)行分類識別，為自動模式匹配提供了可能.基于以上研究成果，本文提出了一種面向物聯(lián)網(wǎng)異構(gòu)數(shù)據(jù)的模式分層匹配算法(hierarchical schema matching algorithm， HSMA)，該算法基于數(shù)據(jù)模式的實(shí)例信息，通過3層映射匹配：特征分類匹配、關(guān)系特征聚類匹配和混合元素匹配，實(shí)現(xiàn)了物聯(lián)網(wǎng)異構(gòu)數(shù)據(jù)的模式自動匹配，減小了復(fù)雜模式下元素間匹配空間，提高了自動匹配的效率和準(zhǔn)確度.

1 相關(guān)研究及問題分析

1.1 相關(guān)研究

目前比較典型且已經(jīng)廣泛應(yīng)用的匹配算法有Auto-match,Clio,COMA,iMAP,Cupid,LSD,GLUE等.Cupid[4]利用屬性名稱、數(shù)據(jù)類型等模式信息計算屬性之間的語義相似性，將語義相似度和結(jié)構(gòu)相似度結(jié)合起來進(jìn)行匹配.COMA[5]利用多種匹配器協(xié)同工作，通過過濾、篩選來提高匹配結(jié)果的準(zhǔn)確率和效率.LSD[6]應(yīng)用機(jī)器學(xué)習(xí)算法實(shí)現(xiàn)匹配并且自動整合匹配結(jié)果，可以很好地發(fā)現(xiàn)1∶1和1∶n的匹配.基于數(shù)據(jù)實(shí)例信息的模式匹配的iMAP[7]方法是一種綜合利用模式中多種類型的信息同時得到模式間的簡單和復(fù)雜映射關(guān)系的方法，可以很好地發(fā)現(xiàn)1∶1和1∶n的匹配.

1.2 問題分析

文獻(xiàn)[8]提出了一種基于實(shí)體分類的數(shù)據(jù)庫模式匹配方法，根據(jù)數(shù)據(jù)實(shí)例信息的語義信息進(jìn)行特征提取，運(yùn)用樸素貝葉斯算法對特征進(jìn)行分類，最后對子模式進(jìn)行相應(yīng)的模式匹配.由于物聯(lián)網(wǎng)數(shù)據(jù)的海量性和異構(gòu)性，無論數(shù)據(jù)庫設(shè)計得多么規(guī)范化，但其屬性名稱和意義的定義因人而異，單一地以屬性名等語義信息進(jìn)行模糊分類的方式是不可取的，因?yàn)檫@種分類僅僅基于人為理解而非源數(shù)據(jù)的本質(zhì)特征.文獻(xiàn)[9]利用數(shù)據(jù)的概率分布統(tǒng)計特征，從另一個角度對數(shù)據(jù)特征進(jìn)行提取，利用BP神經(jīng)網(wǎng)絡(luò)算法提高了模式匹配效率和準(zhǔn)確度.然而該算法針對的僅僅是1:1列之間的匹配，不適用于復(fù)雜模式匹配.隨著數(shù)據(jù)規(guī)模不斷增大，匹配空間和匹配次數(shù)也會急劇增加，導(dǎo)致匹配效率低下.與文獻(xiàn)[8-9]的算法相比，本文提出的HSMA算法能夠較好地解決在現(xiàn)實(shí)應(yīng)用中自動獲取解析數(shù)據(jù)源模式信息困難的問題，通過解析海量異構(gòu)的原始數(shù)據(jù)，按照物聯(lián)網(wǎng)數(shù)據(jù)的時間序列性特征將解析的特征進(jìn)行分類，從而代表數(shù)據(jù)源的模式特征；其次，HSMA算法中的關(guān)系特征聚類方法具有一定創(chuàng)新性，尤其對物聯(lián)網(wǎng)傳感數(shù)據(jù)的特征聚類有良好的效果，消除了數(shù)據(jù)集數(shù)據(jù)間不同數(shù)據(jù)類型差異的影響；最后，HSMA運(yùn)用分層的方法逐步縮小匹配空間，減少匹配次數(shù)，提高了匹配的效率.

2 HSMA算法

為了實(shí)現(xiàn)物聯(lián)網(wǎng)異構(gòu)數(shù)據(jù)(結(jié)構(gòu)化數(shù)據(jù))的模式匹配的智能化，我們設(shè)計了一種模式分層匹配算法HSMA.對于輸入的一個未知源數(shù)據(jù)，我們首先根據(jù)時間序列特征和數(shù)據(jù)類型特征對其所有的數(shù)據(jù)集進(jìn)行分類，獲得子模式集合.與此同時，通過之前的研究成果IFRAT算法，獲取未知數(shù)據(jù)源領(lǐng)域特征信息，根據(jù)領(lǐng)域的不同初始化相應(yīng)的領(lǐng)域標(biāo)準(zhǔn)集合以及標(biāo)準(zhǔn)化數(shù)據(jù)庫進(jìn)行關(guān)系特征聚類匹配，建立各類中源數(shù)據(jù)集合和目標(biāo)數(shù)據(jù)庫之間的映射關(guān)系(第1層匹配)；然后依據(jù)所提取的數(shù)據(jù)集特征，運(yùn)用機(jī)器學(xué)習(xí)算法，對每個子模式中的數(shù)據(jù)集進(jìn)行聚類，進(jìn)一步縮小匹配空間和范圍，對聚類結(jié)果與相應(yīng)的標(biāo)準(zhǔn)集合數(shù)據(jù)集進(jìn)行相似度計算，建立匹配映射(第2層匹配)；最后將相匹配的聚類中的元素混合并進(jìn)行相似度計算(第3層匹配)，產(chǎn)生源數(shù)據(jù)與目標(biāo)數(shù)據(jù)庫之間的模式匹配結(jié)果.通過以上3層匹配，HSMA逐步縮小匹配空間，降低了匹配次數(shù)，從而提高匹配效率.HSMA算法的整體架構(gòu)如圖1所示：

Fig. 1 Architecture of HSMA圖1 HSMA算法架構(gòu)

2.1 源數(shù)據(jù)標(biāo)準(zhǔn)化

每個數(shù)據(jù)集中存在多種類型數(shù)據(jù)，以往的模式匹配算法都是對同一個數(shù)據(jù)集中不同類型元素進(jìn)行單獨(dú)處理，處理方法多樣，雖然能夠保留單一元素特征，但是卻破壞了不同類型元素間的關(guān)聯(lián)關(guān)系，失去了整個數(shù)據(jù)集的特征.因此，針對數(shù)據(jù)集中常見的數(shù)據(jù)格式(如數(shù)值、字符、日期等)，需要尋找一個統(tǒng)一的數(shù)據(jù)處理方式以保證其特征的完整性.首先，我們將每個結(jié)構(gòu)化數(shù)據(jù)集都看作是一個存在行列關(guān)系的2維矩陣，矩陣中的相鄰行元素的差值變化結(jié)果作為新矩陣的行，我們將新的矩陣成為關(guān)系矩陣.差值變化結(jié)果用-，0，+表示，通過該方法，我們用關(guān)系值代替了原來的內(nèi)容值，將不同類型的數(shù)據(jù)轉(zhuǎn)化為同一標(biāo)準(zhǔn)，最終得到關(guān)系矩陣.關(guān)系矩陣作為數(shù)據(jù)集的一個標(biāo)準(zhǔn)化形式，能夠更好地被用于數(shù)據(jù)集的特征挖掘.

為了更好地對HSMA算法進(jìn)行理解，我們對本文中所用到的一些名詞進(jìn)行定義.

定義1. 關(guān)系矩陣.對于任意常見的結(jié)構(gòu)化數(shù)據(jù)Dm×n，都可以通過相鄰行做差的方法，差值結(jié)果用-，0，+這3種符號表示，我們將這樣的矩陣定義為關(guān)系矩陣，用M表示.

定義2. 關(guān)系鍵對.關(guān)系矩陣M的每一行中元素兩兩組合所形成的鍵對.

定義3. 特征列.對于關(guān)系矩陣M的任意一列，當(dāng)且僅當(dāng)同時滿足2個條件：1)該列元素的數(shù)值類型為日期類型或可以轉(zhuǎn)化成日期類型的其他數(shù)據(jù)類型；2)該列中的元素“+”或元素“-”的出現(xiàn)頻率大于閾值θ(我們?nèi)ˇ?90%)，這樣的列被稱作時間序列特征列.如果僅滿足條件2，則該列被稱為主特征列.

定義4. 時間序列數(shù)據(jù).物聯(lián)網(wǎng)傳感器產(chǎn)生的原始數(shù)據(jù)，按照時間順序以結(jié)構(gòu)化的形式存儲，這樣的數(shù)據(jù)集合被稱為時間序列數(shù)據(jù).

2.2 3層映射匹配

本節(jié)對HSMA的分層匹配算法進(jìn)行了詳細(xì)的描述，共分為3層：第1層為特征分類匹配(時間序列特征和數(shù)據(jù)類型特征)；第2層為關(guān)系特征聚類匹配；第3層為混合元素匹配.基于分層的思想，我們將復(fù)雜的異構(gòu)數(shù)據(jù)模式匹配過程分割成3步，逐步縮小其匹配空間.對于每一步的匹配，都是基于物聯(lián)網(wǎng)異構(gòu)數(shù)據(jù)特性，比較源數(shù)據(jù)與標(biāo)準(zhǔn)數(shù)據(jù)間的相似性，構(gòu)建映射關(guān)系，最終實(shí)現(xiàn)物聯(lián)網(wǎng)異構(gòu)數(shù)據(jù)的模式自動匹配.

2.2.1 特征分類匹配

HSMA算法在特征分類匹配過程中提供2種分類方法：

1) 時間序列特征分類

時間序列是物聯(lián)網(wǎng)異構(gòu)數(shù)據(jù)的標(biāo)志性特征，可以被用來進(jìn)行物聯(lián)網(wǎng)異構(gòu)數(shù)據(jù)分類.首先我們將物聯(lián)網(wǎng)異構(gòu)數(shù)據(jù)的按時間序列特性分為3類：

① 時間序列數(shù)據(jù)類P.所有包含時間序列特征列的數(shù)據(jù)集屬于時間序列數(shù)據(jù)類(如傳感網(wǎng)傳感數(shù)據(jù)).

② 時間序列屬性類Q.包含主特征列的數(shù)據(jù)集歸于時間序列數(shù)據(jù)屬性類(如傳感網(wǎng)監(jiān)測對象元數(shù)據(jù))，如描述時間序列屬性的相關(guān)信息.

③ 非時間序列類R.包含與時間序列無關(guān)的數(shù)據(jù)集，一般由許多相關(guān)輔助信息組成.

HSMA算法將物聯(lián)網(wǎng)異構(gòu)數(shù)據(jù)按照時間序列特征分類，最后得到數(shù)據(jù)分類集合{時間序列數(shù)據(jù)類，時間序列屬性類，非時間序列類}，其具體的分類算法如算法1所示：

算法1. 時間序列特征分類算法.

輸入：物聯(lián)網(wǎng)異構(gòu)數(shù)據(jù)集合X={x1,x2,…,xn}(結(jié)構(gòu)化數(shù)據(jù))；

輸出：時間序列特征類集合{P，Q，R}.

① 獲取物聯(lián)網(wǎng)異構(gòu)數(shù)據(jù)集合(結(jié)構(gòu)化數(shù)據(jù))，X={x1,x2,…,xn};

② 對X中所有數(shù)據(jù)集xi進(jìn)行數(shù)據(jù)標(biāo)準(zhǔn)化，得到與X相對應(yīng)的關(guān)系矩陣集合Y={M1,M2,…,Mn};

③ ?xi∈X，遍歷xi的每一列，依據(jù)時間序列特征對xi進(jìn)行分類;

④ for eachxi∈Xdo

⑤ for eachcol屬于Mi的列集合 do

⑥n=Column_num(Mi);

⑧ ifθ≥90% then

⑨ ifcol∈Type.datethen

⑩xi∈P;

2) 數(shù)據(jù)類型特征分類

物聯(lián)網(wǎng)異構(gòu)數(shù)據(jù)中，不同領(lǐng)域的源數(shù)據(jù)集合具有不同的數(shù)據(jù)類型分布特征，依據(jù)該特征對物聯(lián)網(wǎng)異構(gòu)數(shù)據(jù)分類.數(shù)據(jù)類型按照物聯(lián)網(wǎng)異構(gòu)數(shù)據(jù)的常見類型被分為5類:數(shù)值型(value)、字符類型(char)、時間類型(date)、字符-數(shù)值類型(char-value)、字符-時間類型(char-date)，考慮在復(fù)雜模式匹配下，相同的數(shù)據(jù)可能被賦予不同的數(shù)據(jù)類型，數(shù)據(jù)類型間的相互轉(zhuǎn)換會導(dǎo)致其分布特征偏離，因此將字符串-數(shù)值等可以相互間進(jìn)行轉(zhuǎn)換的情況列入數(shù)據(jù)類型特征.利用各個數(shù)據(jù)類型出現(xiàn)的頻率值，構(gòu)建一個5維的特征向量，然后依據(jù)特征向量對物聯(lián)網(wǎng)異構(gòu)數(shù)據(jù)進(jìn)行特征分類：

① 時間主導(dǎo)類E.由于時間類型的特殊性，只要包含時間類型的數(shù)據(jù)集都屬于時間主導(dǎo)類.

② 數(shù)值主導(dǎo)類F.數(shù)值類型(如int,long,float,double等)占比重大的數(shù)據(jù)集屬于數(shù)值主導(dǎo)類.

③ 字符主導(dǎo)類G.字符類型(如char,varchar,nvarchar等)占比重大的數(shù)據(jù)集屬于字符導(dǎo)類.

HSMA算法將物聯(lián)網(wǎng)異構(gòu)數(shù)據(jù)按照數(shù)據(jù)類型特征分類，最后得到數(shù)據(jù)分類集合{E，F(xiàn)，G}，其具體的分類過程如算法2所示：

算法2. 數(shù)據(jù)類型特征分類算法.

輸入：物聯(lián)網(wǎng)異構(gòu)數(shù)據(jù)集合X={x1,x2…,xn}(結(jié)構(gòu)化數(shù)據(jù))；

輸出：數(shù)據(jù)類型特征類集合{E，F(xiàn)，G}.

① 獲取物聯(lián)網(wǎng)異構(gòu)數(shù)據(jù)集合(結(jié)構(gòu)化數(shù)據(jù))，X={x1,x2…,xn};

② 對X中所有數(shù)據(jù)集xi進(jìn)行數(shù)據(jù)結(jié)構(gòu)標(biāo)準(zhǔn)化;

③ ?xi∈X，遍歷xi的每一列，依據(jù)數(shù)據(jù)類型分布特征構(gòu)建xi的特征向量vi，得到X相對應(yīng)的特征矩陣V=(v1,v2,…,vn);

④ for eachxi∈Xdo

⑤ for eachcol∈xido

⑥ 統(tǒng)計過程①中各個數(shù)據(jù)類型發(fā)生次數(shù);

⑦ end for

⑧ 構(gòu)建數(shù)據(jù)類型特征向量vi;

⑨n=Column_num(xi);

2.2.2 關(guān)系特征聚類匹配

通過2.2.1節(jié)中的特征分類匹配，對源數(shù)據(jù)S和標(biāo)準(zhǔn)化數(shù)據(jù)庫T中的數(shù)據(jù)分別進(jìn)行時間序列特征分類和數(shù)據(jù)類型特征分類，得到的結(jié)果集合統(tǒng)稱為Scla和Tcla.在本節(jié)，我們采用SOM聚類方法對Scla和Tcla中的數(shù)據(jù)集進(jìn)行歸類，進(jìn)一步縮小匹配空間.在聚類過程中，我們采用關(guān)系矩陣M作為數(shù)據(jù)集的特征矩陣，因?yàn)殛P(guān)系矩陣M具有以下特點(diǎn)：1)M可以將數(shù)據(jù)集中不同類型的數(shù)據(jù)轉(zhuǎn)換成統(tǒng)一的符號表示；2)M可以保留元素間的相互關(guān)系，而傳統(tǒng)的匹配方法忽略了這一點(diǎn)；3)M解決了復(fù)雜模式匹配下元素排列順序多變的問題，更好地表現(xiàn)數(shù)據(jù)集特征.關(guān)系矩陣M中，每一行中所有項(xiàng)兩兩組合形成關(guān)系鍵對，HSMA算法通過對數(shù)據(jù)集進(jìn)行行遍歷，提取數(shù)據(jù)集關(guān)系鍵對的頻率分布特征，作為該數(shù)據(jù)集的特征向量vi，基于得到的特征向量進(jìn)行聚類匹配.詳細(xì)過程如算法3所示：

算法3. 關(guān)系特征聚類匹配算法.

輸入：Scla，Tcla;

輸出：Scla和Tcla的聚類集合.

① 獲取Scla和Tcla中的分類集合：Scla或Tcla={Classification1，Classification2，Classi-fication3};

②dataset∈{E,F,G};

③ for eachClassification∈Sclado

④ for eachds∈datasetdo

⑤ds→M;

⑥ for eachrow屬于M的行集合 do

⑦ 關(guān)系鍵Key←{(-，-),(-，0),(-，+),(0，0),(0，+),(+，+)};

⑧ 統(tǒng)計每種關(guān)系鍵Key出現(xiàn)的次數(shù);

⑨ end for

⑩n←統(tǒng)計所有關(guān)系鍵Key出現(xiàn)的總次數(shù)；

在本節(jié)，我們基于關(guān)系矩陣中提取的特征向量，對Scla中的所有數(shù)據(jù)集進(jìn)行聚類，得到聚類集合D={d1,d2,…,dl}，通過計算歐氏距離，確定Tcla中的每一個數(shù)據(jù)集在Scla中最相似的聚類集合，從而進(jìn)一步縮小匹配空間.我們假設(shè)并認(rèn)定S中的每一個聚類對應(yīng)T中唯一的數(shù)據(jù)集，即數(shù)據(jù)集之間只存在1∶n的關(guān)系.

2.2.3 混合元素匹配

基于2.2.2節(jié)得到的聚類集合D.?di∈D，我們將di中的所有元素混合在一起，采用文獻(xiàn)[10]的算法對于單一元素進(jìn)行聚類匹配，該算法能夠快速有效地發(fā)現(xiàn)聚類中心，能夠在短時間內(nèi)完成聚類過程且過程精簡，最終得到匹配結(jié)果集合R={r1,r2,…,rl}.考慮到現(xiàn)實(shí)情況的復(fù)雜性，我們很難做到元素1∶1的精準(zhǔn)匹配，所以?ri∈R，我們規(guī)定ri中只包含1個標(biāo)準(zhǔn)化數(shù)據(jù)元素和φ個源數(shù)據(jù)的元素(這里的φ人為設(shè)定，本文選取φ=1,2,3)，這φ個源數(shù)據(jù)的元素作為最相似的元素被推薦用戶，具體如算法4所示：

算法4. 混合元素匹配算法

輸入：聚類集合D←{d1,d2,…,dl};

輸出：匹配結(jié)果集合R←{r1,r2,…,rl}.

① 獲取聚類集合：D←{d1,d2,…,dl};

② for eachdi∈Ddo

③ 運(yùn)用文獻(xiàn)[10]算法進(jìn)行匹配;

④ 設(shè)定φ的數(shù)值;

⑤ri←di的匹配結(jié)果;

⑥ end for

⑦ return匹配結(jié)果集合R←{r1,r2,…,rl}.

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

3.1 數(shù)據(jù)選取

為了證明HSMA的可行性和有效性，我們選取工業(yè)物聯(lián)網(wǎng)家電產(chǎn)品測試領(lǐng)域的家用空調(diào)性能測試中13個不同廠家的30個數(shù)據(jù)庫作為源數(shù)據(jù)，將基于國際標(biāo)準(zhǔn)IEEE 1851的空調(diào)測試數(shù)據(jù)庫作為標(biāo)準(zhǔn)化數(shù)據(jù)庫(采用Oracle)，數(shù)據(jù)詳細(xì)信息如表1所示:

Table 1 Performance Test Data of Residential Air Conditioner

我們認(rèn)為一般情況下存在2種常見的異構(gòu)形式：行列轉(zhuǎn)換和拆分.

1) 行列轉(zhuǎn)換.不是完全屬于同一列的內(nèi)容被列入同一列中，為了消除結(jié)構(gòu)不同對匹配造成的影響，我們需要對這一類型的列進(jìn)行邏輯行轉(zhuǎn)換，同時記錄相應(yīng)映射關(guān)系，如圖2所示：

Fig. 2 Row-column transforming of IoT heterogeneous data圖2 物聯(lián)網(wǎng)異構(gòu)數(shù)據(jù)行列轉(zhuǎn)換

2) 拆分.通常情況下列的合并要么是字符串由特殊字符隔開，要么布爾型直接合并，所以找到合并字段進(jìn)行邏輯拆分，同時記錄相應(yīng)的映射關(guān)系，如圖3所示：

Fig. 3 Logic splitting of IoT heterogeneous data圖3 物聯(lián)網(wǎng)異構(gòu)數(shù)據(jù)邏輯拆分

3.2 算法對比

我們采用不同的基于數(shù)據(jù)實(shí)例和數(shù)據(jù)庫模式信息的模式匹配算法與HSMA算法進(jìn)行對比，詳細(xì)的對比信息如表2所示：

1) SMEC[8].通過樸素貝葉斯學(xué)習(xí)將實(shí)體分為不同的類，以同樣的類來匹配子模式之間的模式元素.

2) SMDD[9].基于神經(jīng)網(wǎng)絡(luò)的模式匹配算法，通過分析模式元素所包含的數(shù)據(jù)實(shí)例的分布規(guī)律，自動完成模式匹配.

3) iMAP[7].一種綜合利用模式中多種類型的信息同時得到模式間的簡單和復(fù)雜映射關(guān)系的方法，在得到匹配關(guān)系的同時保存對每個匹配關(guān)系的判斷過程，當(dāng)用戶對最終結(jié)果進(jìn)行調(diào)整時，向用戶提供保存的判斷過程作為用戶進(jìn)行調(diào)整的依據(jù).

Table 2 Comparison of Different Algorithms表2 不同算法之間比較

3.3 實(shí)測結(jié)果

為了評估HSMA的匹配質(zhì)量，我們采用3個通用指標(biāo)[11]進(jìn)行評估：

1) 查準(zhǔn)率(Precision).匹配結(jié)果中正確匹配結(jié)果的比率.

(1)

其中,T為正確識別的匹配結(jié)果，P為匹配方法返回的匹配結(jié)果，F(xiàn)為錯誤的匹配.

2) 查全率(Recall).匹配結(jié)果中正確匹配結(jié)果占實(shí)際匹配結(jié)果的比率.

(2)

其中，R為手工匹配結(jié)果.

3)F1_measure.能夠全面評價匹配質(zhì)量的統(tǒng)計量.

(3)

3.3.1 HSMA算法自測

1) HSMA算法的匹配質(zhì)量受到參數(shù)φ選取的影響.通過對φ設(shè)定不同的值，分析比較其查準(zhǔn)率、查全率和F1-measure，結(jié)果如圖4所示.與φ=1相比，當(dāng)φ>1時，查全率、查準(zhǔn)率和全面性都有提高，因?yàn)镠SMA算法無法保證精準(zhǔn)的1∶1匹配，模式的異構(gòu)性導(dǎo)致存在多個相近的相似度結(jié)果.但并不是φ值越大越好，φ的增大會導(dǎo)致匹配干擾項(xiàng)增加，降低匹配質(zhì)量，當(dāng)φ=3時，可以看出其匹配質(zhì)量大于φ=1但小于φ=2.

Fig. 4 Matching quality of HSMA under different φ圖4 在不同的φ下HSMA的匹配質(zhì)量

2) HSMA算法的匹配質(zhì)量受到輸入數(shù)據(jù)庫數(shù)量的影響.輸入數(shù)據(jù)庫的個數(shù)會直接影響關(guān)系特征聚類的效果，充足的數(shù)據(jù)會使數(shù)據(jù)特征更加明顯.如圖5所示，對于不同的φ值，當(dāng)輸入數(shù)據(jù)庫數(shù)量在(0，15)范圍時，其匹配質(zhì)量隨著輸入數(shù)據(jù)庫個數(shù)的增加而不斷提高且變化較為明顯；但當(dāng)輸入數(shù)據(jù)庫數(shù)量大于15后，匹配質(zhì)量增長緩慢.

Fig. 5 Matching quality of HSMA with the increasing number of input databases圖5 隨著輸入數(shù)據(jù)庫數(shù)量的增加HSMA的匹配質(zhì)量

Fig. 6 Matching time of HSMA圖6 HSMA需要的匹配時間

3) HSMA算法的時間效率受參數(shù)φ選取的影響.圖6比較了在φ值的不同情況下源數(shù)據(jù)個數(shù)對HSMA算法時間效率的影響.如圖6所示，φ越大，HSMA算法所用的匹配時間就越大，因?yàn)棣罩档脑黾訉?dǎo)致在混合元素匹配過程中匹配次數(shù)的增多，提高了時間復(fù)雜度；當(dāng)φ值固定時，采用時間序列特征分類的HSMA算法的匹配時間低于采用數(shù)據(jù)類型特征分類的HSMA算法.

4) HSMA算法的時間效率受特征分類的影響.我們隨機(jī)選取15個數(shù)據(jù)源作為HSMA算法的輸入，分別采用無分類、時間序列特征分類和數(shù)據(jù)類型特征分類并且設(shè)定不同的值，分析比較其每一層匹配所用時間，結(jié)果如圖7所示.φ的選取僅僅會影響混合元素匹配的匹配時間，φ值越大混合元素匹配過程所用的時間就越多；當(dāng)φ值固定時，采用時間序列分類的HSMA算法的匹配時間相對較小.

Fig. 7 Hierarchical matching time of HSMA圖7 HSMA的每一層匹配時間

3.3.2 算法性能對比

由3.3.1節(jié)可得，當(dāng)選取φ=2，采用時間序列特征分類的HSMA算法的性能最高，因此將其與3.2節(jié)中各個模式匹配算法進(jìn)行比較.我們選取了30個異構(gòu)數(shù)據(jù)庫作為HSMA的輸入，比較所得結(jié)果如圖8所示.如圖8(a)所示，HSMA算法的匹配質(zhì)量與其他算法相比較高，其中源數(shù)據(jù)庫的異構(gòu)性和模式信息的不完整導(dǎo)致SMEC效率最差.如圖8(b)所示，由于HSMA算法采用預(yù)處理以及多次聚類，導(dǎo)致其所用時間明顯高于其他算法.

Fig. 8 Performance comparison of HSMA with other algorithms圖8 HSMA算法與其他算法的性能比較

4 總結(jié)和未來工作

我們設(shè)計了一種模式分層匹配算法HSMA，對于輸入的一個未知源數(shù)據(jù)，根據(jù)領(lǐng)域的不同初始化相應(yīng)的領(lǐng)域標(biāo)準(zhǔn)集合以及標(biāo)準(zhǔn)化數(shù)據(jù)庫進(jìn)行特征分類匹配，建立各分類中源數(shù)據(jù)集合和標(biāo)準(zhǔn)數(shù)據(jù)庫數(shù)據(jù)集合的映射關(guān)系；然后提取源數(shù)據(jù)集和目標(biāo)數(shù)據(jù)庫表中的關(guān)系特征，運(yùn)用SOM聚類算法，對每一個子模式中的數(shù)據(jù)集進(jìn)行聚類，對聚類結(jié)果與相應(yīng)的標(biāo)準(zhǔn)數(shù)據(jù)庫數(shù)據(jù)集進(jìn)行相似度計算，建立匹配映射；最后將匹配結(jié)果集合中的混合元素進(jìn)行相似度計算，進(jìn)行單一元素匹配.通過以上3層匹配，HSMA算法逐步縮小匹配空間，降低了匹配次數(shù)，從而提高匹配質(zhì)量和效率.

由于在關(guān)系特征聚類匹配及混合元素匹配的過程中，聚類算法的好壞直接決定了最后的匹配質(zhì)量和總體的匹配時間，聚類雖然能夠縮小匹配空間，但同時有可能帶來匹配錯誤，導(dǎo)致相關(guān)元素并不在同一個類中.未來會嘗試使用不同的機(jī)器學(xué)習(xí)算法對HSMA算法進(jìn)行改進(jìn)，并且尋找最好的組合模式來提高聚類的效果.此外本文在實(shí)驗(yàn)驗(yàn)證環(huán)節(jié)采用iMAP,SMDD等經(jīng)典算法與HSMA算法進(jìn)行對比，提高了對比結(jié)果的可靠性，但是這些算法偏于老舊，下一步將采用近幾年的新算法進(jìn)行比較，以驗(yàn)證HSMA算法的先進(jìn)性.