基于特征加權(quán)的分布式大數(shù)據(jù)相關(guān)性挖掘方法

戴惠麗，王敬宇

(1. 閩南科技學(xué)院，福建泉州362332；2. 北京郵電大學(xué)，北京 100876)

1 引言

數(shù)據(jù)挖掘是一種通過數(shù)據(jù)計(jì)算來發(fā)現(xiàn)數(shù)據(jù)內(nèi)部潛在規(guī)律和特征的過程，是目前人工智能和數(shù)據(jù)庫建設(shè)領(lǐng)域的研究熱點(diǎn)[1，2]。數(shù)據(jù)挖掘技術(shù)的發(fā)展也帶來了很多新的問題和挑戰(zhàn)，在海量數(shù)據(jù)背景下，對于數(shù)據(jù)挖掘技術(shù)的要求已經(jīng)不僅僅滿足于數(shù)據(jù)相關(guān)性挖掘的準(zhǔn)確性，還需要保證數(shù)據(jù)相關(guān)性挖掘的效率與實(shí)際效果。為此，相關(guān)學(xué)者對數(shù)據(jù)相關(guān)性挖掘方法進(jìn)行深入研究。

米捷和劉道華[3]提出基于語義關(guān)聯(lián)性特征融合的大數(shù)據(jù)挖掘方法，對高位相空間進(jìn)行重構(gòu)，在重構(gòu)空間中提取數(shù)據(jù)語義關(guān)聯(lián)特征，并進(jìn)行其進(jìn)行自適應(yīng)訓(xùn)練，得到訓(xùn)練后的測試集。運(yùn)用模糊C均值算法融合處理數(shù)據(jù)的關(guān)聯(lián)特征，實(shí)現(xiàn)數(shù)據(jù)挖掘的目的。實(shí)驗(yàn)結(jié)果表明，該方法具有數(shù)據(jù)挖掘準(zhǔn)確率較高的優(yōu)勢，但是在面向海量數(shù)據(jù)源時，不能對任務(wù)進(jìn)行快速分配，存在數(shù)據(jù)相關(guān)性挖掘時間較長的問題。毛曉菊[4]提出基于模糊關(guān)聯(lián)規(guī)則的海量數(shù)據(jù)挖掘方法，依據(jù)模糊理論對海量數(shù)據(jù)進(jìn)行模糊化處理，組建數(shù)據(jù)庫，對其中的數(shù)據(jù)進(jìn)行聚類與離散化處理，根據(jù)關(guān)聯(lián)規(guī)則實(shí)現(xiàn)海量數(shù)據(jù)挖掘。實(shí)驗(yàn)結(jié)果表明，該方法能夠有效降低數(shù)據(jù)挖掘所占內(nèi)存，并且數(shù)據(jù)挖掘的支持度較高，但是由于各個節(jié)點(diǎn)之間的任務(wù)是隨機(jī)分配的，使得不同節(jié)點(diǎn)之間的計(jì)算時間差別較大，進(jìn)而導(dǎo)致整體挖掘時間較長，挖掘效率不高。孫紅和李存進(jìn)[5]提出融合遺傳算法和關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘改進(jìn)方法，將改進(jìn)的遺傳算法融入到關(guān)聯(lián)規(guī)則中，基于遺傳算法的全局搜索能力，實(shí)現(xiàn)數(shù)據(jù)挖掘效率的提升，同時，融入親密度原理提高數(shù)據(jù)挖掘的可靠性。實(shí)驗(yàn)結(jié)果表明，該方法具有較高的魯棒性，但是任務(wù)分配均勻程度較差，在一定程度上影響了挖掘方法的整體性能。

針對傳統(tǒng)方法存在的問題，設(shè)計(jì)一種基于特征加權(quán)的分布式大數(shù)據(jù)相關(guān)性挖掘方法。該方法通過軟子空間聚類，獲取加權(quán)聚類中心與權(quán)值。在此基礎(chǔ)上，通過MapReduce編程模型，對每個數(shù)據(jù)簇的聚類中心進(jìn)行反復(fù)掃描，確定對應(yīng)的子集，計(jì)算樣本到聚類中心的距離，并在此過程中去除孤立點(diǎn)，解決了傳統(tǒng)挖掘方法總體收斂速度較低的問題，從而提高了數(shù)據(jù)相關(guān)性的挖掘效率。

2 基于特征加權(quán)的分布式大數(shù)據(jù)相關(guān)性挖掘

2.1 軟子空間聚類

