郵件網(wǎng)絡(luò)挖掘系統(tǒng)中的EHITS算法研究

1、郵件網(wǎng)絡(luò)挖掘系統(tǒng)中的EHITS算法研究熊金劉悅許洪波(中國科學(xué)院計算技術(shù)研究所，北京100080)Email：xiongjinsoftwareictaccfl摘要：本文在對HITS方法進行重要改進的基礎(chǔ)上，提出了一種改進的郵件網(wǎng)絡(luò)挖掘方法EHITS，本文對EHITS采用的種子選取方法和種子個數(shù)的選取進行了深入細致的研究和比較，并在此基礎(chǔ)上給出了一種優(yōu)化的種子選取方法，取得了較好的實驗結(jié)果。關(guān)鍵詞：郵件拓撲圖；HITS算法；安然郵件語料庫The Research on EHITS Algorithm inEmail Network Mining SystemJin Xiong Yue Liu H

2、ongbo XuAbstractThis paper proposes an email networking mining algorithm EHITS，which is based Off the improved HITS algorithmThe seeds number and the selecting methods in EHITSalgorithm are investigated and compared in detail，an optimizing selecting method is proposed and the beaer experiment result

3、s are achieved【key wordsEmail graph；HITS Algorithm；Enron E-mail Dataset1、引言隨著互聯(lián)網(wǎng)的發(fā)展，網(wǎng)絡(luò)成為越來越多的人工作生活中相互聯(lián)系的重要工具，而電子郵件作為互聯(lián)網(wǎng)時代的產(chǎn)物，已成為一種重要的通訊方式。人們早就認識到電子郵件的重要性，并對其進行了各種研究，比如垃圾郵件過濾，社團發(fā)現(xiàn)和重要人物發(fā)現(xiàn)等。人們可以利用郵件中不同的數(shù)據(jù)做不同的研究，比如利用郵件正文進行郵件分類，利用時間、源地址等對整個系統(tǒng)做一些宏觀方面的統(tǒng)計，利用郵件收發(fā)關(guān)系的結(jié)構(gòu)發(fā)現(xiàn)社團和重要人物，但是這些方面的已有研究都很難達到滿意的效果。目前大多數(shù)關(guān)于郵件

4、挖掘的研究都是結(jié)合多方面的數(shù)據(jù)，過于復(fù)雜的方法往往導(dǎo)致處理速度比較慢。此外，由于郵件涉及個人隱私問題，盡管有人做過不少努力，但是到目前為止已收集的一些郵件語料庫的規(guī)模都是有限的，對真實的大規(guī)模郵件語料的挖掘還比較少。本文對鏈接分析中的HITS算法進行了若干改進，提出了EHITS算法，并將其應(yīng)用于郵件拓撲結(jié)構(gòu)的挖掘中，取得了一定效果。論文重點探討了種子選取方法和種子數(shù)量對EHITS算法的影響，對三種種子選取方法進行的比較表明我們提出的種子選取方法比其他兩種都要好，而在該種子選取方法下種子選取個數(shù)的實驗表明種子個數(shù)對挖掘結(jié)果影響不大。2、相關(guān)研究從結(jié)構(gòu)網(wǎng)絡(luò)中發(fā)現(xiàn)重要節(jié)點的研究有不少，其中最簡單的一

5、種做法是按照發(fā)送郵件數(shù)(number ofsent emails)的多少來判斷用戶的重要性，但是這種方法可靠性不高，而且很基金項目：973課題大規(guī)模文本內(nèi)容計算(課題編號：2004CB318109)；計算所知識創(chuàng)新科研課題短文本挖掘技術(shù)研究作者簡介：熊金(1981一)，女。碩士研究生，主要研究方向為大規(guī)模內(nèi)容處理。文本挖掘，信息分析劉悅，博士；許洪波副研究員。郵件網(wǎng)絡(luò)挖掘系統(tǒng)中的EHITS算法研究容易被利用；Golbeck和Hendler1提出了一種基于信譽值(reputation values)給郵件地址排序的方法得到重要節(jié)點，但是這種方法中信譽值的計算還是具有一定的模糊性；把社會網(wǎng)中一些計

