當前位置:首頁 » 操作系統 » k均值聚類演算法c

k均值聚類演算法c

發布時間: 2024-06-22 06:00:49

⑴ 數據挖掘裡面最簡單的演算法是什麼

鄙人認為k-means演算法不怎麼難,不論是一維的還是二維的,用c或c++實現都不十分復雜,這方面的代碼也很多。

演算法描述:
K均值聚類演算法:
給定類的個數K,將N個對象分到K個類中去,
使得類內對象之間的相似性最大,而類之間的相似性最小。

基本演算法的步驟:
輸入:k, data[n];
(1) 選擇k個初始中心點,例如c[0]=data[0],…c[k-1]=data[k-1];
(2) 對於data[0]….data[n], 分別與c[0]…c[n-1]比較,假定與c[i]差值最少,就標記為i;
(3) 對於所有標記為i點,重新計算c[i]={ 所有標記為i的data[j]之和}/標記為i的個數;
(4) 重復(2)(3),直到所有c[i]值的變化小於給定閾值或者前後兩次的中心不再發生變化。

⑵ 聚類演算法

1. 概述

K-means聚類演算法也稱k均值聚類演算法,是集簡單和經典於一身的基於距離的聚類演算法。它採用距離作為相似性的評價指標,即認為兩個對象的距離越近,其相似度就越大。該演算法認為類簇是由距離靠近的對象組成的,因此把得到 緊湊且獨立的簇作為最終目標。

2. 演算法核心思想

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

3. 演算法實現步驟

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

2、從數據集中隨機選擇k個數據點作為質心。

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

4、把所有數據歸好集合後,一共有k個集合。然後重新計算每個集合的質心。

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

6、如果新質心和原質心距離變化很大,需要迭代3~5步驟。

4. 演算法步驟圖解

上圖a表達了初始的數據集,假設k=2。在圖b中,我們隨機選擇了兩個k類所對應的類別質心,即圖中的紅色質心和藍色質心,然後分別求樣本中所有點到這兩個質心的距離,並標記每個樣本的類別為和該樣本距離最小的質心的類別,如圖c所示,經過計算樣本和紅色質心和藍色質心的距離,我們得到了所有樣本點的第一輪迭代後的類別。此時我們對我們當前標記為紅色和藍色的點分別求其新的質心,如圖d所示,新的紅色質心和藍色質心的位置已經發生了變動。圖e和圖f重復了我們在圖c和圖d的過程,即將所有點的類別標記為距離最近的質心的類別並求新的質心。最終我們得到的兩個類別如圖f。

K-means術語:

簇:所有數據的點集合,簇中的對象是相似的。

質心:簇中所有點的中心(計算所有點的中心而來)

5. K-means演算法優缺點

優點:

1、原理比較簡單,實現也是很容易,收斂速度快。

2、當結果簇是密集的,而簇與簇之間區別明顯時, 它的效果較好。

3、主要需要調參的參數僅僅是簇數k。

缺點:

1、K值需要預先給定,很多情況下K值的估計是非常困難的。

2、K-Means演算法對初始選取的質心點是敏感的,不同的隨機種子點得到的聚類結果完全不同 ,對結果影響很大。

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

4、採用迭代方法,可能只能得到局部的最優解,而無法得到全局的最優解。

⑶ 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均值聚類演算法與模糊C均值聚類演算法在原理和處理步驟上有什麼區別

K均值聚類是隨機選取聚類中心,但是演算法最終不一定會收斂到最優解,這與初值的選取有關,模糊C均值聚類:我覺得是在K均值的基礎上,人為的加入了隸屬度這個概念,通過每步迭代得到每個模式的隸屬度,最後根據隸屬度的大小進行分類!

⑸ k均值聚類演算法、c均值聚類演算法、模糊的c均值聚類演算法的區別

k均值聚類:---------一種硬聚類演算法,隸屬度只有兩個取值0或1,提出的基本根據是「類內誤差平方和最小化」准則;
模糊的c均值聚類演算法:-------- 一種模糊聚類演算法,是k均值聚類演算法的推廣形式,隸屬度取值為[0 1]區間內的任何一個數,提出的基本根據是「類內加權誤差平方和最小化」准則;
這兩個方法都是迭代求取最終的聚類劃分,即聚類中心與隸屬度值。兩者都不能保證找到問題的最優解,都有可能收斂到局部極值,模糊c均值甚至可能是鞍點。
至於c均值似乎沒有這么叫的,至少從我看到文獻來看是沒有。不必糾結於名稱。如果你看的是某本模式識別的書,可能它想表達的意思就是k均值。
實際上k-means這個單詞最先是好像在1965年的一篇文獻提出來的,後來很多人把這種聚類叫做k均值。但是實際上十多年前就有了類似的演算法,但是名字不一樣,k均值的歷史相當的復雜,在若干不同的領域都被單獨提出。追尋演算法的名稱與歷史沒什麼意義,明白具體的實現方法就好了。