為了提升數(shù)據(jù)處理的高效性，將批量處理聚類算法與同增量學(xué)習(xí)策略相結(jié)合，提出子空間聚類算法。子空間聚類算法主要是依據(jù)數(shù)據(jù)的原始特征空間，將其進(jìn)行分割從而得到不同特征子集。子空間的聚類實(shí)際上是在線學(xué)習(xí)的一種策略，為人們提供了很好的大規(guī)模數(shù)據(jù)處理方式。在線學(xué)習(xí)具體可以分為“硬”競爭學(xué)習(xí)和“軟”競爭學(xué)習(xí)，學(xué)習(xí)的過程中，WTA(Winner Take All)競爭學(xué)習(xí)理論規(guī)則針對數(shù)據(jù)集中新輸入樣本的獲勝節(jié)點(diǎn)只有一個，其聚類的中心遞歸方程可以表示為

vi*(t)=vi*(t-1)-η(t)×D(vi*(t-1)，xNt)

(1)

其中

i*=arg mind(vi(t-1)，xNt)

(2)

式中，vi(t-1)表示聚類中心；xNt表示數(shù)據(jù)樣本；d(vi(t-1)，xNt)表示聚類中心和數(shù)據(jù)樣本之間的距離；D(vi*(t-1)，xNt)表示度量間距；η表示學(xué)習(xí)速率，該速率會隨著時間的延長而逐漸減少，引入該參數(shù)的主要目的是為了防止目標(biāo)接觸出現(xiàn)震蕩，并保證算法的收斂。由于目前的軟子空間聚類都是基于單個目標(biāo)函數(shù)對聚類評價(jià)準(zhǔn)則進(jìn)行優(yōu)化，而聚類算法的真正目的是尋找數(shù)據(jù)內(nèi)部的潛在結(jié)構(gòu)或規(guī)律，按照這種潛在的相似性程度對數(shù)據(jù)樣本進(jìn)行聚類劃分，使經(jīng)過劃分后得到的數(shù)據(jù)簇類內(nèi)部更加緊致，而類間更加分離[6]。從某種意義上說，所提出的在線軟子空間聚類算法是基于“軟”競爭學(xué)習(xí)理論，將軟子空間內(nèi)高維度、大規(guī)模的數(shù)據(jù)進(jìn)行分割，得到若干個數(shù)據(jù)子塊，子塊的大小是由內(nèi)存和數(shù)據(jù)流速度所決定的，將子塊的相關(guān)統(tǒng)計(jì)信息進(jìn)行處理，形成加權(quán)聚類中心，并利用隸屬度函數(shù)求解出聚類中心的權(quán)值。

2.2 選擇特征加權(quán)

根據(jù)軟子空間內(nèi)數(shù)據(jù)的聚類結(jié)果，進(jìn)行特征加權(quán)選擇。特征加權(quán)選擇是機(jī)器學(xué)習(xí)與數(shù)據(jù)相關(guān)性挖掘研究中的經(jīng)典問題，隨著高維特征和大規(guī)模數(shù)據(jù)的出現(xiàn)，對于特征加權(quán)選擇來說，精度已經(jīng)不能滿足實(shí)際的需求，因此，需要對其進(jìn)行綜合化和多樣化的改進(jìn)[7]。通過對大量的特征加權(quán)選擇方法進(jìn)行分析后，得到特征加權(quán)選擇技術(shù)框架，如下圖1所示。

圖1 特征選擇技術(shù)框架

根據(jù)圖1可知，在特征選擇的過程中，從原始特征集合中，依據(jù)一定的規(guī)律或規(guī)則生成的某些特征子集，可以稱之為生成策略；通過評價(jià)準(zhǔn)則對特征子集的相關(guān)性進(jìn)行評價(jià)，從而判斷生成的特征子集是否合理[8]；停止條件主要判斷特征子集是否符合起始定義的要求，在結(jié)論驗(yàn)證中需要驗(yàn)證相關(guān)特征子集的有效性。

在特征選擇方法中存在很多選擇性，隨著特征選擇技術(shù)向機(jī)器學(xué)習(xí)方面的擴(kuò)展，可以選擇不同的學(xué)習(xí)算法對數(shù)據(jù)庫的樣本進(jìn)行特征挑選，以便選出比較合理的特征子集。再根據(jù)數(shù)據(jù)庫中訓(xùn)練數(shù)據(jù)集的標(biāo)記使用情況，將特征加權(quán)選擇算法進(jìn)行進(jìn)一步劃分[9]。一般情況下，其可以劃分為有監(jiān)督、無監(jiān)督和半監(jiān)督三種算法，這三種不同類型的算法區(qū)別在于使用數(shù)據(jù)時，對于數(shù)據(jù)的處理側(cè)重點(diǎn)不相同?？紤]到本文研究的實(shí)際情況，選擇了過濾型方法，這是因?yàn)槠湓u價(jià)標(biāo)準(zhǔn)并不會過分依賴于分類器，而是更加依賴于數(shù)據(jù)特征本身攜帶的信息和規(guī)則。

