基于結(jié)構(gòu)的ｅ－ｍａｉｌ挖掘算法：ＥＨＩＴＳ

摘要：在總結(jié)和分析Web網(wǎng)絡(luò)中經(jīng)典的鏈接分析算法（HITS算法）的基礎(chǔ)上，提出了一種從郵件語(yǔ)料中發(fā)現(xiàn)全局權(quán)威人物的EHITS算法。首先，詳細(xì)介紹了該算法中選取種子、擴(kuò)展種子集和迭代計(jì)算的方法，并通過(guò)實(shí)驗(yàn)與其他方法進(jìn)行了比較；最后，對(duì)該算法在安然郵件語(yǔ)料庫(kù)上的實(shí)驗(yàn)結(jié)果進(jìn)行評(píng)價(jià)。結(jié)果表明，該算法在郵件語(yǔ)料庫(kù)中發(fā)現(xiàn)全局權(quán)威人物方面是非常有效的。

關(guān)鍵詞：電子郵件挖掘； 關(guān)系網(wǎng)絡(luò)拓?fù)鋱D； 權(quán)威； EHITS； 安然郵件語(yǔ)料庫(kù)

中圖分類(lèi)號(hào)：TP301.6文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001－3695(2008)04－1171－04

隨著互聯(lián)網(wǎng)的發(fā)展，電子郵件已成為一種重要的通信方式。人們?cè)缇驼J(rèn)識(shí)到電子郵件的重要性，并對(duì)其進(jìn)行了各種研究，如垃圾郵件過(guò)濾、社團(tuán)發(fā)現(xiàn)和關(guān)鍵人物發(fā)現(xiàn)等[1~3]。

從語(yǔ)料中發(fā)現(xiàn)關(guān)鍵人物已經(jīng)越來(lái)越受到人們的關(guān)注。2005年TREC新增了一項(xiàng)專(zhuān)家發(fā)現(xiàn)任務(wù)，該任務(wù)的目的就是從W3C語(yǔ)料（主要是郵件語(yǔ)料）中發(fā)現(xiàn)與主題相關(guān)的專(zhuān)家或?qū)＜医M。本文試圖從結(jié)構(gòu)的角度來(lái)解決這個(gè)問(wèn)題，從復(fù)雜的郵件語(yǔ)料庫(kù)中發(fā)現(xiàn)專(zhuān)家，尋找關(guān)鍵人物。根據(jù)應(yīng)用不同，關(guān)鍵人物的定義也有所不同。本文定義的關(guān)鍵人物是全局意義上與主題無(wú)關(guān)的權(quán)威人物，也就是整個(gè)語(yǔ)料庫(kù)中的關(guān)鍵人物。

在傳統(tǒng)的Web挖掘中，有兩個(gè)經(jīng)典的鏈接分析算法，即HITS和PageRank算法。HITS算法利用網(wǎng)頁(yè)之間的鏈接關(guān)系來(lái)發(fā)現(xiàn)與主題相關(guān)的權(quán)威網(wǎng)頁(yè)[4]，它是一種針對(duì)局部關(guān)系的重要度計(jì)算方法，對(duì)每個(gè)主題都必須在線(xiàn)計(jì)算。PageRank算法也是利用網(wǎng)頁(yè)之間的鏈接關(guān)系計(jì)算網(wǎng)頁(yè)重要度[5]，它是一種全局重要度的計(jì)算方法，目前主要應(yīng)用于網(wǎng)頁(yè)查詢(xún)結(jié)果的排序。本文試圖利用結(jié)構(gòu)的信息來(lái)發(fā)現(xiàn)全局意義上的權(quán)威人物。實(shí)驗(yàn)發(fā)現(xiàn)，PageRank算法在該應(yīng)用中效果不太理想，而HITS算法又無(wú)法直接應(yīng)用于本文的問(wèn)題。通過(guò)對(duì)HITS和PageRank算法的分析，筆者提出了一種基于結(jié)構(gòu)的e－mail挖掘算法：EHITS。該方法在沒(méi)有主題的情況下能夠高效地發(fā)現(xiàn)全局權(quán)威人物，彌補(bǔ)了只從文本內(nèi)容的角度進(jìn)行人物分析的不足。

1相關(guān)研究

