k均值演算法終止

1. 聚類演算法--KMeans

    與分類、序列標注等任務不同，聚類是在事先並不知道任何樣本標簽的情況下，通過數據之間的內在關系把樣本劃分為若干類別，使得同類別樣本之間的相似度高，不同類別之間的樣本相似度低(即增大類內聚，減少類間距)。    

    聚類屬於非監督學習，K均值聚類是最基礎常用的聚類演算法。它的基本思想是，通過迭代尋找K個簇(Cluster)的一種劃分方案，使得聚類結果對應的損失函數最小。其中，損失函數可以定義為各個樣本距離所屬簇中心點的誤差平方和。

其中 代表第i個樣本， 是 所屬的簇，  代表簇對應的中心點，M是樣本總數。

相關概念：

    K值： 要得到的簇的個數。

    質心： 每個簇的均值向量。即向量各維取平均即可。

    距離量度： 常用歐幾里得距離和餘弦相似度(先標准化)。

    KMeans的主要思想是：在給定K值和K個初始類簇中心點的情況下，把每個點(亦即數據記錄)分到離其最近的類簇中心點所代表的類簇中，所有點分配完畢之後，根據一個類簇內的所有點重新計算該類簇的中心點(取平均值)，然後再迭代的進行分配點和更新類簇中心點的步驟，直至類簇中心點的變化很小，或者達到指定的迭代次數。

    KMeans的核心目標是將給定的數據集劃分成K個簇(K是超餐)，並給出每個樣本數據對應的中心點。具體步驟非常簡單：

    （1）首先確定一個K值，即我們希望將數據集經過聚類得到k個集合。

    （2）從數據集中隨機選擇K個數據點作為質心。

    （3）對數據集中每一個點，計算其與每一個質心的距離(如歐式距離)，離哪個質心近，就劃分到哪個質心所屬的集合。

    （4）把所有數據歸好集合後，一共有K個集合。然後重新計算每個集合的質心。

    （5）如果新計算出來的質心和原來的質心之間的距離小於某一個設置的閾值(表示重新計算的質心的位置變化不大，趨於穩定，或者說收斂)，我們可以認為聚類已經達到期望的結果，演算法終止。

    （6）如果新質心和原質心距離變化很大，需要迭代3-5步驟。

KMeans最核心的部分是先固定中心點，調整每個樣本所屬的類別來減少J；再固定每個樣本的類別，調整中心點繼續減小J。兩個過程交替循環，J單調遞減直到極小值，中心點和樣本劃分的類別同時收斂。

KMeans的優點 ：

 高效可伸縮，計算復雜度為O(NKt)接近於線性(N是數據量，K是聚類總數，t是迭代輪數)。

 收斂速度快，原理相對通俗易懂，可解釋性強。

當結果簇是密集的，而簇與簇之間區別是明顯時，他的效果較好。主要需要調參的參數僅僅是簇數K。

缺點 ：

 受初始值和異常點影響，聚類結果可能不是全局最優而是局部最優。K-Means演算法對初始選取的質心點是敏感的，不同的隨機種子點得到的聚類結果完全不同，對結果影響很大。

 K是超參數，一般需要按經驗選擇。

 對噪音和異常點比較的敏感，用來檢測異常值。

 只能發現球狀的簇。在K-Means中，我們用單個點對cluster進行建模，這實際上假設各個cluster的數據是呈高維球型分布的，但是在生活中出現這種情況的概率並不算高。例如，每一個cluster是一個一個的長條狀的，K-Means的則根本識別不出來這種類別( 這種情況可以用GMM )。實際上，K-Means是在做凸優化，因此處理不了非凸的分布。

根據以上特點，我們可以從下面幾個角度對演算法做調優。

（1）數據預處理：歸一化和異常點過濾

    KMeans本質是一種基於歐式距離度量的數據劃分方法，均值和方差大的維度將對數據的聚類結果產生決定性影響 。所以在聚類前對數據( 具體的說是每一個維度的特徵 )做歸一化和單位統一至關重要。此外，異常值會對均值計算產生較大影響，導致 中心偏移 ，這些雜訊點最好能提前過濾。

（2）合理選擇K值

    K值的選擇一般基於實驗和多次實驗結果。例如採用 手肘法 ，嘗試不同K值並將對應的損失函數畫成折線。手肘法認為圖上的 拐點就是K的最佳值 (k=3)。

