基于Ｍｕｌｔｉ－Ａｇｅｎｔ的Ｗｅｂ個性化信息推送系統

〔摘 要〕針對搜索引擎在信息檢索過程中存在的缺陷，本文提出了一種基于Multi-Agent的Web個性化信息推送系統模型，并給出了該模型的結構#65380;工作流程以及算法設計#65377;該系統采用Multi-Agent系統的體系結構和反饋機制，各個Agent分工協作完成信息推送任務，體現了信息服務的智能化與個性化等特點#65377;

〔關鍵詞〕Agent;信息檢索;信息過濾;信息推送;向量空間模型;相似度;文檔聚類

〔中圖分類號〕TP393 〔文獻標識碼〕B 〔文章編號〕1008-0821(2009)08-0117-05

Study of Web Personalized Information Push System Based on Multi-AgentHuang Jizheng

(Library，Zhanjiang Normal University，Zhanjiang 524048，China)

〔Abstract〕Because of the limitation which exists in the information retrieval process，its proposed that Web personalized information push model based on Multi-Agent.Its system structure，work flow，algorithms design are given too.The system adopts system structure and feedback mechanism of Multi-Agent system.Each Agent cooperates to finish information push task，manifest the characteristics of intellectualization and individuality of information service etc.

〔Key words〕Agent;information searching;information filtering;information push;vector space model;similarity;documents clustering

根據中國互聯網絡信息中心(CNNIC)《第21次中國互聯網絡發展狀況統計報告》顯示，中國網站數#65380;網頁數和網頁字節數超過60%的增長速度，反映了網上信息資源的增加速度很快，網民可以享用的信息資源越來越豐富，截至2007年12月，網民數己達到2.1億人，目前2.1億網民中使用搜索引擎的比例是72.4%[1]#65377;搜索引擎是通往浩瀚信息海洋的捷徑，實踐表明，搜索引擎是有效的網絡信息拉取(查詢)的輔助工具#65377;遺憾的是，盡管目前提供的搜索引擎很多，但仍存在著一些缺陷:①信息導引能力差，只要所輸入的關鍵詞相同，就會返回相同的信息，而不會考慮到不同用戶的不同興趣愛好和學科領域，導致大量無關信息的涌現#65377;②不能主動給用戶反映網絡上的信息的動態變化#65377;③往往具有相同興趣的用戶對信息的需求基本一致，但傳統的搜索引擎并不提供協作過濾功能，使用戶失去了準確獲取信息的一個重要方式#65377;④一般不具備學習功能，不能主動發現和收集用戶所需要的信息#65377;⑤普通用戶往往因不能準確地用關鍵詞描述自己的信息需求而難以獲取準確信息#65377;因此，如何使用戶能真正享受到快捷準確的個性戶信息服務已成為一個重要的研究課題#65377;

1 智能Agent

1.1 Agent技術

Agent用來最一般地說明一個軟硬件系統，它具有以下4個特性:①自治性:Agent可以在沒有人或其他Agent直接干預的情況下運作，而且對自己的行為和內部狀態有某種控制能力;②社會性:Agent和其他Agent(也可能是人)通過某種Agent語言進行信息交流;③反應性:Agent能夠理解周圍的環境，并對環境的化作出實時的響應;④能動性:Agent不僅簡單地對其環境作出反應，也能夠通過接受某些啟動信息，表現出有目標的行為#65377;Agent除了具備以上特性外，還具備一些人類才具有的特性，如知識#65380;信念#65380;義務#65380;意圖等[2]#65377;

1.2 MAS(Multi-Agent System)

Agent一般由知識庫#65380;通信模塊和可選的功能組件組成，它可以感知系統環境的變化，并對這種變化做出自主的反映，因而具有智能性#65377;由于一個智能主體的能力受其知識#65380;計算資源及其與其他主體相互關系的制約，限制了單主體系統解決問題的能力#65377;為了解決大型#65380;復雜的現實問題，在分布式人工智能領域引入了多主體系統MAS(Multi-Agent System)#65377;MAS是由分布在網絡上的多個Agent松散藕合而成的大型復雜系統，各Agent要對熟悉的環境做出迅速的響應，同時能夠協調與其他Agent的沖突，并最終做出決策[3]#65377;

