一種基于多Agent的Web數據挖掘方法

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

關鍵詞:Web數據挖掘; 多Agent; Web數據; 網絡通信量; 并行挖掘

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

1 Web數據挖掘

1.1 數據挖掘

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

1.2 Web數據挖掘

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

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

2 多Agent技術

2.1 Agent概述

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

2.2 Agent的結構

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

Agent的結構還可以分為反應式、慎思式和混合式。反應式Agent只簡單地對外部刺激產生響應，沒有任何內部狀態。每個Agent既是客戶，又是服務器，它根據程序提出請求或做出回答。慎思式Agent是一個具有顯式符號模型的基于知識的系統，其環境模型通常是預先知道的，因而對動態環境存在一定的局限性，不適合用于未知環境。混合式Agent是反應式Agent與慎思式Agent的結合，它兼備兩者的特征。

2.3 Agent間的協作和協調

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

3 一種基于多Agent的Web數據挖掘模型

3.1 相關的Agent和挖掘技術

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

3.2 基于多Agent的Web數據挖掘模型

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

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

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

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

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

圖1 一種基于多Agent的Web數據挖掘模型

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

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

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

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

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

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

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

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

4 性能測試和結果分析

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

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

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

5 結 語

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

參考文獻

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

[2]劉云，劉東蘇. 基于Web的數據倉庫與數據挖掘技術[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. 可視化數據挖掘:數據可視化和數據挖掘的技術與工具[M]. 朱建秋， 蔡偉杰， 譯. 北京: 電子工業出版社， 2004.

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