從文本內(nèi)容的角度進(jìn)行郵件分析的研究工作已有很多，主要集中在郵件分類(lèi)方面。其中著名的工作有卡耐基—梅隆大學(xué)的Klimt和Yang[6，7]提出的基于SVM的郵件分類(lèi)方法。他們?cè)敿?xì)分析了“From”“Body”“Subject”和“To .CC”四個(gè)域?qū)Ψ诸?lèi)效果的貢獻(xiàn)，并考慮了三種組合方式，即獨(dú)立域分析、等權(quán)值組合和線(xiàn)性組合（權(quán)值是訓(xùn)練出來(lái)的）。該方法在安然郵件語(yǔ)料庫(kù)上的實(shí)驗(yàn)結(jié)果表明：From 和Body域?qū)Ψ诸?lèi)效果貢獻(xiàn)大，To和CC域?qū)Ψ诸?lèi)效果貢獻(xiàn)小，同時(shí)線(xiàn)性組合的效果要好于另外兩種組合方式。除此之外，他們還探討了利用Thread來(lái)提高分類(lèi)效果的方法。

除了從文本內(nèi)容的角度對(duì)郵件進(jìn)行實(shí)驗(yàn)分析外，也有人對(duì)郵件語(yǔ)料庫(kù)的網(wǎng)絡(luò)結(jié)構(gòu)信息進(jìn)行了分析。卡耐基—梅隆大學(xué)的Diesner和Carley[8]從社會(huì)網(wǎng)絡(luò)的角度分析了安然郵件語(yǔ)料庫(kù)，根據(jù)不同的時(shí)間點(diǎn)，得到e－mail用戶(hù)之間的郵件關(guān)系網(wǎng)絡(luò)，通過(guò)比較不同時(shí)間點(diǎn)關(guān)系網(wǎng)絡(luò)的差異來(lái)反映人物的變更。在實(shí)驗(yàn)中，他們選擇了兩個(gè)時(shí)間點(diǎn)：2000年10月和2001年10月，發(fā)現(xiàn)在2000年10月的關(guān)鍵人物中至少有一半在2001年10月的關(guān)系網(wǎng)絡(luò)中仍然是非常重要的人物。同時(shí)他們還發(fā)現(xiàn)安然公司的雇員職位等級(jí)明顯，高層官員之間形成一個(gè)緊密的團(tuán)，他們之間互相支持，但是與公司其他人的關(guān)系卻很脆弱。Priebe等人[9]介紹了一種瀏覽圖上統(tǒng)計(jì)數(shù)據(jù)的方法，并且把這個(gè)理論應(yīng)用到安然郵件語(yǔ)料庫(kù)在時(shí)序上的原型發(fā)現(xiàn)問(wèn)題中。McCallum等人[10]把a(bǔ)uthor－recipient－topic (ART)模型應(yīng)用到安然郵件語(yǔ)料庫(kù)的社會(huì)網(wǎng)絡(luò)分析中。Drineas 等人[11]在安然郵件語(yǔ)料庫(kù)上進(jìn)行了光譜分析，并且發(fā)現(xiàn)他們通過(guò)PCAT（principal component analysis techniques）的方法得到的關(guān)系圖中存在一個(gè)包含了其中70％節(jié)點(diǎn)的大團(tuán)。

從郵件用戶(hù)關(guān)系網(wǎng)絡(luò)中發(fā)現(xiàn)重要人物的研究已有很多。其中，最簡(jiǎn)單的一種做法是按照發(fā)送郵件數(shù)的多少來(lái)判斷用戶(hù)的重要性，但是這種方法可靠性不高，而且很容易被利用；J.Golbeck 等人[12]提出了一種基于信譽(yù)值對(duì)郵件用戶(hù)排序的方法，從而得到重要人物，但是這種方法中信譽(yù)值的計(jì)算還是具有一定的模糊性。M. Newman借鑒社會(huì)計(jì)算中心性計(jì)算方法來(lái)發(fā)現(xiàn)網(wǎng)絡(luò)中的重要人物[13]，他用中介性指標(biāo)來(lái)衡量合著網(wǎng)中作家的重要性。中介性的指標(biāo)用于衡量一個(gè)人作為媒介者的能力。在有向圖中的節(jié)點(diǎn)i的中介性計(jì)算公式為C′B(ni)=∑j

4實(shí)驗(yàn)結(jié)果分析

本文的實(shí)驗(yàn)語(yǔ)料庫(kù)是經(jīng)典的安然郵件語(yǔ)料庫(kù)（安然語(yǔ)料的相關(guān)資料可到William Cohen的主頁(yè)http://www－2.cs.cmu.edu/~enron/下載）。該語(yǔ)料庫(kù)包含150個(gè)用戶(hù)的276 052封郵件信息文件。其中，在郵件頭的from域和to域中出現(xiàn)的郵件地址就有67 047個(gè)。

