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

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

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

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

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

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

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

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

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