導航:首頁 > 源碼編譯 > k均值演算法道客巴巴

k均值演算法道客巴巴

發布時間:2023-03-19 02:57:48

㈠ K均值聚類分析的原理

在訓練圖像中,數據事件數量非常多。如果將這些數據事件逐一與模擬區域數據模式進行比對,對計算機性能要求高,計算效率低下。對數據事件分析發現,很多數據事件具有很高的相似性,可以將其劃分為同一類。這樣大大減少數據事件的個數,提高了運算效率。基於這樣考慮,聚類分析技術被引入到多點地質統計學中。

J.B.MacQueen在1967年提出的K-means演算法是到目前為止用於科學和工業應用的諸多聚類演算法中一種極有影響的技術。它是聚類方法中一個基本的劃分方法,常常採用誤差平方和准則函數作為聚類准則函數,誤差平方和准則函數定義為

多點地質統計學原理、方法及應用

式中:mi(i=1,2,…,k)是類i中數據對象的均值,分別代表K個類。

K-means演算法的工作原理:首先隨機從數據集中選取K個點作為初始聚類中心,然後計算各個樣本到聚類中的距離,把樣本歸到離它最近的那個聚類中心所在的類。計算新形成的每一個聚類的數據對象的平均值來得到新的聚類中心,如果相鄰兩次的聚類中心沒滑模有任何變化,說明樣本調整結束,聚類准則函數已經收斂。本演算法的一個特點是在每次迭代中都要考察每個樣本的分類是否正確。若不正確,就要調整,在全部樣本調整完後,再修改聚類中心,進入下一次迭代。如果在一次迭代演算法中,所有的樣本被正確分類,則不會有調整,聚類中心也不會有任何變化,這標志著已經收斂,因此演算法結束。

基本步驟如下:

a.對於數據對象集,任意選取K個對象作為初始的類中心;

b.根據類中對象的平均值,將每個對象重新賦給最相似的類;

c.更新類的平均值,即計算每個類中對象的平均值;

d.重復b和c步驟;

e.直到不再發生變化。

圖2-7是利用K-means方法做的一個數據事件的聚類分析結果。數據類定義為10個。數據事件來自於圖2-8,採用的數據樣板是8×8的數據樣板。

K-means演算法優點為當聚類是密集的,且類與類之間區別明顯時,效果較好。對於處理大數據集,這個算信遲緩法是相對可伸縮和高效的,缺點主要有三個:

圖2-7 K-means方法聚類結果

圖2-8 用於聚類的訓練圖像,數據樣板選擇為8*8

1)在K-means演算法中K是事先給定的,這個K值的選定是非常難以估計的。很多時候,事先並不知道給定的數據集旦敏應該分成多少個類別才最合適。這是K-means演算法的一個不足。

2)在K-means演算法中,首先需要根據初始聚類中心來確定一個初始劃分,然後對初始劃分進行優化。這個初始聚類中心的選擇對聚類結果有較大的影響,一旦初始值選擇的不好,可能無法得到有效的聚類結果,這也成為K-means演算法的一個主要問題。

3)從K-means演算法框架可以看出,該演算法需要不斷地進行樣本分類調整,不斷地計算調整後的新的聚類中心,因此當數據量非常大時,演算法的時間開銷是非常大的。所以需要對演算法的時間復雜度進行分析、改進,提高演算法應用范圍。

㈡ 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,則算念碧法收斂,計算結束。

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

㈣ 大數據十大經典演算法之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演算法是什麼

K-means演算法是一種基於距離的聚類演算法,也叫做K均值或K平均,也經常被稱為勞埃德(Lloyd)演算法。是通過迭代的方式將數據集中的各個點劃分到距離它最近的簇內,距離指的是數據點到簇中心的距離。

K-means演算法的思想很簡單,對於給定的樣本集,按照樣本之間的距離大小,將樣本劃分為K個簇。將簇內的數據盡量緊密的連在一起,而讓簇間的距離盡量的大。

