一種數(shù)據(jù)挖掘系統(tǒng)的研究與實現(xiàn)

摘要 在研究與分析虛擬社會中人與人之間交互關系特點的基礎上，設計和實現(xiàn)了互聯(lián)網(wǎng)中潛在非法組織的成員推理和追蹤系統(tǒng)。為再現(xiàn)虛擬社會中人與人之間的交互過程并對其進行推理分析，研究和設計了3大功模塊：數(shù)據(jù)采集模塊、數(shù)據(jù)庫模塊、網(wǎng)絡分析模塊。經(jīng)驗證，系統(tǒng)達到了設計要求。
關鍵詞 在線社會網(wǎng)絡；數(shù)據(jù)采集；數(shù)據(jù)庫；網(wǎng)絡分析

隨著電子信息技術的發(fā)展，互聯(lián)網(wǎng)已走進千家萬戶，并已廣泛應用于各行各業(yè)。與此同時，一種新的社會形態(tài)逐漸形成，即“在線社會網(wǎng)絡”。文中在研究與分析虛擬社會中人與人之間交互關系特點基礎上，設計和實現(xiàn)了互聯(lián)網(wǎng)中潛在非法組織的成員推理和追蹤系統(tǒng)。系統(tǒng)包括：數(shù)據(jù)采集模塊(網(wǎng)絡爬蟲模塊)、數(shù)據(jù)庫模塊、網(wǎng)絡分析模塊。

1 數(shù)據(jù)采集模塊設計
數(shù)據(jù)采集模塊主要用來完成BBS論壇數(shù)據(jù)的收集、分析。
1．1 網(wǎng)絡爬蟲
網(wǎng)絡爬蟲是一種按照一定的規(guī)則，自動的抓取萬維網(wǎng)信息的程序或者腳本。它根據(jù)既定的抓取目標，有選擇地訪問萬維網(wǎng)上的網(wǎng)頁與相關鏈接，獲取需要的信息。與傳統(tǒng)的搜索引擎不同，網(wǎng)絡爬蟲并不追求大的網(wǎng)絡覆蓋率，而將目標定為抓取與某一特定主題內(nèi)容相關的網(wǎng)頁，為面向主題的用戶查詢準備數(shù)據(jù)資源。
1．2 數(shù)據(jù)采集模塊實現(xiàn)
網(wǎng)絡爬蟲模塊實現(xiàn)了采集數(shù)據(jù)的功能，包括獲取鏈接、歸類鏈接、主題鏈接、獲取數(shù)據(jù)和分析數(shù)據(jù)5個子模塊。獲取鏈接功能描述：當輸入論壇網(wǎng)址，系統(tǒng)就開始收集該論壇的網(wǎng)頁鏈接，這是一迭代的過程，爬蟲程序下載完一個網(wǎng)頁鏈接后，打開該網(wǎng)頁的源代碼，從中得到下一個鏈接信息，將所有收集得到的網(wǎng)頁鏈接保存到本地txt文本中。歸類鏈接功能描述：將所有的網(wǎng)頁鏈接按照年份歸類到以年份為名稱的不同文件夾，方便以后導入數(shù)據(jù)。主題鏈接功能描述：根據(jù)輸入的年份獲得所有主題鏈接，寫入txt文本并保存在本地相應的年份文件夾。獲取數(shù)據(jù)功能描述：根據(jù)之前抓取的主題鏈接，逐行打開鏈接，抓取網(wǎng)頁源文件，以txt文本形式保存。分析數(shù)據(jù)功能描述：利用正則表達式，從收集到的txt源文件中匹配出有效數(shù)據(jù)保存到本地。

2 數(shù)據(jù)庫模塊設計
數(shù)據(jù)庫模塊主要是對數(shù)據(jù)庫的操作，包括數(shù)據(jù)導入，數(shù)據(jù)更新，數(shù)據(jù)導出和數(shù)據(jù)整理4個子模塊。數(shù)據(jù)導入模塊功能描述：從本地正則分析過的txt文檔提取相應的回復關系保存到數(shù)據(jù)庫中。數(shù)據(jù)更新模塊功能描述：對數(shù)據(jù)源(Forum)相應表中的回復時間和發(fā)表時間記錄進行添加和更新。數(shù)據(jù)導出模塊功能描述：根據(jù)用戶輸入的年份，將數(shù)據(jù)庫的舊數(shù)據(jù)源(Forum)中符合年份要求的記錄導入到新數(shù)據(jù)源(Export Data)中，為網(wǎng)絡分析做好準備。數(shù)據(jù)整理模塊功能描述：為以后的網(wǎng)絡分析進行的準備工作，其主要功能是完成一些數(shù)據(jù)庫的操作，例如利用原始的Reply關系構建Basic network、Together-reply network、Each-reply network、Semantic netwrok。對語義網(wǎng)絡(Semantic netwr ok)中的每條回復進行語義打分等。

