K-means | 牛的大腦

k-means
優點:簡單有效率,任一演算法所得之結果,都可透過此方法進行改善
缺點:1各群的資料分佈須呈圓形分佈且有類似的大小時,才能得到較佳的解,2初始值沒設好容易陷入區域最佳解

說明
在分割式方法中，最常被使用也最具代表性的方法為K-means 分群演算法，該方法由MacQueen於1967 所提出來。k-means 分群演算法是一種簡單易懂且廣為使用的非監督式學習的演算法。K-means 分群演算法要先決定將資料分為x個群組，其中每一個群組必須至少包含一項資料，而任何一個資料都應該屬於某一個群組，依據資料之間的距離，取得群組的中心位置，切割出群集與群集之間的界線。

step
1決定群數量
2初始化,有以下兩種做法
做法1,將各資料物件指派(ex:隨機指派)到其中一群,在計算各群中心
做法2,指派(ex:隨機指派)其中一個資料物件當其中一個群中心
3分配每個資料物件到擁有最短矩離的群(每個物件要算自己與每個群中心的距離,若算出來的距離假設是和a群最近,則該物件屬於a群)
4重算所有群中心
5重覆3,4直到所有群中心不在有任何改變
ps:
2維距離公式 sqrt( (1x-2x)^2 + (1y-2y)^2 )
2維N點中心公式 (x1+x2+x3+…+xN)/N,(y1+y2+…+yN)/N
ps:
設點有1,2,3,…,N
維度有x,y,z
3維距離公式 sqrt( (1x-2x)^2 + (1y-2y)^2 + (1z-2z)^2 )
3維N點中心公式 (x1+x2+x3+…+xN)/N,(y1+y2+y3+…+yN)/N,(z1+z2+z3+…+zN)/N

ex:

	x1	x2
a	5	3
b	-1	1
c	1	-2
d	-3	-2

1
設定群數量為2
並隨機分兩群為ab,cd,
2
決定ab的群中心和cd的群中心,如下

	x1	x2
ab	(5+(-1))/2=2	(3+1)/2=2
cd	(1+(-3))/2=-1	(-2+(-2))/2=-2

3
找出點與ab或cd那個最近,以分配每個資料物件到最適合的群,如下
min{(a,ab),(a,cd)}={10,61}=(a,ab)=sqrt(10)
min{(b,ab),(b,cd)}={10,9}=(b,cd)=sqrt(9) 因b,cd小於b,ab,所以b從ab群改到cd群
min{(c,ab),(c,cd)}={17,4}=(c,cd)=sqrt(4)
min{(d,ab),(d,cd)}={41,4}=(d,cd)=sqrt(4)
ps:(x1,y1),(x2,y2)的距離=sqrt((x1-x2)(x1-x2)+(y1-y2)(y1-y2))
根據以上結果,兩群已變成a,bcd
4
重算所有群中心,決定a的群中心和b(cd)的群中心,如下

	x1	x2
a	5	3
b(cd)	(-1+(-1))/2=-1	(1+(-2))/2=-0.5

5
找出點與a或b(cd)那個最近,以分配每個資料物件到最適合的群,如下
min{(a,a),(a,b(cd))}={0,52}=(a,a)=sqrt(0)
min{(b,a),(b,b(cd))}={40,4}=(b,b(cd))=sqrt(4)
min{(c,a),(c,b(cd))}={41,5}=(c,b(cd))=sqrt(5)
min{(d,a),(d,b(cd))}={89,5}=(d,b(cd))=sqrt(5)
根據以上結果,兩群仍然是a,bcd
6
因結果不變,所以為最終分群結果

……………………………….
使用工具
minitab

k-mean步驟
1先將資料貼到worksheet
2點擊stat > multivariate > cluster k-mean ,會跳出對話視窗
2.1將左欄要用到的欄位選取好後按select,則要用到的欄位會出現在右欄variables中
2.2點擊number of cluster,並輸入群的數量
2.3點擊下方storage,會跳出對話視窗,
2.3.1在cluster membership column內輸入一欄位 ex:d
2.3.2點擊ok後storage對話視窗關閉
2.4點擊ok,cluster k-means對話視窗關閉
4結果顯示
ps:
k-mean的輸入資料形式通常為一筆筆的資料,如下(取自uci iris data)
5.7,4.4,1.5,0.4,Iris-setosa
5.4,3.9,1.3,0.4,Iris-setosa
5.1,3.5,1.4,0.3,Iris-setosa
ex:
以上述範例為例,則結果為
a (5,3) 群1
b (-1,1) 群2
c (1,-2) 群2
d (-3,-2)群2
將上述範例改為3個群為例,則結果為
a (5,3) 群1
b (-1,1) 群2
c (1,-2) 群3
d (-3,-2)群2

…………………………..

kmean for php 程式碼(beta)
ps:好像還有一些問題