為了將尋找最佳K值的過程自動化，研究人員提出了Gap Statistic方法。不需要人們用肉眼判斷，只需要找到最大的Gap Statistic對應的K即可。

       損失函數記為  ，當分為K類時，Gap Statistic定義為：  。 是 的期望 ，一般由蒙特卡洛模擬產生。我們在樣本所在的區域內按照均勻分布隨機地產生和原始樣本數一樣多的隨機樣本，並對這個隨機樣本做KMeans，得到一個 ，重復多次就可以計算出 的近似值。

       的物理含義是隨機樣本的損失與實際樣本的損失之差。Gap越大說明聚類的效果越好 。一種極端情況是，隨著K的變化 幾乎維持一條直線保持不變。說明這些樣本間沒有明顯的類別關系，數據分布幾乎和均勻分布一致，近似隨機。此時做聚類沒有意義。

（3）改進初始值的選擇

    之前我們採用隨機選擇K個中心的做法，可能導致不同的中心點距離很近，就需要更多的迭代次數才能收斂。如果在選擇初始中心點時能 讓不同的中心盡可能遠離 ，效果往往更好。這類演算法中，以K-Means++演算法最具影響力。

（4）採用核函數

    主要思想是通過一個非線性映射，將輸入空間中的數據點映射到高維的特徵空間中，並在新的空間進行聚類。非線性映射增加了數據點線性可分的概率(與SVM中使用核函數思想類似)對於非凸的數據分布可以達到更為准確的聚類結果。

 (1）初始的K個質心怎麼選？

    最常用的方法是隨機選，初始質心的選取對最終聚類結果有影響，因此演算法一定要多執行幾次，哪個結果更合理，就用哪個結果。當然也有一些優化的方法，第一種是選擇彼此距離最遠的點，具體來說就是先選第一個點，然後選離第一個點最遠的當第二個點，然後選第三個點，第三個點到第一、第二兩點的距離之和最小，以此類推。第二種是先根據其他聚類演算法(如層次聚類)得到聚類結果，從結果中每個分類選一個點

（2）關於離群值？

    離群值就是遠離整體的，非常異常、非常特殊的數據點，在聚類之前應該將這些"極大""極小"之類的離群數據都去掉，否則會對於聚類的結果有影響。但是，離散值往往自身就很有分析的價值，可以把離群值單獨作為一類來分析。

（3）單位要一致！

（4）標准化

    數據中X整體都比較小，比如都是1到10之間的數，Y很大，比如都是1000以上的數，那麼在計算距離的時候Y起到的作用就比X大很多，X對於距離的影響幾乎可以忽略，這也有問題。因此，如果K-Means聚類中選擇歐幾里得距離計算距離，數據集又出現了上面所述的情況，就一定要進行數據的標准化(normalization)，即將數據按比例縮放，使之落入一個小的特定區間。

    K-Means是無監督學習的聚類演算法，沒有樣本輸出；而KNN是監督學習的分類演算法，有對應的類別輸出 。KNN基本不需要訓練，對測試集裡面的點，只需要找到在訓練集中最近的K個點，用這最近的K個點的類別來決定測試點的類別。而K-Means則有明顯的訓練過程，找到K個類別的最佳質心，從而決定樣本的簇類別。當然，兩者也有一些相似點，兩個演算法都包含一個過程，即找出和某一個點最近的點。 兩周都利用了最近鄰的思想 。

2. K-均值演算法（K-means algorithm）

K-均值演算法概述：

首先，我們有一個無標簽數據集，我們想要把它們分成兩個類，然後我們使用k-均值演算法來做：

1、我們選取兩個點，稱為聚類中心（cluster centroids）：

2、遍歷所有的點，更靠近哪個聚類中心，就把它歸為那一個類中：

3、移動聚類中心到它們察態自己類的均值處：

4、然後我們繼續第2步，遍歷所有的點，看它離哪個聚類中心更近就把它歸到那一類中：

5、繼續第3步，移動聚類中心到它們自己類的均值處：

6、繼續第2步：

7、肢族繼續第3步：

8、繼續第2步：

如此反復，當點的顏色不再變化，我們便認為K均值方法已經收斂了。

輸入：

對於沒有明顯區分的數據也可以很好敗飢源的分開：

3. k均值聚類演算法原理

 演算法：
第一步：選K個初始聚類中心，z1(1)，z2(1)，…，zK(1)，其中括弧內的序號為尋找聚類中心的迭代運算斗高並的次序號。聚類中心的向量值可任意設定，例如可選開始的K個模式樣本的向量值作為初始聚類中心。
第二步：逐個將需分類的模式樣本{x}按最小距離准則分配給K個聚類中心中的某一個zj(1)。
假設i=j時， ，則 ，其中k為迭代運算的次序號，第一次迭代k=1，Sj表示第j個聚類，其聚類中心為zj。
第三步：計算各個聚類中心空跡的新的向量值，zj(k+1)，j=1,2,…,K
求各聚類域中所包含樣本的均值向量：

其中Nj為第j個聚類域Sj中所包含的樣本個數。以均值向量作為新的聚類中心，可使如下聚類准則函數最小：

在這一步中要分別計算K個聚類中的樣本均值向量，所以稱之為K-均值演算法。
第四步：若 ，j=1,2,…,K，則返回第二步，將模式樣本逐個重新分類，重復迭代運算；
若 ，j=1,2,…,K，則算念碧法收斂，計算結束。

4. K均值演算法介紹

從沒有標記過的數據中學習稱之為非監督學習。
在非監督學習中，通過演算法來定義一些數據的結構，將數據分別聚合到這些子集中，這種演算法稱之為聚類演算法。

K均值 (K-means) 演算法是最常用的一種聚類演算法。

假設有槐閉運如上的數據集，可以看到只有輸入 ，沒有輸出 。

下面說明一下K均值演算法的過程

K均值演算法的代價函數為：

優化目標就是使用上面的代價函數最小化所有參數。

上述步驟中
第3步集群分配，是通過找到離樣本最近的聚類中心點來最小化代價函數；
第4步移動質心，是通過改變樣本和聚類中心點的距離來最小代價函數。
在K均值演算法中，代價函數是一直下降的，不可能出現上升的情況。

聚類中心的個數 一般都是小於樣本數量 的，因此可以隨機取 個樣本來作為聚類中心。

步驟

這樣做的優點是方便快捷，缺點是不一定能夠找到最佳的聚類中心，容易陷入局部最優。鉛梁
這種陷入局部最優的情況在聚態行類中心過少時一般會出現，一般在 的情況下，解決辦法是多次執行該步驟，比較代價函數的值，取最小值。

聚類中心數量的選擇沒有固定的方法，跟主觀上的判斷有很大關系，也跟業務，以及一些客觀條件，以及使用K均值演算法的目標有關。

5. 簡述K-均值演算法的工作流程

K-均值演算法（K-means clustering algorithm）是一種常見的聚類演算法，用於將一組數據劃分為K個不同的簇或組。其工作流程如下：

• 初始化：隨機選擇K個點作為初始的簇中心（centroid）。

• 分配數據點：對於每個數據點，計算它與每個簇中心的距離，並將它分配到距離最近的簇中心所在的簇。

• 更新簇中心：對於每個簇，計算其所有成員的平均值，並將該平均值作為新的簇中心。

• 重復步驟2和步驟3，直到滿足某個停止准則，例如簇中心不再發生變化，簇內平方和達到最小值，或達到預定的迭代次數。

• 輸出：演算法輸出K個簇及其對應的簇中心。

K-均值演算法是一種迭代演算法，通過不斷地更新簇中心和重新分配數據點，最終將數據點劃分為K個不同的賣猜簇。該演算法的性能與初始的簇中罩型中心的選擇有關，不同的初始選擇可能會導致不同的結果。因此，通常會進行多次運行，選擇最終結果最優的一次運行作為演算法的悶顫輸出。

6. 如何更加有效地選擇的k均值聚類中的k

K均值聚類法分為如下幾個步驟：
一、初慎高始化聚類中心
1、根據具體問題,憑經驗從樣本集中選出C個比較合適的樣本作為初始聚類中心.
2、用前C個樣本作為初始聚類中心.
3、將全部樣本隨機地分成C類,計算每類的樣本均值,將樣凱畢本均值作為初始聚類中心.
二、初始聚類
1、按就近原則將樣本歸入各聚類中心所代表的類中.
2、取一樣本,將其歸入與其最近的聚類中心的那一類中,重新計算樣本均值,更寬孫尺新聚類中心.然後取下一樣本,重復操作,直至所有樣本歸入相應類中.
三、判斷聚類是否合理
採用誤差平方和准則函數判斷聚類是否合理,不合理則修改分類.循環進行判斷、修改直至達到演算法終止條件.

7. 大數據十大經典演算法之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;
}