3 網(wǎng)絡分析模塊
網(wǎng)絡分析模塊是整個系統(tǒng)的核心模塊，其主要基于用戶交互模塊，對網(wǎng)絡進行各種犯罪推理，主要包含以下3個子模塊：用戶可信度更新模塊、選擇下一個調(diào)查目標和犯罪網(wǎng)絡的社區(qū)發(fā)現(xiàn)。
3．1 基于貝葉斯網(wǎng)絡用戶可信度更新模塊
社交和信息通信網(wǎng)絡，例如Internet，經(jīng)常以圖表示，其中網(wǎng)絡成員用節(jié)點表示，成員之間的關系用連接邊表示。刑事調(diào)查人員可以把每個成員視為一個代理，從互聯(lián)網(wǎng)搜集關于成員的數(shù)據(jù)來建立犯罪概率網(wǎng)絡。

圖1(a)是一個犯罪網(wǎng)絡的實例圖，黑色節(jié)點表示該成員被調(diào)查過，即刑事調(diào)查人員通過分析一個特殊成員的資料信息等來觀察成員的狀態(tài)，可調(diào)查人員并不知道這個成員的真實身份，白色節(jié)點表示該成員未被調(diào)查過。考慮一個圖有節(jié)點i=1，2，…，n，節(jié)點(白色節(jié)點)的狀態(tài)用xi表示，每個xi有M種可能狀態(tài)，設定M=2，即每個節(jié)點有兩種狀態(tài)，犯罪分子和合法用戶。每個未被觀察過的節(jié)點被連接到一個被觀察過的節(jié)點(黑色節(jié)點)yi上。一般來說，觀察有關yi的一些信息，然后想推斷出一些關于xi的身份。進一步假設xi和)yi之間存在一些統(tǒng)計依賴，用一個聯(lián)合相容函數(shù)表示為φ(xi，yi)。這個函數(shù)通常被稱作xi的證據(jù)，即可以通過觀察yi推理得到關于xi的任何事情。因此，能夠計算所有未知節(jié)點xi的信念b(xi)，以至于能夠推理得到潛在的未知信息。
更新步驟如下：
輸入。本地概率分布φi(xi，yi)，如果隱藏節(jié)點i被證實是犯罪分子，則φi(xi，yi)={1，0}；隱藏節(jié)點之間的鄰接關系用n×n矩陣來描述，如果兩個節(jié)點鄰近并直接相連，則鄰接值為1，否則為0。隱藏節(jié)點之間的相容矩陣ψij(xi，yi)用2×2的矩陣來表述，矩陣中各元素的值由隱藏節(jié)點之間的依賴或信任關系計算而得。算法。信念傳播算法。輸出。b(xi)，每個隱藏節(jié)點xi的犯罪概率。
3．2 利用MPFS算法選擇下一步調(diào)查目標
當若干犯罪分子已被從犯罪網(wǎng)絡中識別出來，就可使用MPFS算法計算這幾個犯罪分子之間的最優(yōu)聯(lián)系。對于調(diào)查人員來說，他們希望以最小的代價盡快調(diào)查和確定犯罪分子。刑事調(diào)查人員經(jīng)常會選擇一些關鍵成員作為新的調(diào)查目標。但直接使用MPFS算法并不能滿足調(diào)查人員的需求。所以擴展MPFS算法來幫助刑事調(diào)查人員來選擇下一步的調(diào)查目標。基本思想就是：如果犯罪概率網(wǎng)絡中的一些成員被證實了是犯罪分子，刑事調(diào)查人員想要知道這些犯罪分子之間的關系如何。一般來說，這些犯罪分子可能屬于一個或幾個犯罪組織。鏈接分析經(jīng)常被用來分析犯罪分子之間的關系，假設犯罪概率網(wǎng)絡中已經(jīng)識別出M個犯罪分子，從這M個犯罪分子中某個節(jié)點s有M-1條到其他幾節(jié)點的最短路徑。盡管這M-1條路徑是從s到其他節(jié)點的最強聯(lián)系，但仍不知道s與其他犯罪分子之間的真正關系，所以還需要進一步調(diào)查研究。在這些最短路徑上存在眾多可疑成員，然而對刑事調(diào)查人員來說，調(diào)查這些路徑上的所有可疑人員是不可能的，因為這需要大量的人力、物力和時間，因此只能選擇關鍵的可疑目標進行調(diào)查。選擇標準就是：最短路徑經(jīng)過次數(shù)最多的節(jié)點作為新的調(diào)查目標。
3．3 犯罪網(wǎng)絡的社區(qū)發(fā)現(xiàn)
許多網(wǎng)絡中都存在團體組織(Community)，即團體內(nèi)部成員之間聯(lián)系比較緊密，而與外部成員聯(lián)系比較松散，一個團體通常由具有相似特征或者相同愛好的成員組成。為尋找犯罪網(wǎng)絡中的團體結構，提出了很多社區(qū)搜索的聚類分析算法，文中著重介紹分裂算法和凝聚算法。
3．3．1 分裂方法中的GN算法
GN算法就是一種典型的分裂方法。它的關鍵思想是通過不斷地從網(wǎng)絡中移除邊介數(shù)(Betweenness)最大的邊將整個網(wǎng)絡分解為各個社區(qū)。
GN算法的基本流程如下：(1)計算網(wǎng)絡中所有邊的Betweenness。(2)找到：Betweenness最高的邊并將它從網(wǎng)絡中移除。(3)重復步驟(2)，直到每個節(jié)點就是一個退化社區(qū)為止。
設一個網(wǎng)絡節(jié)點數(shù)為m，邊數(shù)為n。GN算法首先隨機選擇網(wǎng)絡中的某個節(jié)點作為初始節(jié)點計算所有到這個節(jié)點的邊介數(shù)。因為選取的初始節(jié)點遍歷網(wǎng)絡中的每個節(jié)點，則網(wǎng)絡中的每條邊都會有m個介數(shù)，然后將m個介數(shù)累加得到某條邊的最終的邊介數(shù)。排列所有邊的介數(shù)，找到邊介數(shù)最大的邊。將邊介數(shù)最大的邊刪除，重復以上步驟，最終可以得到網(wǎng)絡的社區(qū)結構。因為邊介數(shù)聚類算法是全局搜索算法，使得GN算法有很強的實用性。GN算法準確度比較高，分析團體結構的效果比原有算法要好，成為目前進行網(wǎng)絡社團分析的標準算法，并得到廣泛應用。
3．3．2 凝聚方法中的Newman快速算法
由于傳統(tǒng)的GN算法不能滿足大規(guī)模的復雜網(wǎng)絡，Newman在GN算法的基礎上提出了一種快速算法，它可以用于分析節(jié)點數(shù)達100萬的復雜網(wǎng)絡。
Newman快速算法實際上是基于貪婪算法思想的一種凝聚算法。算法步驟如下：
(1)初始化網(wǎng)絡為n個社區(qū)，即每個節(jié)點就是一個獨立社區(qū)。初始的eij和αi滿足

