基于特征加權的分布式大數據相關性挖掘方法

戴惠麗，王敬宇

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

1 引言

數據挖掘是一種通過數據計算來發現數據內部潛在規律和特征的過程，是目前人工智能和數據庫建設領域的研究熱點[1，2]。數據挖掘技術的發展也帶來了很多新的問題和挑戰，在海量數據背景下，對于數據挖掘技術的要求已經不僅僅滿足于數據相關性挖掘的準確性，還需要保證數據相關性挖掘的效率與實際效果。為此，相關學者對數據相關性挖掘方法進行深入研究。

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

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

2 基于特征加權的分布式大數據相關性挖掘

2.1 軟子空間聚類

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

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

(1)

其中

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

(2)

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

2.2 選擇特征加權

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

圖1 特征選擇技術框架

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

在特征選擇方法中存在很多選擇性，隨著特征選擇技術向機器學習方面的擴展，可以選擇不同的學習算法對數據庫的樣本進行特征挑選，以便選出比較合理的特征子集。再根據數據庫中訓練數據集的標記使用情況，將特征加權選擇算法進行進一步劃分[9]。一般情況下，其可以劃分為有監督、無監督和半監督三種算法，這三種不同類型的算法區別在于使用數據時，對于數據的處理側重點不相同。考慮到本文研究的實際情況，選擇了過濾型方法，這是因為其評價標準并不會過分依賴于分類器，而是更加依賴于數據特征本身攜帶的信息和規則。

在特征選擇過程中，將信息和規則視為互相獨立的存在，并通過某種搜索策略，將合理的特征子集選擇出來，將訓練集與全部特征進行輸入，根據數據集本身各個特征的評價標準來構建相應的特征子集[10]。通過特征空間搜索機制得到特征子集與特征評價標準，并將特征評價結果輸入到特征空間搜索機制中，由此得到訓練集、特征子集和測試集，共同構成數據特征。

2.3 設計分布式大數據相關性挖掘方案

由于數據的復雜性不斷提高，大數據相關性挖掘的難度也在不斷加大，傳統相關性挖掘算法在有效的時間內無法提供準確的計算結果[11]。目前，云計算的飛速發展為數據相關性挖掘提供了一定的優勢，對于分布式大數據來說，云計算平臺的分布式存儲、分布式計算和數據的融合處理，在相關性挖掘的過程中會將計算任務進行分配，保證海量數據在較短的時間內完成計算，并保證其計算過程的擴展性。

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

由于設計的相關性挖掘算法是針對分布式大數據而言的，首先數據是分布式存儲的，數據經過預處理之后執行后續的分布式算法，經過頻繁項集計算后，MapReduce任務會通過某數據集掃描實現所有項，并執行并行化的數據統計，數據重新排列并分割，通過后綴模式的轉換將原始的數據分割節點獨立計算，形成子事務幾何。主要作用是獨立進行數據的相關性挖掘，并保證結果的準確性，得到計算量的估值與分組，再次經過局部計算，最后得到匯聚結果。算法的示意圖如圖2所示。

圖2 分布式大數據相關性挖掘步驟

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

3 實驗分析

為了驗證設計的基于特征加權的分布式大數據相關性挖掘方法在大數據挖掘中的性能表現，需要將設計的挖掘方法與傳統基于語義關聯性特征融合的大數據挖掘方法(文獻[3]方法)、基于模糊關聯規則的海量數據挖掘方法(文獻[4]方法)以及融合遺傳算法和關聯規則的數據挖掘改進方法(文獻[5]方法)進行比較。

3.1 實驗環境與參數設置

首先對實驗環境參數進行設置，參數與變量定義如下表1所示：

表1 實驗環境參數

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

圖3 數據集D1中事物項的頻次分布情況

對以上四個數據集進行特征統計，得到事務數據集特征統計結果如下表2所示：

表2 事務數據集的特征統計信息

在上述實驗環境設置條件下，對設計的數據挖掘方法和傳統數據挖掘方法進行實驗，并對實驗結果進行分析和研究。

3.2 實驗結果與分析

1)數據挖掘計算時間對比

為了直觀看出不同挖掘方法的性能，統計了在同等配置下不同數據挖掘算法對不同節點的計算時間，結果如下圖4所示：

圖4 不同方法對不同節點的計算時間差異

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

2)任務分配均勻度對比

為了明確分布式數據各個節點的任務分配均勻程度，可以通過下式進行計算

(3)

利用式(3)計算不同方法的節點任務分配均勻程度，結果如圖5所示。

圖5 不同方法節點任務分配均勻程度對比

分析圖5可知，當測試時間低于10s時，不同方法的節點任務分配均勻程度呈現出持續增長的趨勢，隨后變化趨勢趨于平緩。對比傳統方法與所設計方法可知，所設計方法的任務分配均衡系數明顯高于傳統方法，其均衡系數最高值接近1.0，說明該方法能夠實現對節點任務的均勻分配。

綜上實驗結果可知，由于傳統方法中任務為隨機分配，并不存在任務量的計算，因此在支持度閾值較小的情況下，計算任務量比較大，時間標準差也比較大；當支持度的閾值增大后，標準差逐漸降低，

說明傳統方法的效率受支持度的閾值影響較大。根據最終的對比結果顯示，所設計方法在分布式大數據相關性挖掘過程中的計算時間與任務分配均衡性均優于傳統方法，說明該方法具有一定的優勢性，更適合應用于數據挖掘領域。

4 結束語

為了解決傳統方法計算時間較長，任務分配均勻程度較差的問題，研究了基于特征加權的相關性挖掘方法，針對傳統方法在挖掘過程中存在的弊端，進行了一系列的改進優化，重新設計了相關性挖掘的方案，優化了任務分配機制，提高了相關性挖掘方法的效率。通過實驗驗證，所設計方法在挖掘效率與任務分配方面均具有明顯的優勢，說明該方法具有可行性。

大數據相關性挖掘是一個新興的研究領域，互聯網時代的數據快速膨脹，使數據挖掘的意義逐漸凸顯出來，在數據挖掘方法中對各個節點的負載進行均衡分配，能夠實現挖掘效率的最優化。