6、算中心性的方法用來發(fā)現(xiàn)網(wǎng)絡(luò)中的重要節(jié)點的做法在2】可以看到，MNewman把中介性指標用在合著網(wǎng)中來衡量作家的的重要性。SWhite【3】提出了網(wǎng)絡(luò)中“最重要節(jié)點”的概念，他們羅列了一系列挖掘網(wǎng)絡(luò)中“最重要節(jié)點”的方法，其中就包含了著名的Google PageRank算法4】和HITS算法5】，這里簡單介紹一下PageRank算法，后面將對HITS算法及其改進進行詳細探討。PageRank算法是Stanford大學(xué)研究人員開發(fā)的Google搜索引擎的頁面質(zhì)量評價算法，它是基于這樣一個模型：以概率c順著超鏈接點擊訪問，或者以概率1-c從一個新的頁面開始訪問，在該模型下，頁面t被訪問到的概率Pr(

7、t)為：Pr(t)=(1一c)+c(：(Pr(t，)仆鄺)，(1)器tj其中。，是指向t的頁面集合，Pr(t)是t的PageRank概率值。3、鏈接分析中的HITS算法HITS算法是IBM的Kleinberg提出的一種網(wǎng)頁鏈接分析算法5】，其基本原理是根據(jù)一個給定的泛指主題檢索提問仃，通過鏈接分析確定該提問的權(quán)威頁。首先要確定HITS算法作用的www子集。理想地，Kleinberg希望得到的集合S。具有以下特點：S。相對較小：S口中相關(guān)網(wǎng)頁豐富；&包含多數(shù)最有價值的authorities頁面。針對具體的檢索提問，構(gòu)建關(guān)于該提問的www聚集子圖的方法如下：a用基于文本的搜索引擎女NAItaVis

8、ta或Hotbot來得到仃的查詢結(jié)果集，取排名最高的前t(t值通常設(shè)為200)位結(jié)果集尺。(稱Y寸RootSet)，K1einberg認為R。滿足特點l和2，但遠不能滿足特點3，因此需要擴充R。b擴充R。分為兩個方面，一是將所有尺仃中頁面所指向的頁面擴充進去，該擴充在數(shù)量上沒有限制，二是將指向R。中每一頁面的鏈接頁面取其中任意d(d值通常設(shè)定為50，如果d不大T-50，則取其所有頁面)個頁面擴充到原來的R。中形成磚(稱為Base Set)。這樣的集合S仃能夠較好地滿足上述三個特點，S盯的數(shù)量范圍一般在1000至5000。然后是計算hubs和authorities。將具有鏈接關(guān)系的頁面集合S。表

9、示為一個有向圖，圖中每個節(jié)點對應(yīng)一個網(wǎng)頁，有向邊(P，q)表示網(wǎng)頁p中有鏈接指向網(wǎng)頁q。Kleinberg認為重要網(wǎng)頁對應(yīng)于圖中的權(quán)威節(jié)點(authority)和樞紐節(jié)點(hub)，而hub節(jié)點和authority節(jié)點之間存在相互增強的關(guān)系。一個好的hub頁指向許多好的authorities，同時一個好的authority頁也有多個好的hubs指向它。對于任一個頁面p，用彳(p)表示頁面p的authority2郵件網(wǎng)絡(luò)挖掘系統(tǒng)中的EHITS算法研究weight(權(quán)威權(quán)重)，用日(p)表示頁面P的hub weight(中心 重)， 足 范化條件：么2(p)=l且H2(p)=l。Kleinberg

10、將網(wǎng)頁權(quán)重的傳遞分為兩種方式，即I操peS口p4作和。操作。I操作為hub到authority的傳遞，表示為：彳(p),b-日(g)其中口口Q=引(p，q)E；o操作為authority到hub的傳遞，表示為：H(p)卜彳(g)，其中_口Q=g I(P，g)E，通 迭代運算即可得到所有網(wǎng) 的最 重。郵件挖掘中的EHITS算法41定 本文借 接分析的思想，利用改 的HITS算法 行 件拓撲 構(gòu)的挖掘。首先根據(jù) 件用 之 的收 關(guān)系構(gòu)造 件拓撲 ，其形式化定 如下：定義1：郵件拓撲圖G=(V，E)是一個有向圖，其中V是頂點的集合，V=“，v2，匕，vf E V表示 件地址，E是有向 的集合，E=(

11、_，_)I v， _ 送了至少1封 件，1f，J刀。與前人建立 件拓撲 的方法不同的是，定 1中的 件拓撲 的 點是 件地址，用 件地址做 點粒度更小，更加接近原始數(shù)據(jù)， 做可以把從 件地址到人 一映射 程中 生的 差推 到后面，以減少 差的 累， 1中描述了一個 的 件拓撲 。圖l郵件拓撲示捌基本假 ：如果(V，_)E v推薦_定義2：任意節(jié)點1，的出度集out(v,)是節(jié)點通過有向邊可以直接到達的節(jié)點集合，出度odeg(V)是出度集out(v,)的大?。蝗攵燃痠n(v,)是所有通過有向邊可以直接到達1，。的節(jié)點集合，入度ideg(v,)是入度集in(v，)的大小，其中out(v,)=匕I“

12、，匕)毋，odeg(v,)=out(v,)I，加(V)=I(，V)毋，ideg(B)爿砌(V)I。3郵件網(wǎng)絡(luò)挖掘系統(tǒng)中的EHITS算法研究42郵件拓撲網(wǎng)中的元素HITS算法是web網(wǎng)中的經(jīng)典算法，在把應(yīng)用到郵件拓撲網(wǎng)之前，先建立一下郵件網(wǎng)中的元素是與web網(wǎng)中的元素的對應(yīng)關(guān)系圖，如下圖2所示。在計算節(jié)點重要度之前需要統(tǒng)計該郵件拓撲圖的連邊分布情況，我們統(tǒng)計的情況是該拓撲圖節(jié)點的連邊分布滿足長尾分布。43EHITS算法的改進HITS算法在網(wǎng)頁鏈接分析中取得了較好的效果，但將其應(yīng)用于郵件拓撲網(wǎng)絡(luò)則存在著若干問題：l、種子選取的問題。在web領(lǐng)域HITS算法與query相關(guān)，通過其他的搜索工具得到一