//kmean for php
//time record
$startime=caclutime();
if($_GET['debug']==1)$kmean['para']['debug']=1; //是否啟用debug mode
$kmean['cluster']['count']=3; //要分的群數量
$datapath='data'; //資料來源
//讀取資料
input_fromfile($kmean['dot'],$datapath);
//執行kmean
kmean($kmean);
//$endtime
$endtime=caclutime();
printf('query took:%3.5fsec',($endtime-$startime));
//////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////
//kmean main function start
function kmean($kmean){
/*
paramenter list
$_GET['init']=1,2,NULL
$_GET['debug']=1,NULL
*/
//記錄所有群中心的位置
//$kmean[cluster][center][int:clusterid:1~n][int:dimensions:1~m]
//ex:
//$kmean[cluster][center][1][1]=cluster1 center value1
//$kmean[cluster][center][1][2]=cluster1 center value2
//$kmean[cluster][center][1][n]=cluster1 center valuem
$kmean['cluster']['center'][1][1]=0;
$kmean['cluster']['center'][1][2]=0;
//記錄該群目前有的點
//$kmean['cluster']['dot'][int:cluster_id:1~m][]
//$kmean[cluster][dot][1][0]=dot_id 第一個群的第一個點的id
//$kmean[cluster][dot][1][1]=dot_id 第一個群的第二個點的id
//記錄所有點的位置及名稱
//$kmean[dot][int:dot_id:1~n][str:name:0]
//$kmean[dot][int:dot_id:1~n][int:dimensions:1~m]
//ex:
//$kmean[dot][1][0]=name
//$kmean[dot][1][1]=value1
//$kmean[dot][1][2]=value2
//$kmean[dot][1][3]=value3
//記錄該點目前的群
//$kmean[dotcluster][int:round:1~n][int:dot_id:1~n]
//ex:
//$kmean[dotcluster][0][1]= 存放第0回合點1的群
//$kmean[dotcluster[0][2]= 存放第0回合點2的群
//$kmean[dotcluster][1][1]= 存放第1回合點1的群
//$kmean[dotcluster][1][2]= 存放第1回合點2的群
if($_GET['debug']==1)$debug=1; //是否啟用debug mode
//取得所有點的總數
$kmean['dotsum']=count($kmean['dot']);
//初始化,先分配dot給指定的群數
if($_GET['init']==null)init_dotcentr_order($kmean);
if($_GET['init']==1)init_dotcentr_remainder($kmean);
if($_GET['init']==2)init_dotcentr_rand($kmean);

/////////////kmean start
while($same<$kmean['dotsum']){
  $same=0; //記錄所有的點在本回合與上一回合相同的數量
  $round++; //記錄回合數
  if($debug==1)echo 'step'.$round.'/n';
//算群中心
  for($i=1;$i<=$kmean['cluster']['count'];$i++){
//$kmean[dot]是所有點的資料
//$kmean[cluster][dot][$i]是$i群的所擁有的點
//群中心的結果會儲存在$kmean[cluster][center][$i]
  computer_clustercenter($kmean['dot'], $kmean['cluster']['dot'][$i] , $kmean['cluster']['center'][$i]);
  if($debug==1){echo 'cluster'.$i.'center=';print_r($kmean['cluster']['center'][$i]);echo '< br>';}
}
unset($kmean['cluster']['dot']);//清空各群有那些點的資料
//重新取得各點與群中心的距離,$i是點
for($i=1;$i<=$kmean['dotsum'];$i++){
//取得該點與所有群的距離,$j是群
  for($j=1;$j<=$kmean['cluster']['count'];$j++){
//取得該點與該群的距離
    $dot2centr[$j]=computer_dot2center($kmean['dot'][$i],$kmean['cluster']['center'][$j]);
//找出和點最近的群中心
    if($dot2centrmin==null){ 
      $dot2centrmin=$dot2centr[$j];
      $kmean['dotcluster'][$round][$i]=$j;
    }else{
      if($dot2centr[$j]<$dot2centrmin){
        $dot2centrmin=$dot2centr[$j];
        $kmean['dotcluster'][$round][$i]=$j; //設定為點的新群
      }
    }
  }
if($debug==1){echo 'dot'.$i.'-clustercenter distance=';print_r($dot2centr);echo '< br>';}
$dot2centrmin=null;
$kmean['cluster']['dot'][$kmean['dotcluster'][$round][$i]][]=$i; //記錄各群有那些點的資料
if( $kmean['dotcluster'][$round][$i]== $kmean['dotcluster'][$round-1][$i])$same++;
//若該回合點的群與上一回合相同則記錄次數,則記錄的次數等同於於點的數量時,就表示本回合與上一回合點的群都沒變過,將觸發while的離開條件
if($debug==1){if( $kmean['dotcluster'][$round][$i]!=$kmean['dotcluster'][$round-1][$i]){
  $debuginfo.=$i.'='.$kmean['dotcluster'][$round-1][$i].'--->'.$kmean['dotcluster'][$round][$i].'< br>';}}
}
if($debug==1){echo 'cluster dot=';print_r($kmean['cluster']['dot']);echo '< br>'.$debuginfo;}
}
//////kmean end

//////////////////
//report
for($i=1;$i<=$kmean['dotsum'];$i++){
while(list($key,$data)=each($kmean['dot'][$i])){
$result.=$data.',';
}
$result.='='.$kmean['dotcluster'][$round][$i];
$result.='
';
}
echo $result;
//other infomation
echo '< br>round='.$round.'< br>';
}
//kmean main function end
/////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////
//init method1 use %
function init_dotcentr_remainder(&$kmean){
for($i=1;$i<=$kmean['dotsum'];$i++){
$clusterid=$i%$kmean['cluster']['count']+1; //計算該點分配的群
$kmean['dotcluster'][0][$i]=$clusterid; //記錄第0回合時該點($i)為那一群
$kmean['cluster']['dot'][$clusterid][]=$i; //記錄該群($clusterid)有那些點($i),並做索引($j)
}
//print_r($kmean['dotcluster'][0]);
//print_r($kmean['cluster']['dot']);
}
////////////////////////////////////////////////////////////////////////////////////////////////
//init method2 use rand
function init_dotcentr_rand(&$kmean){
for($i=1;$i<=$kmean['dotsum'];$i++){
$clusterid=rand(1,$kmean['cluster']['count']); //計算該點分配的群
$kmean['dotcluster'][0][$i]=$clusterid; //記錄第0回合時該點($i)為那一群
$kmean['cluster']['dot'][$clusterid][]=$i; //記錄該群($clusterid)有那些點($i),並做索引($j)
}
//print_r($kmean['dotcluster'][0]);
//print_r($kmean['cluster']['dot']);
}
///////////////////////////////////////////////////////////////////////////////////////////////
//init method3 user by order
function init_dotcentr_order(&$kmean){
$groupcount=ceil($kmean['dotsum']/$kmean['cluster']['count']);
for($i=1;$i<=$kmean['dotsum'];$i++){
if($i%$groupcount==1)$clusterid++;
$kmean['dotcluster'][0][$i]=$clusterid; //記錄第0回合時該點($i)為那一群
$kmean['cluster']['dot'][$clusterid][]=$i; //記錄該群($clusterid)有那些點($i),並做索引($j)
}
//print_r($kmean['dotcluster'][0]);
//print_r($kmean['cluster']['dot']);
}
////////////////////////////////////////////////////////////////////////////////////////////////
function computer_clustercenter($dot_all,$clusterdot_index,&$center){
//$dot_all[1~n][1~m]
//$clusterdot_index[1~x]
//$center[1~m]
$debug=0;
$clusterdot_total=count($clusterdot_index);
$dimensions_total=count($dot_all[1])-1;//要扣除name,所以要減1
for($i=1;$i<=$dimensions_total;$i++){
$center[$i]=0;
for($j=0;$j<$clusterdot_total;$j++){
$center[$i]+=$dot_all[$clusterdot_index[$j]][$i];
if($debug==1){$debuginfo.=$dot_all[$clusterdot_index[$j]][$i].'+';}
}
$center[$i]=$center[$i]/$clusterdot_total;
if($debug==1){echo $center[$i].'='.$debuginfo.'/'.$clusterdot_total.';< br>'; $debuginfo=null;}
}
// (x1+x2+x3+...+xN)/N,(y1+y2+y3+...+yN)/N,(z1+z2+z3+...+zN)/N
}
///////////////////////////////////////////////////////////////////////////////////////////////
function computer_dot2center($dot,$center){
$dimensions_total=count($center);
for($i=1;$i<=$dimensions_total;$i++){
$distance+=($dot[$i]-$center[$i])*($dot[$i]-$center[$i]);
}
//sqrt( (1x-2x)^2 + (1y-2y)^2 + (1z-2z)^2 )
return $distance;
}
//kmean end
/////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////
//////////optional function
///////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////
function input_fromfile(&$kmeandot,$sourcedata){
/*
data fromat description
name1,attribute1_value,attribute2_value,...attributeN_value
name2,attribute1_value,attribute2_value,...attributeN_value
.......
nameN,attribute1_value,attribute2_value,...attributeN_value
ex:
Iris-setosa,5.1,3.5,1.4,0.2
Iris-setosa,4.9,3,1.4,0.2
Iris-setosa,4.7,3.2,1.3,0.2
Iris-setosa,4.6,3.1,1.5,0.2
Iris-setosa,5,3.6,1.4,0.2
ps:attribute must is continue,not discrete
*/
$inputdata=file($sourcedata);
$i=1;
while(list($key,$dot_id)=each($inputdata)){
$dot_id = trim($dot_id, " n.");
$kmeandot[$i++]=explode(',',$dot_id);
}
}
//////////////////////////////////////////////////////////////////////////////////////////////
function caclutime(){
$time = explode( " ", microtime());
$usec = (double)$time[0];
$sec = (double)$time[1];
return $sec + $usec;
}

分享此文：