8. K均值演算法

代價函數可以定義為各個樣本距離所屬簇中心點的誤差平方和

K均值演算法有一些缺點，例如受初值和離群點的影響每次的結果不穩定、結果 通常不是全局最優而是局部最優解、無法很好地解決數據簇分布差別比較大的情 況(比如一類是另一類樣本數量的100倍)、不太適用於離散分類等。但是瑕不掩 瑜，K均值聚類的優點也是很明顯和突出的，主要體現在:對於大數據集，K均值 聚類演算法相對是可伸縮和高效的，它的計算復雜度是O(NKt)接近於線性，其中N是 數據對象的數目，K是聚類的簇數，t是迭代的輪數。盡管演算法經常以局部最優結 束，但一般情況下達到的局部最優已經可以滿足聚類的需求。
其實書中也少講了缺點，那就是關於k的選擇，當維度很高的時候，你很難判斷選擇k多少比較合適。
不過書中在演算法調優中說了。所謂的調優其是也是變相的說那些缺點。

K均值演算法的調優一般可以從以下幾個角度出發。

(1)數據歸一化和離群點處理。
K均值聚類本質上是一種基於歐式距離度量的數據劃分方法，均值和方差大的 維度將對數據的聚類結果產生決定性的影響，所以未做歸一化處理和統一單位的 數據是無法直接參與運算和比較的。同時，離群點或者少量的雜訊數據就會對均 值產生較大的影響，導致中心偏移，因此使用K均值聚類演算法之前通常需要對數據 做預處理。