演算法流程

1、選取數據空間中的K個對象作為初始中心,每個對象代表一個聚類中心。

2、對於樣本中的數據對象,根據它們與這些聚類中心的歐氏距離,按距離最近的准則將它們分到距離它們最近的聚類中心(最相似)所對應的類。

3、更新聚類中心:將每個類別中所有對象所對應的均值作為該類別的聚類中心,計算目標函數的值。

4、判斷聚類中心和目標函數的值是否發生改變,若不變,則輸出結果,若改變,則返回2)。

㈥ 什麼是k均值聚類演算法

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

兩者區別如下:

一、指代不同

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

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

二、步驟不同

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

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


三、目的不同

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

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


㈦ K均值演算法介紹

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

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


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

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

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

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

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

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

步驟

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

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

㈧ 聚類演算法 - kmeans

kmeans即k均值演算法。k均值聚類是最著名的劃分聚類演算法,由於簡潔和效率使得他成為所有聚類演算法中最廣泛使用的。給定一個數據點集合和需要的聚類數目k,k由用戶指定,k均值演算法根據某個距離函數反復把數據分入k個聚類中。

簡易動畫過程在這, 傳送門
第一步 ,輸入k的值,即我們希望將數據集經過聚類得到k類,分為k組
第二步 ,從數據集中隨機選擇k個數據點作為初識的聚類中心(質心,Centroid)
第三步 ,對集合中每一個數據點,計算與每一個聚類中心的距離,離哪個中心距離近,就標記為哪個中心。待分配完全時,就有第一次分類。
第四步 ,每一個分類根據現有的數據重新計算,並重新選取每個分類的中心(質心)
第五至N步 ,重復第三至四步,直至符合條件結束迭代步驟。條件是如果新中心和舊中心之間的距離小於某一個設置的閾值(表示重新計算的質心的位置變化不大,趨於穩定,或者說收斂),可以認為我們進行的聚類已經達到期望的結果,終止迭代過程。

該演算法的核心就是選擇合適的k值,不同的k值出來有不同的結果。

手肘法的核心指標是SSE(sum of the squared errors,誤差平方和),

其中,Ci是第i個簇,p是Ci中的樣本點,mi是Ci的質心(Ci中所有樣本的均值),SSE是所有樣本的聚類誤差,代表了聚類效果的好壞。

手肘法的核心思想是:隨著聚類數k的增大,樣本劃分會更加精細,每個簇的聚合程度會逐漸提高,那麼誤差平方和SSE自然會逐漸變小。並且,當k小於真實聚類數時,由於k的增大會大幅增加每個簇的聚合程度,故SSE的下降幅度會很大,而當k到達真實聚類數時,再增加k所得到的聚合程度回報會迅速變小,所以SSE的下降幅度會驟減,然後隨著k值的繼續增大而趨於平緩,也就是說SSE和k的關系圖是一個手肘的形狀,而這個肘部對應的k值就是數據的真實聚類數。當然,這也是該方法被稱為手肘法的原因。

該方法的核心指標是輪廓系數(Silhouette Coefficient),某個樣本點Xi的輪廓系數定義如下:

其中,a是Xi與同簇的其他樣本的平均距離,稱為凝聚度,b是Xi與最近簇中所有樣本的平均距離,稱為分離度。而最近簇的定義是

其中p是某個簇Ck中的樣本。事實上,簡單點講,就是用Xi到某個簇所有樣本平均距離作為衡量該點到該簇的距離後,選擇離Xi最近的一個簇作為最近簇。

求出所有樣本的輪廓系數後再求平均值就得到了 平均輪廓系數 。平均輪廓系數的取值范圍為[-1,1],且簇內樣本的距離越近,簇間樣本距離越遠,平均輪廓系數越大,聚類效果越好。那麼,很自然地,平均輪廓系數最大的k便是最佳聚類數。

