鄭博文，趙逢禹

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上海 200093)

異構(gòu)數(shù)據(jù)索引是在異構(gòu)數(shù)據(jù)空間中建立索引，進(jìn)而提供高效、便捷和多樣化的數(shù)據(jù)查詢。隨著互聯(lián)網(wǎng)和云計(jì)算技術(shù)的飛速發(fā)展、涉及的數(shù)據(jù)量急劇增加、信息化水平的不斷提升、各種各樣的數(shù)據(jù)流種類和規(guī)模也持續(xù)增長(zhǎng)的情況下，最優(yōu)異構(gòu)數(shù)據(jù)索引是解決在海量數(shù)據(jù)中快速查詢出所需要的數(shù)據(jù)的一個(gè)最直接也是最有效的方法[1-4]。

異構(gòu)數(shù)據(jù)索引已有許多研究成果，文獻(xiàn)[5]中，Nafaa Jabeur在用CAN路由的方法來增加分布式系統(tǒng)的可擴(kuò)展性，實(shí)現(xiàn)異構(gòu)數(shù)據(jù)索引的建立。文獻(xiàn)[6]中，Benjamin Shapiro利用R-tree和Bloom-Filter相結(jié)合的方法實(shí)現(xiàn)異構(gòu)數(shù)據(jù)索引的建立并提高點(diǎn)查詢和范圍查詢的效率。文獻(xiàn)[7]中，Song Baoyan基于可變網(wǎng)格技術(shù)提出了VGHI二級(jí)異構(gòu)索引結(jié)構(gòu)，通過在每個(gè)子空間上構(gòu)建M樹管理自身的數(shù)據(jù)，這種二級(jí)異構(gòu)索引有效地管理了分布式系統(tǒng)和每個(gè)子空間的索引。文獻(xiàn)[8]中，Traversel通過在改進(jìn)的MapReduce框架上構(gòu)建文件索引來提高查詢處理的效率，提出了結(jié)合Overlay結(jié)構(gòu)和B-tree索引的二級(jí)索引結(jié)構(gòu)CG-index，能夠有效地支持云環(huán)境上的查詢處理操作。

盡管異構(gòu)數(shù)據(jù)索引的研究取得了許多成果，但還存在一些問題。(1)Song Baoyan提出的VGHI二級(jí)異構(gòu)索引[9]結(jié)構(gòu)和Nafaa Jabeur利用CAN路由的方法建立的索引結(jié)構(gòu)太過龐大，占用過多的物理空間，無法高效地建立最優(yōu)異構(gòu)數(shù)據(jù)索引；(2)Benjamin Shapiro利用R-tree和Bloom-Filter相結(jié)合構(gòu)建異構(gòu)數(shù)據(jù)索引的方法和Traversel通過MapReduce框架構(gòu)建索引的方法雖然能快速地構(gòu)建索引，但運(yùn)用R-tree構(gòu)建的索引是通過對(duì)索引進(jìn)行范圍劃分，其原理是非葉結(jié)點(diǎn)存儲(chǔ)其所有子結(jié)點(diǎn)的區(qū)域范圍，這種區(qū)域范圍使索引結(jié)構(gòu)較為簡(jiǎn)單，在海量數(shù)據(jù)中無法根據(jù)異構(gòu)數(shù)據(jù)索引進(jìn)行快速的精準(zhǔn)查詢。

本文主要研究在大數(shù)據(jù)的背景下快速構(gòu)建索引且通過決策樹分類算法準(zhǔn)確地構(gòu)建索引從而優(yōu)化異構(gòu)數(shù)據(jù)索引結(jié)構(gòu)。最后在大量的公開數(shù)據(jù)集上進(jìn)行索引優(yōu)化實(shí)驗(yàn)，根據(jù)構(gòu)建的異構(gòu)數(shù)據(jù)索引提高海量數(shù)據(jù)查詢的性能和可擴(kuò)展性。

1 異構(gòu)數(shù)據(jù)索引