Agent技術作為目前人工智能(AI)領域研究的一個熱點，為實現信息服務的智能化#65380;個性化及主動性提供了新的方向#65377;針對這一情況，本文提出了一種基于Multi-Agent的web個性化信息推送系統模式，并詳細敘述了系統的設計思想#65380;體系結構和算法設計#65377;

2 系統結構與設計

2.1 系統的設計思想

本文所設計的Web個性化信息推送系統是一個基于Multi-Agent的智能系統，應用機器學習技術自適應調整用戶興趣模型，以提供智能化#65380;個性化的主動信息服務#65377;系統由用戶Agent#65380;學習Agent#65380;過濾Agent#65380;檢索Agent#65380;推薦Agent#65380;用戶模型庫#65380;領域模型庫和文檔信息庫組成#65377;根據用戶的興趣，這些Agent通過共同的通信語言和通信機制進行相互交流和協作來快速準確地完成對中文網絡信息的個性化過濾，主動為用戶提供某類感興趣的相關信息#65377;

2.2 系統的體系結構

Web個性化信息推送系統的總體結構如圖1所示#65377;

2.3 系統工作流程

系統的工作流程是:用戶Agent與用戶進行交互，接受用戶的個性化信息要求;學習Agent觀察用戶Agent記錄的用戶檢索查詢記錄和瀏覽行為以獲取用戶興趣，并將之寫入用戶模型庫;同時提取和計算出各主題概念所對應的關鍵詞及其相應權重，根據該領域的專業詞典，寫入領域模型庫;檢索Agent在領域模型庫中取權值最大的3-10個特征項作為查詢關鍵詞，借助搜索引擎進行相關檢索，將查詢到的結果URL作為起點，開始進行文檔采集;過濾Agent依據領域模型對采集的文檔進行分析，抽取文檔特征，形成文檔結構化表示;推薦Agent通過比較結構化的文檔屬性與用戶模型，尋找相似度最大的若干用戶，并將其選擇的文檔通過用戶Agent推送給用戶;學習Agent利用機器學習技術對用戶相關性反饋信息進行學習，自適應地調整用戶模型和領域模型，使用戶模型更好地體現用戶的興趣#65377;

模型系統的工作流程如上所述，經過相關性反饋學習之后，修改后的用戶模型更加體現用戶的興趣，因此用戶利用修改過的用戶模型進行信息挖掘的時候將獲得更高的查準率#65377;經過整個檢索過程，一方面用戶得到了符合自己興趣的信息，另一方面系統學習到了用戶的信息興趣，為個性化信息檢索和主動信息服務提供基礎知識#65377;

2.4 系統功能分析

2.4.1 用戶模型庫

用戶模型庫記錄反映用戶各興趣點的模型#65377;用戶模型庫的主要作用是:

(1)用戶模型用于信息文檔的過濾，可為推薦Agent提供用戶的興趣模型，通過與過濾Agent所提供的領域相關的信息文檔的結構化特征進行相似性比較，從而提供給用戶其最感興趣的文檔#65377;

(2)用于推薦Agent比較用戶之間相似性的標準，從而可向相似用戶推薦相關文檔#65377;

2.4.2 領域模型庫

領域模型庫用來描述各知識領域中主題概念間的關系及與各概念相關的關鍵詞#65377;本文所設計的領域模型為樹形結構#65377;領域模型庫的主要作用是:

(1)作為構造用戶模型的基礎，用戶可通過選擇領域的主題概念及其關鍵詞作為其基本的興趣點，形成用戶模型的框架基礎;

(2)作為搜集信息的基礎，為檢索Agent調用其他搜索引擎提供關鍵詞;

(3)作為對網頁進行分類的基礎#65377;過濾Agent利用領域模型庫中的信息，通過分析文檔特征形成文檔的結構化表示，計算網頁與各主題概念的隸屬程度，從而對網頁進行分類#65377;

2.4.3 文檔信息庫

