❶ 如何正確選擇聚類演算法
作者 | Josh Thompson
來源 | 數據派THU
Choosing the Right Clustering Algorithm for your Dataset - KDnuggets
聚類演算法十分容易上手，但是選擇恰當的聚類演算法並不是一件容易的事。
數據聚類是搭建一個正確數據模型的重要步驟。數據分析應當根據數據的共同點整理信息。然而主要問題是，什麼通用性參數可以給出最佳結果，以及什麼才能稱為「最佳」。
本文適用於菜鳥數據科學家或想提升聚類演算法能力的專家。下文包括最廣泛使用的聚類演算法及其概況。根據每種方法的特殊性，本文針對其應用提出了建議。
四種基本演算法以及如何選擇
聚類模型可以分為四種常見的演算法類別。盡管零零散散的聚類演算法不少於100種，但是其中大部分的流行程度以及應用領域相對有限。
基於整個數據集對象間距離計算的聚類方法，稱為基於連通性的聚類（connectivity-based）或層次聚類。根據演算法的「方向」，它可以組合或反過來分解信息——聚集和分解的名稱正是源於這種方向的區別。最流行和合理的類型是聚集型，你可以從輸入所有數據開始，然後將這些數據點組合成越來越大的簇，直到達到極限。
層次聚類的一個典型案例是植物的分類。數據集的「樹」從具體物種開始，以一些植物王國結束，每個植物王國都由更小的簇組成（門、類、階等）。
層次聚類演算法將返回樹狀圖數據，該樹狀圖展示了信息的結構，而不是集群上的具體分類。這樣的特點既有好處，也有一些問題：演算法會變得很復雜，且不適用於幾乎沒有層次的數據集。這種演算法的性能也較差：由於存在大量的迭代，因此整個處理過程浪費了很多不必要的時間。最重要的是，這種分層演算法並不能得到精確的結構。
同時，從預設的類別一直分解到所有的數據點，類別的個數不會對最終結果產生實質性影響，也不會影響預設的距離度量，該距離度量粗略測量和近似估計得到的。
根據我的經驗，由於簡單易操作，基於質心的聚類（Centroid-based）是最常出現的模型。 該模型旨在將數據集的每個對象劃分為特定的類別。 簇數（k）是隨機選擇的，這可能是該方法的最大問題。 由於與k最近鄰居（kNN）相似，該k均值演算法在機器學習中特別受歡迎。
計算過程包括多個步驟。首先，輸入數據集的目標類別數。聚類的中心應當盡可能分散，這有助於提高結果的准確性。
其次，該演算法找到數據集的每個對象與每個聚類中心之間的距離。最小坐標距離（若使用圖形表示）確定了將對象移動到哪個群集。
之後，將根據類別中所有點的坐標平均值重新計算聚類的中心。重復演算法的上一步，但是計算中要使用簇的新中心點。除非達到某些條件，否則此類迭代將繼續。例如，當簇的中心距上次迭代沒有移動或移動不明顯時，聚類將結束。
盡管數學和代碼都很簡單，但k均值仍有一些缺點，因此我們無法在所有情景中使用它。缺點包括：
因為優先順序設置在集群的中心，而不是邊界，所以每個集群的邊界容易被疏忽。 無法創建數據集結構，其對象可以按等量的方式分類到多個群集中。 需要猜測最佳類別數（k），或者需要進行初步計算以指定此量規。相比之下，期望最大化演算法可以避免那些復雜情況，同時提供更高的准確性。簡而言之，它計算每個數據集點與我們指定的所有聚類的關聯概率。用於該聚類模型的主要工具是高斯混合模型（GMM）–假設數據集的點服從高斯分布。
k-means演算法可以算是EM原理的簡化版本。它們都需要手動輸入簇數，這是此類方法要面對的主要問題。除此之外，計算原理（對於GMM或k均值）很簡單：簇的近似范圍是在每次新迭代中逐漸更新的。
與基於質心的模型不同，EM演算法允許對兩個或多個聚類的點進行分類-它僅展示每個事件的可能性，你可以使用該事件進行進一步的分析。更重要的是，每個聚類的邊界組成了不同度量的橢球體。這與k均值聚類不同，k均值聚類方法用圓形表示。但是，該演算法對於不服從高斯分布的數據集根本不起作用。這也是該方法的主要缺點：它更適用於理論問題，而不是實際的測量或觀察。
最後，基於數據密度的聚類成為數據科學家心中的最愛。
這個名字已經包括了模型的要點——將數據集劃分為聚類，計數器會輸入ε參數，即「鄰居」距離。因此，如果目標點位於半徑為ε的圓（球）內，則它屬於該集群。
具有雜訊的基於密度的聚類方法（DBSCAN）將逐步檢查每個對象，將其狀態更改為「已查看」，將其劃分到具體的類別或雜訊中，直到最終處理整個數據集。用DBSCAN確定的簇可以具有任意形狀，因此非常精確。此外，該演算法無需人為地設定簇數 —— 演算法可以自動決定。
盡管如此，DBSCAN也有一些缺點。如果數據集由可變密度簇組成，則該方法的結果較差；如果對象的位置太近，並且無法輕易估算出ε參數，那麼這也不是一個很好的選擇。
總而言之，我們並不能說選擇了錯誤的演算法，只能說其中有些演算法會更適合特定的數據集結構。為了採用最佳的（看起來更恰當的）演算法，你需要全面了解它們的優缺點。
例如，如果某些演算法不符合數據集規范，則可以從一開始就將其排除在外。為避免繁瑣的工作，你可以花一些時間來記住這些信息，而無需反復試驗並從自己的錯誤中學習。
我們希望本文能幫助你在初始階段選擇最好的演算法。繼續這了不起的工作吧！
❷ knn演算法如何選擇一個最佳k值
K最近鄰(k-Nearest Neighbor，KNN)分類演算法，是一個理論上比較成熟的方法，也是最簡單的機器學習演算法之一。該方法的思路是：如果一個樣本在特徵空間中的k個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。KNN演算法中，所選擇的鄰居都是已經正確分類的對象。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。 KNN方法雖然從原理上也依賴於極限定理，但在類別決策時，只與極少量的相鄰樣本有關。由於KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。
KNN演算法不僅可以用於分類，還可以用於回歸。通過找出一個樣本的k個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該樣本產生的影響給予不同的權值(weight)，如權值與距離成正比。該演算法在分類時有個主要的不足是，當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本佔多數。 該演算法只計算「最近的」鄰居樣本，某一類的樣本數量很大，那麼或者這類樣本並不接近目標樣本，或者這類樣本很靠近目標樣本。無論怎樣，數量並不能影響運行結果。可以採用權值的方法（和該樣本距離小的鄰居權值大）來改進。
該方法的另一個不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。該演算法比較適用於樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域採用這種演算法比較容易產生誤分。
❸ BGP協議最佳路徑的選擇演算法有哪些
每個BGP路由器通過鄰居聲名與周邊的一個或多個路由器連接。一旦建立了鄰居關系，這些BGP路由器之間就會相互交換路由信息。據我最近一次統計，整個互聯網上有大約12.5萬個路由信息，因此要配備一個強大的路由器才能將所有BGP路由信息接收下來。
由於整個互聯網的BGP路由表有超過20萬個路由，同時一個BGP路由器可能從多個來源收到多份的路由表，因此肯定會有一種方法可以比較不同的BGP路由表，並從中選擇最佳的路由方案。這種方法就是BGP最佳路徑選擇演算法。
可能你會注意到，CiscoBGP路由器會將應用權重（weight）作為路由表的第一標准，而其它品牌的路由器則不是這樣。Cisco的官方BGP最佳路徑選擇演算法文檔中詳細列明了所參考的各項標准。接下來我會列出每種標准並給出解釋和範例。
默認情況下，BGP最佳路徑都是基於最短自治系統（AS）的原理得出的。不過很多時候，諸如weight，localpreference以及MED這樣的標准都是網路管理員自行設定的。
接下來我們就按照BGP選擇最佳路徑的參考順序將這幾項標准介紹一下：
#1 Weight —權重是Cisco為本地路由器設定的自定義參數，並不隨路由器更新而變化。如果指向某一IP地址的路徑有多條（這很常見），那麼BGP會尋找權重最高的路徑。設定權重的參考因素很多，包括鄰居命令，as-path訪問列表，或者路由鏡像等。
#2 Local Preference — 本地出口優先順序參數會告知AS哪條路徑具有本地優先，數值越高優先順序越高。默認為100。比如：
bgp default local-preference 150
#3 Network or Aggregate—這個參數會選擇本地發起的網路或聚合作為路徑。將特定的路徑加入路由中，會讓路由更有效率，同時也節省了網路空間。更多有關聚合的信息，可以參考Cisco的文章「UnderstandingRouteAggregation in BGP.」
#4 Shortest AS_PATH — BGP 只有在weight， localpreference和locallyoriginated相當接近的時候才使用這個參數。
#5 Lowest origin type — 這個參數處理Interior Gateway Protocol（IGP）協議的優先順序低於 Exterior Gateway Protocol （EGP）協議。
#6 Lowest multi-exit discriminator （MED） — 較低的MED值要優於較高的MED值。
#7 eBGP over iBGP — 類似於#5， BGP AS Path 更傾向 eBGP 而不是 iBGP。
#8 Lowest IGP metric — 這個參數傾向於採用最低IGP作為BGP下一跳。
#9 Multiple paths — 這個參數決定是否要在路由表中裝入多個路徑。可以參考 BGPMultipath獲取更多信息。
#10 External paths — 當所有路徑都為外部路徑時，選擇首先接收到的路徑（較老的路徑）。
#11 Lowest router ID — 選擇來自具有最低路由器ID的BGP路由器的路徑。
#12 Minimum cluster list — 如果多個路徑的originator或路由器ID相同，選擇cluster列表長度最短的路徑。
❹ 最佳置換演算法最後一個怎麼辦
最佳置換演算法(OPT)(理想置換演算法):從主存中移出永遠不再需要的頁面;如無這樣的頁面存在,則選擇最長時間不需要訪問的頁面。於所選擇的被淘汰頁面將是以後永不使用的,或者是在最長時間內不再被訪問的頁面,這樣可以保證獲得最低的缺頁率。 最佳置換演算法可以用來評價其他演算法。