基于決策樹分類算法異構(gòu)數(shù)據(jù)的索引優(yōu)化

鄭博文，趙逢禹

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

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

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

盡管異構(gòu)數(shù)據(jù)索引的研究取得了許多成果，但還存在一些問題。(1)Song Baoyan提出的VGHI二級異構(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)建索引，但運用R-tree構(gòu)建的索引是通過對索引進(jìn)行范圍劃分，其原理是非葉結(jié)點存儲其所有子結(jié)點的區(qū)域范圍，這種區(qū)域范圍使索引結(jié)構(gòu)較為簡單，在海量數(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)化實驗，根據(jù)構(gòu)建的異構(gòu)數(shù)據(jù)索引提高海量數(shù)據(jù)查詢的性能和可擴展性。

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

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

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

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

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

2.1 索引屬性決策樹的建立

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

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

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

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

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

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

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

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

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

3 算法

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

3.1 基本定義

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

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

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

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

(1)

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

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

(2)

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

(3)

定義5 信息增益是兩個信息量之間的差值，其中一個信息量是需確定T的一個元素的信息量，另一個信息量是已得到的屬性X的值需確定的T一個元素的信息量，信息增益公式[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個，屬于索引標(biāo)志“否”有2個，則通過上述公式(1)分別計算其信息熵

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

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

根據(jù)得到的熵值，可以用式(4)計算第一個根節(jié)點所依賴的信息增益值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ù)計算得到的各候選屬性的信息增益率，選取信息增益率最大的“主屬性列的出現(xiàn)頻次”作為決策樹分裂節(jié)點。

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

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

算法 決策樹生成generate_decision_tree。

輸入

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

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

輸出 一個決策樹。

方法

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

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

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

(4)root.value=splitting_criterion；

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

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

(6)由節(jié)點root長出一個條件為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é)點root下增加一個葉子節(jié)點child,child.value=null,child.tag=vote(n),這里vote(n)是頻次多數(shù)表決函數(shù)，取最普遍的索引標(biāo)志賦值給child.tag，跳轉(zhuǎn)步驟(9)，否則轉(zhuǎn)步驟(10)；

(8)增加一個由generate_decision_tree(n,attribute_list-splitting_criterion)返回的節(jié)點(子樹)//遞歸調(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 實驗步驟和結(jié)果

4.1 實驗數(shù)據(jù)流

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

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

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

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

圖3 屬性列詳情圖

4.3 決策樹訓(xùn)練

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

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

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

圖5 決策樹

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

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

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

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

4.4 實驗結(jié)果

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

5 結(jié)束語

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