異構(gòu)數(shù)據(jù)索引由局部索引和全局索引兩部分組成，其中，全局索引是通過分布式系統(tǒng)匯總的各個(gè)節(jié)點(diǎn)信息得到的，它是由一個(gè)分布式系統(tǒng)進(jìn)行維護(hù)。局部索引采用R-tree[10]管理數(shù)據(jù)，整個(gè)索引采用“自下而上”的方式構(gòu)建。在局部節(jié)點(diǎn)上建立局部索引，然后將各個(gè)局部索引的信息發(fā)布到全局索引上，通過全局索引可以得到每個(gè)集群的子空間的范圍以及它的鄰居空間的信息，即給定一個(gè)具體的數(shù)據(jù)信息，通過全局索引可以快速地找到該數(shù)據(jù)所屬的子空間，在查詢時(shí)可以快速地縮小目標(biāo)空間的范圍。

當(dāng)用戶向全局索引中的任意節(jié)點(diǎn)發(fā)送查詢請(qǐng)求時(shí)，全局索引節(jié)點(diǎn)通過全局索引表找到與查詢相關(guān)的局部節(jié)點(diǎn)，并將查詢請(qǐng)求轉(zhuǎn)發(fā)給相關(guān)的局部數(shù)據(jù)節(jié)點(diǎn)，局部數(shù)據(jù)節(jié)點(diǎn)通過局部索引完成其本地?cái)?shù)據(jù)的查詢處理，最后將查詢結(jié)果返回。在異構(gòu)數(shù)據(jù)查詢中，異構(gòu)數(shù)據(jù)索引起到了至關(guān)重要的作用，而在異構(gòu)數(shù)據(jù)索引中的對(duì)局部索引優(yōu)化成了關(guān)鍵。

2 異構(gòu)數(shù)據(jù)索引優(yōu)化的方法

在傳統(tǒng)的數(shù)據(jù)庫(kù)索引中，表的第一列通常為表的主屬性，所以可以根據(jù)每張表的第一列屬性構(gòu)建主屬性局部索引。對(duì)于數(shù)據(jù)庫(kù)表的其他屬性列，如果某一列與其他表中的屬性列一致，則該列在很大程度上會(huì)成為條件篩選屬性或關(guān)聯(lián)屬性，所以也挑選該屬性列構(gòu)建局部索引，稱為非主屬性局部索引。本文基于索引屬性決策樹分類算法來判斷各個(gè)子節(jié)點(diǎn)上的表的屬性列是否應(yīng)該建立局部索引。

2.1 索引屬性決策樹的建立

索引屬性決策樹是一個(gè)監(jiān)督學(xué)習(xí)的分類算法，該方法分為決策樹的學(xué)習(xí)與基于決策樹的分類。首先從已含有正確索引的數(shù)據(jù)庫(kù)中得到主屬性列和非主屬性列的兩個(gè)屬性特征，然后統(tǒng)計(jì)所有屬性列在數(shù)據(jù)庫(kù)中的頻次，該頻次為屬性特征值。把屬性特征、屬性特征值以及屬性列是否是索引列匯集在一起，得到如表1所示的索引屬性數(shù)據(jù)訓(xùn)練集。

表1 索引屬性數(shù)據(jù)訓(xùn)練集

由表1可知，索引標(biāo)志取值為“是”與“否”，分別表示該屬性列是否被索引，主屬性列的出現(xiàn)頻次，非主屬性列的出現(xiàn)頻次，索引標(biāo)志Tag構(gòu)成一個(gè)元組，所有的元組形成數(shù)據(jù)集D?；诒?中的數(shù)據(jù)，使用決策樹生成算法，可以構(gòu)建出索引決策樹。該索引決策樹給出了屬性特征值的取值組合與是否是索引的關(guān)系。

2.2 基于索引決策樹的索引優(yōu)化

索引屬性決策樹建立后，就可以使用該決策樹對(duì)節(jié)點(diǎn)上所有表的索引進(jìn)行優(yōu)化。首先將節(jié)點(diǎn)上的所有表的主屬性列與非主屬性列的出現(xiàn)頻次進(jìn)行分析，構(gòu)建了索引屬性初始數(shù)據(jù)集，如表2所示。

表2 索引屬性初始數(shù)據(jù)集