（2)合理選擇K值。
K值的選擇是K均值聚類最大的問題之一，這也是K均值聚類演算法的主要缺 點。實際上，我們希望能夠找到一些可行的辦法來彌補這一缺點，或者說找到K值 的合理估計方法。但是，K值的選擇一般基於經驗和多次實驗結果。例如採用手肘 法，我們可以嘗試不同的K值，並將不同K值所對應的損失函數畫成折線，橫軸 為K的取值，縱軸為誤差平方和所定義的損失函數，如圖5.3所示

由圖可見，K值越大，距離和越小;並且，當K=3時，存在一個拐點，就像人 的肘部一樣;當K (1,3)時，曲線急速下降;當K>3時，曲線趨於平穩。手肘法認 為拐點就是K的最佳值。
手肘法是一個經驗方法，缺點就是不夠自動化，因此研究員們又提出了一些 更先進的方法，其中包括比較有名的Gap Statistic方法[5]。Gap Statistic方法的優點 是，不再需要肉眼判斷，而只需要找到最大的Gap statistic所對應的K即可，因此該 方法也適用於批量化作業。在這里我們繼續使用上面的損失函數，當分為K簇時， 對應的損失函數記為Dk。Gap Statistic定義為
Gap(K)=E(logDk)−logDk

內按照均勻分布隨機地產生和原始樣本數一樣多的隨機樣本，並對這個隨機樣本
做K均值，得到一個Dk;重復多次就可以計算出E(logDk)的近似值。那麼Gap(K)有
什麼物理含義呢?它可以視為隨機樣本的損失與實際樣本的損失之差。試想實際 樣本對應的最佳簇數為K，那麼實際樣本的損失應該相對較小，隨機樣本損失與實 際樣本損失之差也相應地達到最小值，從而Gap(K)取得最大值所對應的K值就是最 佳的簇數。根據式(5.4)計算K =1,2,...,9所對應的Gap Statistic

(3)採用核函數。
採用核函數是另一種可以嘗試的改進方向。傳統的歐式距離度量方式，使得K 均值演算法本質上假設了各個數據簇的數據具有一樣的先驗概率，並呈現球形或者 高維球形分布，這種分布在實際生活中並不常見。面對非凸的數據分布形狀時， 可能需要引入核函數來優化，這時演算法又稱為核K均值演算法，是核聚類方法的一種 [6]。核聚類方法的主要思想是通過一個非線性映射，將輸入空間中的數據點映射到 高位的特徵空間中，並在新的特徵空間中進行聚類。非線性映射增加了數據點線 性可分的概率，從而在經典的聚類演算法失效的情況下，通過引入核函數可以達到 更為准確的聚類結果。

K均值演算法的主要缺點如下。
(1)需要人工預先確定初始K值，且該值和真實的數據分布未必吻合。
(2)K均值只能收斂到局部最優，效果受到初始值很大。
(3)易受到噪點的影響。
(4)樣本點只能被劃分到單一的類中。

■ K-means++演算法
K均值的改進演算法中，對初始值選擇的改進是很重要的一部分。而這類演算法 中，最具影響力的當屬K-means++演算法。原始K均值演算法最開始隨機選取數據集中 K個點作為聚類中心，而K-means++按照如下的思想選取K個聚類中心。假設已經 選取了n個初始聚類中心(0<n<K)，則在選取第n+1個聚類中心時，距離當前n個 聚類中心越遠的點會有更高的概率被選為第n+1個聚類中心。在選取第一個聚類中 心(n=1)時同樣通過隨機的方法。可以說這也符合我們的直覺，聚類中心當然是 互相離得越遠越好。當選擇完初始點後，K-means++後續的執行和經典K均值演算法 相同，這也是對初始值選擇進行改進的方法等共同點。

