摘 要:基于多Agent的數(shù)據(jù)挖掘技術，不僅能夠針對不同的Web數(shù)據(jù)綜合采用不同的挖掘算法，而且可以在各站點進行并行挖掘，避免Web通信量過載。在簡述Agent技術和Web數(shù)據(jù)挖掘技術的基礎上，結合多Agent和Web數(shù)據(jù)挖掘，設計出一種新型數(shù)據(jù)挖掘模型，且進一步闡述了該模型，并做了一些分析測試。結果證明，該方法能有效提高Web數(shù)據(jù)挖掘的速度、準確率和覆蓋率，提高了數(shù)據(jù)利用率。

關鍵詞:Web數(shù)據(jù)挖掘; 多Agent; Web數(shù)據(jù); 網(wǎng)絡通信量; 并行挖掘

中圖分類號:TP311文獻標識碼:A

文章編號:1004-373X(2010)08-0083-04

New Method of Web Data Mining Based on Multi-Agent

XIONG Hai-liang， BAI Zhen-xing

(Air Force Engineering Institute， Air Force Engineering University， Xi’an710038， China)

Abstract:The data mining technology based on multi-Agent can perform different mining algorithms to deal with different Web data， and can realize data parallel mining in each platform， to avoid the over loadin of communication capacity. On the basis of summarization of the technologies of Agent and Web data mining， one new model of Web data mining is designed by combining multi-agent and web data mining. The model is elaborated， and some analysis and testing are done. The result indicates that the method can efficiently improve the speed， accuracy and coverage of the Web data mining and raise the data utilization.

Keywords:Web data mining; multi-Agent; web data; Web communication capacity;parallel mining

0 引 言

Web數(shù)據(jù)挖掘具有很重要的意義，即能從大量的信息中發(fā)現(xiàn)用戶感興趣的信息，將Web上的豐富信息轉變成有用的知識。Web數(shù)據(jù)挖掘分為三類:Web內容挖掘、Web訪問信息挖掘和Web結構挖掘等。Agent是人工智能領域發(fā)展起來的新型計算模型，具有功能的連續(xù)性和自主性，即Agent能夠連續(xù)不斷地感知外界發(fā)生以及自身狀態(tài)的變化，并自主產(chǎn)生相應的動作。由于Agent的上述特點，Agent已廣泛用于分布計算環(huán)境，用于協(xié)同計算以完成某項任務。單一挖掘技術的效果往往不令人滿意，以多Agent系統(tǒng)為平臺，通過技術融合，形成一種并行、自主、協(xié)作的挖掘方法，可以收到更好的效果。本文基于Agent和多Agent的上述特點，設計出一種基于多Agent的Web數(shù)據(jù)挖掘新模型，能夠更好、更有效地進行智能Wen數(shù)據(jù)挖掘，而且可以直接在網(wǎng)絡上進行挖掘。由于它具有更好的多Agent系統(tǒng)結構，可使集中和分散的方式相統(tǒng)一，而且采用了移動Agent，故提高了數(shù)據(jù)挖掘的靈活性，避免了Web通信擁塞，提高了Web數(shù)據(jù)挖掘[1]速度、覆蓋率和準確率，能發(fā)現(xiàn)用一般方法所發(fā)現(xiàn)不了的知識，使Web數(shù)據(jù)得到有效利用。

1 Web數(shù)據(jù)挖掘

1.1 數(shù)據(jù)挖掘

數(shù)據(jù)挖掘(Data Mining)是一個從大量數(shù)據(jù)中獲取有效、新穎、潛在有用、最終可理解的模式的非平凡過程。數(shù)據(jù)挖掘的廣義觀點:數(shù)據(jù)挖掘就是從存放在數(shù)據(jù)庫、數(shù)據(jù)倉庫或其他信息庫中大量的數(shù)據(jù)中“挖掘”有趣知識的過程。數(shù)據(jù)挖掘，又稱為數(shù)據(jù)庫中知識發(fā)現(xiàn)，目前數(shù)據(jù)挖掘的研究主要分為Web數(shù)據(jù)挖掘和空間數(shù)據(jù)挖掘，這里主要研究的是Web數(shù)據(jù)挖掘問題。

