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

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

隨著電子信息技術(shù)的發(fā)展，互聯(lián)網(wǎng)已走進(jìn)千家萬戶，并已廣泛應(yīng)用于各行各業(yè)。與此同時(shí)，一種新的社會(huì)形態(tài)逐漸形成，即“在線社會(huì)網(wǎng)絡(luò)”。文中在研究與分析虛擬社會(huì)中人與人之間交互關(guān)系特點(diǎn)基礎(chǔ)上，設(shè)計(jì)和實(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è)計(jì)
數(shù)據(jù)采集模塊主要用來完成BBS論壇數(shù)據(jù)的收集、分析。
1．1 網(wǎng)絡(luò)爬蟲
網(wǎng)絡(luò)爬蟲是一種按照一定的規(guī)則，自動(dòng)的抓取萬維網(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ù)采集模塊實(shí)現(xiàn)
網(wǎng)絡(luò)爬蟲模塊實(shí)現(xiàn)了采集數(shù)據(jù)的功能，包括獲取鏈接、歸類鏈接、主題鏈接、獲取數(shù)據(jù)和分析數(shù)據(jù)5個(gè)子模塊。獲取鏈接功能描述：當(dāng)輸入論壇網(wǎng)址，系統(tǒng)就開始收集該論壇的網(wǎng)頁鏈接，這是一迭代的過程，爬蟲程序下載完一個(gè)網(wǎng)頁鏈接后，打開該網(wǎng)頁的源代碼，從中得到下一個(gè)鏈接信息，將所有收集得到的網(wǎng)頁鏈接保存到本地txt文本中。歸類鏈接功能描述：將所有的網(wǎng)頁鏈接按照年份歸類到以年份為名稱的不同文件夾，方便以后導(dǎo)入數(shù)據(jù)。主題鏈接功能描述：根據(jù)輸入的年份獲得所有主題鏈接，寫入txt文本并保存在本地相應(yīng)的年份文件夾。獲取數(shù)據(jù)功能描述：根據(jù)之前抓取的主題鏈接，逐行打開鏈接，抓取網(wǎng)頁源文件，以txt文本形式保存。分析數(shù)據(jù)功能描述：利用正則表達(dá)式，從收集到的txt源文件中匹配出有效數(shù)據(jù)保存到本地。

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

3 網(wǎng)絡(luò)分析模塊
網(wǎng)絡(luò)分析模塊是整個(gè)系統(tǒng)的核心模塊，其主要基于用戶交互模塊，對(duì)網(wǎng)絡(luò)進(jìn)行各種犯罪推理，主要包含以下3個(gè)子模塊：用戶可信度更新模塊、選擇下一個(gè)調(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é)點(diǎn)表示，成員之間的關(guān)系用連接邊表示。刑事調(diào)查人員可以把每個(gè)成員視為一個(gè)代理，從互聯(lián)網(wǎng)搜集關(guān)于成員的數(shù)據(jù)來建立犯罪概率網(wǎng)絡(luò)。

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

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

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