❶ Kmeans聚類演算法簡介（有點枯燥）
1. Kmeans聚類演算法簡介
由於具有出色的速度和良好的可擴展性，Kmeans聚類演算法算得上是最著名的聚類方法。Kmeans演算法是一個重復移動類中心點的過程，把類的中心點，也稱重心(centroids)，移動到其包含成員的平均位置，然後重新劃分其內部成員。k是演算法計算出的超參數，表示類的數量；Kmeans可以自動分配樣本到不同的類，但是不能決定究竟要分幾個類。k必須是一個比訓練集樣本數小的正整數。有時，類的數量是由問題內容指定的。例如，一個鞋廠有三種新款式，它想知道每種新款式都有哪些潛在客戶，於是它調研客戶，然後從數據里找出三類。也有一些問題沒有指定聚類的數量，最優的聚類數量是不確定的。後面我將會詳細介紹一些方法來估計最優聚類數量。
Kmeans的參數是類的重心位置和其內部觀測值的位置。與廣義線性模型和決策樹類似，Kmeans參數的最優解也是以成本函數最小化為目標。Kmeans成本函數公式如下：
μiμi是第kk個類的重心位置。成本函數是各個類畸變程度(distortions)之和。每個類的畸變程度等於該類重心與其內部成員位置距離的平方和。若類內部的成員彼此間越緊湊則類的畸變程度越小，反之，若類內部的成員彼此間越分散則類的畸變程度越大。求解成本函數最小化的參數就是一個重復配置每個類包含的觀測值，並不斷移動類重心的過程。首先，類的重心是隨機確定的位置。實際上，重心位置等於隨機選擇的觀測值的位置。每次迭代的時候，Kmeans會把觀測值分配到離它們最近的類，然後把重心移動到該類全部成員位置的平均值那裡。
2. K值的確定
2.1 根據問題內容確定
這種方法就不多講了，文章開篇就舉了一個例子。
2.2 肘部法則
如果問題中沒有指定kk的值，可以通過肘部法則這一技術來估計聚類數量。肘部法則會把不同kk值的成本函數值畫出來。隨著kk值的增大，平均畸變程度會減小；每個類包含的樣本數會減少，於是樣本離其重心會更近。但是，隨著kk值繼續增大，平均畸變程度的改善效果會不斷減低。kk值增大過程中，畸變程度的改善效果下降幅度最大的位置對應的kk值就是肘部。為了讓讀者看的更加明白，下面讓我們通過一張圖用肘部法則來確定最佳的kk值。下圖數據明顯可分成兩類：
從圖中可以看出，k值從1到2時，平均畸變程度變化最大。超過2以後，平均畸變程度變化顯著降低。因此最佳的k是2。
2.3 與層次聚類結合
經常會產生較好的聚類結果的一個有趣策略是，首先採用層次凝聚演算法決定結果粗的數目，並找到一個初始聚類，然後用迭代重定位來改進該聚類。
2.4 穩定性方法
穩定性方法對一個數據集進行2次重采樣產生2個數據子集，再用相同的聚類演算法對2個數據子集進行聚類，產生2個具有kk個聚類的聚類結果，計算2個聚類結果的相似度的分布情況。2個聚類結果具有高的相似度說明kk個聚類反映了穩定的聚類結構，其相似度可以用來估計聚類個數。採用次方法試探多個kk，找到合適的k值。
2.5 系統演化方法
系統演化方法將一個數據集視為偽熱力學系統，當數據集被劃分為kk個聚類時稱系統處於狀態kk。系統由初始狀態k=1k=1出發，經過分裂過程和合並過程，系統將演化到它的穩定平衡狀態 kiki ，其所對應的聚類結構決定了最優類數 kiki 。系統演化方法能提供關於所有聚類之間的相對邊界距離或可分程度，它適用於明顯分離的聚類結構和輕微重疊的聚類結構。
2.6 使用canopy演算法進行初始劃分
基於Canopy Method的聚類演算法將聚類過程分為兩個階段
(1) 聚類最耗費計算的地方是計算對象相似性的時候，Canopy Method在第一階段選擇簡單、計算代價較低的方法計算對象相似性，將相似的對象放在一個子集中，這個子集被叫做Canopy，通過一系列計算得到若干Canopy，Canopy之間可以是重疊的，但不會存在某個對象不屬於任何Canopy的情況，可以把這一階段看做數據預處理；
(2) 在各個Canopy內使用傳統的聚類方法(如Kmeans)，不屬於同一Canopy的對象之間不進行相似性計算。
從這個方法起碼可以看出兩點好處：首先，Canopy不要太大且Canopy之間重疊的不要太多的話會大大減少後續需要計算相似性的對象的個數；其次，類似於Kmeans這樣的聚類方法是需要人為指出K的值的，通過(1)得到的Canopy個數完全可以作為這個k值，一定程度上減少了選擇k的盲目性。
其他方法如貝葉斯信息准則方法(BIC)可參看文獻[4]。
3. 初始質心的選取
選擇適當的初始質心是基本kmeans演算法的關鍵步驟。常見的方法是隨機的選取初始中心，但是這樣簇的質量常常很差。處理選取初始質心問題的一種常用技術是：多次運行，每次使用一組不同的隨機初始質心，然後選取具有最小SSE(誤差的平方和)的簇集。這種策略簡單，但是效果可能不好，這取決於數據集和尋找的簇的個數。
第二種有效的方法是，取一個樣本，並使用層次聚類技術對它聚類。從層次聚類中提取kk個簇，並用這些簇的質心作為初始質心。該方法通常很有效，但僅對下列情況有效：(1)樣本相對較小，例如數百到數千(層次聚類開銷較大)；(2) kk相對於樣本大小較小。
第三種選擇初始質心的方法，隨機地選擇第一個點，或取所有點的質心作為第一個點。然後，對於每個後繼初始質心，選擇離已經選取過的初始質心最遠的點。使用這種方法，確保了選擇的初始質心不僅是隨機的，而且是散開的。但是，這種方法可能選中離群點。此外，求離當前初始質心集最遠的點開銷也非常大。為了克服這個問題，通常該方法用於點樣本。由於離群點很少(多了就不是離群點了)，它們多半不會在隨機樣本中出現。計算量也大幅減少。
第四種方法就是上面提到的canopy演算法。
4. 距離的度量
常用的距離度量方法包括：歐幾里得距離和餘弦相似度。兩者都是評定個體間差異的大小的。
歐氏距離是最常見的距離度量，而餘弦相似度則是最常見的相似度度量，很多的距離度量和相似度度量都是基於這兩者的變形和衍生，所以下面重點比較下兩者在衡量個體差異時實現方式和應用環境上的區別。
藉助三維坐標系來看下歐氏距離和餘弦相似度的區別：
從圖上可以看出距離度量衡量的是空間各點間的絕對距離，跟各個點所在的位置坐標(即個體特徵維度的數值)直接相關；而餘弦相似度衡量的是空間向量的夾角，更加的是體現在方向上的差異，而不是位置。如果保持A點的位置不變，B點朝原方向遠離坐標軸原點，那麼這個時候餘弦相似cosθ是保持不變的，因為夾角不變，而A、B兩點的距離顯然在發生改變，這就是歐氏距離和餘弦相似度的不同之處。
根據歐氏距離和餘弦相似度各自的計算方式和衡量特徵，分別適用於不同的數據分析模型：歐氏距離能夠體現個體數值特徵的絕對差異，所以更多的用於需要從維度的數值大小中體現差異的分析，如使用用戶行為指標分析用戶價值的相似度或差異；而餘弦相似度更多的是從方向上區分差異，而對絕對的數值不敏感，更多的用於使用用戶對內容評分來區分用戶興趣的相似度和差異，同時修正了用戶間可能存在的度量標准不統一的問題(因為餘弦相似度對絕對數值不敏感)。
因為歐幾里得距離度量會受指標不同單位刻度的影響，所以一般需要先進行標准化，同時距離越大，個體間差異越大；空間向量餘弦夾角的相似度度量不會受指標刻度的影響，餘弦值落於區間[-1,1]，值越大，差異越小。但是針對具體應用，什麼情況下使用歐氏距離，什麼情況下使用餘弦相似度？
從幾何意義上來說，n維向量空間的一條線段作為底邊和原點組成的三角形，其頂角大小是不確定的。也就是說對於兩條空間向量，即使兩點距離一定，他們的夾角餘弦值也可以隨意變化。感性的認識，當兩用戶評分趨勢一致時，但是評分值差距很大，餘弦相似度傾向給出更優解。舉個極端的例子，兩用戶只對兩件商品評分，向量分別為(3,3)和(5,5)，這兩位用戶的認知其實是一樣的，但是歐式距離給出的解顯然沒有餘弦值合理。
5. 聚類效果評估
我們把機器學習定義為對系統的設計和學習，通過對經驗數據的學習，將任務效果的不斷改善作為一個度量標准。Kmeans是一種非監督學習，沒有標簽和其他信息來比較聚類結果。但是，我們還是有一些指標可以評估演算法的性能。我們已經介紹過類的畸變程度的度量方法。本節為將介紹另一種聚類演算法效果評估方法稱為輪廓系數(Silhouette Coefficient)。輪廓系數是類的密集與分散程度的評價指標。它會隨著類的規模增大而增大。彼此相距很遠，本身很密集的類，其輪廓系數較大，彼此集中，本身很大的類，其輪廓系數較小。輪廓系數是通過所有樣本計算出來的，計算每個樣本分數的均值，計算公式如下：
aa是每一個類中樣本彼此距離的均值，bb是一個類中樣本與其最近的那個類的所有樣本的距離的均值。
6. Kmeans演算法流程
輸入：聚類個數k，數據集XmxnXmxn。
輸出：滿足方差最小標準的k個聚類。
(1) 選擇k個初始中心點，例如c[0]=X[0] , … , c[k-1]=X[k-1]；
(2) 對於X[0]….X[n]，分別與c[0]…c[k-1]比較，假定與c[i]差值最少，就標記為i；
(3) 對於所有標記為i點，重新計算c[i]={ 所有標記為i的樣本的每個特徵的均值}；
(4) 重復(2)(3)，直到所有c[i]值的變化小於給定閾值或者達到最大迭代次數。
Kmeans的時間復雜度：O(tkmn)，空間復雜度：O((m+k)n)。其中，t為迭代次數，k為簇的數目，m為樣本數，n為特徵數。
7. Kmeans演算法優缺點
7.1 優點
(1). 演算法原理簡單。需要調節的超參數就是一個k。
(2). 由具有出色的速度和良好的可擴展性。
7.2 缺點
(1). 在 Kmeans 演算法中 kk 需要事先確定，這個 kk 值的選定有時候是比較難確定。
(2). 在 Kmeans 演算法中，首先需要初始k個聚類中心，然後以此來確定一個初始劃分，然後對初始劃分進行優化。這個初始聚類中心的選擇對聚類結果有較大的影響，一旦初始值選擇的不好，可能無法得到有效的聚類結果。多設置一些不同的初值，對比最後的運算結果，一直到結果趨於穩定結束。
(3). 該演算法需要不斷地進行樣本分類調整，不斷地計算調整後的新的聚類中心，因此當數據量非常大時，演算法的時間開銷是非常大的。
(4). 對離群點很敏感。
(5). 從數據表示角度來說，在 Kmeans 中,我們用單個點來對 cluster 進行建模，這實際上是一種最簡化的數據建模形式。這種用點來對 cluster 進行建模實際上就已經假設了各 cluster的數據是呈圓形(或者高維球形)或者方形等分布的。不能發現非凸形狀的簇。但在實際生活中，很少能有這種情況。所以在 GMM 中，使用了一種更加一般的數據表示，也就是高斯分布。
(6). 從數據先驗的角度來說，在 Kmeans 中,我們假設各個 cluster 的先驗概率是一樣的,但是各個 cluster 的數據量可能是不均勻的。舉個例子,cluster A 中包含了10000個樣本,cluster B 中只包含了100個。那麼對於一個新的樣本,在不考慮其與A cluster、 B cluster 相似度的情況,其屬於 cluster A 的概率肯定是要大於 cluster B的。
(7). 在 Kmeans 中，通常採用歐氏距離來衡量樣本與各個 cluster 的相似度。這種距離實際上假設了數據的各個維度對於相似度的衡量作用是一樣的。但在 GMM 中，相似度的衡量使用的是後驗概率 αcG(x|μc,∑c)αcG(x|μc,∑c) ，通過引入協方差矩陣,我們就可以對各維度數據的不同重要性進行建模。
(8). 在 Kmeans 中，各個樣本點只屬於與其相似度最高的那個 cluster ，這實際上是一種 hard clustering 。
針對Kmeans演算法的缺點，很多前輩提出了一些改進的演算法。例如 K-modes 演算法，實現對離散數據的快速聚類，保留了Kmeans演算法的效率同時將Kmeans的應用范圍擴大到離散數據。還有K-Prototype演算法，可以對離散與數值屬性兩種混合的數據進行聚類，在K-prototype中定義了一個對數值與離散屬性都計算的相異性度量標准。當然還有其它的一些演算法，這里我 就不一一列舉了。
Kmeans 與 GMM 更像是一種 top-down 的思想，它們首先要解決的問題是，確定 cluster 數量，也就是 k 的取值。在確定了 k 後,再來進行數據的聚類。而 hierarchical clustering 則是一種 bottom-up 的形式，先有數據，然後通過不斷選取最相似的數據進行聚類。
❷ kmeans聚類演算法是什麼
K-means演算法是最為經典的基於劃分的聚類方法，是十大經典數據挖掘演算法之一。K-means演算法的基本思想是：以空間中k個點為中心進行聚類，對最靠近他們的對象歸類。通過迭代的方法，逐次更新各聚類中心的值，直至得到最好的聚類結果。
聚類屬於無監督學習，以往的回歸、樸素貝葉斯、SVM等都是有類別標簽y的，也就是說樣例中已經給出了樣例的分類。而聚類的樣本中卻沒有給定y，只有特徵x，比如假設宇宙中的星星可以表示成三維空間中的點集。
(2)kmeans演算法ppt擴展閱讀：
k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較小。聚類相似度是利用各聚類中對象的均值所獲得一個「中心對象」（引力中心）來進行計算的。
（1）適當選擇c個類的初始中心；
（2）在第k次迭代中，對任意一個樣本，求其到c個中心的距離，將該樣本歸到距離最短的中心所在的類；
（3）利用均值等方法更新該類的中心值；
（4）對於所有的c個聚類中心，如果利用（2）（3）的迭代法更新後，值保持不變，則迭代結束，否則繼續迭代。
❸ Kmeans演算法原理
Kmeans是一種無監督的基於距離的聚類演算法，其變種還有Kmeans++。
注意，某些聚類中心可能沒有被分配到樣本，這樣的聚類中心就會被淘汰（意味著最終的類數可能會減少）
和其他機器學習演算法一樣，K-Means 也要評估並且最小化聚類代價，在引入 K-Means 的代價函數之前，先引入如下定義：
引入代價函數：
5） 對噪音和異常點比較的敏感。
數據呈圓形、凸型、在一起的簇的數據形狀近似高斯分布的這些數據是kmeans喜歡的數據。
❹ K-means改進演算法(一)：K-means++
在普通的K-means演算法中，會存在以下的缺點：
1). 只能收斂到局部最優，受到初始值較大；
2). K不確定，需自己確定；
3). 受noise影響較大。
為了改進k-means演算法，出現了K-means++，ISODATA和Kernel K-means等方法。
其中K-means++演算法是對初始值選擇進行了改進。
普通k-means演算法的步驟大概如下所示（假設k=3）：
普通的K均值演算法是隨機選取K個點作為聚類的中心，而K-means++按照如下的思想選取K個聚類中心，其基本的思想是，K個初始聚類中心相互之間應該分得越開、離得越遠越好（圖片來自 https://www.cnblogs.com/yixuan-xu/p/6272208.html ）：
❺ 大數據十大經典演算法之k-means
大數據十大經典演算法之k-means
k均值演算法基本思想：
K均值演算法是基於質心的技術。它以K為輸入參數，把n個對象集合分為k個簇，使得簇內的相似度高，簇間的相似度低。
處理流程：
1、為每個聚類確定一個初始聚類中心，這樣就有k個初始聚類中心；
2、將樣本按照最小距離原則分配到最鄰近聚類
3、使用每個聚類中的樣本均值作為新的聚類中心
4、重復步驟2直到聚類中心不再變化
5、結束，得到K個聚類
劃分聚類方法對數據集進行聚類時的要點：
1、選定某種距離作為數據樣本間的相似性度量，通常選擇歐氏距離。
2、選擇平價聚類性能的准則函數
用誤差平方和准則函數來評價聚類性能。
3、相似度的計算分局一個簇中對象的平均值來進行
K均值演算法的優點：
如果變數很大，K均值比層次聚類的計算速度較快（如果K很小）；
與層次聚類相比，K均值可以得到更緊密的簇，尤其是對於球狀簇；
對於大數據集，是可伸縮和高效率的；
演算法嘗試找出使平方誤差函數值最小的k個劃分。當結果簇是密集的，而簇與簇之間區別明顯的時候，效果較好。
K均值演算法缺點：
最後結果受初始值的影響。解決辦法是多次嘗試取不同的初始值。
可能發生距離簇中心m最近的樣本集為空的情況，因此m得不到更新。這是一個必須處理的問題，但我們忽略該問題。
不適合發現非凸面形狀的簇，並對雜訊和離群點數據較敏感，因為少量的這類數據能夠對均值產生較大的影響。
K均值演算法的改進：
樣本預處理。計算樣本對象量量之間的距離，篩掉與其他所有樣本那的距離和最大的m個對象。
初始聚類中心的選擇。選用簇中位置最靠近中心的對象，這樣可以避免孤立點的影響。
K均值演算法的變種：
K眾數（k-modes）演算法，針對分類屬性的度量和更新質心的問題而改進。
EM（期望最大化）演算法
k-prototype演算法
這種演算法不適合處理離散型屬性，但是對於連續型具有較好的聚類效果。
k均值演算法用途：
圖像分割；
衡量足球隊的水平；
下面給出代碼：
#include <iostream>
#include <vector>
//auther archersc
//JLU
namespace CS_LIB
{
using namespace std;
class Kmean
{
public:
//輸入格式
//數據數量N 維度D
//以下N行，每行D個數據
istream& loadData(istream& in);
//輸出格式
//聚類的數量CN
//中心維度CD
//CN行，每行CD個數據
//數據數量DN
//數據維度DD
//以下DN組，每組的第一行兩個數值DB, DDis
//第二行DD個數值
//DB表示改數據屬於一類，DDis表示距離改類的中心的距離
ostream& saveData(ostream& out);
//設置中心的數量
void setCenterCount(const size_t count);
size_t getCenterCount() const;
//times最大迭代次數， maxE ,E(t)表示第t次迭代後的平方誤差和，當|E(t+1) - E(t)| < maxE時終止
void clustering(size_t times, double maxE);
private:
double calDistance(vector<double>& v1, vector<double>& v2);
private:
vector< vector<double> > m_Data;
vector< vector<double> > m_Center;
vector<double> m_Distance;
vector<size_t> m_DataBelong;
vector<size_t> m_DataBelongCount;
};
}
#include "kmean.h"
#include <ctime>
#include <cmath>
#include <cstdlib>
//auther archersc
//JLU
namespace CS_LIB
{
template<class T>
void swap(T& a, T& b)
{
T c = a;
a = b;
b = c;
}
istream& Kmean::loadData(istream& in)
{
if (!in){
cout << "input error" << endl;
return in;
}
size_t dCount, dDim;
in >> dCount >> dDim;
m_Data.resize(dCount);
m_DataBelong.resize(dCount);
m_Distance.resize(dCount);
for (size_t i = 0; i < dCount; ++i){
m_Data[i].resize(dDim);
for (size_t j = 0; j < dDim; ++j){
in >> m_Data[i][j];
}
}
return in;
}
ostream& Kmean::saveData(ostream& out)
{
if (!out){
cout << "output error" << endl;
return out;
}
out << m_Center.size();
if (m_Center.size() > 0)
out << << m_Center[0].size();
else
out << << 0;
out << endl << endl;
for (size_t i = 0; i < m_Center.size(); ++i){
for (size_t j = 0; j < m_Center[i].size(); ++j){
out << m_Center[i][j] << ;
}
out << endl;
}
out << endl;
out << m_Data.size();
if (m_Data.size() > 0)
out << << m_Data[0].size();
else
out << << 0;
out << endl << endl;
for (size_t i = 0; i < m_Data.size(); ++i){
out << m_DataBelong[i] << << m_Distance[i] << endl;
for (size_t j = 0; j < m_Data[i].size(); ++j){
out << m_Data[i][j] << ;
}
out << endl << endl;
}
return out;
}
void Kmean::setCenterCount(const size_t count)
{
m_Center.resize(count);
m_DataBelongCount.resize(count);
}
size_t Kmean::getCenterCount() const
{
return m_Center.size();
}
void Kmean::clustering(size_t times, double maxE)
{
srand((unsigned int)time(NULL));
//隨機從m_Data中選取m_Center.size()個不同的樣本點作為初始中心。
size_t *pos = new size_t[m_Data.size()];
size_t i, j, t;
for (i = 0; i < m_Data.size(); ++i){
pos[i] = i;
}
for (i = 0; i < (m_Data.size() << 1); ++i){
size_t s1 = rand() % m_Data.size();
size_t s2 = rand() % m_Data.size();
swap(pos[s1], pos[s2]);
}
for (i = 0; i < m_Center.size(); ++i){
m_Center[i].resize(m_Data[pos[i]].size());
for (j = 0; j < m_Data[pos[i]].size(); ++j){
m_Center[i][j] = m_Data[pos[i]][j];
}
}
delete []pos;
double currE, lastE;
for (t = 0; t < times; ++t){
for (i = 0; i < m_Distance.size(); ++i)
m_Distance[i] = LONG_MAX;
for (i = 0; i < m_DataBelongCount.size(); ++i)
m_DataBelongCount[i] = 0;
currE = 0.0;
for (i = 0; i < m_Data.size(); ++i){
for (j = 0; j < m_Center.size(); ++j){
double dis = calDistance(m_Data[i], m_Center[j]);
if (dis < m_Distance[i]){
m_Distance[i] = dis;
m_DataBelong[i] = j;
}
}
currE += m_Distance[i];
m_DataBelongCount[m_DataBelong[i]]++;
}
cout << currE << endl;
if (t == 0 || fabs(currE - lastE) > maxE)
lastE = currE;
else
break;
for (i = 0; i < m_Center.size(); ++i){
for (j = 0; j < m_Center[i].size(); ++j)
m_Center[i][j] = 0.0;
}
for (i = 0; i < m_DataBelong.size(); ++i){
for (j = 0; j < m_Data[i].size(); ++j){
m_Center[m_DataBelong[i]][j] += m_Data[i][j] / m_DataBelongCount[m_DataBelong[i]];
}
}
}
}
double Kmean::calDistance(vector<double>& v1, vector<double>& v2)
{
double result = 0.0;
for (size_t i = 0; i < v1.size(); ++i){
result += (v1[i] - v2[i]) * (v1[i] - v2[i]);
}
return pow(result, 1.0 / v1.size());
//return sqrt(result);
}
}
#include <iostream>
#include <fstream>
#include "kmean.h"
using namespace std;
using namespace CS_LIB;
int main()
{
ifstream in("in.txt");
ofstream out("out.txt");
Kmean kmean;
kmean.loadData(in);
kmean.setCenterCount(4);
kmean.clustering(1000, 0.000001);
kmean.saveData(out);
return 0;
}