然后使用生成的索引屬性決策樹對(duì)索引屬性初始數(shù)據(jù)集執(zhí)行分類，得到各個(gè)表中屬性列是否應(yīng)該建立局部索引。該方法有效地判斷各個(gè)表中屬性列是否需要建立索引，避免了索引建立過于冗余的問題，也保證了數(shù)據(jù)查詢的高效性。

局部索引建立完成后，基于MapReduce框架[8]對(duì)分布式文件系統(tǒng)構(gòu)建全局文件索引，該方法避免了基于可變網(wǎng)格技術(shù)的全局索引占用物理空間較大的問題，這種全局文件索引滿足了海量數(shù)據(jù)能在系統(tǒng)中的動(dòng)態(tài)線性擴(kuò)展，其次也滿足了分布式計(jì)算能力。通過分布式文件系統(tǒng)中的全局文件索引，能快速地查找到各個(gè)節(jié)點(diǎn)信息，在通過各個(gè)節(jié)點(diǎn)上的局部索引，就可以快速準(zhǔn)確地查找到所需數(shù)據(jù)。圖1所示為異構(gòu)數(shù)據(jù)索引的整體架構(gòu)。

圖1 異構(gòu)數(shù)據(jù)索引架構(gòu)圖

3 算法

決策樹(Decision Tree)[11-13]利用了概率論的原理，并且利用一種樹形圖作為分析工具。其基本原理是用決策點(diǎn)代表決策問題，用方案分枝代表可供選擇的方案，用概率分枝代表方案可能出現(xiàn)的各種結(jié)果，經(jīng)過對(duì)局部索引在各種結(jié)果條件下?lián)p益值的計(jì)算比較，為決策者提供決策依據(jù)。在局部索引建立方法中，采用決策樹算法進(jìn)行分析和調(diào)整索引結(jié)構(gòu)。通過數(shù)據(jù)庫(kù)表中屬性列的相關(guān)信息，運(yùn)用熵[14]值得到各個(gè)屬性的信息增益值，然后得到分裂屬性，進(jìn)而通過決策樹生成算法構(gòu)建決策樹[14-15]。

3.1 基本定義

本文采用C4.5算法來計(jì)算各個(gè)屬性的信息增益率(gain ratio)。C4.5算法解決了ID3算法不能處理連續(xù)值屬性的問題，而且克服了ID3算法偏向于多屬性值的缺點(diǎn)。這點(diǎn)在大數(shù)據(jù)索引構(gòu)建中，有效地解決了多維度、多屬性值索引構(gòu)建問題。

C4.5算法是以信息論為基礎(chǔ)，用信息熵和信息增益率作為衡量標(biāo)準(zhǔn)。下面先定義要用到的概念：

定義1 若存在n個(gè)相同概率的消息，則每個(gè)消息的概率p是1/n，一個(gè)消息傳遞的信息量為log2(n)。

定義2 若有n個(gè)消息，其給定概率分布為p=(p1,p2,…,pn)，則由該分布傳遞的信息量成為p的熵，記為

(1)

定義3 若一個(gè)記錄集合T根據(jù)類別屬性的值被分成互相獨(dú)立的類C1,C2,…,Ck，則識(shí)別T的一個(gè)元素所屬哪個(gè)類所需要的信息量為Info(T)=I(p)，其中p為C1,C2,…,Ck的概率分布，即

p=(|C1|/|T|,…,|Ck|/|T|)

(2)

定義4 若先根據(jù)非類別屬性X的值將T分成集合T1,T2,…,Tn，則確定T中一個(gè)元素類的信息量可通過確定Ti的加權(quán)平均數(shù)來得到，即Info(Ti)的加權(quán)平均值為

(3)

定義5 信息增益是兩個(gè)信息量之間的差值，其中一個(gè)信息量是需確定T的一個(gè)元素的信息量，另一個(gè)信息量是已得到的屬性X的值需確定的T一個(gè)元素的信息量，信息增益公式[3]為

Gain(X,T)=Info(T)-Info(X,T)

(4)

再取得分裂信息度量

(5)

所以信息增益率為

(6)

