"K-mean Clustering"一種用於分類的方法。
在這邊簡單介紹如何去實做一個k-mean clustering 演算法。
首先我們先了解一下何謂 K-mean 演算法->(維基解釋)
然而我們今天要實作的k-mean 演算法則是參考這篇(k-mean 算法)
簡單來說 假設今天有五個點，我們要將他分成兩類(取兩個中心)。 該如何分類?
當然，假設上那兩個中心點是隨機產生的位置。(位置很重要會影響群聚結果)
要如何將A, B ,C ,D ,E 分成兩類?
 |
| 參考資料圖來源 |
上圖之中灰色的點即為兩個分類點。我們要將他分成兩群。
以下為流程順序。
1) A,B,C -> 上面灰色的點 D,E ->灰色的點。 (根據什麼? -> 歐式距離)
2) 然後重新定義他們的中心點。 (根據 幾何取中心點->有限點集的中心)
3) 然後在重新跑 1~2。直到那兩個點不在變動為止。
當然，演算法是簡單的，還有更多延伸部分去將他們分類，群集。
就請參考上述連結去看吧。
首先我們先來看如何取距離 ， 取距離的方式會影響結果。
(機器學習中各種距離算法)
我們這邊使用的是歐式距離
假設有兩個點 A(x1,y1) B(x2,y2)
則他們的距離為 ((x1-x2) ^2 + (y1-y2) ^2 ) ^ (1/2)
那我們如何取中心點呢!? 使用有限點集的中心取點最直覺方式就是
將所有X坐標 以及Y坐標 分別相加 除以 N個點。(請直接參考維基百科)
好吧 各種距離取點方式都講解完了。開始吧!
[程式解說]
開始先宣告點集合 以及類別集合(此處乃指中心點,分群點)
int[,] nodes;
int[,] classes;
然後我們使用動態配置記憶體方式來初始其空間。(這也是C#相當便利的一點)
nodes = new int[nodeNumber,3];
classes = new int[nodeNumber,2];
nodeNumber 是使用者輸入的 點個數。那為什麼classes 也要初始點個數的值呢? ->因為有可能全部分成一類。
然而第二維空間則是
[0] -> x坐標
[1] ->y坐標
[2]->屬於哪一個分群點
接下來就是隨機產生點集合以及分群點
for (int i = 0; i < nodeNumber; i++) {
Random random = new Random((int)DateTime.Now.Millisecond);
// get x
nodes[i, 0] = random.Next(0, 10);
Thread.Sleep(20);
// get y
nodes[i, 1] = random.Next(0, 10);
}
for (int i = 0; i < classNumber; i++){
Random random = new Random((int)DateTime.Now.Millisecond);
// get x
classes[i, 0] = random.Next(0, 10);
Thread.Sleep(20);
// get y
classes[i, 1] = random.Next(0, 10);
}
中間有用到thread.sleep 是因為要使thread稍為停一下而避免取到同樣的值。
距離公式
static double distance(int x1, int y1, int x2 , int y2) {
return Math.Sqrt( Math.Pow((x1-x2),2) + Math.Pow((y1-y2),2));
}
印出結果
static void showResult(int[,] nodes,int nodeNumber,int[,] classes,int classNumber){
for (int i = 0; i < classNumber; i++)
{
System.Console.WriteLine("class[{0}]--({1},{2})",i, classes[i, 0], classes[i, 1]);
}
System.Console.WriteLine("-------------------");
for (int i = 0; i < nodeNumber; i++)
{
System.Console.WriteLine("({0},{1}) --> class[{2}]", nodes[i, 0], nodes[i, 1], nodes[i, 2]);
}
}
核心演算法!!! -> 此處將不斷遞迴至 結果一樣為止
static void kMean(int nodeNumber , int classNumber, int[,] nodes, int[,] classes)
{
//
// A
//
for (int i = 0; i < nodeNumber; i++)
{
double min = 100000;
for (int j = 0; j < classNumber; j++)
{
double mindDistance = distance(nodes[i, 0], nodes[i, 1], classes[j, 0], classes[j, 1]);
if (mindDistance < min)
{
min = mindDistance;
nodes[i, 2] = j; // flag to set the group that the coordinate belong to.
}
}
}
//
// B
//
int[,] tempClasses = new int[nodeNumber, 3];
for (int j = 0; j < classNumber; j++)
{
int[] tempCoordinate = new int[2];
for (int i = 0; i < nodeNumber; i++)
{
if (nodes[i, 2] == j)
{
// new class
tempCoordinate[0] += nodes[i, 0];
tempCoordinate[1] += nodes[i, 1];
tempClasses[j, 2]++;
}
}
if (tempClasses[j, 2] == 0)
tempClasses[j, 2] = 1;
tempClasses[j, 0] = tempCoordinate[0] / tempClasses[j, 2];
tempClasses[j, 1] = tempCoordinate[1] / tempClasses[j, 2];
System.Console.WriteLine("count = {3},class[{0}] :new cor ({1},{2})", j, tempClasses[j, 0], tempClasses[j, 1], tempClasses[j, 2]);
}
//
// C
//
int k = 0;
for ( k = 0; k < classNumber; k++ )
{
if ((tempClasses[k, 0] != classes[k, 0]) || (tempClasses[k, 1] != classes[k, 1]))
{
recursiveFlag = 1;
break;
}
}
if (k >= classNumber)
recursiveFlag = 0;
if (recursiveFlag == 1)
{
for (int j = 0; j < classNumber; j++)
{
classes[j, 0] = tempClasses[j, 0];
classes[j, 1] = tempClasses[j, 1];
}
// recursive
kMean(nodeNumber, classNumber, nodes, classes);
loopCount++;
}
if (recursiveFlag == 0)
{
showResult(nodes, nodeNumber, classes, classNumber);
}
}
這邊解釋一下上述程式碼部分。
A 部分-> 首先先計算各點到分群點的距離 ，並且離分群點較近的群聚再一起
B 部分-> 計算新的 分群點。 (使用上述 有線點集合方法)
C部分-> 檢查是否分群點為一致? 不一致再重新遞迴K-mean 函式。
如此一來就完成了k-mean演算法。
完整程式碼如下:
參考資料來源 :
機器學習中的相似性度量
C# 多維陣列
維基百科-幾何中心
K-mean算法
張志星老師-K-mean
沒有留言:
張貼留言