在特征選擇過程中，將信息和規(guī)則視為互相獨(dú)立的存在，并通過某種搜索策略，將合理的特征子集選擇出來，將訓(xùn)練集與全部特征進(jìn)行輸入，根據(jù)數(shù)據(jù)集本身各個特征的評價(jià)標(biāo)準(zhǔn)來構(gòu)建相應(yīng)的特征子集[10]。通過特征空間搜索機(jī)制得到特征子集與特征評價(jià)標(biāo)準(zhǔn)，并將特征評價(jià)結(jié)果輸入到特征空間搜索機(jī)制中，由此得到訓(xùn)練集、特征子集和測試集，共同構(gòu)成數(shù)據(jù)特征。

2.3 設(shè)計(jì)分布式大數(shù)據(jù)相關(guān)性挖掘方案

由于數(shù)據(jù)的復(fù)雜性不斷提高，大數(shù)據(jù)相關(guān)性挖掘的難度也在不斷加大，傳統(tǒng)相關(guān)性挖掘算法在有效的時間內(nèi)無法提供準(zhǔn)確的計(jì)算結(jié)果[11]。目前，云計(jì)算的飛速發(fā)展為數(shù)據(jù)相關(guān)性挖掘提供了一定的優(yōu)勢，對于分布式大數(shù)據(jù)來說，云計(jì)算平臺的分布式存儲、分布式計(jì)算和數(shù)據(jù)的融合處理，在相關(guān)性挖掘的過程中會將計(jì)算任務(wù)進(jìn)行分配，保證海量數(shù)據(jù)在較短的時間內(nèi)完成計(jì)算，并保證其計(jì)算過程的擴(kuò)展性。

在傳統(tǒng)的分布式大數(shù)據(jù)相關(guān)性挖掘過程中，任務(wù)的分配機(jī)制為隨機(jī)分配，沒有考慮不同任務(wù)的計(jì)算量差異。在初始化階段，對整個數(shù)據(jù)集進(jìn)行隨機(jī)抽樣，在迭代階段選擇合適的聚類中心，并替代當(dāng)前幾何中表現(xiàn)不好的樣本點(diǎn)。這樣一來就會導(dǎo)致各個節(jié)點(diǎn)之間的計(jì)算時間相差較大，降低挖掘方法的總體收斂速度。因此，本文在設(shè)計(jì)分布式大數(shù)據(jù)相關(guān)性挖掘方案時，主要依托MapReduce編程模型，對每個數(shù)據(jù)簇的聚類中心進(jìn)行反復(fù)掃描，確定對應(yīng)子集，并在子集上計(jì)算樣本到聚類中心的距離，在去除孤立點(diǎn)的同時進(jìn)行重新劃分，并對算法的并行化進(jìn)行設(shè)計(jì)[12]。

由于設(shè)計(jì)的相關(guān)性挖掘算法是針對分布式大數(shù)據(jù)而言的，首先數(shù)據(jù)是分布式存儲的，數(shù)據(jù)經(jīng)過預(yù)處理之后執(zhí)行后續(xù)的分布式算法，經(jīng)過頻繁項(xiàng)集計(jì)算后，MapReduce任務(wù)會通過某數(shù)據(jù)集掃描實(shí)現(xiàn)所有項(xiàng)，并執(zhí)行并行化的數(shù)據(jù)統(tǒng)計(jì)，數(shù)據(jù)重新排列并分割，通過后綴模式的轉(zhuǎn)換將原始的數(shù)據(jù)分割節(jié)點(diǎn)獨(dú)立計(jì)算，形成子事務(wù)幾何。主要作用是獨(dú)立進(jìn)行數(shù)據(jù)的相關(guān)性挖掘，并保證結(jié)果的準(zhǔn)確性，得到計(jì)算量的估值與分組，再次經(jīng)過局部計(jì)算，最后得到匯聚結(jié)果。算法的示意圖如圖2所示。

圖2 分布式大數(shù)據(jù)相關(guān)性挖掘步驟