在表1的屬性數(shù)據(jù)訓(xùn)練集中，取表中前5行數(shù)據(jù)為構(gòu)成數(shù)據(jù)集D，候選屬性集合A={“作為主屬性列的出現(xiàn)頻次”，“作為非主屬性列的出現(xiàn)頻次”}，其中D中索引標(biāo)志“是”有3個(gè)，屬于索引標(biāo)志“否”有2個(gè)，則通過上述公式(1)分別計(jì)算其信息熵

下面對(duì)候選屬性集中每個(gè)屬性分別計(jì)算信息熵，要注意的是，本文將候選屬性值劃分為離散的區(qū)間集合。這里假設(shè)將頻次大于等于4的區(qū)間值都?xì)w為高頻次類，將頻次小于4的歸為低頻次類，所以可得其信息熵為：“作為主屬性列的出現(xiàn)頻次”的熵

同理可得“作為非主屬性列的出現(xiàn)頻次”的熵

根據(jù)得到的熵值，可以用式(4)計(jì)算第一個(gè)根節(jié)點(diǎn)所依賴的信息增益值Gain(A1)=Info(D)-Info(A1)=0.971-0.649=0.322Gain(A2)=Info(D)-Info(A2)=0.971-0.887=0.084

根據(jù)式(5)可得各候選屬性的分裂信息度量

然后帶入式(6)可得信息增益率為

根據(jù)計(jì)算得到的各候選屬性的信息增益率，選取信息增益率最大的“主屬性列的出現(xiàn)頻次”作為決策樹分裂節(jié)點(diǎn)。

3.2 索引屬性決策樹構(gòu)建算法

決策樹是以自頂向下遞歸的方法構(gòu)成，從屬性數(shù)據(jù)訓(xùn)練集中通過信息增益計(jì)算得到?jīng)Q策樹分裂節(jié)點(diǎn)來構(gòu)建決策樹。隨著樹的構(gòu)建，訓(xùn)練集遞歸地劃分成較小的子集，最終生成索引屬性決策樹。具體算法描述如下：

算法 決策樹生成generate_decision_tree。

輸入

(1)數(shù)據(jù)訓(xùn)練元組集合為D；

(2)attribute_list={“作為主屬性列的出現(xiàn)頻次”，“作為非主屬性列的出現(xiàn)頻次”}為候選屬性的集合。

輸出 一個(gè)決策樹。

方法

(1)創(chuàng)建樹的root節(jié)點(diǎn)；

(2)If 索引標(biāo)志相同(假設(shè)D.Tag==“是”) then 返回root，root.value=(”主屬性列的出現(xiàn)頻次”,”非主屬性列的出現(xiàn)頻次”)，root.child=”是”，轉(zhuǎn)步驟(7)，否則轉(zhuǎn)步驟(3)；

(3)計(jì)算attribute_list 中各屬性的信息增益率，選擇attribute_list 中具有最高信息增益率的屬性作為splitting_criterion，計(jì)算該屬性的頻次期望值，并把該值賦給root.ave；

(4)root.value=splitting_criterion；

(5)設(shè)d是D中root.value=splitting_criterion的數(shù)據(jù)元組的集合。//數(shù)據(jù)集的一個(gè)劃分；

ForD中root.value=splitting_criterion的屬性頻次值依次與root.ave進(jìn)行比較，然后轉(zhuǎn)步驟(6)；

(6)由節(jié)點(diǎn)root長(zhǎng)出一個(gè)條件為d.value與root.ave比較后的分枝(例如d.value > root.ave創(chuàng)建左分枝)，然后轉(zhuǎn)步驟(7)；

(7)設(shè)n是D中按照root.ave分枝后的數(shù)據(jù)集合。ifn為null then節(jié)點(diǎn)root下增加一個(gè)葉子節(jié)點(diǎn)child,child.value=null,child.tag=vote(n),這里vote(n)是頻次多數(shù)表決函數(shù)，取最普遍的索引標(biāo)志賦值給child.tag，跳轉(zhuǎn)步驟(9)，否則轉(zhuǎn)步驟(10)；