文檔信息庫記錄所收集的網頁(全文和URL)#65380;相應文檔的結構化信息(主要是關鍵詞的詞頻)及與之相關性最大的若干主題概念的隸屬度#65377;文檔信息庫的主要作用是:

(1)為用戶提供快速的獲取相關網頁的手段，通過該庫向用戶推薦隸屬度較高的網頁;

(2)為檢索Agent記錄歷史信息避免重復搜索同一頁面#65377;

2.4.4 用戶Agent

用戶Agent是用戶與系統的交互接口，接受用戶的個性化信息要求#65377;用戶Agent的任務是:

(1)與用戶進行交互，接受用戶反饋信息，將用戶反饋信息提供給學習Agent進行機器學習，以修改用戶模型，使用戶模型能更好地表現用戶的興趣;

(2)在交互過程中，通過監測用戶的查詢#65380;瀏覽等行為過程，并將這些信息提供給學習Agent進行分析，動態地學習用戶興趣#65377;

2.4.5 學習Agent

學習Agent的任務是通過接收用戶Agent所記錄的用戶顯式和隱式相關性反饋信息學習用戶興趣，通過機器學習修改用戶模型并調節領域模型#65377;

2.4.6 檢索Agent

檢索Agent的主要任務是:

(1)借助搜索引擎在網絡中搜集與領域相關的網頁;

(2)在系統設定的時間內對資源數據庫信息掃描，將掃描到的變化結果寫入到搜索信息索引中，使得更新能夠被用戶搜索而又不必更新智能Agent系統程序#65377;

2.4.7 過濾Agent

過濾Agent是整個系統的核心，它的設計直接關系到系統的功能和性能#65377;過濾Agent的主要功能是對網頁進行分析，抽取文檔特征，形成文檔的結構化表示，作用如下:

(1)對網頁進行特征抽取，形成結構化的網頁屬性#65377;

(2)分析網頁中有價值的超鏈接，向信息檢索Agent提供進一步下載的URL列表#65377;

(3)對新收入的網頁進行分析，提取新的主題概念關鍵詞，并將其加入用戶模型庫#65377;

2.4.8 推送Agent

推送Agent負責把收入的網頁推薦給感興趣的相關用戶#65377;推送Agent每隔一定的時間或當收入的網頁達到一定數量時啟動文檔選擇任務，通過比較結構化的文檔屬性與用戶模型，尋找相似度最大的若干文檔通過用戶Agent推送給用戶#65377;

3 多Agent的通信和協作

3.1 Agent間的通信

多Agent通信機制直接影響了多Agent系統的協同工作能力和系統的性能#65377;本系統下的多個Agent通過ACL通信語言和FIPA消息傳遞機制進行通信和協同工作#65377;在FIPA規范下的Agent平臺有3個主要的子系統:索引器#65380;AMS(Agent Manage System，Agent管理系統)和MTS(MessageTransport Service，消息傳輸服務)#65377;Agent間消息的傳送通過MTS系統中的ACC(Agent Communication Channel)提供的消息傳送服務以“信封+消息”的格式傳輸來實現#65377;根據信封中定義的地址等信息，在MTS為Agent平臺上的Agent找到合適的消息傳送通道ACC后，ACC進行通信協議的判定和消息的傳輸#65377;當消息抵達目的地后，再通過ACC，Agent就可以解讀ACL所要傳達的信息，多Agent之間的溝通也隨即完成[4]#65377;

3.2 Agent間的協作

Agent的協作是保證系統能在一起工作的關鍵#65377;協調與協作是多Agent研究的核心問題之一，因為以自主的Agent為中心，使多Agent的知識#65380;愿望#65380;意圖#65380;規劃#65380;行動協調，以致到達協作是多Agent的目標#65377;協調是指一組Agent完成一些集體活動時相互作用的性質#65377;在開放#65380;動態的多Agent環境下，具有不同目標的多個Agent必須對其目標#65380;資源的使用進行協調#65377;在出現資源沖突時，若沒有很好的協調就可能出現死鎖#65377;而在另一種情況下，即單個Agent無法獨立完成目標，需要其他Agent的幫助，這時就需要協作#65377;一般來說，當某個Agent相信通過協作能帶來好處時，會產生協作的愿望，進而尋求協作伙伴#65377;在多Agent中協作不僅能提高單個Agent以及由多個Agent所形成系統的整體行為的性能，增強Agent及Agent系統解決問題的能力，還能使系統具有更好的靈活性[5]#65377;正是協作使得幾個智能Agent能將它們各自的努力組合起來完成信息的推送這一目標#65377;