本文實(shí)驗(yàn)中還用到了150個(gè)人的一些其他信息，一份人名與職位的對(duì)應(yīng)表[16]和一份人名與郵箱的對(duì)應(yīng)表[17]，如表2、3所示。人名與郵箱的對(duì)應(yīng)表中給出了這150個(gè)人對(duì)應(yīng)的郵箱，這些信息是根據(jù)基于內(nèi)容的方法得到的，這些信息可以幫助人們找到郵箱的主人。而在人名與職位的對(duì)應(yīng)表中給出了這150個(gè)人的職位信息，可以利用這些職位信息來(lái)評(píng)價(jià)實(shí)驗(yàn)結(jié)果的好壞。

實(shí)驗(yàn)中首先提取郵件頭中的收發(fā)郵箱，根據(jù)郵件的收發(fā)關(guān)系構(gòu)建安然郵件關(guān)系網(wǎng)；然后主要針對(duì)三種種子選取方案進(jìn)行了比較，選取的種子個(gè)數(shù)為50。第一種方案（baseline）從所有節(jié)點(diǎn)中隨機(jī)選取節(jié)點(diǎn)作為種子，本文把該方案作為基準(zhǔn)，在此基礎(chǔ)上改進(jìn)種子選取策略，提出了另外兩種選取方案。其一為基于內(nèi)容的方案，即首先通過(guò)基于內(nèi)容的方法找到150個(gè)已知人物的郵箱，再?gòu)闹须S機(jī)選出50個(gè)作為種子；其二為基于結(jié)構(gòu)的方案，即用PageRank對(duì)節(jié)點(diǎn)（郵箱）進(jìn)行排序，選取前50個(gè)作為種子。實(shí)驗(yàn)結(jié)果如圖2所示。

圖2中橫軸表示職位的代號(hào)，基本上按照職位的高低排序，由左至右的職位分別為president、CEO、vice president、director、manager、managing director、in house lawyer、trader、employee;縱軸表示該職位平均權(quán)威值與最低職位employee的平均權(quán)威值之差。y值越大，表明本文的算法可以更加清晰地把高職位的人物和普通員工區(qū)分開(kāi)來(lái)。從圖2可以看出基于結(jié)構(gòu)的方案要優(yōu)于基于內(nèi)容的方案和baseline。原因之一是因?yàn)樵谝?guī)模較大的關(guān)系圖中用PageRank算法進(jìn)行排序效果一般都比較好；另外采用不同的基于內(nèi)容的方法得到的實(shí)驗(yàn)結(jié)果也是不一樣的，因此筆者下一步將更深入地研究基于結(jié)構(gòu)的方法與基于內(nèi)容的方法對(duì)于郵件挖掘的有效性。



EHITS算法（使用基于結(jié)構(gòu)的種子選取方案）在安然郵件關(guān)系網(wǎng)上的權(quán)威值排序結(jié)果如表4所示（只列了前五個(gè)）。表中最后一列的職位信息來(lái)自前面提到的表2（人名與職位的對(duì)應(yīng)表）。表2中的150個(gè)雇員中有4個(gè)president、4個(gè)CEO和1個(gè)COO。如果把這9個(gè)人作為參考答案，表1中列出的權(quán)威值最大的5個(gè)人中有就有2個(gè)president、2個(gè)CEO和1個(gè)COO，準(zhǔn)確率達(dá)到100％，召回率也達(dá)到了55.6％。

5結(jié)束語(yǔ)

基于RN拓?fù)鋱D，本文提出了一種從關(guān)系網(wǎng)絡(luò)中發(fā)現(xiàn)關(guān)鍵人物的EHITS算法。該算法主要通過(guò)選取種子、擴(kuò)展種子集和迭代計(jì)算三個(gè)步驟實(shí)現(xiàn)對(duì)RN拓?fù)鋱D中的節(jié)點(diǎn)打分。在安然郵件語(yǔ)料庫(kù)上首先構(gòu)建RN拓?fù)鋱D，通過(guò)實(shí)驗(yàn)比較了基于結(jié)構(gòu)和基于內(nèi)容的種子選取方案，同時(shí)給出了EHITS算法（采用基于結(jié)構(gòu)的種子選取方案）在安然郵件關(guān)系網(wǎng)上的實(shí)驗(yàn)結(jié)果。結(jié)果表明EHITS算法在關(guān)系網(wǎng)絡(luò)中發(fā)現(xiàn)全局權(quán)威人物方面是非常有效的。