■ ISODATA演算法
當K值的大小不確定時，可以使用ISODATA演算法。ISODATA的全稱是迭代自 組織數據分析法。在K均值演算法中，聚類個數K的值需要預先人為地確定，並且在 整個演算法過程中無法更改。而當遇到高維度、海量的數據集時，人們往往很難准 確地估計出K的大小。ISODATA演算法就是針對這個問題進行了改進，它的思想也 很直觀。當屬於某個類別的樣本數過少時，把該類別去除;當屬於某個類別的樣 本數過多、分散程度較大時，把該類別分為兩個子類別。ISODATA演算法在K均值 演算法的基礎之上增加了兩個操作，一是分裂操作，對應著增加聚類中心數;二是 合並操作，對應著減少聚類中心數。ISODATA演算法是一個比較常見的演算法，其缺 點是需要指定的參數比較多，不僅僅需要一個參考的聚類數量Ko，還需要制定3個
閾值。下面介紹ISODATA演算法的各個輸入參數。
(1)預期的聚類中心數目Ko。在ISODATA運行過程中聚類中心數可以變 化，Ko是一個用戶指定的參考值，該演算法的聚類中心數目變動范圍也由其決定。 具體地，最終輸出的聚類中心數目常見范圍是從Ko的一半，到兩倍Ko。
(2)每個類所要求的最少樣本數目Nmin。如果分裂後會導致某個子類別所包 含樣本數目小於該閾值，就不會對該類別進行分裂操作。
(3)最大方差Sigma。用於控制某個類別中樣本的分散程度。當樣本的分散 程度超過這個閾值時，且分裂後滿足(1)，進行分裂操作。
(4)兩個聚類中心之間所允許最小距離Dmin。如果兩個類靠得非常近(即這 兩個類別對應聚類中心之間的距離非常小)，小於該閾值時，則對這兩個類進行
合並操作。
如果希望樣本不劃分到單一的類中，可以使用模糊C均值或者高斯混合模型， 高斯混合模型會在下一節中詳細講述。

K均值聚類的迭代演算法實際上是一種最大期望演算法 (Expectation-Maximization algorithm)，簡稱EM演算法。EM演算法解決的是在概率模 型中含有無法觀測的隱含變數情況下的參數估計問題。
EM演算法只保證收斂到局部最優解

9. k-means聚類演算法常用的終止條件有哪些

K-means 演算法屬於聚類分析方法中一種基本的且應用最廣泛的劃分演算法，它是一種已知聚類類別數的聚類演算法。指定類別數為K，對樣本集合進行聚類，聚類的結果由K 個聚類中心來表達，基於給定的聚類目標函數（或者說是聚類效果判別准則），演算法採用迭代更新的方法，每一次迭代過程都是向目標函數值減小的方向進行，最終的聚類結果使目標函數值取得極小值，達到較優的聚類效果。使用平均誤差准則函數E作為聚類結果好壞的衡量標准之一，保證了演算法運行結果的可靠性和有效性。

10. 什麼是k均值聚類演算法

適用條件：系統聚類法適於二維有序樣品聚類的樣品個數比較均勻。K均值聚類法適用於快速高效，特別是大宴滾褲量數據時使用。

兩者區別如下：

一、指代不同

1、K均值聚類法：是一種迭代求解的聚類分析演算法。

2、系統聚類法：又叫分層聚晌簡類法，聚類分析的一種方法。

二、步驟不同

1、K均值聚類法：步驟是隨機選取K個對象作為初始的聚類中心，然後計算每個對象與各個種子聚類中心之間的距離，把每個對象分配給距離它最近的聚類中心。

2、系統聚類法：開始時把每個樣品作為一類，然後把最靠近的樣品（即距離最小的群品）首先聚為小類，再將已聚合的小類按其類間距離再合並，不斷繼續下去，最後把一切子類都聚合到一個大類。

三、目的不同

1、K均值聚類法：終止條件可以是沒有（或最小數目）對象被重新分配給不同的聚類，沒有（或最小數目）聚類中心再發生變化，誤差平方和局部最小。

2、系統聚類法：是以距離為相似統計量時，確定新類與其他各類之間距離的方法，如最短距離法、最長距離法備滾、中間距離法、重心法、群平均法、離差平方和法、歐氏距離等。