基于結構的ｅ－ｍａｉｌ挖掘算法：ＥＨＩＴＳ

摘要：在總結和分析Web網絡中經典的鏈接分析算法（HITS算法）的基礎上，提出了一種從郵件語料中發現全局權威人物的EHITS算法。首先，詳細介紹了該算法中選取種子、擴展種子集和迭代計算的方法，并通過實驗與其他方法進行了比較；最后，對該算法在安然郵件語料庫上的實驗結果進行評價。結果表明，該算法在郵件語料庫中發現全局權威人物方面是非常有效的。

關鍵詞：電子郵件挖掘； 關系網絡拓撲圖； 權威； EHITS； 安然郵件語料庫

中圖分類號：TP301.6文獻標志碼：A

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

隨著互聯網的發展，電子郵件已成為一種重要的通信方式。人們早就認識到電子郵件的重要性，并對其進行了各種研究，如垃圾郵件過濾、社團發現和關鍵人物發現等[1~3]。

從語料中發現關鍵人物已經越來越受到人們的關注。2005年TREC新增了一項專家發現任務，該任務的目的就是從W3C語料（主要是郵件語料）中發現與主題相關的專家或專家組。本文試圖從結構的角度來解決這個問題，從復雜的郵件語料庫中發現專家，尋找關鍵人物。根據應用不同，關鍵人物的定義也有所不同。本文定義的關鍵人物是全局意義上與主題無關的權威人物，也就是整個語料庫中的關鍵人物。

在傳統的Web挖掘中，有兩個經典的鏈接分析算法，即HITS和PageRank算法。HITS算法利用網頁之間的鏈接關系來發現與主題相關的權威網頁[4]，它是一種針對局部關系的重要度計算方法，對每個主題都必須在線計算。PageRank算法也是利用網頁之間的鏈接關系計算網頁重要度[5]，它是一種全局重要度的計算方法，目前主要應用于網頁查詢結果的排序。本文試圖利用結構的信息來發現全局意義上的權威人物。實驗發現，PageRank算法在該應用中效果不太理想，而HITS算法又無法直接應用于本文的問題。通過對HITS和PageRank算法的分析，筆者提出了一種基于結構的e－mail挖掘算法：EHITS。該方法在沒有主題的情況下能夠高效地發現全局權威人物，彌補了只從文本內容的角度進行人物分析的不足。

1相關研究

從文本內容的角度進行郵件分析的研究工作已有很多，主要集中在郵件分類方面。其中著名的工作有卡耐基—梅隆大學的Klimt和Yang[6，7]提出的基于SVM的郵件分類方法。他們詳細分析了“From”“Body”“Subject”和“To .CC”四個域對分類效果的貢獻，并考慮了三種組合方式，即獨立域分析、等權值組合和線性組合（權值是訓練出來的）。該方法在安然郵件語料庫上的實驗結果表明：From 和Body域對分類效果貢獻大，To和CC域對分類效果貢獻小，同時線性組合的效果要好于另外兩種組合方式。除此之外，他們還探討了利用Thread來提高分類效果的方法。

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

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

4實驗結果分析

本文的實驗語料庫是經典的安然郵件語料庫（安然語料的相關資料可到William Cohen的主頁http://www－2.cs.cmu.edu/~enron/下載）。該語料庫包含150個用戶的276 052封郵件信息文件。其中，在郵件頭的from域和to域中出現的郵件地址就有67 047個。

本文實驗中還用到了150個人的一些其他信息，一份人名與職位的對應表[16]和一份人名與郵箱的對應表[17]，如表2、3所示。人名與郵箱的對應表中給出了這150個人對應的郵箱，這些信息是根據基于內容的方法得到的，這些信息可以幫助人們找到郵箱的主人。而在人名與職位的對應表中給出了這150個人的職位信息，可以利用這些職位信息來評價實驗結果的好壞。

實驗中首先提取郵件頭中的收發郵箱，根據郵件的收發關系構建安然郵件關系網；然后主要針對三種種子選取方案進行了比較，選取的種子個數為50。第一種方案（baseline）從所有節點中隨機選取節點作為種子，本文把該方案作為基準，在此基礎上改進種子選取策略，提出了另外兩種選取方案。其一為基于內容的方案，即首先通過基于內容的方法找到150個已知人物的郵箱，再從中隨機選出50個作為種子；其二為基于結構的方案，即用PageRank對節點（郵箱）進行排序，選取前50個作為種子。實驗結果如圖2所示。

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



EHITS算法（使用基于結構的種子選取方案）在安然郵件關系網上的權威值排序結果如表4所示（只列了前五個）。表中最后一列的職位信息來自前面提到的表2（人名與職位的對應表）。表2中的150個雇員中有4個president、4個CEO和1個COO。如果把這9個人作為參考答案，表1中列出的權威值最大的5個人中有就有2個president、2個CEO和1個COO，準確率達到100％，召回率也達到了55.6％。

5結束語

基于RN拓撲圖，本文提出了一種從關系網絡中發現關鍵人物的EHITS算法。該算法主要通過選取種子、擴展種子集和迭代計算三個步驟實現對RN拓撲圖中的節點打分。在安然郵件語料庫上首先構建RN拓撲圖，通過實驗比較了基于結構和基于內容的種子選取方案，同時給出了EHITS算法（采用基于結構的種子選取方案）在安然郵件關系網上的實驗結果。結果表明EHITS算法在關系網絡中發現全局權威人物方面是非常有效的。

EHITS算法還可以用于專家發現、垃圾郵件過濾等應用中。在專家發現中先通過基于內容的方法得到主題相關的文檔，然后用EHITS算法對文檔中出現的專家進行打分。在垃圾郵件過濾中，通過EHITS算法對所有的郵件進行打分，分值非常低的郵件被認為是垃圾郵件。這是筆者下一步研究和應用的重點。

參考文獻：

[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.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”