⑹ 如何編寫求K-均值聚類演算法的Matlab程序

在聚類分析中,K-均值聚類演算法(k-means
algorithm)是無監督分類中的一種基本方法,其也稱為C-均值演算法,其基本思想是:通過迭代的方法,逐次更新各聚類中心的值,直至得到最好的聚類結果。
假設要把樣本集分為c個類別,演算法如下:
(1)適當選擇c個類的初始中心;
(2)在第k次迭代中,對任意一個樣本,求其到c個中心的距離,將該樣本歸到距離最短的中心所在的類,
(3)利用均值等方法更新該類的中心值;
(4)對於所有的c個聚類中心,如果利用(2)(3)的迭代法更新後,值保持不變,則迭代結束,否則繼續迭代。
下面介紹作者編寫的一個分兩類的程序,可以把其作為函數調用。
%%
function
[samp1,samp2]=kmeans(samp);
作為調用函數時去掉注釋符
samp=[11.1506
6.7222
2.3139
5.9018
11.0827
5.7459
13.2174
13.8243
4.8005
0.9370
12.3576];
%樣本集
[l0
l]=size(samp);
%%利用均值把樣本分為兩類,再將每類的均值作為聚類中心
th0=mean(samp);n1=0;n2=0;c1=0.0;c1=double(c1);c2=c1;for
i=1:lif
samp(i)<th0
c1=c1+samp(i);n1=n1+1;elsec2=c2+samp(i);n2=n2+1;endendc1=c1/n1;c2=c2/n2;
%初始聚類中心t=0;cl1=c1;cl2=c2;
c11=c1;c22=c2;
%聚類中心while
t==0samp1=zeros(1,l);
samp2=samp1;n1=1;n2=1;for
i=1:lif
abs(samp(i)-c11)<abs(samp(i)-c22)
samp1(n1)=samp(i);
cl1=cl1+samp(i);n1=n1+1;
c11=cl1/n1;elsesamp2(n2)=samp(i);
cl2=cl2+samp(i);n2=n2+1;
c22=cl2/n2;endendif
c11==c1
&&
c22==c2t=1;endcl1=c11;cl2=c22;
c1=c11;c2=c22;
end
%samp1,samp2為聚類的結果。
初始中心值這里採用均值的辦法,也可以根據問題的性質,用經驗的方法來確定,或者將樣本集隨機分成c類,計算每類的均值。
k-均值演算法需要事先知道分類的數量,這是其不足之處。

⑺ kmeans聚類演算法是什麼

K-means演算法是最為經典的基於劃分的聚類方法,是十大經典數據挖掘演算法之一。K-means演算法的基本思想是:以空間中k個點為中心進行聚類,對最靠近他們的對象歸類。通過迭代的方法,逐次更新各聚類中心的值,直至得到最好的聚類結果。

聚類屬於無監督學習,以往的回歸、樸素貝葉斯、SVM等都是有類別標簽y的,也就是說樣例中已經給出了樣例的分類。而聚類的樣本中卻沒有給定y,只有特徵x,比如假設宇宙中的星星可以表示成三維空間中的點集。

(7)k均值聚類演算法c擴展閱讀:

k個聚類以便使得所獲得的聚類滿足:同一聚類中的對象相似度較高;而不同聚類中的對象相似度較小。聚類相似度是利用各聚類中對象的均值所獲得一個「中心對象」(引力中心)來進行計算的。

(1)適當選擇c個類的初始中心;

(2)在第k次迭代中,對任意一個樣本,求其到c個中心的距離,將該樣本歸到距離最短的中心所在的類;

(3)利用均值等方法更新該類的中心值;

(4)對於所有的c個聚類中心,如果利用(2)(3)的迭代法更新後,值保持不變,則迭代結束,否則繼續迭代。

熱點內容
ftp免費工具 發布:2024-07-14 02:34:24 瀏覽:246
android應用查看簽名 發布:2024-07-14 02:19:54 瀏覽:615
sql的演算法 發布:2024-07-14 02:18:07 瀏覽:381
以下是c語言的特點 發布:2024-07-14 02:07:10 瀏覽:441
世界上第一個編譯儀 發布:2024-07-14 02:06:36 瀏覽:439
java腳本實現搶qq紅包 發布:2024-07-14 02:05:13 瀏覽:977
編譯原理461 發布:2024-07-14 01:33:12 瀏覽:572
腳本運行時間長 發布:2024-07-14 01:02:09 瀏覽:793
電腦版花雨庭伺服器ip地址是什麼 發布:2024-07-14 00:42:39 瀏覽:768
凱美瑞國產版哪個配置好 發布:2024-07-14 00:41:51 瀏覽:953