1.2 Web數(shù)據(jù)挖掘

Web數(shù)據(jù)挖掘[2]就是從大量的、不完全的、有噪聲的、模糊的、隨機的Web數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的，但又是有用的信息和知識的過程。Web挖掘的數(shù)據(jù)來源主要有幾個方面:服務器日志數(shù)據(jù)、在線市場數(shù)據(jù)、Web頁面以及Web頁面超鏈接關系等。因此，Web挖掘可分為三種主要挖掘類型，即Web內容挖掘、Web訪問信息挖掘[3]和Web結構挖掘。

Web在邏輯上是一個由文檔節(jié)點和超鏈接構成的圖。Web數(shù)據(jù)挖掘以提取Web數(shù)據(jù)集中的關聯(lián)規(guī)則、發(fā)現(xiàn)序列模式、生成分類規(guī)則、進行聚類等為主要手段。但由于Web中的大量數(shù)據(jù)都是非結構、半結構和異構的，所以采用單一的數(shù)據(jù)挖掘方法很難實現(xiàn)。傳統(tǒng)的Web數(shù)據(jù)挖掘只能分開進行挖掘，然后進行人工處理，而本文所實現(xiàn)的數(shù)據(jù)挖掘則不需要人為參與，進行綜合Web數(shù)據(jù)挖掘后，可顯示和存儲最終挖掘結果。Web數(shù)據(jù)是一種異構的、分布式的數(shù)據(jù)環(huán)境，Web數(shù)據(jù)源分布在網(wǎng)絡上的各個地方，對Web數(shù)據(jù)的處理必然涉及到大量的遠程操作。在此，希望網(wǎng)絡傳輸少量的數(shù)據(jù)，以減輕網(wǎng)絡壓力。本文很好地解決了此問題。

2 多Agent技術

2.1 Agent概述

Agent及其相關概念和技術的最直接背景是分布式人工智能，其基本思想在20世紀50年代由John.McCarthy提出。目前，已廣泛應用于過程控制、生產(chǎn)制造、信息管理、智能數(shù)據(jù)庫、數(shù)據(jù)挖掘、網(wǎng)絡管理和電子商務等領域。Agent技術[4]是一種新型計算模型，具有高度智能化，易于構造分布式系統(tǒng)，且軟件的復用性強等優(yōu)點，是目前人工智能研究的熱門方向。Agent的兩個主要特征是智能性和代理性。一個完整的Agent概念應該具有這些特征，如:自主性、主動性、持續(xù)性、社交性、反應性、進化性或適應性、可移動性、可靠性和代理性。本文所設計的Agent基本具有這些特征。

2.2 Agent的結構

Agent的基本結構由感知模塊、處理模塊、控制模塊、執(zhí)行模塊、通信模塊和方法集組成。感知模塊、通信模塊、執(zhí)行模塊負責與系統(tǒng)環(huán)境和其他的Agent進行交互，處理模塊負責對感知和接收到的信息進行初步處理和存儲。控制模塊運用方法集對所接收到的處理模塊處理后的信息和其他Agent的通信信息進行進一步的分析、推理，為通信和執(zhí)行模塊的執(zhí)行做出決策。

Agent的結構還可以分為反應式、慎思式和混合式。反應式Agent只簡單地對外部刺激產(chǎn)生響應，沒有任何內部狀態(tài)。每個Agent既是客戶，又是服務器，它根據(jù)程序提出請求或做出回答。慎思式Agent是一個具有顯式符號模型的基于知識的系統(tǒng)，其環(huán)境模型通常是預先知道的，因而對動態(tài)環(huán)境存在一定的局限性，不適合用于未知環(huán)境?；旌鲜紸gent是反應式Agent與慎思式Agent的結合，它兼?zhèn)鋬烧叩奶卣鳌?/p>