圖2中，當(dāng)分布式計(jì)算中的數(shù)據(jù)成為子數(shù)據(jù)集后，HDFS文件系統(tǒng)在Hadoop平臺中以64M為單位給節(jié)點(diǎn)分配數(shù)據(jù)，并通過合并較小的數(shù)據(jù)提高存儲效率。確定Map的任務(wù)量之后將其輸出，輸出內(nèi)容是后續(xù)程序的數(shù)據(jù)輸入值。所提相關(guān)性挖掘方案的改進(jìn)重點(diǎn)就是分配機(jī)制的改進(jìn)，受Hadoop的Shuffle均衡分組機(jī)制的影響，數(shù)據(jù)挖中的各個節(jié)點(diǎn)都會收到不同的事務(wù)分組，在這種均衡機(jī)制下，多個分組將依次有序輸入。當(dāng)新輸入事務(wù)的key發(fā)生變化時，對已建立的FP樹進(jìn)行條件FP樹挖掘，計(jì)算完成后獲得其頻繁項(xiàng)集，并清空FP樹，開始新項(xiàng)的FP樹建立及頻繁項(xiàng)集挖掘，直至完成所有頻繁項(xiàng)集的挖掘。至此完成基于特征加權(quán)的分布式大數(shù)據(jù)相關(guān)性挖掘方法設(shè)計(jì)。

3 實(shí)驗(yàn)分析

為了驗(yàn)證設(shè)計(jì)的基于特征加權(quán)的分布式大數(shù)據(jù)相關(guān)性挖掘方法在大數(shù)據(jù)挖掘中的性能表現(xiàn)，需要將設(shè)計(jì)的挖掘方法與傳統(tǒng)基于語義關(guān)聯(lián)性特征融合的大數(shù)據(jù)挖掘方法(文獻(xiàn)[3]方法)、基于模糊關(guān)聯(lián)規(guī)則的海量數(shù)據(jù)挖掘方法(文獻(xiàn)[4]方法)以及融合遺傳算法和關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘改進(jìn)方法(文獻(xiàn)[5]方法)進(jìn)行比較。

3.1 實(shí)驗(yàn)環(huán)境與參數(shù)設(shè)置

首先對實(shí)驗(yàn)環(huán)境參數(shù)進(jìn)行設(shè)置，參數(shù)與變量定義如下表1所示：

表1 實(shí)驗(yàn)環(huán)境參數(shù)

實(shí)驗(yàn)集群選擇的是9臺高性能的計(jì)算機(jī)，其中包含1臺管理節(jié)點(diǎn)，8臺計(jì)算子節(jié)點(diǎn)，以上實(shí)驗(yàn)集群的相關(guān)節(jié)點(diǎn)中，其配置均為4GB內(nèi)存，Intel CoreTM i7-3770 CPU@3.40GHz型號CPU，主板為Intel Q77，操作系統(tǒng)為Ubuntu 14.04，Hadoop發(fā)行版本為0.23。在本次實(shí)驗(yàn)中，采用的是公共數(shù)據(jù)源，并將此數(shù)據(jù)源擴(kuò)展至事物數(shù)為105，2×105，4×105，8×105四個級別的測試數(shù)據(jù)集中，將這四個數(shù)據(jù)集記作D1、D2、D3、D4，選擇四個數(shù)據(jù)集的D1數(shù)據(jù)集進(jìn)行詳細(xì)數(shù)據(jù)頻次分析，分布情況如下圖3所示：

圖3 數(shù)據(jù)集D1中事物項(xiàng)的頻次分布情況

對以上四個數(shù)據(jù)集進(jìn)行特征統(tǒng)計(jì)，得到事務(wù)數(shù)據(jù)集特征統(tǒng)計(jì)結(jié)果如下表2所示：

表2 事務(wù)數(shù)據(jù)集的特征統(tǒng)計(jì)信息

在上述實(shí)驗(yàn)環(huán)境設(shè)置條件下，對設(shè)計(jì)的數(shù)據(jù)挖掘方法和傳統(tǒng)數(shù)據(jù)挖掘方法進(jìn)行實(shí)驗(yàn)，并對實(shí)驗(yàn)結(jié)果進(jìn)行分析和研究。

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

1)數(shù)據(jù)挖掘計(jì)算時間對比

為了直觀看出不同挖掘方法的性能，統(tǒng)計(jì)了在同等配置下不同數(shù)據(jù)挖掘算法對不同節(jié)點(diǎn)的計(jì)算時間，結(jié)果如下圖4所示：