(8)增加一個(gè)由generate_decision_tree(n,attribute_list-splitting_criterion)返回的節(jié)點(diǎn)(子樹)//遞歸調(diào)用，并在attribute_list中刪除已分裂的屬性；

(9)end for；

(10)返回root。

3.3 基于索引屬性決策樹構(gòu)建子空間索引

為構(gòu)建子空間上子空間索引表，首先需要構(gòu)建如表2所示的子空間索引屬性初始數(shù)據(jù)集。然后根據(jù)索引決策樹分析，索引屬性初始數(shù)據(jù)集中各屬性是否需要建立索引。最后得到需要建立索引的所有屬性的集合，然后根據(jù)該集合中的屬性分別建立索引。

4 實(shí)驗(yàn)步驟和結(jié)果

4.1 實(shí)驗(yàn)數(shù)據(jù)流

本實(shí)驗(yàn)采用Hadoop2.0平臺(tái)以及hive，sqoop等相關(guān)插件，另外數(shù)據(jù)展示庫(kù)為Oracle數(shù)據(jù)庫(kù)，數(shù)據(jù)的處理時(shí)序圖如圖2所示。

圖2 數(shù)據(jù)流程圖

4.2 數(shù)據(jù)集及處理

實(shí)驗(yàn)所采用的數(shù)據(jù)集來自開源社區(qū)某通信行業(yè)的真實(shí)數(shù)據(jù)，共有643張表?，F(xiàn)先將643張表結(jié)構(gòu)用腳本導(dǎo)入hive中，存入HDFS，然后再編制腳本將各節(jié)點(diǎn)的第一屬性列和表與表之間的非第一屬性列信息和字段關(guān)聯(lián)信息統(tǒng)計(jì)入庫(kù)到臨時(shí)表中并通過sqoop導(dǎo)出至oracle展示庫(kù)。屬性列詳情如圖3所示。圖中INDEX_NAME為每張表的第一屬性列，TABLE_NAME為表名。

圖3 屬性列詳情圖

4.3 決策樹訓(xùn)練

為構(gòu)建決策樹，需要獲取子空間中實(shí)際的數(shù)據(jù)庫(kù)表以及對(duì)應(yīng)的索引數(shù)據(jù)。本文收集了200張表，獲取這些表的索引信息和屬性列相關(guān)信息，進(jìn)行主屬性列和非主屬性列的頻次統(tǒng)計(jì)和匯總，得到如圖4所示的屬性列頻次統(tǒng)計(jì)表，表中分別存入屬性列，作為主屬性列的出現(xiàn)頻次，作為非主屬性列的出現(xiàn)頻次，以及已知的索引標(biāo)志。

圖4 索引屬性數(shù)據(jù)訓(xùn)練集

再運(yùn)用上述決策樹構(gòu)建算法對(duì)已有的屬性數(shù)據(jù)訓(xùn)練集進(jìn)行分析并建立決策樹模型，圖5為通過決策樹分類對(duì)主屬性列和非主屬性列分別分類，構(gòu)建決策樹。

圖5 決策樹

決策樹建立完成后，將632張表類比表2進(jìn)行頻次統(tǒng)計(jì)和匯總，如圖6所示，表中分別存入屬性列，INDEX_SUM作為主屬性列的出現(xiàn)頻次，COL_SUM作為非主屬性列的出現(xiàn)頻次。

圖6 索引屬性初始數(shù)據(jù)集

將圖6已統(tǒng)計(jì)完成的索引屬性初始數(shù)據(jù)集帶入圖5生成的決策樹中，最終得到相應(yīng)的索引屬性結(jié)果集，如圖7所示。

圖7 索引屬性結(jié)果集

4.4 實(shí)驗(yàn)結(jié)果

從索引屬性結(jié)果集中可得出對(duì)于DAY_ID, DAY_KEY, DT, USERCODE，PROVNAME等字段無論對(duì)于主鍵索引頻次還是字段關(guān)聯(lián)頻次都有較高的值且索引標(biāo)志為“是”，那么在這個(gè)字段上建立索引是最優(yōu)索引，而對(duì)于BINDTYPE，OSINDEX等字段，主鍵索引頻次和字段關(guān)聯(lián)頻次都偏低且索引標(biāo)志為“否”，那么這類字段是沒有必要建立索引的。然后與原始索引表進(jìn)行對(duì)比，準(zhǔn)確率達(dá)90%，有個(gè)別字段沒有建立索引，通過驗(yàn)證，證明了索引決策樹對(duì)于建立索引的作用。

