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

關鍵詞： Web服務；關聯(lián)規(guī)則；并行數(shù)據(jù)挖據(jù)；動態(tài)數(shù)據(jù)集

中圖分類號：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 引 言

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

2 Web Service簡介

2.1 Web Service技術

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

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

2.2 Web Service的結構

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

3 關聯(lián)規(guī)則并行數(shù)據(jù)挖掘

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

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

3.1 分布式關聯(lián)規(guī)則挖掘算法[CD2]CD算法

關聯(lián)規(guī)則挖掘問題就是發(fā)現(xiàn)具有用戶指定的最小支持度（minsup）和最小置信度（minconf）的關聯(lián)規(guī)則。該問題可以分解為2個子問題：

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

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

3.2 基于動態(tài)數(shù)據(jù)集劃分的并行挖掘算法

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

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

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

4 系統(tǒng)設計

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

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



//生成本地代理對象

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

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

//用多線程發(fā)送數(shù)據(jù)

AsyncCallback1 = new AsyncCallback(CallBack)；

AsyncCallback2 = new AsyncCallback(CallBack1)；

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

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

private void CallBack(IAsyncResult assignHandle) [JY]//回調(diào)函數(shù)1

{

startIndex += number；

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

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

}

private void CallBack1(IAsyncResult assignHandle)[JY]//回調(diào)函數(shù)2

{

startIndex += number；

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

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

}

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

5 實例分析

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

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

6 結 語

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

參 考 文 獻

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

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

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

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

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

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