基于Ｗｅｂ Ｓｅｒｖｉｃｅ技術分布式并行數據挖掘的研究與實現

摘 要：主要介紹基于Web Service技術的一個數據挖掘系統，在一個關聯規則挖掘的并行算法—CD算法的基礎上，結合一種基于動態數據集劃分的并行關聯規則挖掘算法，利用動態方式分配數據量，使每個處理器獲得相同多的數據集，解決在網絡中大量分散的數據因通信等問題而引起的負載平衡，從而提高了數據挖掘效率。

關鍵詞： Web服務；關聯規則；并行數據挖據；動態數據集

中圖分類號：TP393 文獻標識碼：B

文章編號：1004-373X(2008)10-042-03

Reserch and Realization of Distributed and Parallel Data Mining Based on Web Service

JIN Chunxia1，2，BAI Qiuchan2

(1.Southeast University，Nanjing，223001，China;2.HuaiyinInstituteofTechnology，Huaian，223001，China)

Abstract：The paper gives a distributed data mining system based on Web Services.On the basis ofCD algorithm，the paper presents a parallel algorithm for mining association rules based on dynamic dataset partition.By uning dynamic method to allocate data，a processor can obtain same dataset.Since it solves the load balance better because of the problems of distributed-data and communication，improves the efficiency of data mining.

Keywords：Web service;association rules;parallel data mining;dynamic dataset

1 引 言

隨著計算機在社會各領域的廣泛深入應用，在測繪、商業、金融業等各領域中每天都在產生數量巨大的數據，Internet領域的迅猛發展也使得網絡中的各種信息日益豐富。而這些數據又分布在不同地區。面對大量的GB級、TB級甚至更多的數據，如何處理數量日益增長的數據成為當今數字化社會面臨的一個極具挑戰性的問題。而隨著網絡系統的廣泛應用，分布式數據挖掘日益受到關注，而分布式系統中存在著分布數據和異構性等問題，因此分布式數據挖掘不僅需要解決集中式數據挖掘中的算法時間復雜性問題，還要考慮數據的轉換、站點擴展性以及通信代價等問題。本文針對并行關聯規則挖掘算法不能有效的解決負載平衡，而導致挖掘效率低的問題，在CD算法的基礎上，介紹一種基于動態數據集劃分的并行關聯規則挖掘算法，更好地實現負載平衡，從而提高并行數據挖掘的效率。

2 Web Service簡介

2.1 Web Service技術

Web Service技術是建立可互操作的分布式應用程序的新平臺。他使得各種平臺以各種不同語言和技術開發的分布式計算技術能夠相互協作和交互，供現有的或潛在的客戶以一些標準的方式訪問。他最大特點就是松耦合、跨平臺，這些特點無疑為分布式數據挖掘提供了良好的支持。

利用Web Service技術構建一個數據挖掘系統，其應有以下幾個特點：靈活的數據挖據架構，可以根據不同的應用領域，靈活和快捷地選擇最合適的數據挖據方法和數據挖據算法；具有分布式的軟件架構，能在更大程度上滿足用戶的需求；可以在一定程度上實現分布并行的數據挖掘，提高數據挖掘的效率。同時利用該技術，可以將一個挖掘任務分配到多臺計算機上運行，從而實現并行數據挖掘^[1]。

2.2 Web Service的結構

Web Service是一種面向服務的體系結構，他能夠創建服務的抽象定義、提供服務的具體實現、發布并查找服務、實現服務實例選擇，并實現可互操作服務的使用。Web service體系結構基于3種角色（服務提供者、服務注冊中心和服務請求者）之間的交互。交互涉及發布、查找和綁定操作。服務提供者是提供最終Web Service的供應商，他既是Web Service的擁有者，負責其所擁有服務的發布、更新和回收，又是實現Web Service的平臺；服務提供者定義 Web Service的服務描述并把他發布到服務請求者或服務注冊中心；服務注冊中心是一個Web Service的注冊地，匯集了很多在線的Web Service。一般來說服務提供者將 Web Service安裝到在線服務器后，會將Web Service發布到服務注冊中心^[1]。圖1示出了這些操作、提供這些操作的組件及他們之間的交互。

3 關聯規則并行數據挖掘

并行數據挖掘的體系結構是對傳統的數據挖掘體系結構的擴展，目的是提高數據挖掘的效率。其主要實現3個功能：在劃分的數據子集上進行局部的數據挖掘任務；合并局部數據挖掘的結果；把全局性的結果呈現給用戶^[2]。

其中局部數據挖掘部分負責把數據集劃分成多個數據子集，并分配到多個處理器上，每個處理器上執行相應的數據挖掘任務，并把結果提供給上層。全局數據挖掘部分負責收集局部數據挖掘的結果，并把這些結果合并成全局的統一結果，用戶通過結果表示工具能夠方便地對全局結果進行評價和理解。

3.1 分布式關聯規則挖掘算法[CD2]CD算法

關聯規則挖掘問題就是發現具有用戶指定的最小支持度（minsup）和最小置信度（minconf）的關聯規則。該問題可以分解為2個子問題：

求出滿足最小支持度的所有項目集；檢測滿足最小支持度的項目集是否滿足最小置信度，并生成對應的關聯規則^[3]。

