導航:首頁 > 源碼編譯 > k中心演算法代碼

k中心演算法代碼

發布時間:2024-09-18 01:22:18

A. 數據挖掘題目,K—均值演算法應用

第一輪
A1(2,10)
B1(5,8),A3(8,4), B2(7,5),B3(6,4),C2(4,9)
C1(1,2),A2(2,5)
對應中心分別是(2,10),(6,6),(1.5, 3.5)
最後結果:
{A1(2,10),B1(5,8),C2(4,9)}
{A3(8,4), B2(7,5),B3(6,4)}
{C1(1,2),A2(2,5)}

B. 八:聚類演算法K-means(20191223-29)

學習內容:無監督聚類演算法K-Means

k-means:模型原理、收斂過程、超參數的選擇

聚類分析是在數據中發現數據對象之間的關系,將數據進行分組,組內的相似性越大,組間的差別越大,則聚類效果越好。

不同的簇類型: 聚類旨在發現有用的對象簇,在現實中我們用到很多的簇的類型,使用不同的簇類型劃分數據的結果是不同的。

基於原型的: 簇是對象的集合,其中每個對象到定義該簇的 原型 的距離比其他簇的原型距離更近,如(b)所示的原型即為中心點,在一個簇中的數據到其中心點比到另一個簇的中心點更近。這是一種常見的 基於中心的簇 ,最常用的K-Means就是這樣的一種簇類型。 這樣的簇趨向於球形。

基於密度的 :簇是對象的密度區域,(d)所示的是基於密度的簇,當簇不規則或相互盤繞,並且有早上和離群點事,常常使用基於密度的簇定義。

關於更多的簇介紹參考《數據挖掘導論》。

基本的聚類分析演算法

     1. K均值: 基於原型的、劃分的距離技術,它試圖發現用戶指定個數(K)的簇。

     2. 凝聚的層次距離: 思想是開始時,每個點都作為一個單點簇,然後,重復的合並兩個最靠近的簇,直到嘗試單個、包含所有點的簇。

     3. DBSCAN: 一種基於密度的劃分距離的演算法,簇的個數有演算法自動的確定,低密度中的點被視為雜訊而忽略,因此其不產生完全聚類。

不同的距離量度會對距離的結果產生影響,常見的距離量度如下所示:

優點:易於實現 

缺點:可能收斂於局部最小值,在大規模數據收斂慢

演算法思想:

選擇K個點作為初始質心 

repeat

    將每個點指派到最近的質心,形成K個簇 

    重新計算每個簇的質心  

until 簇不發生變化或達到最大迭代次數

這里的「重新計算每個簇的質心」,是根據目標函數來計算的,因此在開始時要考慮 距離度量和目標函數。

考慮歐幾里得距離的數據,使用 誤差平方和(Sum of the Squared Error,SSE) 作為聚類的目標函數,兩次運行K均值產生的兩個不同的簇集,使用SSE最小的那個。

k表示k個聚類中心,ci表示第幾個中心,dist表示的是歐幾里得距離。 

這里有一個問題就是為什麼,我們更新質心是讓所有的點的平均值,這里就是SSE所決定的。

k均值演算法非常簡單且使用廣泛,但是其有主要的兩個缺陷:

1. K值需要預先給定 ,屬於預先知識,很多情況下K值的估計是非常困難的,對於像計算全部微信用戶的交往圈這樣的場景就完全的沒辦法用K-Means進行。對於可以確定K值不會太大但不明確精確的K值的場景,可以進行迭代運算,然後找出Cost Function最小時所對應的K值,這個值往往能較好的描述有多少個簇類。

2. K-Means演算法對初始選取的聚類中心點是敏感的 ,不同的隨機種子點得到的聚類結果完全不同

3. K均值演算法並不是很所有的數據類型。 它不能處理非球形簇、不同尺寸和不同密度的簇,銀冠指定足夠大的簇的個數是他通常可以發現純子簇。

4. 對離群點的數據進行聚類時,K均值也有問題 ,這種情況下,離群點檢測和刪除有很大的幫助。

下面對初始質心的選擇進行討論:

當初始質心是隨機的進行初始化的時候,K均值的每次運行將會產生不同的SSE,而且隨機的選擇初始質心結果可能很糟糕,可能只能得到局部的最優解,而無法得到全局的最優解。

多次運行,每次使用一組不同的隨機初始質心,然後選擇一個具有最小的SSE的簇集。該策略非常的簡單,但是效果可能不是很好,這取決於數據集合尋找的簇的個數。

關於更多,參考《數據挖掘導論》

為了克服K-Means演算法收斂於局部最小值的問題,提出了一種 二分K-均值(bisecting K-means)

將所有的點看成是一個簇

當簇小於數目k時

    對於每一個簇

        計算總誤差

        在給定的簇上進行K-均值聚類,k值為2        計算將該簇劃分成兩個簇後總誤差

    選擇是的誤差最小的那個簇進行劃分

在原始的K-means演算法中,每一次的劃分所有的樣本都要參與運算,如果數據量非常大的話,這個時間是非常高的,因此有了一種分批處理的改進演算法。

使用Mini Batch(分批處理)的方法對數據點之間的距離進行計算。

Mini Batch的好處:不必使用所有的數據樣本,而是從不同類別的樣本中抽取一部分樣本來代表各自類型進行計算。n 由於計算樣本量少,所以會相應的減少運行時間n 但另一方面抽樣也必然會帶來准確度的下降。

