【文章內(nèi)容簡介】 的對象相異。 但目前對于聚類并無一個學(xué)術(shù)上的統(tǒng)一定義，這里使用出 Everitt在 1974年關(guān)于聚類所下的定義：一個類簇內(nèi)的實(shí)體是相似的，不同類簇的實(shí)體是不相似的；一個類簇是測試空間中點(diǎn)的會聚，同一類簇的任意兩個點(diǎn)間的距離小于不同類簇的任意兩個點(diǎn)間的距離；類簇可以描 述為一個包含密度相對較高的點(diǎn)集的多維空間中的連通區(qū)域，它們借助包含密度相對較低的點(diǎn)集的區(qū)域與其他區(qū)域 (類簇 )相分離 [14]。 ? 數(shù)據(jù)準(zhǔn)備：包括特征標(biāo)準(zhǔn)化和降維 ? 特征選擇：從最初的特征中選擇最有效的特征 ,并將其存儲于向量中 。 ? 特征提?。和ㄟ^對所選擇的特征進(jìn)行轉(zhuǎn)換形成新的突出特征 ? 聚類：首先選擇合適特征類型的某種距離函數(shù)（或構(gòu)造新的距離函數(shù)）進(jìn)行接近程度的度量而后執(zhí)行聚類 ? 聚類結(jié)果評估：是指對聚類結(jié)果進(jìn)行評估。評估主要分為外部有效 。 ? 性評估、內(nèi)部有效性評估和相關(guān)性測試評估 北京交通大學(xué)畢業(yè)設(shè)計(jì)（論文） 第 14 頁 聚類分析方法 由于多維數(shù)據(jù)集的復(fù)雜性，要求有不同的聚類方法對各種復(fù)雜數(shù)據(jù)類型進(jìn)行分析。目前主要的聚類分析方法有以下幾種： ? 劃分式聚類 (partitioning methods) 劃分式聚類需要預(yù)先指定聚類數(shù)目或聚類中心，通過反復(fù)迭代運(yùn)算，逐步降低目標(biāo)函數(shù)的誤差值，當(dāng)目標(biāo)函數(shù)值收斂時，得到最終聚類結(jié)果。使用這個基本思想的算法有： KMEANS算法、 KMEDOIDS算法、模糊聚類算法以及圖論算法 [15] ? 層次方法 (hierarchical methods) 這種方法對給定的數(shù)據(jù)集進(jìn)行層次似的分解，直到某種條件 滿足為止。具體又可分為“自底向上”和“自頂向下”兩種方案。例如在“自底向上”方案中，初始時每 一個數(shù)據(jù)紀(jì)錄都組成一個單獨(dú)的組，在接下來的迭代中，它把那些相互鄰近的組合并成一個組，直到所有的記錄組成一個分組或者某個條件滿足為止。代表算法 有： BIRCH算法、 CURE算法、 CHAMELEON算法等 [16] ? 基于密度的方法 (densitybased methods) 基于密度的方法與其它方法的一個根本區(qū)別是：它不是基于各種各樣的距離的，而是基于密度的。這樣就能克服基于距離的算法只能發(fā)現(xiàn)“類圓形”的聚類的缺點(diǎn)。這 個方法的指導(dǎo)思想就是，只要一個區(qū)域中的點(diǎn)的密度大過某個閥值，就把它加到與之相近的聚類中去。代表算法有： DBSCAN算法、 OPTICS算法、 DENCLUE算法等 ? 基于網(wǎng)格的方法 (gridbased methods) 這種方法首先將數(shù)據(jù)空間劃分成為有限個單元（ cell）的網(wǎng)格結(jié)構(gòu) ,所有的處理都是以單個的單元為對象的。這么處理的一個突出的優(yōu)點(diǎn)就是處北京交通大學(xué)畢業(yè)設(shè)計(jì)（論文） 第 15 頁 理速度很快，通常這是與目標(biāo)數(shù)據(jù)庫中記錄的個數(shù)無關(guān)的，它只與把數(shù)據(jù)空間分為多少個單元有關(guān)。代表算法有： STING算法、 CLIQUE算法、WAVECLUSTER算法 ? 基 于模型的方法 (modelbased methods) 基于模型的方法給每一個聚類假定一個模型，然后去尋找能夠很好的滿足這個模型的數(shù)據(jù)集。這樣一個模型可能是數(shù)據(jù)點(diǎn)在空間中的密度分布函數(shù)或者其它。它的一個潛在的假定就是：目標(biāo)數(shù)據(jù)集是由一系列的概率分布所決定的。通常有兩種嘗試方向：統(tǒng)計(jì)的方案和神經(jīng)網(wǎng)絡(luò)的方案 [17]。 技術(shù)方法框架 本文以 數(shù)據(jù)挖掘的交叉產(chǎn)業(yè)標(biāo)準(zhǔn)過程 ()作為參考 [18]，結(jié)合具體的社交網(wǎng)站數(shù)據(jù)挖掘需求，構(gòu)建如下圖技術(shù)方法框架： 定 義 社 交 網(wǎng) 絡(luò) 用戶 行 為 具 體 內(nèi) 容確 定 網(wǎng) 頁 爬取 內(nèi) 容通 過 網(wǎng) 頁 爬蟲 爬 取 數(shù) 據(jù)選 擇 最 合 理模 型 進(jìn) 行 解釋對 數(shù) 據(jù) 進(jìn) 行聚 類 分 析對 分 析 結(jié) 果做 出 評 估數(shù) 據(jù) 圖 23 社交網(wǎng)絡(luò)用戶行為數(shù)據(jù)挖掘過程 北京交通大學(xué)畢業(yè)設(shè)計(jì)（論文） 第 16 頁 3 基于 網(wǎng)絡(luò)爬蟲技術(shù)的 數(shù)據(jù)采集 網(wǎng)絡(luò)爬蟲工作原理 網(wǎng)絡(luò)爬蟲基本工作原理 網(wǎng)絡(luò)爬蟲，即 Spider , 通常是指遵循 HTTP協(xié)議、根據(jù)其中的超鏈接以及 WEB頁面文檔之間的索引關(guān)系來遍歷萬維網(wǎng)信息空間的軟件程序。網(wǎng)絡(luò)爬蟲是一個功能強(qiáng)大的自動提取網(wǎng)頁的程序，負(fù)責(zé)收集頁面來源。網(wǎng)絡(luò)爬蟲通過訪問某一 URL頁面，來獲得此頁面內(nèi)其他 URL，并且根據(jù)這些 URL來遍歷這個站點(diǎn)或者跳轉(zhuǎn)到其他站點(diǎn)，從而實(shí)現(xiàn)遍歷整個互聯(lián)網(wǎng)空間，進(jìn)而獲得需要的 URL集合。其主要工作原理如下圖所示 [19]： 圖 31 網(wǎng)絡(luò)爬蟲基本原理 如上所述，常見的搜索引擎類網(wǎng)絡(luò)爬蟲負(fù)責(zé)收集互聯(lián)網(wǎng)世界的所有頁面并且存儲下來。除了以上通用爬蟲之外，還有一些定向爬蟲負(fù)責(zé)在一些北京交通大學(xué)畢業(yè)設(shè)計(jì)（論文） 第 17 頁 細(xì)分領(lǐng)域收集特定信息。 URL 存在形態(tài)分析 從聯(lián)系的角度來看，互聯(lián)網(wǎng)上的 URL可分為有聯(lián)系的和孤立的 2類，如下圖所示： 圖 32 互聯(lián)網(wǎng) URL分類 大部分的 URL都是相互關(guān)聯(lián)的，比如從 urla出發(fā)，通過 urlb、 urld可到達(dá) urlf，所有關(guān)聯(lián)的 URL最后組成了一個復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)。但是 也存在一些 URL，比如 url url2等是相對孤立的，試圖從 urla系列以及 url1等頁面直接來獲得另外 url url3是不可能的。 從 URL的出現(xiàn)位置來可看， 我們可將 URL的出現(xiàn)位置分為如下幾類： ? HTML靜態(tài)標(biāo)簽 HTML靜態(tài)頁面中存在大量 URL入口，比如某頁面存在 A標(biāo)簽： a href= /a ， 通過解析 A標(biāo)簽的結(jié)構(gòu)，我們知道這里存在一個新的 url鏈接 似的標(biāo)簽還有： img src=” form action=/ method=POST 北京交通大學(xué)畢業(yè)設(shè)計(jì)（論文） 第 18 頁 frame src= / script src= / ...... 因?yàn)檫@些鏈接是靜止在頁面內(nèi)，屬于比較容易發(fā)現(xiàn)的鏈接類型。在頁面下載回來后，我們甚至可簡單地通過正則表 達(dá)式查找出這些鏈接。 ? 動態(tài)生成的鏈接 這里說的動態(tài)生成的鏈接是指通過 javasript/vbscript生成的鏈接，它們需要通過 script腳本解釋引擎來組裝生成，如下偽代碼： 圖 33 script腳本動態(tài)生成鏈接代碼 從這段偽代碼中，我們無法直接看出來存在什么鏈接，分析代碼可知，變量 URL由 3個部分組成 ， path、 page還有用戶輸入的 id值。明顯地，要知北京交通大學(xué)畢業(yè)設(shè)計(jì)（論文） 第 19 頁 道最后的 URL，需要在輸入框里輸入數(shù)據(jù)并且觸發(fā)這個函數(shù)執(zhí)行。 ? 用戶交互中產(chǎn)生的新 鏈接 HTTP協(xié)議是請求 響應(yīng)式的交互型模型，在 WEB 上深入發(fā)展，請求響應(yīng)的形式更加多樣化。云計(jì)算所使用的技術(shù)也大量使用了 WEB ， ajax數(shù)據(jù)請求方式被廣泛使用， json、 xml等格式的數(shù)據(jù)傳遞給爬蟲的 URL發(fā)現(xiàn)帶來了困難。比如：在 json的任意一個位置，都可能是一個 URL，也可能看著像是 URL，實(shí)際上只是一個不存在的 URL字符串。為了確認(rèn)其是否為 URL，需要觀察其行為表現(xiàn)，這些數(shù)據(jù)從服務(wù)端返回后，客戶端實(shí)際去訪問的 URL字符串才是爬蟲真正需要尋找的目標(biāo)。 ? 存在于第三 方組件里的 URL 在 flash、 silverlight等其他第三方組件里也存在 URL鏈接，這些鏈接的生成需要對應(yīng)的組件來解釋。在 flash應(yīng)用中，我們點(diǎn)擊某些按鈕時，會觸發(fā)一些新的網(wǎng)絡(luò)請求，這些請求是通過內(nèi)嵌的 ActionScript來驅(qū)動的。silverlight以及一些其他第三方組件也是類似。 定向爬蟲定制 本文以人人網(wǎng) 數(shù)據(jù) 為具體案例進(jìn)行分析，因而需要對 人人網(wǎng)特定數(shù)據(jù)進(jìn)行抓取。通過定制人人網(wǎng)定向型爬蟲，抓取指定網(wǎng)站 上的數(shù)據(jù)。 北京交通大學(xué)畢業(yè)設(shè)計(jì)（論文） 第 20 頁 通過 wireshark 抓包法分析 HTTP 協(xié)議 Wireshark（前稱 Ethereal）是一個網(wǎng)絡(luò)封包分析軟件。網(wǎng)絡(luò)封包分析軟件的功能是擷取網(wǎng)絡(luò)封包，并盡可能顯示出最為詳細(xì)的網(wǎng)絡(luò)封包資料。本文通過 Wireshark抓取人人網(wǎng) HTTP協(xié)議 。 先啟動 wireshark程序，在 captureoptions 在彈出界面里選中你的網(wǎng)卡，雙擊，會彈出如下圖所示的設(shè)置規(guī)則處。簡單地，可使用規(guī)則 Host加上人人站點(diǎn)域名。確定之后開始等操作下來就可開始抓包。 圖 34 Wireshark規(guī)則設(shè)置 北京交通大學(xué)畢業(yè)設(shè)計(jì)（論文） 第 21 頁 圖 35 利用 Wireshark抓包過程 分析網(wǎng)站行為 本文通過火狐瀏覽器 +firebug來分析 網(wǎng)站行為： Firebug是火狐瀏覽器下的一款開發(fā)類插件，它可以對 HTML、javascript和 CSS等進(jìn)行查看和編輯。本文主要通過它對網(wǎng)頁頁面代碼進(jìn)行分析，如下圖所示： 北京交通大學(xué)畢業(yè)設(shè)計(jì)（論文） 第 22 頁 圖 36 通過 firebug對網(wǎng)頁代碼進(jìn)行查閱 在觀察到網(wǎng)頁代碼后，可制定對應(yīng)的定向爬蟲實(shí)現(xiàn)方案，例如從哪個頁面開始，需要從這個頁面中獲得什么關(guān)鍵信息，哪些信息會在下一個