4 算法設計

4.1 文檔的向量空間模型

為了將文本文檔表示成計算機容易處理的形式，需要對文檔進行一定的特征抽取，該特征既要能包括文檔的大部分關鍵詞，又要方便計算機根據這些特征計算文檔之間的關聯度#65377;根據實際情況，我們選取了向量空間模型(VSM)來對文檔的語義結構進行建模#65377;VSM是由一組規范化正交詞條矢量所張成的向量空間，每個文檔映射成向量空間的一個點，向量間的距離表示文檔的相似度#65377;

假如用符號D表示文檔，t表示特征項，w表示權重，那么根據VSM的定義可以得到文檔的向量空間模型:D=(t1w1，t2w2，…，tnwn)#65377;由于t1，t2，…，tn互不關聯，可以把它們看作是n維向量空間的n個維度，而w則表示該文檔在這些方向上面的投影坐標，每個坐標反映了該文檔在相應的特征項所表示的含義上面的意義大小[6]#65377;

在信息檢索向量空間模型中，文檔是由相互獨立的關鍵詞t1，t2，…，tn構成，令D=(D1，D2，…，Dn)表示由m個索引關鍵詞構成的n個文檔，其中Dj=(d1j，d2j，…，dmj)是文檔向量，dij表示關鍵詞i發生在文檔j中的頻率權重，這樣就定義了一個m維關鍵詞文檔向量空間，即詞語向量空間[6]#65377;在文檔向量空間當中，對文檔進行分類#65380;聚類#65380;排序和相關性反饋都要分析兩個向量之間的相似度#65377;

4.2 相似度的計算

在基于VSM的信息檢索中，有許多種計算相似度(點與點的距離)的方法，基于簡化的數學公式分析，我們采用余弦系數計算文本的相關性[6-7]#65377;

sim(Di，Dj)=∑mk=1dkidkj∑mk=1dki2∑mk=1dkj2(1)

4.3 文檔聚類算法

為了從用戶的反饋文檔當中總結出某種規律，得到用戶的信息檢索模型，下面分析一下文檔的聚類過程#65377;聚類是指將文檔集合分成若干個簇，要求同一個簇內文檔內容的相似度盡可能地大，而不同簇間的相似度盡可能地小[8]#65377;目前，基于向量空間模型的常見文檔聚類算法有分割算法中的k-means算法和層次算法中的凝聚層次算法#65377;

4.3.1 k-means算法

k-means算法以k為參數，把n個對象分為k個簇，以使簇內具有較高的相似度，簇間的相似度較低#65377;一般步驟如下:

(1)在N個對象中隨機選取K個對象作為初始的聚類中心;

(2)把其余的N-K個對象歸到距離最近的聚類中;

(3)重新計算每一個聚類的中心;

(4)重復(2)和(3)，直到每個聚類中心不再改變#65377;

這種算法的實質是一種多次迭代的方法，把每篇文檔看成一個對象，利用文檔與聚類中心之間的相似度進行聚類，在數據量較小時，具有較好的聚類效果，當處理大規模數據時，時間復雜度也是O(n)，但聚類效果差，計算量也會增大[9]#65377;

4.3.2 凝聚的層次算法

凝聚的層次算法將數據對象組成一棵聚類的樹#65377;其一般步驟如下:

(1)把N個對象作為N個聚類，計算所有聚類兩兩之間的相似度;

(2)合并最為相似(滿足距離要求)的聚類;

(3)重新計算更新后的所有聚類兩兩之間的相似度;

(4)重復(2)和(3)，直到剩下一個聚類#65377;

這種算法盡管方法簡單，聚類效果一般比k-means算法要好，但是時間復雜度為O(n2)#65377;由于聚類之間不能交換對象，如果某一步選擇不恰當，將導致低質量的聚類結果，它也不具有很好的伸縮性[9]#65377;