圖4 不同方法對不同節(jié)點(diǎn)的計(jì)算時間差異

圖4中，橫軸表示的是不同的計(jì)算節(jié)點(diǎn)，縱軸表示的是計(jì)算時間。從圖中能夠明顯看出不同挖掘方法在相同配置下對不同計(jì)算節(jié)點(diǎn)計(jì)算時間的差異。由于傳統(tǒng)數(shù)據(jù)挖掘方法采用的隨機(jī)任務(wù)分配機(jī)制使得不同節(jié)點(diǎn)之間的計(jì)算時間差別較大，而并行任務(wù)的完成時間是由節(jié)點(diǎn)中的最大完成時間決定的，這在一定程度上使挖掘方法的效率有所降低。而設(shè)計(jì)的基于特征加權(quán)的分布式大數(shù)據(jù)相關(guān)性挖掘方法，能夠利用各個分組的任務(wù)計(jì)算量對信息進(jìn)行預(yù)估，從而完成任務(wù)均衡分配，使得各個節(jié)點(diǎn)的任務(wù)計(jì)算時間基本穩(wěn)定在5-10s之間。并且所設(shè)計(jì)方法的計(jì)算時間明顯低于傳統(tǒng)方法，說明該方法的數(shù)據(jù)相關(guān)性挖掘效率更高。

2)任務(wù)分配均勻度對比

為了明確分布式數(shù)據(jù)各個節(jié)點(diǎn)的任務(wù)分配均勻程度，可以通過下式進(jìn)行計(jì)算

(3)

利用式(3)計(jì)算不同方法的節(jié)點(diǎn)任務(wù)分配均勻程度，結(jié)果如圖5所示。

圖5 不同方法節(jié)點(diǎn)任務(wù)分配均勻程度對比

分析圖5可知，當(dāng)測試時間低于10s時，不同方法的節(jié)點(diǎn)任務(wù)分配均勻程度呈現(xiàn)出持續(xù)增長的趨勢，隨后變化趨勢趨于平緩。對比傳統(tǒng)方法與所設(shè)計(jì)方法可知，所設(shè)計(jì)方法的任務(wù)分配均衡系數(shù)明顯高于傳統(tǒng)方法，其均衡系數(shù)最高值接近1.0，說明該方法能夠?qū)崿F(xiàn)對節(jié)點(diǎn)任務(wù)的均勻分配。

綜上實(shí)驗(yàn)結(jié)果可知，由于傳統(tǒng)方法中任務(wù)為隨機(jī)分配，并不存在任務(wù)量的計(jì)算，因此在支持度閾值較小的情況下，計(jì)算任務(wù)量比較大，時間標(biāo)準(zhǔn)差也比較大；當(dāng)支持度的閾值增大后，標(biāo)準(zhǔn)差逐漸降低，

說明傳統(tǒng)方法的效率受支持度的閾值影響較大。根據(jù)最終的對比結(jié)果顯示，所設(shè)計(jì)方法在分布式大數(shù)據(jù)相關(guān)性挖掘過程中的計(jì)算時間與任務(wù)分配均衡性均優(yōu)于傳統(tǒng)方法，說明該方法具有一定的優(yōu)勢性，更適合應(yīng)用于數(shù)據(jù)挖掘領(lǐng)域。

4 結(jié)束語

為了解決傳統(tǒng)方法計(jì)算時間較長，任務(wù)分配均勻程度較差的問題，研究了基于特征加權(quán)的相關(guān)性挖掘方法，針對傳統(tǒng)方法在挖掘過程中存在的弊端，進(jìn)行了一系列的改進(jìn)優(yōu)化，重新設(shè)計(jì)了相關(guān)性挖掘的方案，優(yōu)化了任務(wù)分配機(jī)制，提高了相關(guān)性挖掘方法的效率。通過實(shí)驗(yàn)驗(yàn)證，所設(shè)計(jì)方法在挖掘效率與任務(wù)分配方面均具有明顯的優(yōu)勢，說明該方法具有可行性。

大數(shù)據(jù)相關(guān)性挖掘是一個新興的研究領(lǐng)域，互聯(lián)網(wǎng)時代的數(shù)據(jù)快速膨脹，使數(shù)據(jù)挖掘的意義逐漸凸顯出來，在數(shù)據(jù)挖掘方法中對各個節(jié)點(diǎn)的負(fù)載進(jìn)行均衡分配，能夠?qū)崿F(xiàn)挖掘效率的最優(yōu)化。