其中，ki為節(jié)點i的度；m為網(wǎng)絡中總的邊數(shù)。
(2)依次合并有邊相連的社團對，并計算合并后的Q值增量
△Q=eij+eij-2aiaj=2(eij-aiaj) (3)
根據(jù)貪婪算法的原理，每次合并應該沿著使Q增大最多或者減少最小的方向進行。該步的算法復雜度為O(m)。每次合并以后，對相應的元素eij更新，并將與i，j社團相關的行和列相加。該步的時間復雜度為O(n)。因此，步驟(2)的總時間復雜度為O(m+n)。
(3)重復執(zhí)行步驟(2)，不斷合并團體，直到整個網(wǎng)絡都合并成為一個團體。最多要執(zhí)行n-1次合并。
該算法總的算法復雜度為O((m+n)n)，對于稀疏網(wǎng)絡則為O(n3)。整個算法完成后可以得到一個社團結構分解的樹狀圖。再通過選擇在不同位置斷開可以得到不同的網(wǎng)狀社團結構。在這些社團結構中，選擇一個對應著局部最大Q值的，就得到最好的網(wǎng)絡社團結構。

4 結束語
以天涯論壇的真實數(shù)據(jù)，對系統(tǒng)各功能模塊進行驗證，實驗結果表明推理和追蹤系統(tǒng)能夠獲得較為理想的結果。需要改進和下一步研究的內(nèi)容有如下幾方面：
(1)數(shù)據(jù)采集過程中利用正則匹配將半結構化的網(wǎng)頁數(shù)據(jù)轉(zhuǎn)化為結構化的數(shù)據(jù)，但是這僅是針對天涯論壇的；對于其他的站點，由于其編碼方式的不同，采用相同的正則表達式，不能準確地提取結構化信息。所以需要提出一種泛化的提取策略，保證對決大多數(shù)站點的交互信息的正確提取。
(2)數(shù)據(jù)庫模塊中，賦予每個用戶ID固定的坐標，以滿足可視化。這種賦值是絕對化的賦值。應該根據(jù)窗口的大小進行相對賦值。經(jīng)過實測，如果主機現(xiàn)實像素改變，其對應的可視化節(jié)點位置可能會發(fā)生扭曲。因此系統(tǒng)的可視化模塊需要進一步改進。
(3)用戶可信度更新采用貝葉斯網(wǎng)絡模型，但模型中的本地證據(jù)和相容函數(shù)都是隨機給定的。而實際上，用戶的可信度可以通過其交互的方式和發(fā)帖的內(nèi)容進行預測。因此需要針對用戶的行為模式，對其可信度進行初步的預測。