2.3 Agent間的協(xié)作和協(xié)調

由于單一挖掘技術的效果往往不令人滿意，而多Agent通過相互的協(xié)作交流，可以完成一個更高層次、更大規(guī)模的任務，因此采用多Agent數(shù)據(jù)挖掘，但Agent之間的協(xié)作和協(xié)調是一個重要問題。因為Agent具有智能性和代理性等特征，所以可以相互通信和協(xié)作，但又由于每個Agent都具有自主性，都會實現(xiàn)自身功能的最大化，因此Agent之間很容易出現(xiàn)沖突，所以對多Agent的協(xié)作，還需要進行協(xié)調，以消除沖突，提高整體效率，實現(xiàn)資源的最優(yōu)配置。Agent Sever定期向挖掘Agent廣播通知，在Agent之間發(fā)生沖突時將產(chǎn)生沖突數(shù)據(jù)，Agent協(xié)調器將收集沖突數(shù)據(jù)，并通過相關算法產(chǎn)生調度信息發(fā)送給發(fā)生沖突的Agent，發(fā)生沖突的Agent將根據(jù)調度信息修正自己的行為。在此，采用協(xié)作和協(xié)調相結合的方法，既發(fā)揮了Agent的整體和并行挖掘的功能，又消除了Agent之間的沖突。Agent之間的通信語言采用ACL語言。

3 一種基于多Agent的Web數(shù)據(jù)挖掘模型

3.1 相關的Agent和挖掘技術

根據(jù)Web數(shù)據(jù)的特點將其分為Web內容數(shù)據(jù)、Web訪問信息數(shù)據(jù)、Web結構數(shù)據(jù)。由于Web內容數(shù)據(jù)主要由各種格式的文本文檔組成，所以主要采用分類和聚類[5]的方法;Web訪問信息數(shù)據(jù)主要是Server Logs，Error，Cookie Logs等用戶訪問日志和用戶注冊、查詢等，所以主要采用序列模式挖掘方法;Web結構數(shù)據(jù)的知識隱藏在Web組織結構及Web頁面之間超鏈接結構中，而超鏈接的頁面必然存在直接或間接的某種主題相關性，所以主要用關聯(lián)規(guī)則挖掘方法。這里Agent之間的協(xié)作根據(jù)Web數(shù)據(jù)挖掘特點和挖掘過程的需要，采用了集中和分散的方式，形成了一個高效的有機整體。

3.2 基于多Agent的Web數(shù)據(jù)挖掘模型

根據(jù)上述Agent和Web數(shù)據(jù)挖掘特點，以及對一些文獻的參考，設計出一種新型的基于多Agent\\的Web數(shù)據(jù)挖掘模型，如圖1所示。

(1) 用戶Agent。主要用于用戶與系統(tǒng)的互操作。收集用戶的挖掘輸入和挖掘結果顯示，用戶可以選擇挖掘模型、數(shù)據(jù)源、挖掘知識類型、挖掘層次指定、最終的模式表示和可視化形式的設定。設置Web數(shù)據(jù)庫數(shù)量以及IP地址。針對三類挖掘的特點，分別指定相關的參數(shù)，如支持度、興趣度。

(2) 知識庫。 主要用來存放Web挖掘所獲得的各種知識和信息。

(3) 結果預處理Agent。 在協(xié)調器的協(xié)調下，對知識庫中的知識進行預處理，并依用戶偏好的形式輸出最終的處理結果，輸出結果用于Web數(shù)據(jù)挖掘的可視化。

