一種數據挖掘系統的研究與實(shí)現

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

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

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

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

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

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

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

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