K-均值(K-means算法)算法學習筆記
——慕課-商務數據分析(復旦大學 -趙衛東/董亮) 學習筆記
文章目錄
- K-均值(K-means算法)算法學習筆記
- 一.聚類分析簡介
- 二.基于劃分的聚類方法
- 四．K-均值(K-means)算法過程
- 五．K值的選取
- 六．K-均值(K-means)具體實現
- 七．K-均值(K-means)算法的優缺點
一.聚類分析簡介
??????聚類分析是一種典型的無監督學習，用于對未知類別的樣本進行劃分，將它們按照一定的規則劃分成若干個類族，把相似（距高相近）的樣本聚在同一個類簇中，把不相似的樣本分為不同的類簇，從而揭示樣本之間內在的性質以及相互之間的聯系規律。
??????聚類算法在銀行，零售，保險，醫學，軍事等諸多領域有著廣泛的應用。
二.基于劃分的聚類方法
??????基于劃分的方法是簡單、常用的一種聚類方法。通過將對象劃分為互斥的簇進行聚類，每個對象僅屬于一個簇。劃分結果旨在使簇之間的相似性低，簇內的相似度高，基于劃分的常用算法有K均值(K-means算法)、k-medoids、k-prototype等。
三．K-均值(K-means)算法簡介
??????K-均值(K-means)聚類是基于劃分的聚類算法，是一種迭代算法。計算樣本點與類簇質心的距離，與類簇質心相近的樣本點劃分為同一類簇。K-均值通過樣本點間的距離來衡量他們之間的相似度，兩個樣本距離越遠，則相似度越低，否則相速度越高。K-均值(K-means)算法不適用于非凸面形狀(非球形)的數據集，例如圖中的例子，聚類結果與初始目標有非常大的差別。
K-均值算法聚類步驟如下：
1.首先選取K個類簇(K需要用戶進行指定)的質心，通常是隨機選取。
2.對剩余的每個樣本點，計算它們到各個質心的歐式距離，并將其歸入到相互間距離最小的質心所在的簇。計算各個新簇的質心。
3.在所有樣本點都劃分完畢后，根據劃分情況重新計算各個簇的質心所在的位置，然后迭代計算各個樣本點到各簇質心的距離，對所有樣本點進行重新劃分。
4.重復第2和第3步，直到迭代計算后，所有樣本點的劃分情況保持不變，此時說明k-均值算法已經得到了最優解，將運行結果返回。
四．K-均值(K-means)算法過程
K-means工作流程：
K-means算法計算步驟基本上可以概括為兩個部分：
1.計算每一個對象到類簇中心的距離；
2.根據類簇內的對象計算新的簇類中心。
創建k個點作為起始質心（多是隨機選擇）
repeat
對數據集中的每個數據點
repeat
對每個質心
計算質心與數據點之間的距離
將數據點分配到距離其最近的類（或簇）
對每一個類（簇），計算類（簇）中所有點的均值并將其作為質心。
K-means開發流程：
收集數據：使用任意方法
準備數據：需要數值型數據類計算距離, 也可以將標稱型數據映射為二值型數據再用于距離計算。
分析數據：使用任意方法
訓練算法：無監督學習不需要訓練步驟
測試算法：應用聚類算法、觀察結果.可以使用量化的誤差指標如誤差平方和（后面會介紹）來評價算法的結果.
使用算法：可以用于所希望的任何應用.通常情況下, 簇質心可以代表整個簇的數據來做出決策.
五．K值的選取
1.與層次類聚算法結合，先通過層次類聚算法得出大致的類聚數目，并且獲得一個初始聚類結果，然后再通過K-均值法改進聚類結果。
2.基于系統演化的方法，將數據集視為偽熱力學系統，在分裂和合并的過程中，將系統演化到穩定平衡狀態而確定K值。
另外在網絡上看到了手肘法和輪廓系數法
https://blog.csdn.net/qq_15738501/article/details/79036255
六．K-均值(K-means)具體實現
慕課上使用python語言實現的我這里使用c++
這里用C++代碼完成iris數據測試：
測試數據：iris測試數據
#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <time.h>using namespace std;#define K 3 //簇的數目
#define DIM_NUM 5
#define DATA_NUM 140//存放元組的屬性信息
typedef vector<double> Tuple;//存儲一條數據記錄 //輸入兩個元組，計算兩個元組間的歐幾里距離
double getDistXY(const Tuple& t1, const Tuple& t2)
{double sum = 0;for (int i = 1; i <= DIM_NUM; ++i){sum += (t1[i] - t2[i]) * (t1[i] - t2[i]);}return sqrt(sum);
}//輸入k個質心和1個元組，根據質心，決定當前元組屬于哪個簇
int clusterOfTuple(const Tuple means[], const Tuple& tuple){double dist = getDistXY(means[0], tuple);double tmp;int label = 0; //標示屬于哪一個簇 for (int i = 1; i<K; i++) //遍歷質心{tmp = getDistXY(means[i], tuple);if (tmp<dist) //選擇距離最小的質心，用label標示{ dist = tmp; label = i; }}return label;
}//輸入簇集和質心，獲得給定簇集的平方誤差
double getVar(vector<Tuple> clusters[], Tuple means[])
{double var = 0;for (int i = 0; i < K; i++) //遍歷質心{vector<Tuple> t = clusters[i];for (unsigned int j = 0; j< t.size(); j++){var += getDistXY(t[j], means[i]); //簇集中所有元組到質心的距離之和}}//cout<<"sum:"<<sum<<endl; return var;}//輸入簇，獲得當前簇的均值（質心）
Tuple getMeans(const vector<Tuple>& cluster)
{int num = cluster.size();Tuple t(DIM_NUM + 1, 0); //初始化dimNum + 1個0填充數組//第一個位置存放記錄編號，第2到dimNum+1個位置存放實際元素 for (int i = 0; i < num; i++) {for (int j = 1; j <= DIM_NUM; ++j){t[j] += cluster[i][j];}}for (int j = 1; j <= DIM_NUM; ++j){t[j] /= num;}return t; //返回簇集中所有元組平均值作為質心//cout<<"sum:"<<sum<<endl;
}void print_Means(const vector<Tuple> clusters[])
{for (int lable = 0; lable < K; lable++){cout << clusters[lable].size() << " " ;Tuple temp = getMeans(clusters[lable]);cout << "(";for (int j = 0; j <= DIM_NUM; ++j){cout << temp[j] << "\t";}cout << ")\n";}
}void print(const vector<Tuple> clusters[])
{for (int lable = 0; lable<K; lable++){cout << "第" << lable + 1 << "個簇：" << endl;vector<Tuple> t = clusters[lable];for (unsigned int i = 0; i<t.size(); i++){cout << i + 1 << ".(";for (int j = 0; j <= DIM_NUM; ++j){cout << t[i][j] << ", ";}cout << ")\n";}}}vector<Tuple>* KMeans(vector<Tuple>& tuples)
{vector<Tuple> clusters[K]; //k個簇 Tuple means[K]; //k個質心 int i = 0;//一開始隨機選取k條記錄的值作為k個簇的質心（均值） srand((unsigned int)time(NULL)); //隨機數發生器的初始化for (i = 0; i<K;){int iToSelect = rand() % tuples.size();if (means[iToSelect].size() == 0){for (int j = 0; j <= DIM_NUM; ++j){means[i].push_back(tuples[iToSelect][j]); //初始化個質心}++i;}}int lable = 0;//根據默認的質心，將輸入的tuples分配給各個簇 for (i = 0; i != tuples.size(); ++i){lable = clusterOfTuple(means, tuples[i]);clusters[lable].push_back(tuples[i]); //初始化各簇}double oldVar = -1;double newVar = getVar(clusters, means); //初始化誤差和cout << "初始的的整體誤差平方和為：" << newVar << endl;int t = 0;//當新舊函數值相差不到1即準則函數值不發生明顯變化時，算法終止while (abs(newVar - oldVar) >= 0.01) {cout << "第 " << ++t << " 次迭代開始：" << endl;for (i = 0; i < K; i++) //更新每個簇的質心 {means[i] = getMeans(clusters[i]);}for (i = 0; i < K; i++) //清空每個簇 {clusters[i].clear();}for (i = 0; i != tuples.size(); ++i) //根據新的質心更新簇集 {lable = clusterOfTuple(means, tuples[i]);clusters[lable].push_back(tuples[i]);}//更新誤差判斷值 oldVar = newVar;newVar = getVar(clusters, means);cout << "此次迭代之后的整體誤差平方和為：" << newVar << endl;}cout << "The result is:\n";print(clusters);print_Means(clusters);return clusters;
}int main()
{char fname[256] = "iris_train.txt";ifstream infile(fname);if (!infile){cout << "不能打開輸入的文件" << fname << endl;return 0;}vector<Tuple> tuples;//從文件流中讀入數據 for (int i = 0; i<DATA_NUM && !infile.eof(); ++i){string str;getline(infile, str);istringstream istr(str);Tuple tuple(DIM_NUM + 1, 0);//第一個位置存放記錄編號，第2到dimNum+1個位置存放實際元素 tuple[0] = i + 1;for (int j = 1; j <= DIM_NUM; ++j){istr >> tuple[j];}tuples.push_back(tuple);}cout << endl << "開始聚類" << endl;KMeans(tuples);system("pause");return 0;
}
運行截圖：
結論：
可以多運行幾次以上代碼，可以看出由于初始點事隨機選取的每次運行得到的結果有所差異。這也是基本K-means算法的一個缺點，隨著眾多改進算法的提出K-means算法的這一問題也得到改善，深入了解的朋友可以查閱相關論文。
想要測試數據的朋友也可以私我。
七．K-均值(K-means)算法的優缺點
優點：
1.聚類效果較優。
2.原理簡單，實現容易，收斂速度快。
3.需要調整的參數較少，通常只需要調整簇數K。
缺點：
1.在 K-means 算法中 k 需要事先確定，這個 k 值的選定有時候是比較難確定。
2.在 K-means 算法中，首先需要初始k個聚類中心，然后以此來確定一個初始劃分，然后對初始劃分進行優化。這個初始聚類中心的選擇對聚類結果有較大的影響，一旦初始值選擇的不好，可能無法得到有效的聚類結果。多設置一些不同的初值，對比最后的運算結果，一直到結果趨于穩定結束。
3.該算法需要不斷地進行樣本分類調整，不斷地計算調整后的新的聚類中心，因此當數據量非常大時，算法的時間開銷是非常大的。
4.對離群點很敏感。
5.從數據表示角度來說，在 K-means 中,我們用單個點來對 cluster 進行建模，這實際上是一種最簡化的數據建模形式。這種用點來對 cluster 進行建模實際上就已經假設了各 cluster的數據是呈圓形(或者高維球形)或者方形等分布的。不能發現非凸形狀的簇。但在實際生活中，很少能有這種情況。所以在 GMM 中，使用了一種更加一般的數據表示，也就是高斯分布。
6.從數據先驗的角度來說，在 K-means 中,我們假設各個 cluster 的先驗概率是一樣的,但是各個 cluster 的數據量可能是不均勻的。舉個例子,cluster A 中包含了10000個樣本,cluster B 中只包含了100個。那么對于一個新的樣本,在不考慮其與A cluster、 B cluster 相似度的情況,其屬于 cluster A 的概率肯定是要大于 cluster B的。
7.在 K-means 中，通常采用歐氏距離來衡量樣本與各個 cluster 的相似度。這種距離實際上假設了數據的各個維度對于相似度的衡量作用是一樣的。但在 GMM 中，相似度的衡量使用的是后驗概率 αcG(x|μc,∑c)αcG(x|μc,∑c) ，通過引入協方差矩陣,我們就可以對各維度數據的不同重要性進行建模。
8.在 K-means 中，各個樣本點只屬于與其相似度最高的那個 cluster ，這實際上是一種 hard clustering 。
針對K-means算法的缺點，很多前輩提出了一些改進的算法。例如 K-modes 算法，實現對離散數據的快速聚類，保留了K-means算法的效率同時將K-means的應用范圍擴大到離散數據。還有K-Prototype算法，可以對離散與數值屬性兩種混合的數據進行聚類，在K-prototype中定義了一個對數值與離散屬性都計算的相異性度量標準。當然還有其它的一些算法，這里我 就不一一列舉了。
K-means 與 GMM 更像是一種 top-down 的思想，它們首先要解決的問題是，確定 cluster 數量，也就是 k 的取值。在確定了 k 后,再來進行數據的聚類。而 hierarchical clustering 則是一種 bottom-up 的形式，先有數據，然后通過不斷選取最相似的數據進行聚類。
感謝瀏覽，小白一枚，請多包涵。
參考網站：
[1]: https://www.cnblogs.com/baiboy/p/pybnc6.html
[2]: https://blog.csdn.net/u013719780/article/details/78413770
總結
以上是生活随笔為你收集整理的计算智能——K-均值算法的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