為了從用戶的行為中得到用戶信息檢索的行為模型，本文借鑒了聚類算法中的一些基本思想，目的在于盡可能減少用戶的介入，自動完成用戶信息檢索模型的建立和修改#65377;

4.4 用戶信息檢索模型

4.4.1 模型的建立

為了將用戶的興趣表示成計算機可以理解的形式，需要對用戶的興趣進行建模#65377;用戶的興趣可以概括為各個不同的相互獨立的主題，主題相當于用戶輸入的檢索關鍵字#65377;在建立用戶興趣模型的過程中，同樣可以利用類似VSM的辦法，將本來抽象的文檔的意義進行合理的量化，映射為向量空間的一個可計算的點，具體步驟如下:

(1)用戶提交檢索主題;

(2)用戶在返回的結果集中選擇自己喜歡的文檔;

(3)計算機對入選的文檔進行分詞#65380;預處理;

(4)對預處理后的文檔特征向量進行降維，并根據一定的規則對每個維度賦予權值#65377;

4.4.2 用戶模型的重建

從用戶模型的建立過程來看，剛開始的時候模型可能是不夠精確的#65377;首先，對于某個新的檢索主題，不存在任何可以代表該主題的示例文檔，因此用戶需要選擇可以代表這一主題的示例文檔，但是由于一級搜索引擎如Google等，可沒有覆蓋該主題相關的全部文檔，或者由于用戶挑選的失誤而遺漏了與該主題相關的重要文檔，僅選擇部分不那么稱心的文檔，這時用戶的模型就出現了偏差#65377;當用這些不準確的文檔作為重心向量去過濾從搜索引擎返回的結果時，將不會反映整個文檔域的中心#65377;其次，由于Internet上的文檔不是靜態的，而是不斷增長的，因而重心向量也是隨著文檔的不斷增長而不斷變化的，因此，同樣要采取一定的措施來保證重心向量能夠根據用戶的選擇不斷更新#65377;

針對這一問題，本系統設計將采用一種基于反饋的方案#65377;反饋的概念來源于經典控制理論，是一種通過不斷比較輸出信號與目標信號的偏差，來修正輸入信號，以保證輸出信號能夠得到有效的控制#65380;與預期相符的方法#65377;根據這個思想，用戶興趣模型的建立并不是一個孤立的過程，而是與信息過濾模型緊密相連的#65377;一般來說，這個過程包含3個模塊:

(1)Profile的生成模塊負責生成用戶興趣文件#65377;它通過分析用戶給出的示例文檔(一般可認為是第一次檢索后經用戶選擇的結果)，形成profile文件，并將該文件保存在磁盤上面#65377;該模塊在后臺運行#65377;

(2)過濾模塊負責過濾文檔流#65377;它通過比較后臺存儲的profile文件和輸入文檔的相關程度，過濾出用戶感興趣的結果文檔，并將它們按照相關性排序后提交給用戶#65377;該模塊運行在前臺#65377;

(3)Profile的重建模塊負責profile的修改#65377;在建立用戶興趣文件時，用戶有時難以準確表述自己的信息需求，但是可以準確地判斷返回的信息是否符合要求而采取針對性的處理，如閱讀#65380;下載#65380;瀏覽等#65377;該模塊利用用戶對結果文檔的評估結果重新修改profile文件#65377;此模塊運行在后臺#65377;

4.4.3 用戶信息檢索模型的3個步驟

(1)profile的建立

在用戶給出示例文檔后，使用聚類算法中的訓練算法來建立profile文件#65377;具體采用類重心分類算法(Text Categorization based on Category，簡記為TC3)，將每個類別看作是詞條的集合，并為類別引入重心矢量的概念#65377;給定類別C和一批類別標識為C的訓練文檔DCtraining，該訓練文檔可以被認為是第一次檢索的結果集，C的重心是指DCtraining中的所有文檔矢量的累加矢量平均值#65377;根據上述定義，類別C的重心矢量可以由該類別的訓練文檔的矢量來計算#65377;公式如下:

∑/∑，d∈DCtraining(2)

