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

1、郵件網(wǎng)絡(luò)挖掘系統(tǒng)中的EHITS算法研究熊金劉悅許洪波(中國(guó)科學(xué)院計(jì)算技術(shù)研究所，北京100080)Email：xiongjinsoftwareictaccfl摘要：本文在對(duì)HITS方法進(jìn)行重要改進(jìn)的基礎(chǔ)上，提出了一種改進(jìn)的郵件網(wǎng)絡(luò)挖掘方法EHITS，本文對(duì)EHITS采用的種子選取方法和種子個(gè)數(shù)的選取進(jìn)行了深入細(xì)致的研究和比較，并在此基礎(chǔ)上給出了一種優(yōu)化的種子選取方法，取得了較好的實(shí)驗(yàn)結(jié)果。關(guān)鍵詞：郵件拓?fù)鋱D；HITS算法；安然郵件語(yǔ)料庫(kù)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ò)成為越來(lái)越多的人工作生活中相互聯(lián)系的重要工具，而電子郵件作為互聯(lián)網(wǎng)時(shí)代的產(chǎn)物，已成為一種重要的通訊方式。人們?cè)缇驼J(rèn)識(shí)到電子郵件的重要性，并對(duì)其進(jìn)行了各種研究，比如垃圾郵件過(guò)濾，社團(tuán)發(fā)現(xiàn)和重要人物發(fā)現(xiàn)等。人們可以利用郵件中不同的數(shù)據(jù)做不同的研究，比如利用郵件正文進(jìn)行郵件分類，利用時(shí)間、源地址等對(duì)整個(gè)系統(tǒng)做一些宏觀方面的統(tǒng)計(jì)，利用郵件收發(fā)關(guān)系的結(jié)構(gòu)發(fā)現(xiàn)社團(tuán)和重要人物，但是這些方面的已有研究都很難達(dá)到滿意的效果。目前大多數(shù)關(guān)于郵件

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

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

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

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

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

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

10、將網(wǎng)頁(yè)權(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，通 迭代運(yùn)算即可得到所有網(wǎng) 的最 重。郵件挖掘中的EHITS算法41定 本文借 接分析的思想，利用改 的HITS算法 行 件拓?fù)?構(gòu)的挖掘。首先根據(jù) 件用 之 的收 關(guān)系構(gòu)造 件拓?fù)?，其形式化定 如下：定義1：郵件拓?fù)鋱DG=(V，E)是一個(gè)有向圖，其中V是頂點(diǎn)的集合，V=“，v2，匕，vf E V表示 件地址，E是有向 的集合，E=(

11、_，_)I v， _ 送了至少1封 件，1f，J刀。與前人建立 件拓?fù)?的方法不同的是，定 1中的 件拓?fù)?的 點(diǎn)是 件地址，用 件地址做 點(diǎn)粒度更小，更加接近原始數(shù)據(jù)， 做可以把從 件地址到人 一映射 程中 生的 差推 到后面，以減少 差的 累， 1中描述了一個(gè) 的 件拓?fù)?。圖l郵件拓?fù)涫景苹炯?：如果(V，_)E v推薦_定義2：任意節(jié)點(diǎn)1，的出度集out(v,)是節(jié)點(diǎn)通過(guò)有向邊可以直接到達(dá)的節(jié)點(diǎn)集合，出度odeg(V)是出度集out(v,)的大??；入度集in(v,)是所有通過(guò)有向邊可以直接到達(dá)1，。的節(jié)點(diǎn)集合，入度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郵件拓?fù)渚W(wǎng)中的元素HITS算法是web網(wǎng)中的經(jīng)典算法，在把應(yīng)用到郵件拓?fù)渚W(wǎng)之前，先建立一下郵件網(wǎng)中的元素是與web網(wǎng)中的元素的對(duì)應(yīng)關(guān)系圖，如下圖2所示。在計(jì)算節(jié)點(diǎn)重要度之前需要統(tǒng)計(jì)該郵件拓?fù)鋱D的連邊分布情況，我們統(tǒng)計(jì)的情況是該拓?fù)鋱D節(jié)點(diǎn)的連邊分布滿足長(zhǎng)尾分布。43EHITS算法的改進(jìn)HITS算法在網(wǎng)頁(yè)鏈接分析中取得了較好的效果，但將其應(yīng)用于郵件拓?fù)渚W(wǎng)絡(luò)則存在著若干問(wèn)題：l、種子選取的問(wèn)題。在web領(lǐng)域HITS算法與query相關(guān)，通過(guò)其他的搜索工具得到一

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

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

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

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

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

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

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

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