(4) Agent協(xié)調器。 Agent協(xié)調器用來初始化和管理Agent，根據(jù)用戶的需求創(chuàng)建相應的Agent Sever，以及負責各Agent之間的通信，消除各Agent因協(xié)作而產(chǎn)生的沖突。Agent協(xié)調器還可以存儲用戶Agent，Agentsever，挖掘Agent，集成Agent和結果預處理Agent的注冊信息和狀態(tài)信息，協(xié)調器還提供命名服務，為各Agent分配地址和資源，以及協(xié)調各Agent之間的通信，協(xié)調器知道每個Agent Sever的原始數(shù)據(jù)，從而在任務分配時做到有的放矢。

圖1 一種基于多Agent的Web數(shù)據(jù)挖掘模型

(5) Agent Sever。它保存有本地數(shù)據(jù)庫的原始數(shù)據(jù)，說明本地數(shù)據(jù)的形式、庫表結構、數(shù)據(jù)范圍等。根據(jù)用戶的需求，可以同時為不同的任務或者同一任務創(chuàng)建多個挖掘Agent，并保留各挖掘Agent的ID和初始信息和狀態(tài)信息，在任務的驅動下，實現(xiàn)Agent在各主機間的移動。最后根據(jù)協(xié)調器傳送來的有關任務，啟動各挖掘Agent的功能模塊。支持挖掘Agent在各節(jié)點之間的流動和協(xié)作，管理挖掘Agent在節(jié)點上的運行，提供對挖掘Agent之間的通信支持，對挖掘Agent提供身份認證。

(6) 挖掘Agent。挖掘Agent包含中介Agent，Web內容挖掘Agent[7]、Web訪問信息Agent[8]、Web結構挖掘Agent。這四種Agent封裝成一個挖掘Agent中，便于與其他Agent進行通信和提高安全性。

(7) 中介 Agent。保留挖掘Agent的ID，并記錄各類挖掘Agent初始信息和狀態(tài)信息，還可以存放各類挖掘Agent在同一Web Database或不同Web Database協(xié)作下挖掘出來的信息結果，并將信息傳送到集成Agent和知識庫。

(8) 集成Agent。接受各中介Agent傳送過來的信息，并進行信息融合和集成，然后進行集中的數(shù)據(jù)挖掘，將最后所獲得的知識存儲到知識庫，并與用戶Agent進行交互。

(9) Web數(shù)據(jù)挖掘可視化[9]。采用可視化工具或者軟件程序將結果預處理Agent傳過來的數(shù)據(jù)進行可視化處理并進行顯示，方便用戶獲取和理解數(shù)據(jù)挖掘所得到的知識。

模型的基本原理是:當用戶通過界面設置好挖掘參數(shù)后，用戶Agent會收集這些參數(shù)，然后檢查有無挖掘的知識并與協(xié)調器通信，向協(xié)調Agent傳遞參數(shù)。挖掘到的知識會自動存入知識庫，由結果預處理Agent進行預處理后，根據(jù)用戶的要求進行可視化顯示。Agent協(xié)器會根據(jù)用戶Agent傳過來的參數(shù)，創(chuàng)建相應的Agent Sever，并分別移動到各站點上，Agent Sever被激活后，根據(jù)不同的任務或者在同一任務下創(chuàng)建多個挖掘Agent，并啟動各Agent的功能模塊。挖掘Agent在Agent Sever的協(xié)調下進行站點內協(xié)作挖掘或者在協(xié)調器的協(xié)調下進行站點間挖掘。所以有的挖掘Agent最后都通過中介Agent將挖掘所獲得的知識傳送到知識Agent或者直接傳送到知識庫。知識Agent將收集到的知識進行集成和處理后，傳送到知識庫或者用戶Agent，最后知識庫里的知識經(jīng)過結果預處理Agent后進行可視化顯示給用戶。