從程序設計的角度來說，建立profile的過程也就是由示例文檔訓練出profile的類矢量的過程#65377;算法描述如下所示#65377;

輸入:示例文檔集合DCtraining

輸出:Profile的類別矢量

算法:①←0

②for each d∈DCtraining

←+;

③←/

(2)文檔過濾

過濾可以看作是一個分類的過程，也就是說存在兩種不同的類別:一類是用戶感興趣的，另一類是用戶不感興趣的#65377;過濾就是要判斷出文檔屬于哪個類，然后將屬于用戶感興趣的類的文檔返回給用戶，而將用戶不感興趣的文檔過濾掉#65377;由于過濾算法將會比較Profile文件中的文檔向量和待過濾的文檔向量，因此過濾算法與生成profile的算法密切相關#65377;目前，存在多種過濾算法，由于在本系統中profile的生成采用了TC3分類算法，故與此相應的過濾算法中，待過濾文檔與用戶興趣的相似度比較采用余弦方法，見公式(1)#65377;

(3)Profile的重建

用戶興趣的學習是一個長期的過程，需要不斷的維護，而維護的方式就是通過用戶給出的反饋自動更新模型#65377;比如，當一個頁面被選中時，則該頁面會展現給用戶，同時由用戶給出反饋#65377;如果用戶喜歡這個頁面，則從這個頁面抽取出的詞的權重將會加到用戶興趣文件中相應詞的權重上#65377;這一過程被稱為相關度反饋#65377;本系統中采用Rccchio反饋模型#65377;更有效的用戶興趣文件可以由以下公式迭代產生:

Pk+1=Pk+β∑n1k=1Rkn1-γ∑n1k=1Skn2(3)

其中，Pk+1，是新的用戶興趣文件，Pk是舊的用戶興趣文件，Rk是用戶反饋中認為感興趣的(相關的)文檔k的內容表示，Sk是用戶認為不感興趣的(不相關)文檔k的內容表示，n1是相關文檔數，n2是不相關文檔數，β#65380;γ值決定了正負反饋的相對作用#65377;

5 結束語

將人工智能領域的Agent技術引入網絡信息服務研究是一個有代表性的研究方向#65377;本文提出了一種基于Multi-Agent的Web個性化信息推送系統模型，并詳細敘述了系統的體系結構#65380;設計思想和相關算法#65377;與傳統搜索引擎相比，該模型具有搜索信息關聯度高#65380;能夠滿足用戶個性化需求等優點，為主動開展個性化信息服務提出了一種有效的實現途徑#65377;但文中用戶信息檢索模型采用的是基于向量空間模型的信息過濾方法，對于文檔的描述普遍使用關鍵詞向量，從而存在很大的信息丟失，因此希望下一步能夠在文檔語義理解方面作初步的探索，研究一種更高質量和高效率的信息過濾算法#65377;

參考文獻

[1]中國互聯網絡信息中心(CNNIC).中國互聯網絡發展狀況統計報告(2008.1)[EB]. http:∥www.cnnic.com.cn，2008-03-02.

[2]王汝傳，徐小龍，黃海平.智能Agent及其在信息網絡中的應用[M].北京:北京郵電大學出版社，2006:10.

[3]王俊松，崔世鋼.Multi-Agent技術及應用[J].計算機工程與應用，2003，(18):22-2 4.

[4]王汝傳，徐小龍，黃海平.智能Agent及其在信息網絡中的應用[M].北京:北京郵電大學出版社，2006:31-42.

[5]王汝傳，徐小龍，黃海平.智能Agent及其在信息網絡中的應用[M].北京:北京郵電大學出版社，2006:46-69.

[6]王偉，王惠榮，劉志強.自動分類模型及算法研究[J].微電子學與計算機，2004，(5) :93-96.

[7]陶躍華.基于向量的相似度計算方案[J].云南師范大學學報，2001，(5):17-18.

[8]徐寶文，張衛豐.搜索引擎與信息獲取技術[M].北京:北京郵電大學出版社，2003:86-94.

[9]唐春生，金以慧.基于聚類特性的大規模文檔聚類算法研究[J].計算機科學，2002，(9):9-11.