簇演算法
⑴ 八:聚類演算法K-means(20191223-29)
學習內容:無監督聚類演算法K-Means
k-means:模型原理、收斂過程、超參數的選擇
聚類分析是在數據中發現數據對象之間的關系,將數據進行分組,組內的相似性越大,組間的差別越大,則聚類效果越好。
不同的簇類型: 聚類旨在發現有用的對象簇,在現實中我們用到很多的簇的類型,使用不同的簇類型劃分數據的結果是不同的。
基於原型的: 簇是對象的集合,其中每個對象到定義該簇的 原型 的距離比其他簇的原型距離更近,如(b)所示的原型即為中心點,在一個簇中的數據到其中心點比到另一個簇的中心點更近。這是一種常見的 基於中心的簇 ,最常用的K-Means就是這樣的一種簇類型。 這樣的簇趨向於球形。
基於密度的 :簇是對象的密度區域,(d)所示的是基於密度的簇,當簇不規則或相互盤繞,並且有早上和離群點事,常常使用基於密度的簇定義。
關於更多的簇介紹參考《數據挖掘導論》。
基本的聚類分析演算法
1. K均值: 基於原型的、劃分的距離技術,它試圖發現用戶指定個數(K)的簇。
2. 凝聚的層次距離: 思想是開始時,每個點都作為一個單點簇,然後,重復的合並兩個最靠近的簇,直到嘗試單個、包含所有點的簇。
3. DBSCAN: 一種基於密度的劃分距離的演算法,簇的個數有演算法自動的確定,低密度中的點被視為雜訊而忽略,因此其不產生完全聚類。
不同的距離量度會對距離的結果產生影響,常見的距離量度如下所示:
優點:易於實現
缺點:可能收斂於局部最小值,在大規模數據收斂慢
演算法思想:
選擇K個點作為初始質心
repeat
將每個點指派到最近的質心,形成K個簇
重新計算每個簇的質心
until 簇不發生變化或達到最大迭代次數
這里的「重新計算每個簇的質心」,是根據目標函數來計算的,因此在開始時要考慮 距離度量和目標函數。
考慮歐幾里得距離的數據,使用 誤差平方和(Sum of the Squared Error,SSE) 作為聚類的目標函數,兩次運行K均值產生的兩個不同的簇集,使用SSE最小的那個。
k表示k個聚類中心,ci表示第幾個中心,dist表示的是歐幾里得距離。
這里有一個問題就是為什麼,我們更新質心是讓所有的點的平均值,這里就是SSE所決定的。
k均值演算法非常簡單且使用廣泛,但是其有主要的兩個缺陷:
1. K值需要預先給定 ,屬於預先知識,很多情況下K值的估計是非常困難的,對於像計算全部微信用戶的交往圈這樣的場景就完全的沒辦法用K-Means進行。對於可以確定K值不會太大但不明確精確的K值的場景,可以進行迭代運算,然後找出Cost Function最小時所對應的K值,這個值往往能較好的描述有多少個簇類。
2. K-Means演算法對初始選取的聚類中心點是敏感的 ,不同的隨機種子點得到的聚類結果完全不同
3. K均值演算法並不是很所有的數據類型。 它不能處理非球形簇、不同尺寸和不同密度的簇,銀冠指定足夠大的簇的個數是他通常可以發現純子簇。
4. 對離群點的數據進行聚類時,K均值也有問題 ,這種情況下,離群點檢測和刪除有很大的幫助。
下面對初始質心的選擇進行討論:
當初始質心是隨機的進行初始化的時候,K均值的每次運行將會產生不同的SSE,而且隨機的選擇初始質心結果可能很糟糕,可能只能得到局部的最優解,而無法得到全局的最優解。
多次運行,每次使用一組不同的隨機初始質心,然後選擇一個具有最小的SSE的簇集。該策略非常的簡單,但是效果可能不是很好,這取決於數據集合尋找的簇的個數。
關於更多,參考《數據挖掘導論》
為了克服K-Means演算法收斂於局部最小值的問題,提出了一種 二分K-均值(bisecting K-means)
將所有的點看成是一個簇
當簇小於數目k時
對於每一個簇
計算總誤差
在給定的簇上進行K-均值聚類,k值為2 計算將該簇劃分成兩個簇後總誤差
選擇是的誤差最小的那個簇進行劃分
在原始的K-means演算法中,每一次的劃分所有的樣本都要參與運算,如果數據量非常大的話,這個時間是非常高的,因此有了一種分批處理的改進演算法。
使用Mini Batch(分批處理)的方法對數據點之間的距離進行計算。
Mini Batch的好處:不必使用所有的數據樣本,而是從不同類別的樣本中抽取一部分樣本來代表各自類型進行計算。n 由於計算樣本量少,所以會相應的減少運行時間n 但另一方面抽樣也必然會帶來准確度的下降。
聚類試圖將數據集中的樣本劃分為若干個通常是不相交的子集,每個子集成為一個「簇」。通過這樣的劃分,每個簇可能對應於一些潛在的概念(也就是類別);需說明的是,這些概念對聚類演算法而言事先是未知的,聚類過程僅能自動形成簇結構,簇對應的概念語義由使用者來把握和命名。
聚類是無監督的學習演算法,分類是有監督的學習演算法。所謂有監督就是有已知標簽的訓練集(也就是說提前知道訓練集里的數據屬於哪個類別),機器學習演算法在訓練集上學習到相應的參數,構建模型,然後應用到測試集上。而聚類演算法是沒有標簽的,聚類的時候,需要實現的目標只是把相似的東西聚到一起。
聚類的目的是把相似的樣本聚到一起,而將不相似的樣本分開,類似於「物以類聚」,很直觀的想法是同一個簇中的相似度要盡可能高,而簇與簇之間的相似度要盡可能的低。
性能度量大概可分為兩類: 一是外部指標, 二是內部指標 。
外部指標:將聚類結果和某個「參考模型」進行比較。
內部指標:不利用任何參考模型,直接考察聚類結果。
對於給定的樣本集,按照樣本之間的距離大小,將樣本集劃分為K個簇。讓簇內的點盡量緊密的連在一起,而讓簇間的距離盡量的大
初學者會很容易就把K-Means和KNN搞混,其實兩者的差別還是很大的。
K-Means是無監督學習的聚類演算法,沒有樣本輸出;而KNN是監督學習的分類演算法,有對應的類別輸出。KNN基本不需要訓練,對測試集裡面的點,只需要找到在訓練集中最近的k個點,用這最近的k個點的類別來決定測試點的類別。而K-Means則有明顯的訓練過程,找到k個類別的最佳質心,從而決定樣本的簇類別。
當然,兩者也有一些相似點,兩個演算法都包含一個過程,即找出和某一個點最近的點。兩者都利用了最近鄰(nearest neighbors)的思想。
優點:
簡單, 易於理解和實現 ;收斂快,一般僅需5-10次迭代即可,高效
缺點:
1,對K值得選取把握不同對結果有很大的不同
2,對於初始點的選取敏感,不同的隨機初始點得到的聚類結果可能完全不同
3,對於不是凸的數據集比較難收斂
4,對噪點過於敏感,因為演算法是根據基於均值的
5,結果不一定是全局最優,只能保證局部最優
6,對球形簇的分組效果較好,對非球型簇、不同尺寸、不同密度的簇分組效果不好。
K-means演算法簡單理解,易於實現(局部最優),卻會有對初始點、雜訊點敏感等問題;還容易和監督學習的分類演算法KNN混淆。
參考閱讀:
1.《 深入理解K-Means聚類演算法 》
2.《 K-Means 》
⑵ 關於隨機生成節點,想在ns2里模擬分簇網路,但實現分簇演算法覺得挺麻煩的,就想模擬下已經分好簇的網路 。
這個很好弄啊,可以在tcl裡面實現也可以在C++裡面實現,用random就行。NS2裡面通過TCL機制和C++協同工作,入門有點暈,具體問題可以給我發郵件[email protected]
⑶ 無線感測器網路通信協議的目錄
第1章 無線感測器網路概述
1.1 引言
1.2 無線感測器網路介紹
1.2.1 無線感測器網路體系結構
1.2.2 無線感測器網路的特點和關鍵技術
1.2.3 無線感測器網路的應用
1.3 無線感測器網路路由演算法
1.3.1 無線感測器網路路由演算法研究的主要思路
1.3.2 無線感測器網路路由演算法的分類
1.3.3 無線感測器網路QoS路由演算法研究的基本思想
1.3.4 無線感測器網路QoS路由演算法研究的分類
1.3.5 平面路由的主流演算法
1.3.6 分簇路由的主流演算法
1.4 ZigBee技術
1.4.1 ZigBee技術的特點
1.4.2 ZigBee協議框架
1.4.3 ZigBee的網路拓撲結構
1.5 無線感測器安全研究
1.5.1 無線感測器網路的安全需求
1.5.2 無線感測器網路安全的研究進展
1.5.3 無線感測器網路安全的研究方向
1.6 水下感測器網路
1.7 無線感測器網路定位
1.7.1 存在的問題
1.7.2 性能評價
1.7.3 基於測距的定位方法
1.7.4 非測距定位演算法
1.7.5 移動節點定位
第2章 無線感測器網路的分布式能量有效非均勻成簇演算法
2.1 引言
2.2 相關研究工作
2.2.1 單跳成簇演算法
2.2.2 多跳成簇演算法
2.3 DEEUC成簇路由演算法
2.3.1 網路模型
2.3.2 DEEUC成簇演算法
2.3.3 候選簇頭的產生
2.3.4 估計平均能量
2.3.5 最終簇頭的產生
2.3.6 平衡簇頭區節點能量
2.3.7 演算法分析
2.4 模擬和分析
2.5 結論及下一步工作
參考文獻
第3章 無線感測器網路分簇多跳能量均衡路由演算法
3.1 無線傳輸能量模型
3.2 無線感測器網路路由策略研究
3.2.1 平面路由
3.2.2 單跳分簇路由演算法研究
3.2.3 多跳層次路由演算法研究
3.3 LEACH-L演算法
3.3.1 LEACH-L的改進思路
3.3.2 LEACH-L演算法模型
3.3.3 LEACH-L描述
3.4 LEACH-L的分析
3.5 實驗模擬
3.5.1 評價參數
3.5.2 模擬環境
3.5.3 模擬結果
3.6 總結及未來的工作
3.6.1 總結
3.6.2 未來的工作
參考文獻
第4章 基於生成樹的無線感測器網路分簇通信協議
4.1 引言
4.2 無線傳輸能量模型
4.3 基於時間延遲機制的分簇演算法(CHTD)
4.3.1 CHTD的改進思路
4.3.2 CHTD簇頭的產生
4.3.3 CHTD簇頭數目的確定
4.3.4 CHTD最優簇半徑
4.3.5 CHTD描述
4.3.6 CHTD的特性
4.4 CHTD簇數據傳輸研究
4.4.1 引言
4.4.2 改進的CHTD演算法(CHTD-M)
4.4.3 CHTD-M的分析
4.5 模擬分析
4.5.1 生命周期
4.5.2 接收數據包量
4.5.3 能量消耗
4.5.4 負載均衡
4.6 總結及未來的工作
4.6.1 總結
4.6.2 未來的工作
參考文獻
第5章 基於自適應蟻群系統的感測器網路QoS路由演算法
5.1 引言
5.2 蟻群演算法
5.3 APAS演算法的信息素自適應機制
5.4 APAS演算法的揮發系數自適應機制
5.5 APAS演算法的QoS改進參數
5.6 APAS演算法的信息素分發機制
5.7 APAS演算法的定向廣播機制
5.8 模擬實驗及結果分析
5.8.1 模擬環境
5.8.2 模擬結果及分析
5.9 總結及未來的工作
5.9.1 總結
5.9.2 未來的工作
參考文獻
第6章 無線感測器網路簇頭選擇演算法
6.1 引言
6.2 LEACH NEW演算法
6.2.1 網路模型
6.2.2 LEACH NEW簇頭選擇機制
6.2.3 簇的生成
6.2.4 簇頭間多跳路徑的建立
6.3 模擬實現
6.4 結論及未來的工作
參考文獻
第7章 水下無線感測網路中基於向量的低延遲轉發協議
7.1 引言
7.2 相關工作
7.3 網路模型
7.3.1 問題的數學描述
7.3.2 網路模型
7.4 基於向量的低延遲轉發協議
7.4.1 基於向量轉發協議的分析
7.4.2 基於向量的低延遲轉發演算法
7.5 模擬實驗
7.5.1 模擬環境
7.5.2 模擬分析
7.6 總結
參考文獻
第8章 無線感測器網路數據融合演算法研究
8.1 引言
8.2 節能路由演算法
8.2.1 平面式路由演算法
8.2.2 層狀式路由演算法
8.3 數據融合模型
8.3.1 數據融合系統
8.3.2 LEACH簇頭選擇演算法
8.3.3 簇內融合路徑
8.3.4 環境設定和能耗公式
8.4 數據融合模擬
8.4.1 模擬分析
8.4.2 模擬結果分析
8.5 結論
參考文獻
第9章 無線感測器網路相關技術
9.1 超寬頻技術
9.1.1 系統結構的實現比較簡單
9.1.2 空間傳輸容量大
9.1.3 多徑分辨能力強
9.1.4 安全性高
9.1.5 定位精確
9.2 物聯網技術
9.2.1 物聯網原理
9.2.2 物聯網的背景與前景
9.3 雲計算技術
9.3.1 SaaS軟體即服務
9.3.2 公用/效用計算
9.3.3 雲計算領域的Web服務
9.4 認知無線電技術
9.4.1 傳統的Ad-hoc方式中無線感測器網路的不足
9.4.2 在ZigBee無線感測器網路中的應用
參考文獻
第10章 無線感測器網路應用
10.1 軍事應用
10.2 農業應用
10.3 環保監測
10.4 建築應用
10.5 醫療監護
10.6 工業應用
10.6.1 工業安全
10.6.2 先進製造
10.6.3 交通控制管理
10.6.4 倉儲物流管理
10.7 空間、海洋探索
10.8 智能家居應用
⑷ 高分求助ns關於分簇演算法源代碼
祝願你成功
⑸ 聚類演算法
1. 概述
K-means聚類演算法也稱k均值聚類演算法,是集簡單和經典於一身的基於距離的聚類演算法。它採用距離作為相似性的評價指標,即認為兩個對象的距離越近,其相似度就越大。該演算法認為類簇是由距離靠近的對象組成的,因此把得到 緊湊且獨立的簇作為最終目標。
2. 演算法核心思想
K-means聚類演算法是一種迭代求解的聚類分析演算法,其步驟是隨機選取K個對象作為初始的聚類中心,然後計算每個對象與各個種子聚類中心之間的距離,把每個對象分配給距離它最近的聚類中心。聚類中心以及分配給它們的對象就代表一個聚類。每分配一個樣本,聚類的聚類中心會根據聚類中現有的對象被重新計算。這個過程將不斷重復直到滿足某個終止條件。終止條件可以是沒有(或最小數目)對象被重新分配給不同的聚類,沒有(或最小數目)聚類中心再發生變化,誤差平方和局部最小。
3. 演算法實現步驟
1、首先確定一個k值,即我們希望將數據集經過聚類得到k個集合。
2、從數據集中隨機選擇k個數據點作為質心。
3、對數據集中每一個點,計算其與每一個質心的距離(如歐式距離),離哪個質心近,就劃分到那個質心所屬的集合。
4、把所有數據歸好集合後,一共有k個集合。然後重新計算每個集合的質心。
5、如果新計算出來的質心和原來的質心之間的距離小於某一個設置的閾值(表示重新計算的質心的位置變化不大,趨於穩定,或者說收斂),我們可以認為聚類已經達到期望的結果,演算法終止。
6、如果新質心和原質心距離變化很大,需要迭代3~5步驟。
4. 演算法步驟圖解
上圖a表達了初始的數據集,假設k=2。在圖b中,我們隨機選擇了兩個k類所對應的類別質心,即圖中的紅色質心和藍色質心,然後分別求樣本中所有點到這兩個質心的距離,並標記每個樣本的類別為和該樣本距離最小的質心的類別,如圖c所示,經過計算樣本和紅色質心和藍色質心的距離,我們得到了所有樣本點的第一輪迭代後的類別。此時我們對我們當前標記為紅色和藍色的點分別求其新的質心,如圖d所示,新的紅色質心和藍色質心的位置已經發生了變動。圖e和圖f重復了我們在圖c和圖d的過程,即將所有點的類別標記為距離最近的質心的類別並求新的質心。最終我們得到的兩個類別如圖f。
K-means術語:
簇:所有數據的點集合,簇中的對象是相似的。
質心:簇中所有點的中心(計算所有點的中心而來)
5. K-means演算法優缺點
優點:
1、原理比較簡單,實現也是很容易,收斂速度快。
2、當結果簇是密集的,而簇與簇之間區別明顯時, 它的效果較好。
3、主要需要調參的參數僅僅是簇數k。
缺點:
1、K值需要預先給定,很多情況下K值的估計是非常困難的。
2、K-Means演算法對初始選取的質心點是敏感的,不同的隨機種子點得到的聚類結果完全不同 ,對結果影響很大。
3、對噪音和異常點比較的敏感。用來檢測異常值。
4、採用迭代方法,可能只能得到局部的最優解,而無法得到全局的最優解。
⑹ 什麼叫做網路的分簇
你在網路上發送一個東西,就是以簇為單位傳送過去的
⑺ 聚類演算法有哪些分類
聚類演算法的分類有:
1、劃分法
劃分法(partitioning methods),給定一個有N個元組或者紀錄的數據集,分裂法將構造K個分組,每一個分組就代表一個聚類,K小於N。而且這K個分組滿足下列條件:
(1) 每一個分組至少包含一個數據紀錄;
(2)每一個數據紀錄屬於且僅屬於一個分組(注意:這個要求在某些模糊聚類演算法中可以放寬);
2、層次法
層次法(hierarchical methods),這種方法對給定的數據集進行層次似的分解,直到某種條件滿足為止。具體又可分為「自底向上」和「自頂向下」兩種方案。
例如,在「自底向上」方案中,初始時每一個數據紀錄都組成一個單獨的組,在接下來的迭代中,它把那些相互鄰近的組合並成一個組,直到所有的記錄組成一個分組或者某個條件滿足為止。
3、密度演算法
基於密度的方法(density-based methods),基於密度的方法與其它方法的一個根本區別是:它不是基於各種各樣的距離的,而是基於密度的。這樣就能克服基於距離的演算法只能發現「類圓形」的聚類的缺點。
4、圖論聚類法
圖論聚類方法解決的第一步是建立與問題相適應的圖,圖的節點對應於被分析數據的最小單元,圖的邊(或弧)對應於最小處理單元數據之間的相似性度量。因此,每一個最小處理單元數據之間都會有一個度量表達,這就確保了數據的局部特性比較易於處理。圖論聚類法是以樣本數據的局域連接特徵作為聚類的主要信息源,因而其主要優點是易於處理局部數據的特性。
5、網格演算法
基於網格的方法(grid-based methods),這種方法首先將數據空間劃分成為有限個單元(cell)的網格結構,所有的處理都是以單個的單元為對象的。這么處理的一個突出的優點就是處理速度很快,通常這是與目標資料庫中記錄的個數無關的,它只與把數據空間分為多少個單元有關。
代表演算法有:STING演算法、CLIQUE演算法、WAVE-CLUSTER演算法;
6、模型演算法
基於模型的方法(model-based methods),基於模型的方法給每一個聚類假定一個模型,然後去尋找能夠很好的滿足這個模型的數據集。這樣一個模型可能是數據點在空間中的密度分布函數或者其它。它的一個潛在的假定就是:目標數據集是由一系列的概率分布所決定的。
通常有兩種嘗試方向:統計的方案和神經網路的方案。
(7)簇演算法擴展閱讀:
聚類演算法的要求:
1、可伸縮性
許多聚類演算法在小於 200 個數據對象的小數據集合上工作得很好;但是,一個大規模資料庫可能包含幾百萬個對象,在這樣的大數據集合樣本上進行聚類可能會導致有偏的結果。
我們需要具有高度可伸縮性的聚類演算法。
2、不同屬性
許多演算法被設計用來聚類數值類型的數據。但是,應用可能要求聚類其他類型的數據,如二元類型(binary),分類/標稱類型(categorical/nominal),序數型(ordinal)數據,或者這些數據類型的混合。
3、任意形狀
許多聚類演算法基於歐幾里得或者曼哈頓距離度量來決定聚類。基於這樣的距離度量的演算法趨向於發現具有相近尺度和密度的球狀簇。但是,一個簇可能是任意形狀的。提出能發現任意形狀簇的演算法是很重要的。
4、領域最小化
許多聚類演算法在聚類分析中要求用戶輸入一定的參數,例如希望產生的簇的數目。聚類結果對於輸入參數十分敏感。參數通常很難確定,特別是對於包含高維對象的數據集來說。這樣不僅加重了用戶的負擔,也使得聚類的質量難以控制。
5、處理「雜訊」
絕大多數現實中的資料庫都包含了孤立點,缺失,或者錯誤的數據。一些聚類演算法對於這樣的數據敏感,可能導致低質量的聚類結果。
6、記錄順序
一些聚類演算法對於輸入數據的順序是敏感的。例如,同一個數據集合,當以不同的順序交給同一個演算法時,可能生成差別很大的聚類結果。開發對數據輸入順序不敏感的演算法具有重要的意義。