文中，Web內容挖掘Agent、Web訪問信息挖掘Agent、Web結構挖掘Agent和中介Agent均采用反應式結構;Agent Sever和Agent協(xié)調器采用混合式結構;集成Agent和結果預處理Agent采用慎思式結構。這主要是因為挖掘Agent直接運行在Web Database上，所要處理的數(shù)據(jù)量巨大，采用反應式可以提高處理速度，同時又可以防止過濾掉一些有用的數(shù)據(jù);集成Agent和結果預處理Agent是對挖掘Agent傳送過來的所有信息和知識進行最后的融合和集成處理，處理的數(shù)據(jù)量不大，但需要很高的精確度，即要求更加細致的加工，所以采用慎思式結構;Agent Sever和Agent協(xié)調器既要考慮到挖掘Agent的特點，又要考慮到集成Agent和結果預處理Agent的特點，同時又要將各種方式的Agent聯(lián)系起來，所以采用混合式結構比較好。

通過本文的設計可以看到，采用Agent的好處是在挖掘時通過多種算法集成，提高了挖掘精度，還可以在不同的挖掘階段使用不同的挖掘算法。每種Agent攜帶不同的數(shù)據(jù)挖掘算法，通過各Agent之間的協(xié)調，實現(xiàn)各種Web數(shù)據(jù)挖掘算法的最優(yōu)配置。但本文提出的數(shù)據(jù)挖掘模型和方法不同于以往的模型和方法。許多文獻設計出的基于多Agent的Web數(shù)據(jù)挖掘程序在單個Database上效果很好，但在多個Database上還存在許多問題，而且有些方法使得網(wǎng)絡通信量巨大，而該模型能很好地解決這個問題。本文設計出的這種挖掘方法具有較好的實用性和智能性，采用的數(shù)據(jù)挖掘Agent具有移動性，能夠由Agent Sever自動創(chuàng)建，且并行地被分派和移動到各Web Database進行工作，返回挖掘結果，避免了大量數(shù)據(jù)在網(wǎng)絡間傳送，所以減少了網(wǎng)絡通信量。另外，Agent既可以進行同一數(shù)據(jù)庫上的協(xié)作，又可以進行不同數(shù)據(jù)庫上的協(xié)作，而且各挖掘Agent還可以進行不同數(shù)據(jù)庫上整體挖掘的協(xié)作。運用Agent協(xié)調器進行集中式協(xié)調，整體消除各協(xié)作Agent之間出現(xiàn)的沖突，而且一級挖掘的數(shù)據(jù)可以直接存放到數(shù)據(jù)庫，所以提高了Web數(shù)據(jù)挖掘的速度、準確率和覆蓋率。

4 性能測試和結果分析

根據(jù)這個模型，使用Voyager平臺進行設計開發(fā)和采用Java語言編程，實現(xiàn)了Apriori，K-means等算法和Agent;采用ACL作為Agent之間的通信語言，并在校園網(wǎng)上進行試驗。運行環(huán)境為InterRCeleronR 430，1.81 GHz，1 GB RAM，Windows XP Professional SP3，以三個系的學科網(wǎng)站數(shù)據(jù)庫為數(shù)據(jù)挖掘對象，對應環(huán)境均為InterRCeleronR 540，1.86 GHz，2 GB RAM，Windows XP Professional SP3。采用三個測試評價標準，即準確率、覆蓋率和網(wǎng)絡通信量變化率。準確率指系統(tǒng)挖掘獲得的知識與與非Agent數(shù)據(jù)挖掘軟件挖掘的知識進行比較所占的比率;覆蓋率指在所有的用戶請求中，系統(tǒng)能夠給出預測結果的次數(shù)所占的比率;網(wǎng)絡通信量變化率指的是系統(tǒng)挖掘時網(wǎng)絡通信量變化量與沒有運行時的網(wǎng)絡通信量之比。

首先，采用非Agent數(shù)據(jù)挖掘軟件分別對三個數(shù)據(jù)庫進行挖掘，記錄下挖掘結果，然后采用該方法設計出軟件，對這三個數(shù)據(jù)庫進行挖掘，將最后獲得的數(shù)據(jù)挖掘結果進行處理和分析比較。最后的分析結果顯示，采用該方法挖掘的覆蓋率達到81.5%，準確率也達到86%。