(1)容易理解,聚類效果不錯,雖然是局部最優, 但往往局部最優就夠了
(2)處理大數據集的時候,該演算法可以保證較好的伸縮性
(3)當簇近似高斯分布的時候,效果非常不錯
(4)演算法復雜度低

(1)K 值需要人為設定,不同 K 值得到的結果不一樣
(2)對初始的簇中心敏感,不同選取方式會得到不同結果
(3)對異常值敏感
(4)樣本只能歸為一類,不適合多分類任務
(5)不適合太離散的分類、樣本類別不平衡的分類、非凸形狀的分類

㈨ k均值聚類演算法的基本思想包括

一種迭代求解的聚類分析演算法。
其步驟是,世讓預將數據分為K組,則隨機選取K個對象作為初始的聚類中心,然後計算每個對象與各個種子聚類中心之間的距離,把每個對象分配給距離它最近的聚類中心。聚類中心以及分配給它們的對象就代表一個聚類。每分配一個樣本,聚類的聚類中心會根據聚類中現有的對象被重新計算。這個過程將不斷重復直到滿足某個終止條件。終止條件可以是沒有(或最小數目)對象被重新分配給不拍返昌同的聚類,沒有(或最小數目)聚類中心再發襲扒生變化,誤差平方和局部最小。

㈩ 聚類演算法之K均值演算法(k-means)的Python實現

K-means演算法是硬聚類演算法,是典型的基於原型的目標函數聚類方法的代表,它是數據點到原型的某種距離作為優化的目標函數,利用函數求極值的方法得到迭代運算的調整規則。K-means演算法以歐式距離作為相似度測度,它是求對應某一初始聚類中心向量V最優分類,使得評價指標J最小。演算法採用誤差平方和准則函數作為聚類准則函數。

通常,人們根據樣本間的某種距離或者相似性來定義聚類,即把相似的(或距離近的)樣本聚為同一類,而把不相似的(或距離遠的)樣本歸在其他類。

所謂聚類問題,就是給定一個元素集合D,其中每個元素具有n個可觀察屬性,使用某種演算法將D劃分成k個子集,要求每個子集內部的元素之間相異度盡可能低,而不同子集的元素相異度盡可能高。其中每個子集叫做一個簇。

k-means演算法是一種很常見的聚類演算法,它的基本思想是:通過迭代尋找k個聚類的一種劃分方案,使得用這k個聚類的均值來代表相應各類樣本時所得的總體誤差最小。

看起來還不錯

分析一個公司的客戶分類,這樣可以對不同的客戶使用不同的商業策略,或是電子商務中分析商品相似度,歸類商品,從而可以使用一些不同的銷售策略,等等。

閱讀全文

與k均值演算法道客巴巴相關的資料

熱點內容
主角第一個召喚的是妲己 瀏覽:6
導通濾波演算法 瀏覽:285
那個網站可以看到所有的影片 瀏覽:228
蘋果手機怎麼把app放到一起分開 瀏覽:185
如何優化伺服器內存 瀏覽:546
韓國愛情推理片完整版 瀏覽:899
鎖步雙冗餘單片機 瀏覽:577
一本都市小說男主獲得了火龍令 瀏覽:121
台灣女同性戀電影,女主角老年才和愛人在一起 瀏覽:69
女大男小之忘年戀新聞 瀏覽:962
類似渣夫的百惠娘的文 瀏覽:990
主角在現代建國的小說 瀏覽:31
一念天堂 電影 瀏覽:62
編譯原理語法分析收獲 瀏覽:135
小仙兒音頻網盤鏈接 瀏覽:718
有本小說主角叫齊天 瀏覽:136
聊齋電影有哪些 瀏覽:499
精通linux設備驅動開發 瀏覽:691
男主姓霍女主角簡寧 瀏覽:115
會計財經法規pdf 瀏覽:600