本鼠鼠在大三下學期的資訊內容安全課程設計報告，我的選題是使用聚類演算法實作網頁聚類
希望對你的課設或者專案有幫助
文章目錄
- 一、選題內容
- 二、方案設計內容
- 2.1、決議網站
- 2.2、過濾停用詞
- 2.3、分詞處理
- 2.4、權重值及向量化表示
- 2.5、聚類初始化處理
- 2.6、聚類實施程序
- 三、流程圖設計
- 四、系統實作
- 4.1決議網站內容
- 4.2、過濾停用詞
- 4.3分詞處理
- 4.4、權重值及向量化表示
- 4.4.1、特征項頻率TF（TermFrequeney）
- 4.4.2、倒排檔案頻率IDF（InverseDocumentFrequency）
- 4.5、K-Means演算法簡介
- 4.5.1 K-Means演算法優點
- 4.5.2 K-Means演算法缺點
- 4.6、對K-Means演算法初始化的改進
- 4.7、K-Means聚類實施程序
- 4.7.1相似度計算公式的選取
- 4.7.2余弦相似度公式的優點
- 4.7.3聚類程序
- 4.8顯示聚類結果
- 五、程式演示
- 六、分析總結
- 6.1、比較不同距離演算法
- 6.2、比較不同的權重距離公式
- 6.3、比較不同的初始化方法
- 6.4、分析不足之處及改進建議
- 6.4.1距離演算法嘗試較少
- 6.4.2沒有嘗試其他聚類演算法
- 6.4.3沒有考慮網頁標簽的權重
- 6.4.4輸出UI界面的兼容性差
- 七、關鍵代碼展示
- **主程式段**
- **K-Means實作**
一、選題內容
該題目給出一組網頁地址，然后對指定的網頁按內容聚成3類，
網頁地址如下：
步驟：
1.抓取指定網址的原始碼；
2.決議網頁文章內容；
3.對文章內容進行分詞，并轉換成向量表示；(可以考慮用詞袋法或TF.IDF，)
4.選取合適的距離公式和聚類演算法進行聚類，要求聚成3類，(可以用歐式距離或余弦距離等，聚類方法可以考慮用K-means方法等，)
要求：
1.顯示決議后網頁文章的內容；(步驟2)
2.顯示文章對應的向量；(步驟3)
3.顯示文章向量與三個類的類中心的距離，(步驟4)
4.顯示最終的分類結果，即哪些網址分為一類，(步驟4)
3、4結果展示可以如下表所示：
二、方案設計內容
選題：網頁聚類系統的設計與實作
任務要求：
（1）顯示決議后網頁文章的內容；
（2）顯示文章對應的向量；
（3）顯示文章向量與三個類的類中心的距離，
（4）顯示最終的分類結果，即哪些網址分為一類，
2.1、決議網站
讀取指定若干網頁的url并決議出其原始碼以及網頁內容，
2.2、過濾停用詞
其中網頁內容中有許多諸如停用詞之類的噪聲資訊，不利于我們對關鍵資訊的把控，所以要通過一個停用詞詞庫來過濾掉這些通用詞，
2.3、分詞處理
根據現有的詞庫字典對過濾掉停用詞的網頁文本內容進行分詞處理，
2.4、權重值及向量化表示
每個網頁將分詞后的詞組資料轉化成字串陣列儲存起來，通過計算每個網頁詞組資料的權重值TF.IDF并將其結果轉化成向量化表示顯示，選用余弦距離公式計算不同網頁權重值的多維向量，
2.5、聚類初始化處理
選用K-means演算法作為聚類演算法，思路如下：任選一個物件作為第一個聚類的中心，計算和第一個中心最遠的物件作為第二個中心,分別計算剩下的物件與第一個和第二個物件的距離，設D1是該物件距離第一個中心的距離，D2是該物件距離第二個中心的距離，從中取Max（Min（D1，D2）），即剩下的物件中距離兩個聚類兩個中心距離較小值中的最大值，該最大值所在的物件作為第三個中心，
2.6、聚類實施程序
分配各個資料物件到最近的簇中，重新計算各個聚類的中心，即該簇成員中向量和的平均值，若中心收斂則輸出結果，否則將重新分配各個簇的中心重復上述步驟，直到簇的中心收斂，即中心位置不變的時候輸出最終聚類的結果，
三、流程圖設計
四、系統實作
本系統程式采用C#語言，運行環境為Windows10，編譯環境為Microsoft Visual C#
4.1決議網站內容
決議網頁內容時使用的是HTMLAgilityPack(1.11.34)，在對網站決議的時候，由于網站格式的不同，決議網站的方法也不同，
一般來說，URL只能使用英文字母、阿拉伯數字和某些標點符號，不能使用其他文字和符號，這是因為網路標準RFC 1738做了硬性規定，這意味著，如果網站內容中有漢字，就必須編碼后使用，常見的中文編碼有UTF-8、GB2313編碼，GBK通常指GB2312編碼 只支持簡體中文字，utf通常指UTF-8，支持簡體中文字、繁體中文字、英文、日文、韓文等語言，支持文字更廣，使用HTMLAgilityPack包時要先通過預先設定好的編碼方式對網站內容進行對應的決議，不同的編碼方式并不互相兼容，出現亂碼則意味著編碼方式不正確，
4.2、過濾停用詞
通過使用字典樹Trie實作，字典樹是一種樹形結構，是哈希樹的變種，它的設計和實作是比較簡單的，一般來說字典樹的典型應用是統計以及排序較多的的字串，還包括對文本詞頻的統計，它的優點是：最大限度地減少低效的重復的字串比較，字典樹的根節點不包含字符，而除根節點外每一個節點都只包含一個字符， 從根節點到某一葉子節點，路徑上經過的字符連接起來，為該節點對應的字串， 每個節點的所有子節點包含的字符都不相同，其示意圖如下：
通過已有的停用詞庫建立一個停用詞庫字典樹，對決議出來的網站內容進行匹配并過濾，該過濾停用詞庫操作的主要目的是為了除去文本中無關緊要的干擾資訊和噪音資訊，讓有價值的資訊更受關注，從而在提高聚類結果的準確性的同時較大程度地降低了計算的資源消耗，
4.3分詞處理
在對決議出來的網頁內容過濾后需要對該內容進行進一步地分詞處理，通過已有的龐大的大概包含2萬多條詞語的詞庫字典建立一個字典樹，字典在生成trie樹的同時, 也把每個詞的出現次數轉換為了頻率，根據給定的詞典數進行查詞匹配操作, 生成幾種可能的句子切分，從句子中某個詞的開始位置,到該句子的結尾，每個開始位置作為字典的鍵, 其中保存了可能的詞語的結束位置，通過匹配字典得到詞, 開始位置加上詞語的長度便得到結束位置，基于前綴詞典數可以實作高效的詞圖掃描，將生成句子中漢字所有可能成詞情況所構成的有向無環圖(DAG)如下圖所示：
其次，采用了動態規劃查找最大概率路徑，找出基于詞頻的最大切分組合查找待分詞句子中已經切分好的詞語, 對該詞語查找該詞語出現的頻率，即次數除以總數, 如果字典中沒有該詞就把詞典中出現頻率最小的那個詞語的頻率作為該詞的頻率,根據動態規劃查找最大概率路徑的方法, 對句子從右往左反向計算最大概率，類似于逆向最大匹配，最后得到最大概率路徑對應的切分組合.
4.4、權重值及向量化表示
本程式使用的權重演算法是TF.IDF，下面詳細介紹它的具體內容，
4.4.1、特征項頻率TF（TermFrequeney）
特征項頻率是指特征項在檔案中出現的次數，特征項可以是字、詞、短語，也可以是經過語意概念詞典進行語意歸并或概念特征提取后的語意單元，不同類別的檔案，在某些特征項的出現頻率上有很大差異，因此頻率資訊是文本分類的重要參考之一，在最初的文本自動分類中，檔案向量就是用來構造的，
4.4.2、倒排檔案頻率IDF（InverseDocumentFrequency）
只使用TF會導致兩種問題：
（1）檔案中大量出現一些對分類沒有貢獻的虛詞如：感嘆詞、介詞、連詞等，如果這些詞出現的頻率過大，在特征提取的時候將這些詞選做了特征詞條，而對分類產生負面的影響，
（2）特征詞的好壞是看能否代表類和檔案的屬性，TF值高的特征詞，如果在所有的檔案中值都高，那就很難說這樣的特征詞到底代表哪個檔案，因此單純使用是有很大的局限性的，人們往往將反檔案頻率和結合使用，
倒排檔案頻率是特征項在檔案集分布情況的量化，其公式如下：
其中為檔案集中的總檔案數，為出現特征項的檔案數，
IDF演算法的核心思想是，在大多數檔案中都出現的特征項不如只在小部分檔案中出現的特征項重要，演算法能夠榷訓一些在大多數檔案中都出現的高頻特征項的重要度，同時增強一些在小部分檔案中出現的低頻特征項的重要性，一個有效的分類特征項應該既能體現所屬類別的內容，又能將該類別同其他類別相區分，所以，在實際應用中與通常是聯合使用的，與的聯合公式如公式所示，其中代表類別號：
TF.IDF公式有許多變種形式，考慮文本長度對特征權值的影響以及防止聚類程序中個別權值很高的項對其他項的抑制作用，在計算各項權重的時候，應對特征項的權值作歸一化處理和適當的均衡處理，本程式采用的是對特征項權值進行均衡處理的公式，如下：
該演算法的主要思想是：如果某個詞或短語，在一個檔案中出現的頻率高，并且在其他檔案中很少出現，則認為此詞或者短語具有很好的類別區分能力，適合用來進行分類；的主要思想是：如果包含詞條的檔案越少，也就是越小，越大，說明詞條具有很好的類別區分能力，
4.5、K-Means演算法簡介
K-Means演算法是一種典型的基于劃分的聚類分析演算法，演算法簡單、收斂速度快，被廣泛地應用于各個領域，雖然演算法具有較強的區域搜索能力，但因對初始聚類中心敏感，容易陷入區域最優，從而影響聚類結果，其基本思想是：根據聚簇數，隨機選取個點作為初始聚類中心，依據每個點與初始聚類中心的距離，將所有點劃分到個簇中，以每個簇的質心作為新的聚類中心，不斷地迭代以上的步驟，對簇進行調整，使簇內物件之間的距離盡可能小，而簇間物件之間的距離盡可能大，直至目標函式收斂，
4.5.1 K-Means演算法優點
K-Means演算法不依賴于順序，即一旦給定一個初始中心分布，無論樣本點的順序如何，生成的聚簇都一樣，對于演算法來說，當結果簇是密集的，而簇類與簇類之間區別明顯時，它的聚類效果較好，而且其聚類速度較快，
4.5.2 K-Means演算法缺點
（1）初聚類個數k的初始化
K-Means演算法的聚類結果依賴于初始值的設定，需要用戶事先給出簇的個數，這樣一旦用戶對待聚類的資料集不了解時，是很難給出合適的值的，很可能會將原本屬于同類的物件強行拆分到不同簇中，或者原本不屬于一類的物件卻被強行合并至一個簇中，
（2）初始聚類中心的選擇
K-Means演算法的結果依賴于由初始聚類中心出發所遇到的第一個區域極值點，不同的初始聚類中心很可能導致截然不同的聚類結果，一旦初值選擇不好，可能無法得到有效的聚類結果，這樣的依賴性就導致聚類結果的不穩定性，且容易陷入區域最優而非全域最優，
4.6、對K-Means演算法初始化的改進
本課設預先給定了聚類個數k=3，所以我著重考慮了初始中心選擇的設計方法，在聚類演算法中，初始化是很重要的一個步驟，初始設定的合理性很大程度上直接關系到結果的準確性，如果初始設定不合理，很可能讓計算程式陷入區域最優的情況，本程式初始化采用最大最小距離聚類演算法，它是模式識別領域中一種比較簡單的聚類分析方法，最大最小原則依據待聚類物件的相似情況選擇距離盡可能遠的物件作為初始聚點最大最小距離聚類演算法見演算法，
最大最小距離聚類演算法的具體實作程序如下：
1）建立網頁資料物件集Sn
2）任取其中一個網頁物件作為第一個初始化聚類中心Z1
3）計算所有其他網頁資料物件到Z1 的距離，取其中中距離最大的值所在的網頁資料物件作為第二個初始化聚類中心Z2
4）計算剩下所有網頁資料物件到Z1 和Z2的距離，選取剩下的網頁資料物件到Z1 、Z2較小值并組合成一個集合，從該集合中找出最大值對應的網頁資料物件作為第三個初始化劇烈中心Z3
4.7、K-Means聚類實施程序
4.7.1相似度計算公式的選取
選取的相似度公式是余弦相似度公式，即兩向量夾角的余弦作為相似度度量，主要特征是相似度計算不依賴于向量的幅值，公式如下：
4.7.2余弦相似度公式的優點
他的優點在于其對高維資料中空值的合理性處理，而在高維空間中的某些屬性上出現的空值是很普遍的現象，如本文面向的文本資料，每篇文本可以用詞頻向量表示，由于詞表中的詞可能很多，而每篇文本一般只包含其中有限的一部分詞，這樣在代表其他未包含的詞的維上就為空，為了向量的比較方便，我們往往給這些空值置0，在使用余弦公式度量時，只是在兩個向量中都有值的維才對相似度有貢獻，而其中一個向量為慷訓者兩者都為空的維，經過點乘以后都變成了0，
4.7.3聚類程序
1）在初始化完三個聚類中心后，比較每組網頁物件資料與該中心的距離，將最近的物件資料添加到對應聚類中心的成員變數中，
2）更新當前聚類中心的資料向量的均值，計算聚類中心均值的方法是：將該簇成員的資料向量累加并除以成員的個數
3）重新計算每個網頁資料物件到三個中心的平均值的距離，若網頁距離最近的中心物件發生變化則更新對應中心的成員變數
4）若更新完各聚類中心的成員變數后結果沒有發生變化，則認為結果是收斂的，輸出聚類結果，否則繼續執行程序2，直至收斂為止
4.8顯示聚類結果
按題目要求，顯示的結果需要進行表格化顯示，本程式采用C#WPF實作，具有良好的人機互動UI界面，表格資訊的內容包括：聚類中心X、Y、Z對應的網頁編號以及網頁分別與三個中心的距離，
由于上述采用的是相似度計算公式，所以實際意義上的距離是與相似度成反比的，而余弦距離公式的結果區間在[0.1]，其中0表示兩個資料物件完全不同，1表示兩個資料物件完全相同，所以我們在輸出顯示距離的時候用1減去相似度值，就可以實作實際意義上距離指標的度量，0代表完全一致，1代表距離無限大，
五、程式演示
程式主界面如圖所示：
包含了四個功能：
1）顯示決議后網站文章的內容
本程式默認網址頁數是9，其中url資料的默認值是題目要求的九個網站，通過HTMLAgilityPack包抓取指定的9個網址后顯示網址內容，程式運行結果如下圖所示：
2）顯示文章對應的向量
通過改進后的公式計算每個網址的TF.iDF值后將其結果向量化輸出顯示：
首先在建立每個網址的詞組陣列資料后，創建一個包含所有網址的詞組陣列的資料，并以該詞組資料為單位每行依次顯示本網站對應詞組的權重值，
3）以表格形式輸出聚類結果
按照題目要求的顯示界面，本程式以類似表格輸出的形式展示，其中每個中心所在的網頁編號以及各自與X、Y、Z中心的距離如圖所示，為了方便了解具體分類的情況，在聚類結束后，將距離每個中心最近的網頁的前五個最高的權重值所在的詞語作為關鍵詞顯示出來，如圖所示：
4）重置網頁資料
若想重置網頁資料可以手動輸入或者點擊“重置網頁”按鈕從文本檔案txt中讀取，默認的讀取路徑是程式Debug目錄下的web.txt檔案，這一設定的主要目的是為了避免手動輸入9個網址，提高了便利，
在嘗試題目要求的九個網站后，我還嘗試了其他九個網站，其網站url保存在本地txt檔案中方便讀取，經驗證，結果是準確的
六、分析總結
6.1、比較不同距離演算法
本次課設實作的是網頁聚類程式，其中聚類演算法選擇的是K-Means，相似度計算選擇的是余弦距離公式，檔案權重值選用的是改進后的TF.IDF，在后續的實施程序中，曾嘗試過歐氏距離算發，由于在歐式距離演算法中每個坐標對歐氏距離的貢獻是同等的，通過斷點除錯發現計算結果帶有較大波動區間，并且結果不準確，隨后放棄該演算法，采用余弦距離公式，
以下是采用歐式距離得出的結果：
以下是采用余弦距離得出的結果：
6.2、比較不同的權重距離公式
此外，改進后的TF.iDF演算法是為了考慮文本長度對特征權值的影響以及防止聚類程序中個別權值很高的項對其他項的抑制作用，
以下是選用傳統的TF*IDF作為權重值的結果，傳統演算法如下：
輸出結果：
以下是選用改進的TF.IDF作為權重值的結果,改進演算法如下：
輸出結果：
可以明顯的看到使用傳統距離公式的結果并不準確，并且每簇資料中距離也有不合理的地方，以計算與X的距離為例，該演算法結果顯示距離X較近的點有四個，并且距離最近的點沒有在該聚類中，通過斷點除錯發現，出現該問題的原因是個別文本長度與其他文本長度差距較大，并且它對特征權值的值波動較大，從而造成聚類程序中該項對其他項產生抑制作用，
其次，由于聚類結果是收斂即輸出，由于該演算法對權重把控的不準確性導致個別錯誤資料也跟著收斂了，
而使用改進后的演算法可以看到即使網頁6與中心X的距離相比于其他不是同類的網站來說更近但是沒有影響到真正距離近的網站，也就是距離是0.8而不是0.9，而傳統演算法中網頁6距離中心X的距離是0.4，可以明顯地看到改進后演算法的優勢，
6.3、比較不同的初始化方法
在上文中已經提到了初始化的重要性，好的初始化中心設定是計算成功的一半，聚類的一大基本原則是中心簇中的資料盡可能接近，而不同中心簇的資料盡可能不同，因此初始化時需要選擇最遠的三個中心，本文的初始化演算法采用最大最小距離演算法，并對隨機初始化中心和使用該演算法做了比較，結果表明，使用了最大最小距離演算法后結果的準確性大大提高，
6.4、分析不足之處及改進建議
6.4.1距離演算法嘗試較少
本次實作雖然對不同的距離演算法和權重計算方式產生了比較，但是也是由于最初使用的方法并不理想才選擇換一種距離演算法的，還有許多諸如絕對值距離法、切比雪夫距離法以及Nsim距離法沒有考慮，
6.4.2沒有嘗試其他聚類演算法
由于在設計K-Means演算法之后就產生了正確的結果，所以只實作了K-Means演算法沒有考慮其他方式，此外據查閱資料發現聚類演算法除了本文使用的基于劃分的K-Means演算法外常用的聚類演算法還有基于層次的聚類演算法、基于密度的方法以及基于模型的聚類演算法，可以改進的地方是多嘗試其他演算法并比較哪一個演算法更適合網頁聚類，
6.4.3沒有考慮網頁標簽的權重
其次，在考慮計算權重時，只是計算TF以及IDF對應的值并進行相應的改進，沒有考慮到網頁是半結構化的，每一個網頁內容都有相應的標簽，每個標簽的權重值應該是不一樣的，比如標題內容的權重值應該比正文內容的權重值大等，這一思想事先考慮到了但是沒有距離落實，
6.4.4輸出UI界面的兼容性差
最后，根據題目的要求，本程式的UI界面是針對9個網頁3個聚類中心而設計的，雖然不同個數的網頁在演算法執行后是沒有問題的，是能夠計算出聚類結果的，但是由于輸出只能是9個網頁3個中心，后續沒有進一步優化界面達到兼容不同個數網頁以及不同個數的聚類中心，尚可改進，
七、關鍵代碼展示
主程式段
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.IO;
using System.Linq;
using System.Net;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
using HtmlAgilityPack;
using JiebaNet.Analyser;
using JiebaNet.Segmenter;
using HtmlDocument = HtmlAgilityPack.HtmlDocument;
namespace K_means_Web_Cluster
{
public partial class Form1 : Form
{
private string[] urls =
{
"http://blog.sina.com.cn/s/blog_59d698c90102zfct.html",
"http://blog.sina.com.cn/s/blog_9c2fe26f0102z3ja.html?tj=fina",
"http://blog.sina.com.cn/s/blog_6479dc5b0102ymb3.html",
"http://blog.sina.com.cn/s/blog_59d698c90102zfd2.html",
"http://blog.sina.com.cn/s/blog_59d698c90102zfcl.html",
"http://blog.sina.com.cn/s/blog_14fdd56530102yknf.html?tj=tiyu",
"http://blog.sina.com.cn/s/blog_62dc4e590102zot3.html?tj=fina",
"http://blog.sina.com.cn/s/blog_1506181220102z9x9.html?tj=fina",
"http://blog.sina.com.cn/s/blog_683c082b0102z3qc.html"
};
private Trie StopTree = new Trie();
private string[] A1;
private double[] IDFs;
private Web[]Webs;
private string[] ALLterms;
private string[][] _2Ddocs;
private string[][] _2Dterms;
public Form1()
{
InitializeComponent();
}
public void InitializeWebs()
{
_2Ddocs = new string[9][];
_2Dterms = new string[9][];
List<string> AllArr = new List<string> { };
StopTree.initialize();
Webs = new Web[9];
var web = new HtmlWeb();
web.OverrideEncoding = Encoding.GetEncoding("utf-8");
int LL = 0;
for (int i = 0; i < 9; i++)
{
var doc = web.Load(urls[i]);
var node = doc.DocumentNode;
var segmenter = new JiebaSegmenter();
var segments = segmenter.Cut(node.InnerText);
string[] ids = segments.ToArray();
ids = DelectStr(ids);
_2Ddocs[i] = ids;
_2Dterms[i] = GetDistinctWords(_2Ddocs[i]);
LL = _2Dterms[i].Length;
for (int k = 0; k < LL; k++)
{
if (!AllArr.Contains(_2Dterms[i][k]))
{
AllArr.Add(_2Dterms[i][k]);
}
}
}
ALLterms = AllArr.ToArray();
for (int i = 0; i < 9; i++)
{
Webs[i] = new Web(_2Ddocs[i], ALLterms);
}
int AllTermsLen = ALLterms.Length;
IDFs = new double[AllTermsLen];
int tt = 0;
for (int i = 0; i < AllTermsLen; i++)
{
for (int k = 0; k < 9; k++)
{
tt += Webs[k].IsContain(ALLterms[i]);
}
IDFs[i] = Math.Log10(0.01 + ((double)9 / (double)(tt)));
tt = 0;
}
for (int i = 0; i < 9; i++)
{
double aa = 0;
Webs[i].iTFIDFs = new double[AllTermsLen];
for (int k = 0; k < AllTermsLen; k++)
{
aa += Webs[i].iTFs[k] * IDFs[k] * IDFs[k];
}
for (int k = 0; k < AllTermsLen; k++)
{
Webs[i].iTFIDFs[k] = Math.Sqrt
(Webs[i].iTFs[k] * IDFs[k] / aa);
}
}
}
private void button1_Click(object sender, EventArgs e)
{
string url = urls[1];
Encoding enc = Encoding.GetEncoding("utf-8");
WebClient webClient = new WebClient();
webClient.Credentials = CredentialCache.DefaultCredentials;
byte[] pagedata = webClient.DownloadData(url);
string pagehtml = enc.GetString(pagedata);
richTextBox1.AppendText(pagehtml);
var web = new HtmlWeb();
web.OverrideEncoding = Encoding.GetEncoding("utf-8");
var doc = web.Load(url);
HtmlNode node = doc.DocumentNode;
richTextBox2.AppendText(node.InnerText);
}
private void button2_Click(object sender, EventArgs e)
{
StopTree.initialize();
var segmenter = new JiebaSegmenter();
var segments = segmenter.Cut(richTextBox2.Text);
richTextBox1.Clear();
string[] ids = segments.ToArray();
ids = DelectStr(ids);
A1 = ids;
for (int i = 0; i < ids.Length; i++)
{
richTextBox1.AppendText(ids[i] + '\n');
}
}
public string[] DelectStr(string[] str)
{
List<string> Arr = new List<string> { };
for (int i = 0; i < str.Length; i++)
{
if (str[i] == "\n" || str[i] == "" ||
str[i] == " " || str[i] ==" " || str[i] == "\r\n" || StopTree.Contains(str[i]) || str[i] == "\t")
{
;
}
else
{
Arr.Add(str[i]);
}
}
return Arr.ToArray();
}
private void button3_Click(object sender, EventArgs e)
{
InitializeWebs();
WawaKMeans kmeans = new WawaKMeans(Webs, 3);
kmeans.Start();
WawaCluster[] clusters = kmeans.Clusters;
foreach (WawaCluster cluster in clusters)
{
List<int> members = cluster.CurrentMembership;
richTextBox3.AppendText('\n'+"-----------------"+'\n');
foreach (int i in members)
{
richTextBox3.AppendText(i.ToString());
}
}
}
public static string[] GetDistinctWords(String[] input)
{
if (input == null)
return new string[0];
else
{
List<string> list = new List<string>();
for (int i = 0; i < input.Length; i++)
if (!list.Contains(input[i])) // N-GRAM SIMILARITY?
list.Add(input[i]);
return list.ToArray();
}
}
public double ComWebDistance(Web X,Web Y)
{
double[] x = X.iTFIDFs;
double[] y = Y.iTFIDFs;
int len = x.Length;
double dis=0;
for(int i=0;i<len;i++)
{
dis += (
(double)(1)) /
((double)(1 + Math.Abs(x[i] - y[i]))
);
}
dis /= len;
return dis;
}
}
}
K-Means實作
using System;
namespace K_means_Web_Cluster
{
public class WawaKMeans
{
/// <summary>
/// 資料的數量
/// </summary>
readonly int _webCount;
/// <summary>
/// 原始資料
/// </summary>
readonly Web[] _webs;
/// <summary>
/// 聚類的數量
/// </summary>
readonly int _k;
/// <summary>
/// 聚類
/// </summary>
double[,] WebDistanceCache;
/// <summary>
/// 網頁距離快取
/// </summary>
private readonly WawaCluster[] _clusters;
internal WawaCluster[] Clusters
{
get { return _clusters; }
}
/// <summary>
/// 定義一個變數用于記錄和跟蹤每個資料點屬于哪個群聚類
/// _clusterAssignments[j]=i;// 表示第 j 個資料點物件屬于第 i 個群聚類
/// </summary>
readonly int[] _clusterAssignments;
/// <summary>
/// 定義一個變數用于記錄和跟蹤每個資料點離聚類最近
/// </summary>
private readonly int[] _nearestCluster;
/// <summary>
/// 定義一個變數，來表示資料點到中心點的距離,
/// 其中—_distanceCache[i][j]表示第i個資料點到第j個群聚物件中心點的距離；
/// </summary>
private readonly double[,] _distanceCache;
public WawaKMeans(Web[]webs, int K)
{
_webs = webs;
_webCount = webs.Length;
_k = K;
_clusters = new WawaCluster[K];
_clusterAssignments = new int[_webCount];
_nearestCluster = new int[_webCount];
_distanceCache = new double[_webCount, _k];
InitRandom();
}
public void Start()
{
while (true)
{
//1、重新計算每個聚類的均值
for (int i = 0; i < _k; i++)
{
_clusters[i].UpdateMean(_webs);
}
//2、計算每個資料和每個聚類中心的距離
for (int i = 0; i < _webCount; i++)
{
for (int j = 0; j < _k; j++)
{
double dist = ((double)(1))/(getCosDistance(_webs[i], _clusters[j].Mean));
_distanceCache[i, j] = dist;
}
}
//3、計算每個資料離哪個聚類最近
for (int i = 0; i < _webCount; i++)
{
_nearestCluster[i] = nearestCluster(i);
}
//4、比較每個資料最近的聚類是否就是它所屬的聚類
//如果全相等表示所有的點已經是最佳距離了，直接回傳；
int k = 0;
for (int i = 0; i < _webCount; i++)
{
if (_nearestCluster[i] == _clusterAssignments[i])
k++;
}
if (k == _webCount)
break;
//5、否則需要重新調整資料點和群聚類的關系，調整完畢后再重新開始回圈；
//需要修改每個聚類的成員和表示某個資料屬于哪個聚類的變數
for (int j = 0; j < _k; j++)
{
_clusters[j].CurrentMembership.Clear();
}
for (int i = 0; i < _webCount; i++)
{
_clusters[_nearestCluster[i]].CurrentMembership.Add(i);
_clusterAssignments[i] = _nearestCluster[i];
}
}
}
/// <summary>
/// 計算某個資料離哪個聚類最近
/// </summary>
/// <param name="ndx"></param>
/// <returns></returns>
int nearestCluster(int ndx)
{
int nearest = -1;
double min = Double.MaxValue;
for (int c = 0; c < _k; c++)
{
double d = _distanceCache[ndx, c];
if (d < min)
{
min = d;
nearest = c;
}
}
if (nearest == -1)
{
;
}
return nearest;
}
/// <summary>
/// 計算某資料離某聚類中心的距離
/// </summary>
/// <param name="coord"></param>
/// <param name="center"></param>
/// <returns></returns>
static double getDistance(Web coord, double[] center)
{
double[] x = coord.iTFIDFs;
double[] y = center;
int len = x.Length;
double dis = 0;
for (int i = 0; i < len; i++)
{
dis += (
(double)(1)) /
((double)(1 + Math.Abs(x[i] - y[i]))
);
}
dis /= len;
return dis;
}
/// <summary>
/// 隨機初始化k個聚類
/// </summary>
///
static public double ComWebDistance(Web X, Web Y)
{
double[] x = X.iTFIDFs;
double[] y = Y.iTFIDFs;
int len = x.Length;
double dis = 0;
for (int i = 0; i < len; i++)
{
dis += (
(double)(1)) /
((double)(1 + Math.Abs(x[i] - y[i]))
);
}
dis /= len;
return dis;
}
public static double ComputeWebCosineSimilarity(Web X, Web Y)
{
double[] vector1 = X.iTFIDFs;
double[] vector2 = Y.iTFIDFs;
if (vector1.Length != vector2.Length)
throw new Exception("DIFER LENGTH");
double denom = (VectorLength(vector1) * VectorLength(vector2));
if (denom == 0D)
return 0D;
else
return (InnerProduct(vector1, vector2) / denom);
}
static double getCosDistance(Web coord, double[] center)
{
double[] vector1 = coord.iTFIDFs;
double[] vector2 = center;
if (vector1.Length != vector2.Length)
throw new Exception("DIFER LENGTH");
double denom = (VectorLength(vector1) * VectorLength(vector2));
if (denom == 0D)
return 0D;
else
return (InnerProduct(vector1, vector2) / denom);
}
public static double VectorLength(double[] vector)
{
double sum = 0.0D;
for (int i = 0; i < vector.Length; i++)
sum = sum + (vector[i] * vector[i]);
return (double)Math.Sqrt(sum);
}
public static double InnerProduct(double[] vector1, double[] vector2)
{
if (vector1.Length != vector2.Length)
throw new Exception("DIFFER LENGTH ARE NOT ALLOWED");
double result = 0D;
for (int i = 0; i < vector1.Length; i++)
result += vector1[i] * vector2[i];
return result;
}
private void InitRandom()
{
WebDistanceCache = new double[_webCount, _webCount];
for(int i=0;i<_webCount;i++)
{
for(int k=0;k<_webCount;k++)
{
WebDistanceCache[i,k] =
(((double)(1))/ComputeWebCosineSimilarity(_webs[i],_webs[k]));
}
}
Random r = new Random();
int tt = r.Next(9);
_clusterAssignments[tt] = 0;
_clusters[0] = new WawaCluster(tt, _webs[tt].iTFIDFs);
double LongestValue = double.MinValue;
int LongestWeb = 0;
for(int i=0;i<_webCount;i++)
{
if(WebDistanceCache[tt,i]> LongestValue)
{
LongestValue = WebDistanceCache[tt,i];
LongestWeb = i;
}
}
_clusters[1] = new WawaCluster(LongestWeb, _webs[LongestWeb].iTFIDFs);
double[] Minarr = new double[_webCount];
double[] MinarrValue = new double[_webCount];
/* double NearestValue = double.MaxValue;
int NearestWeb = 0;*/
for(int i=0;i<_webCount;i++)
{
if(WebDistanceCache[i,tt]<=WebDistanceCache[i,LongestWeb])
{
MinarrValue[i] = WebDistanceCache[i,tt];
Minarr[i] = tt;
}
else
{
MinarrValue[i] = WebDistanceCache[i,LongestWeb];
Minarr[i] = LongestWeb;
}
}
int xx = 0;
double MAX = double.MinValue;
for (int i = 0; i < _webCount; i++)
{
if(MinarrValue[i]>MAX)
{
MAX = MinarrValue[i];
xx = i;
}
}
double Sita = MAX / LongestValue;
_clusters[2] = new WawaCluster(xx, _webs[xx].iTFIDFs);
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/299923.html
標籤：其他
上一篇：簡單網路預警系統設計與實作