13、個種子集合，而在郵件關(guān)系網(wǎng)中沒有這樣的query搜索入口。2、根集擴展的問題。在全局上的擴展會帶來大量無意義的節(jié)點。本文針對HITS算法應(yīng)用到郵件關(guān)系網(wǎng)中遇到的兩個問題，提出了EHITS算法來挖據(jù)郵件網(wǎng)絡(luò)中的重要用戶。EHITS算法對HITS算法的改進主要有以下幾點：l、種子選取方法不同。EHITS的種子集不是通過基于內(nèi)容的搜索創(chuàng)建的，而是利用AddrRank算法得到。AddrRank算法利用公式(2)迭代計算郵件拓撲圖中每個節(jié)點的aw值(地址的權(quán)值)，權(quán)值最高的n個節(jié)點被選出來建立根集R，n的取值根據(jù)郵件系統(tǒng)的規(guī)模決定。aw(v,)=(1-c)N+c幸(aw(v：)odeg(v_，)(2)E

14、jn(崎)其中，是郵件拓撲圖中的節(jié)點總數(shù)，c(口w(v，)。deg(v瑚表示從節(jié)點_訪問節(jié)點”EIn(VI)V的概率，所有概率值相加得到從所有其他節(jié)點訪問節(jié)點v，的概率；“一砂肼表示隨機訪問節(jié)點_的概率。兩部分的和表示訪問節(jié)點V的總概率，用這個概率作為節(jié)點的權(quán)值。4郵件網(wǎng)絡(luò)挖掘系統(tǒng)中的EHITS算法研究2、根集擴展方法不同。EHITS算法不是在全局上擴展根集，而只是在靠前的數(shù)千個節(jié)點中擴展，這樣可以避免帶入很多無意義的節(jié)點。3、最后，在迭代計算階段，EHITS算法不是等概率累加，而是把節(jié)點的權(quán)值aw作為影響因子參與計算，新的計算公式如下：EA(vi)=(EH(vj)宰刪()(3)v，塒(1)E

15、H(vi)=(尉(_)+aw(vj)(4)vjeout(v,)44用戶的重要度計算利用EHITS算法得到的EA值和EH值?？梢杂嬎忝總€節(jié)點的重要度imp(v,)=aEA(v,)+(1-口)EH(v,)(0口1)(7)其中參數(shù)口是人為設(shè)定的值，表示權(quán)威值在整個重要度中的權(quán)值。當(dāng)口=0時，重要性完全按樞紐值排序：當(dāng)Of=1時，重要性則完全按權(quán)威值排序；當(dāng)口=05時權(quán)威值和樞紐值對重要性的影響各占一半。上面得到的只是郵件地址的重要性，要得到郵件地址的擁有者用戶的重要性需要考慮一個人擁有多個郵件地址的情況。本文的方法假設(shè)已經(jīng)得到了一個這樣的映射表addr，用戶只的郵件地址集addr(p，)=Vv，是用

16、戶p擁有的郵件地址)。用戶的重要性計算公式(8)impp(pj)=maximp(v,)I Vaddr(p,)(8)最后具有最高impp值的用戶是最重要的用戶。4、實驗比較和實驗結(jié)果分析41、實驗語料本文實驗選用的語料庫是安然郵件語料集，它是FERC(Federal Energy Regulatory Commission)在2003年公開的。最初的安然郵件語料集包含了158個用戶的619。446封郵件信息文件，除去附件后有用戶151個，郵件信息文件大約517，431個，分布在3500個文件夾里。由于有很多人對安然郵件語料集做過處理，有很多不同的安然郵件語料集的版本，本文實驗中所用的安然郵件語料

17、集是從William Cohen的主頁上下載的(http：www-2CScmueduenron)，包含了150個用戶的276，052封郵件信息文件，其中在郵件頭的”From”域和”To”域中出現(xiàn)的郵件地址就有67047個。本文實驗中還用到了150個人的一些其他信息，一份人名與職位的對應(yīng)表和一份人名與郵箱的對應(yīng)表，該表中列出了150個人的190個郵箱地址信息。5郵件網(wǎng)絡(luò)挖掘系統(tǒng)中的EHITS算法研究42、實驗結(jié)果利用EHITS算法挖掘出的enron郵件語料中的重要人物如下表所示，這跟人們的直觀判斷非常吻合，表明算法取得了良好效果。重要度排名舛名職位郵件地址lLouiseKitchenPresjd

18、entlou i sek i tcheneenronCOB2JohnLavoratoCEOjohn1avorat09enroncom3SallyBeckC()osal lybeekenrontOm4Kenneth LayCEOkenneth1 ayOenronCOIg5DavidDelaineyCEOdayiddelaineyenronCOB43、種子選取方法的比較在HITS算法中種子選取的好壞直接影響到結(jié)果的好壞，本文在確定種子個數(shù)(50)的情況下對三種代表性種子選取方法進行了實驗對比。三種種子選取方法分別為：方案一、從人名與郵箱的對應(yīng)表中的190個地址中隨機選取50個地址作為根集，方案二、

19、選取aw值最高的50個地址作為根集，方案三、隨機選取50個地址作為根集。實驗結(jié)果如圖2所示。圖2R|=50時各個職位的平均權(quán)威值比較圖從圖2可以看出這三種方案從整體上都體現(xiàn)了職位之間的高低關(guān)系，職位越高，其權(quán)威值越高。同時從實驗結(jié)果可以看出我們提出的方案二優(yōu)于方案一，而方案一又優(yōu)于方案二o44、種子選取個數(shù)的比較在種子選取方案確定的情況下，需要分析種子選取個數(shù)對實驗結(jié)果的影響。本文采用方案二的種子選取方法，種子選取的個數(shù)依次取10，20，30，直到100，得到如圖3所示6郵件網(wǎng)絡(luò)挖掘系統(tǒng)中的EHITS算法研究的實驗結(jié)果。圖3不同種子選取個數(shù)下平均權(quán)威值比較圖從圖3可以看出，在方案二下，種子選取

20、個數(shù)的多少對實驗結(jié)果影響并不大。這是因為aw值高的節(jié)點之間聯(lián)系比較緊密，雖然aw值高的節(jié)點沒有全部包含在種子集合中，但是經(jīng)過擴展后aw值高的節(jié)點基本上還是被擴展進來了。這說明采用好的種子選取方法相比于種子個數(shù)的多少作用更大。5、結(jié)論本文基于郵件的收發(fā)關(guān)系建立了郵件拓撲圖，對HITS方法進行了重要改進，提出了適用于郵件網(wǎng)絡(luò)的EHITS方法，然后重點分析了種子選取方法和種子選取個數(shù)對EHITS算法的影響。實驗結(jié)果表明了EHITS方法的有效性，本文提出的利用AddrRank方法來選取種子的方法要優(yōu)于從190個重要地址中選取種子和隨機選取種子的方法，而在AddrRank方法下種子選取個數(shù)對實驗結(jié)果沒有太大的影響。參考文獻：【1】JGolbeck and JHendlerReputation Network Analysis for Email FilteringIn Procofthe Conference onEmail and Anti-Spam(CEAS)，Mountain View，CA，USA，July