k均值演算法改進

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

㈡ 針對kmeans演算法的缺點可以做哪些方面的改進

一些可以改進的方麵包括：

• 初始化點的選擇：可以使用更加有效的方法來選擇初始聚類中心，以避免初始聚類中心的選擇對結果的影響。

• 相異度度量方法：kmeans演算法使用歐幾里得距離作為相異度度量方法，但可以使用更加適合某些應用場景的其他相異度度量方法，如餘弦相似度、皮爾遜相關系數等。

• 處理異常值：kmeans演算法可能對異常值敏感，可以使用一些方法來降低對異常值的影響。

• 聚類數量的確定：kmeans演算法需要提前確定聚類數量，可以使用一些方法來確定合適的聚類數量，如肘部法則、輪廓系數等。

• 並行化：kmeans演算法是一種計算密集型演算法，可以使用並行化技術加速計算。

㈢ 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演算法只保證收斂到局部最優解