聚類試圖將數據集中的樣本劃分為若干個通常是不相交的子集,每個子集成為一個「簇」。通過這樣的劃分,每個簇可能對應於一些潛在的概念(也就是類別);需說明的是,這些概念對聚類演算法而言事先是未知的,聚類過程僅能自動形成簇結構,簇對應的概念語義由使用者來把握和命名。

聚類是無監督的學習演算法,分類是有監督的學習演算法。所謂有監督就是有已知標簽的訓練集(也就是說提前知道訓練集里的數據屬於哪個類別),機器學習演算法在訓練集上學習到相應的參數,構建模型,然後應用到測試集上。而聚類演算法是沒有標簽的,聚類的時候,需要實現的目標只是把相似的東西聚到一起。

聚類的目的是把相似的樣本聚到一起,而將不相似的樣本分開,類似於「物以類聚」,很直觀的想法是同一個簇中的相似度要盡可能高,而簇與簇之間的相似度要盡可能的低。

性能度量大概可分為兩類: 一是外部指標, 二是內部指標 。

外部指標:將聚類結果和某個「參考模型」進行比較。

內部指標:不利用任何參考模型,直接考察聚類結果。

對於給定的樣本集,按照樣本之間的距離大小,將樣本集劃分為K個簇。讓簇內的點盡量緊密的連在一起,而讓簇間的距離盡量的大

初學者會很容易就把K-Means和KNN搞混,其實兩者的差別還是很大的。

K-Means是無監督學習的聚類演算法,沒有樣本輸出;而KNN是監督學習的分類演算法,有對應的類別輸出。KNN基本不需要訓練,對測試集裡面的點,只需要找到在訓練集中最近的k個點,用這最近的k個點的類別來決定測試點的類別。而K-Means則有明顯的訓練過程,找到k個類別的最佳質心,從而決定樣本的簇類別。

當然,兩者也有一些相似點,兩個演算法都包含一個過程,即找出和某一個點最近的點。兩者都利用了最近鄰(nearest neighbors)的思想。

優點:

簡單, 易於理解和實現 ;收斂快,一般僅需5-10次迭代即可,高效

缺點:

    1,對K值得選取把握不同對結果有很大的不同

    2,對於初始點的選取敏感,不同的隨機初始點得到的聚類結果可能完全不同

    3,對於不是凸的數據集比較難收斂

    4,對噪點過於敏感,因為演算法是根據基於均值的

    5,結果不一定是全局最優,只能保證局部最優

    6,對球形簇的分組效果較好,對非球型簇、不同尺寸、不同密度的簇分組效果不好。

K-means演算法簡單理解,易於實現(局部最優),卻會有對初始點、雜訊點敏感等問題;還容易和監督學習的分類演算法KNN混淆。

參考閱讀:

1.《 深入理解K-Means聚類演算法 》

2.《 K-Means 》

C. 直線k中值演算法

不好意思忘了輸出到文件,不知道你指的運行不了是不是這個意思,還有我沒有自己找數據測試過,實在不能保證結果的正確性,下面是輸出到文件的程序
#include <stdio.h>
struct res
{
int x,w,c;
};
FILE* fp;
int n,k;
int ans=2100000000;
struct res r[10];
void dfs(int depth,int prev,int cur)
{
int i,j;
if(depth==k)return;
for(i=prev+1;i<n;i++)
{
int temp=0,tempcur=cur;
tempcur+=r[i].c;
for(j=prev+1;j<i;j++)
{
if(depth==0||(depth!=0&&r[i].x+r[prev].x<r[j].x*2))tempcur+=(r[i].x-r[j].x)*r[j].w;
else
tempcur+=(r[j].x-r[prev].x)*r[j].w;
}
for(j=i+1;j<n;j++)
{
temp+=(r[j].x-r[i].x)*r[j].w;
}
if(tempcur+temp<ans)ans=tempcur+temp;
dfs(depth+1,i,tempcur);
}
}
int main()
{
int i;
fp=fopen("kml0.in","r");
fscanf(fp,"%d%d",&n,&k);
for(i=0;i<n;i++)fscanf(fp,"%d%d%d",&r[i].x,&r[i].w,&r[i].c);
fclose(fp);
dfs(0,-1,0);
fp=fopen("output0.out","w");
fprintf(fp,"%d",ans);
fclose(fp);
return(0);
}

閱讀全文

與k中心演算法代碼相關的資料

熱點內容
料音APP怎麼找 瀏覽:38
怎麼登錄個稅ApP 瀏覽:143
linux網路編程send 瀏覽:903
md5加密演算法php 瀏覽:998
電腦建立了文件夾怎麼編輯內容 瀏覽:959
安卓微信如何轉接蘋果微信上 瀏覽:457
蘭州初學數控編程培訓 瀏覽:887
騰訊程序員很可愛 瀏覽:999
壓縮機有泄壓的嗎 瀏覽:143
壓縮空氣支管需要做氣密性實驗嗎 瀏覽:256
問道達飛注冊工具源碼 瀏覽:911
平安信用卡app怎麼激活 瀏覽:138
單張文件夾力架 瀏覽:843
android自定義jar 瀏覽:546
APP怎麼安裝的系統 瀏覽:924
程序員那麼可愛哪部小說改編的 瀏覽:138
免費解壓軟體官方免費下載 瀏覽:92
程序員做bug被女人懟 瀏覽:808
javajdk配置環境變數 瀏覽:687
京東刷腳本用什麼安卓模擬器 瀏覽:118