運行過程中，網(wǎng)絡通信量的變化率僅為7.1%。與其他同類基于Agent的挖掘方法相比較，覆蓋率和準確率約提高了5%左右，基本上符合理論設計和期望值。由模型可以看出，本文在系統(tǒng)中加入了中介Agent和集成Agent，形成了一級挖掘與二級挖掘的相結合，避免了二級挖掘對一級挖掘結果中知識的忽略，提高了知識庫中知識的覆蓋率;采用多重協(xié)作與協(xié)調相結合，對挖掘系統(tǒng)結構進行優(yōu)化調整，消除了Agent協(xié)作中的沖突，因此挖掘精度得到了很大的提高;由于采用了移動Agent[10]，使得網(wǎng)絡通信量的變化率很小，所以系統(tǒng)運行速度有了很大提高。

5 結 語

使用移動Agent和Agent Sever創(chuàng)建挖掘Agent，并且分別并行地移動到各個Web數(shù)據(jù)庫，從而實現(xiàn)了并行挖掘和移動挖掘，提高了數(shù)據(jù)挖掘的效率，減少了網(wǎng)絡數(shù)據(jù)傳輸量。由于多Agent自身的一系列特點，能更好地滿足異構數(shù)據(jù)處理的要求。目前，很多文獻只使用了分布式數(shù)據(jù)挖掘或者利用Agent的移動性挖掘，沒有將兩者很好地結合起來，有些文獻也沒有處理好Agent之間的協(xié)作。本文將兩者很好地結合起來，還引入了中介Agent、集成Agent及知識庫，采用Agent自主式與集中協(xié)調相結合的方式，不僅很好地實現(xiàn)了二級挖掘，而且該模型的體系結構更為優(yōu)越，有效地利用了Agent的社會性，且挖掘性能更好。因此這種挖掘方法的整體性能優(yōu)越，不僅避免了因數(shù)據(jù)挖掘而讓網(wǎng)絡變得擁塞，而且效率也得到了提高，能提供全面和更準確的知識。

參考文獻

[1]曼麗春， 朱宏， 楊全勝. Web數(shù)據(jù)挖掘研究與探討[J]. 現(xiàn)代電子技術， 2005， 28(8): 3-6.

[2]劉云，劉東蘇. 基于Web的數(shù)據(jù)倉庫與數(shù)據(jù)挖掘技術[J]. 情報理論與實踐， 2001(4): 289-290.

[3]王實. 基于Web訪問信息挖掘的推薦方法研究[D]. 北京: 中國科學院計算機技術研究所， 2001.

[4]張仰森. 人工智能原理與應用[M]. 北京:高等教育出版社，2004.

[5]戴濤. 聚類分析算法研究[D]. 北京: 清華大學， 2004.

[6]BERNON C， COSSENTINO M， GLEIZES M， et al. A Study of some Multi-Agent Meta-model[C].\\: Proc. of the Fifth International Workshop on Agent-Oriented Software Engineering， 2004.

[7]姜麗華， 黃敏， 馬永光， 等. 基于Multi-agent技術的Web文本挖掘模型及應用[J]. 計算機工程， 2005， 31(1): 217-218.

[8]SRIKANT J. Web usage mining:discorvery and applications of usage patterns from Web data[J]. SIGKDD Explorations， 2000(1): 12-23.

[9]SOUKUP Tom， DAVIDSON Ian. 可視化數(shù)據(jù)挖掘:數(shù)據(jù)可視化和數(shù)據(jù)挖掘的技術與工具[M]. 朱建秋， 蔡偉杰， 譯. 北京: 電子工業(yè)出版社， 2004.

[10]張云勇， 劉錦德. 移動Agent技術[M]. 北京: 清華大學出版社，2003.