CD算法是在任意水平分區的基礎上進行并行計算，是一種分布式關聯規則挖掘算法。該算法通過分割數據庫完成并行化。如果有N個處理器節點，則各節點將獲得數據庫的1/N，然后分別在各數據庫子集上完成數據挖掘，他類似于Apriori的算法。在第一階段，每個分區獨立地進行數據庫掃描，計算出各個候選集的支持度，然后將各候選集的支持度進行相加得到全局支持度，相加后的支持度若大于minsup則認為該項集是全局的。CD算法在每一次掃描結束后需要一個同步點，然后再進行下一次分區的掃描，而在每一次掃描后CD算法的通訊量復雜性為O（n2）。因為，隨著結點數的增多，CD算法的通訊量將迅速增加。因此在關聯規則并行挖掘算法中，CD算法雖具有較好的性能，但其響應時間是隨事務數量增加而呈線性增加的，因此解決的方案是在CD算法的基礎上進行動態數據劃分。

3.2 基于動態數據集劃分的并行挖掘算法

然而并行算法的關鍵是負載平衡，而影響負載平衡的主要因素是處理器的性能、分配給處理器任務的多少，以及網絡速度等。雖然CD算法使每個處理器獲得相同多的數據集，但因為數據集的稠密程度（即數據集中頻繁集的數目）不同，他們實際上獲得的任務量不一定是相同的，并且也沒有考慮到處理器的性能和網絡速度上的差異。因此必須實時地對處理器的工作情況進行評估，從而動態地決定分配給每個處理器數據的多少，以此實現負載平衡。

對于并行挖掘而言，數據集的傳輸要花費大量的時間。因此，要盡量地減少通信量，最好在第一次數據庫掃描時完成對各個工作節點的評估，并以此為依據將數據集分配到各個處理器。

因而在本算法中，采用集中式的體系結構。一個處理器作為控制處理器專門負責生成全局的候選集和頻繁集，并負責和其他處理器進行信息交互，而其他處理器作為工作處理器，他們之間不存在信息交互。

4 系統設計

利用Web Service構建一個并行挖掘的平臺，Web Service端主要負責數據集的支持度計數，數據挖據客戶端負責數據的預處理、挖據任務的分配和匯總以及挖掘結果的顯示。Web Service并行計算網絡由分布的主機構成，每個主機上都有一個相同的數據挖據子任務處理模塊，他們都以Web Service的形式發布，供Web Service調用者使用。

挖掘任務的分配和匯總模塊是最關鍵的模塊，他的主要任務是負責根據各個數據挖掘Web Service端的計算情況，將數據動態的分配到各個數據挖掘Web Service端，并負責協調各個數據挖掘Web Service端的工作。要同時向多個數據挖掘Web Service端發送數據，必須采用多線程技術以進行異步調用，在這里采用回調來實現，其實例代碼如下：



//生成本地代理對象

ws = new DCD.localhost.DCDws()；

ws1 = new DCD.localhost1.DCDws()；

//用多線程發送數據

AsyncCallback1 = new AsyncCallback(CallBack)；

AsyncCallback2 = new AsyncCallback(CallBack1)；

ws.BeginGetDb(db1，AsyncCallback1，1)；

ws1.BeginGetDb(db2，AsyncCallback2，1)；

private void CallBack(IAsyncResult assignHandle) [JY]//回調函數1

{

startIndex += number；

Array.Copy(db， startIndex， db1， 0， number)；

ws.BeginGetDb(db1，AsyncCallback1，1)； 

}

private void CallBack1(IAsyncResult assignHandle)[JY]//回調函數2

{

startIndex += number；

Array.Copy(db， startIndex， db2， 0， number)；

ws.BeginGetDb(db2，AsyncCallback2，1)； 

}

該實例代碼實現數據挖據客戶端同時向2個數據挖掘Web Service端發送數據的功能。數據挖據客戶端1次向數據挖掘Web Service端發送大小為number的數據。當數據挖據客戶端收到數據挖掘Web Service端反饋的上一次接收的數據已處理完的信號后，便繼續向該數據挖掘Web Service端發送下一個大小為number的數據。這樣便實現了根據數據挖掘Web Service端的處理能力進行數據集的動態分配，以實現負載平衡。

5 實例分析

為了便于檢驗挖掘結果的正確性并能更好地比較算法的性能，該實驗采用的數據是用SQL語句在SQL Server上生成的隨機數據。他的大小分別為16萬行，項的個數都為20。在實驗中將塊的大小設為1 k行。16萬行的實驗結果如圖4所示。

從實驗的結果可以看出，當存在負載不平衡現象時，利用本文提出的算法可使并行挖掘效率有一定程度的提高。

6 結 語

本文提出一種對CD算法進行改進的并行關聯規則挖掘算法。他利用第一次數據庫掃描對影響負載平衡的主要因素進行評估，然后將數據集分配給每個處理器，從而實現負載平衡。然而在本算法中，根據處理器對設定任務的完成時間來對影響負載平衡的主要因素進行評估，在實驗中發現有時他的性能不是很理想，因此更加精確地進行評估將是進一步研究的方向。

參 考 文 獻

［1］柴曉路.Web服務架構與開放互操作技術\\[M\\].北京：清華大學出版社，2002.

［2］葛麗娜，鐘誠.一個有效的分布式并行挖掘關聯規則算法［J］．計算機工程與設計，2004(8):1 258-1 260.

［3］胡吉明，鮮學豐.挖掘關聯規則中Apriori算法的研究與改進\\[J\\].計算機技術與發展，2006，16(4):99-101.

［4］郭玉濱.關聯規則挖掘算法研究\\[J\\].棗莊學院學報，2006，23(2):70-73.

作者簡介 金春霞 女， 1973年出生，陜西咸陽人，淮陰工學院講師，東南大學在讀碩士研究生。研究方向為計算機應用。

白秋產 男，1973年出生，陜西禮泉人，淮陰工學院講師，碩士。研究方向為工業控制。