5 結(jié)束語

由于互聯(lián)網(wǎng)和云計(jì)算技術(shù)的飛速發(fā)展，涉及的數(shù)據(jù)量急劇增加，海量數(shù)據(jù)的索引優(yōu)化是大數(shù)據(jù)中值得深入研究并解決的問題，而基于決策樹分類算法的索引優(yōu)化方法下，可以有效地預(yù)測(cè)出大量的表中字段是否可以建立索引，通過對(duì)各個(gè)子空間的表字段進(jìn)行處理，得到索引表數(shù)據(jù)，根據(jù)這一數(shù)據(jù)去建立索引，不僅節(jié)省了數(shù)據(jù)庫(kù)空間資源，同時(shí)可以根據(jù)全局索引和局部索引的二級(jí)索引結(jié)構(gòu)，快速定位索引信息，這樣也節(jié)省了索引查找時(shí)間。但本文在構(gòu)建決策樹時(shí)，只考慮了主屬性與非主屬性出現(xiàn)的頻次，所以在創(chuàng)建索引上可能不夠精確。在后續(xù)研究中，擬考慮加入子空間各個(gè)表的大小、屬性列的取值分散度等決策屬性來提高準(zhǔn)確率，提高索引優(yōu)化效率。

[1] Meng Xiaofeng.From database to dataspace, from the service to enterprises to serve the public[R].Beijing:Renmin University of China,2009.

[2] Paolo Giardullo.Does ‘bigger’ mean‘better’? Pitfalls and shortcuts associated with big data for social research[J].Quality&Quantity,2016,50(2):529-547.

[3] Franklin M, Halevy A,Maier D.From databases to dataspaces:a new abstraction for information management[J].ACM SIGMOD Record,2005,34(4):27-33.

[4] Halevy A,Franklin M,Maier D.Principles of dataspace systems[C].Chicago,USA:Proceedings of the 25th ACM Sigmod-Sigactsigart Symposium on Principles of Database Systems(PODS’06),2006.

[5] Nafaa Jabeur,Sherali Zeadally,Biju Sayed.Mobile social networks applications[J].Communications of the ACM,2013,56(3):74-79.

[6] Benjamin Shapiro R,Pilar N Ossorio.Regulation of online social network studies[J].Science,2013(339):144-145.

[7] Quinlan J R.Induction of decsion tree[J].Machine Learning,1986(7):81-106.

[8] 宋寶燕,劉字,丁琳琳.大數(shù)據(jù)環(huán)境下一種基于可變網(wǎng)格的高維數(shù)據(jù)索引[J].計(jì)算機(jī)與數(shù)字工程,2015,312(43):1717-1728.

[9] 管天云,侯春華.大數(shù)據(jù)技術(shù)在智能管道海量數(shù)據(jù)分析與挖掘中的應(yīng)用[J].現(xiàn)代電信科技,2014(Z1):59-62.

[10] Tan M.Cost-sensitive learning of classification knowledge and its applications in robotics[J].Machine Learning,1993,13(1):1-33.

[11] Breslow L A,Aha W.David simplifying decision tree:a survey[J].Knowledge Engineering Review,1997,12(1):1-40.

[12] Arno J,Knobbe,Siebes A,et al.Multi-relational decision tree induction[C]. Prague:Proceedings of the Third European Conference on Principles of Data Mining and Knowledge Discovery,1999.

[13] Mehenni T,Moussaoui A.Data mining from multiple heterogeneous relational databases using decision tree classification[J].Pattern Recognition Letters,2012,33(13):1768-1775.

[14] Quinlan J R.C4.5:Programs for machine learning[M].Morgan Kauffna,1993(8):23-30.

[15] Agrawal R,Lmielinshi T,Swmi A.Database mining:a performance perspective[J].IEEE Transactions on Knowledge and Engineering,1993,5(6):914-925.