EHITS算法還可以用于專(zhuān)家發(fā)現(xiàn)、垃圾郵件過(guò)濾等應(yīng)用中。在專(zhuān)家發(fā)現(xiàn)中先通過(guò)基于內(nèi)容的方法得到主題相關(guān)的文檔，然后用EHITS算法對(duì)文檔中出現(xiàn)的專(zhuān)家進(jìn)行打分。在垃圾郵件過(guò)濾中，通過(guò)EHITS算法對(duì)所有的郵件進(jìn)行打分，分值非常低的郵件被認(rèn)為是垃圾郵件。這是筆者下一步研究和應(yīng)用的重點(diǎn)。

參考文獻(xiàn)：

[1]SHETTY J， ADIBI J. Discovering important nodes through graph entropy: the case of enron e－mail database[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Chicago: ACM Press，2005:74 －81.

[2]SHETTY J， ADIBI J. The enron dataset database schema and brief statistical report [R]. California: University of Southern California ，2004.

[3]PAUL A C， DIEDERICH J， NEJDL W. MailRank: using ranking for spam detection[C]//Proc of CIKM2005. Bremen:ACM Press， 2005: 373－380.

[4]KLEINBERG J. Authoritative sources in a hyperlinked environment[J].JACM， 1999， 46(5): 604－632.

[5]PAGE L， BRIN S， MOTWANI R， et al. The PageRank citation ranking: bringing order to the Web[R]. Stanford: Stanford University， 1998.

[6]KLIMT B， YANG Y. Introducing the enron corpus[C]//Proc of the 1st Conference on E－mail and Anti－Spam (CEAS) 2004. California:[s.n]，2004.

[7]KLIMT B， YANG Y. The enron corpus: a new dataset for e－mail classification research[C]//Proc of European Conference on Machine Learning. Heidelberg: Springer， 2004: 217－226.

[8]DIESNER J，CARLEY K. Exploration of communication networks from the enron e－mail corpus[C]//Proc ofSIAM International Conference on Data Mining， SIAM Workshop on Link Analysis， Counter－terrorism and Security. California:[s.n.]，2005: 3－14.

[9]PRIEBE C E， CONROY J M， MARCHETTE D J，et al. Scan statistics on enron graphs[C]//Proc of SIAM International Conference on Data Mining， SIAM Workshop on Link Analysis， Counterterrorism and Security.California:[s.n.]，2005: 229－247.

[10]McCALLUM A， CORRADA－EMMANUEL A， WANG X. The author－recipient－topic model for topic and role discovery in social networks with application to enron and academic e－mail[C]//Proc of SIAM International Conference on Data Mining， SIAM Workshop on Link Analysis， Counterterrorism and Security. California:[s.n.]，2005:173－182.

[11]DRINEAS P， KRISHNAMOORTHY M S， SOFKA M D，et al. Stu－dying e－mail graphs for intelligence monitoring and analysis in the absence of semantic information[C]//Proc of IEEE International Conference on Intelligence and Security Informatics. Heidelberg：Sprin－ger， 2004: 297－306.

[12]GOLBECK J， HENDLER J. Reputation network analysis for e－mail filtering[C]//Proc of the Conference on E－mail and Anti－Spam (CEAS) 2004. California:[s.n.]， 2004.

[13]BRIN S， PAGE L. The anatomy of a large－scale hypertextual Web search engine[C]//Proc of the 7th International World Wide Web Conference (WWW7).1998:107－117.

[14]WHITE S， SMYTH P. Algorithms for estimating relative importance in networks[C]//ACM SIGKDD International Conference on Know－ledge Discovery and Data Mining， SESSION: Research Track. Wa－shington DC: ACM Press，2003:266－275.

[15]BORGATTI S. Identifying sets of key players in a network [J]. Computational Mathematical and Organizational Theory，2005，12(1): 127－131.

[16]SHETTY J. Enron_Employee_Status.xls[EB/OL］.[2006－09]. http://www.isi.edu/~adibi/Enron/Enron.htm.

[17]CORRADA－EMMANUEL A. Mapping file[EB/OL］.[2006－09].http://ciir.cs.umass.edu/~corrada/enron/folder－normalized－author.txt.gz.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”