本文目錄一覽：
- 1、聚類算法–KMeans
- 2、kmeans算法用Python怎麼實現
- 3、一段代碼，求教.k-means算法的分割
- 4、KMEANS算法。哪位高手指點一下啊。知道kmeans算法但看不懂下面代碼。請盡量多注釋一下啊。謝謝啦！在線等
聚類算法–KMeans
與分類、序列標註等任務不同，聚類是在事先並不知道任何樣本標籤的情況下，通過數據之間的內在關係把樣本劃分為若干類別，使得同類別樣本之間的相似度高，不同類別之間的樣本相似度低(即增大類內聚，減少類間距)。
聚類屬於非監督學習，K均值聚類是最基礎常用的聚類算法。它的基本思想是，通過迭代尋找K個簇(Cluster)的一種劃分方案，使得聚類結果對應的損失函數最小。其中，損失函數可以定義為各個樣本距離所屬簇中心點的誤差平方和。
其中 代表第i個樣本， 是 所屬的簇， 代表簇對應的中心點，M是樣本總數。
相關概念：
K值： 要得到的簇的個數。
質心： 每個簇的均值向量。即向量各維取平均即可。
距離量度： 常用歐幾里得距離和餘弦相似度(先標準化)。
KMeans的主要思想是：在給定K值和K個初始類簇中心點的情況下，把每個點(亦即數據記錄)分到離其最近的類簇中心點所代表的類簇中，所有點分配完畢之後，根據一個類簇內的所有點重新計算該類簇的中心點(取平均值)，然後再迭代的進行分配點和更新類簇中心點的步驟，直至類簇中心點的變化很小，或者達到指定的迭代次數。
KMeans的核心目標是將給定的數據集劃分成K個簇(K是超餐)，並給出每個樣本數據對應的中心點。具體步驟非常簡單：
（1）首先確定一個K值，即我們希望將數據集經過聚類得到k個集合。
（2）從數據集中隨機選擇K個數據點作為質心。
（3）對數據集中每一個點，計算其與每一個質心的距離(如歐式距離)，離哪個質心近，就劃分到哪個質心所屬的集合。
（4）把所有數據歸好集合後，一共有K個集合。然後重新計算每個集合的質心。
（5）如果新計算出來的質心和原來的質心之間的距離小於某一個設置的閾值(表示重新計算的質心的位置變化不大，趨於穩定，或者說收斂)，我們可以認為聚類已經達到期望的結果，算法終止。
（6）如果新質心和原質心距離變化很大，需要迭代3-5步驟。
KMeans最核心的部分是先固定中心點，調整每個樣本所屬的類別來減少J；再固定每個樣本的類別，調整中心點繼續減小J。兩個過程交替循環，J單調遞減直到極小值，中心點和樣本劃分的類別同時收斂。
KMeans的優點 ：
高效可伸縮，計算複雜度為O(NKt)接近於線性(N是數據量，K是聚類總數，t是迭代輪數)。
收斂速度快，原理相對通俗易懂，可解釋性強。
當結果簇是密集的，而簇與簇之間區別是明顯時，他的效果較好。主要需要調參的參數僅僅是簇數K。
缺點 ：
受初始值和異常點影響，聚類結果可能不是全局最優而是局部最優。K-Means算法對初始選取的質心點是敏感的，不同的隨機種子點得到的聚類結果完全不同，對結果影響很大。
K是超參數，一般需要按經驗選擇。
對噪音和異常點比較的敏感，用來檢測異常值。
只能發現球狀的簇。在K-Means中，我們用單個點對cluster進行建模，這實際上假設各個cluster的數據是呈高維球型分布的，但是在生活中出現這種情況的概率並不算高。例如，每一個cluster是一個一個的長條狀的，K-Means的則根本識別不出來這種類別( 這種情況可以用GMM )。實際上，K-Means是在做凸優化，因此處理不了非凸的分布。
根據以上特點，我們可以從下面幾個角度對算法做調優。
（1）數據預處理：歸一化和異常點過濾
KMeans本質是一種基於歐式距離度量的數據劃分方法，均值和方差大的維度將對數據的聚類結果產生決定性影響 。所以在聚類前對數據( 具體的說是每一個維度的特徵 )做歸一化和單位統一至關重要。此外，異常值會對均值計算產生較大影響，導致 中心偏移 ，這些噪聲點最好能提前過濾。
（2）合理選擇K值
K值的選擇一般基於實驗和多次實驗結果。例如採用 手肘法 ，嘗試不同K值並將對應的損失函數畫成折線。手肘法認為圖上的 拐點就是K的最佳值 (k=3)。
為了將尋找最佳K值的過程自動化，研究人員提出了Gap Statistic方法。不需要人們用肉眼判斷，只需要找到最大的Gap Statistic對應的K即可。
損失函數記為 ，當分為K類時，Gap Statistic定義為： 。 是 的期望 ，一般由蒙特卡洛模擬產生。我們在樣本所在的區域內按照均勻分布隨機地產生和原始樣本數一樣多的隨機樣本，並對這個隨機樣本做KMeans，得到一個 ，重複多次就可以計算出 的近似值。
的物理含義是隨機樣本的損失與實際樣本的損失之差。Gap越大說明聚類的效果越好 。一種極端情況是，隨着K的變化 幾乎維持一條直線保持不變。說明這些樣本間沒有明顯的類別關係，數據分布幾乎和均勻分布一致，近似隨機。此時做聚類沒有意義。
（3）改進初始值的選擇
之前我們採用隨機選擇K個中心的做法，可能導致不同的中心點距離很近，就需要更多的迭代次數才能收斂。如果在選擇初始中心點時能 讓不同的中心儘可能遠離 ，效果往往更好。這類算法中，以K-Means++算法最具影響力。
（4）採用核函數
主要思想是通過一個非線性映射，將輸入空間中的數據點映射到高維的特徵空間中，並在新的空間進行聚類。非線性映射增加了數據點線性可分的概率(與SVM中使用核函數思想類似)對於非凸的數據分布可以達到更為準確的聚類結果。
(1）初始的K個質心怎麼選？
最常用的方法是隨機選，初始質心的選取對最終聚類結果有影響，因此算法一定要多執行幾次，哪個結果更合理，就用哪個結果。當然也有一些優化的方法，第一種是選擇彼此距離最遠的點，具體來說就是先選第一個點，然後選離第一個點最遠的當第二個點，然後選第三個點，第三個點到第一、第二兩點的距離之和最小，以此類推。第二種是先根據其他聚類算法(如層次聚類)得到聚類結果，從結果中每個分類選一個點
（2）關於離群值？
離群值就是遠離整體的，非常異常、非常特殊的數據點，在聚類之前應該將這些”極大””極小”之類的離群數據都去掉，否則會對於聚類的結果有影響。但是，離散值往往自身就很有分析的價值，可以把離群值單獨作為一類來分析。
（3）單位要一致！
（4）標準化
數據中X整體都比較小，比如都是1到10之間的數，Y很大，比如都是1000以上的數，那麼在計算距離的時候Y起到的作用就比X大很多，X對於距離的影響幾乎可以忽略，這也有問題。因此，如果K-Means聚類中選擇歐幾里得距離計算距離，數據集又出現了上面所述的情況，就一定要進行數據的標準化(normalization)，即將數據按比例縮放，使之落入一個小的特定區間。
K-Means是無監督學習的聚類算法，沒有樣本輸出；而KNN是監督學習的分類算法，有對應的類別輸出 。KNN基本不需要訓練，對測試集裡面的點，只需要找到在訓練集中最近的K個點，用這最近的K個點的類別來決定測試點的類別。而K-Means則有明顯的訓練過程，找到K個類別的最佳質心，從而決定樣本的簇類別。當然，兩者也有一些相似點，兩個算法都包含一個過程，即找出和某一個點最近的點。 兩周都利用了最近鄰的思想 。
kmeans算法用Python怎麼實現
1、從Kmeans說起
Kmeans是一個非常基礎的聚類算法，使用了迭代的思想，關於其原理這裡不說了。下面說一下如何在matlab中使用kmeans算法。
創建7個二維的數據點：
複製代碼 代碼如下:
x=[randn(3,2)*.4;randn(4,2)*.5+ones(4,1)*[4 4]];
使用kmeans函數：
複製代碼 代碼如下:
class = kmeans(x, 2);
x是數據點，x的每一行代表一個數據；2指定要有2個中心點，也就是聚類結果要有2個簇。 class將是一個具有70個元素的列向量，這些元素依次對應70個數據點，元素值代表着其對應的數據點所處的分類號。某次運行後，class的值是：
複製代碼 代碼如下:
2
2
2
1
1
1
1
這說明x的前三個數據點屬於簇2，而後四個數據點屬於簇1。 kmeans函數也可以像下面這樣使用：
複製代碼 代碼如下:
[class, C, sumd, D] = kmeans(x, 2)
class =
2
2
2
1
1
1
1
C =
4.0629 4.0845
-0.1341 0.1201
sumd =
1.2017
0.2939
D =
34.3727 0.0184
29.5644 0.1858
36.3511 0.0898
0.1247 37.4801
0.7537 24.0659
0.1979 36.7666
0.1256 36.2149
class依舊代表着每個數據點的分類;C包含最終的中心點，一行代表一個中心點；sumd代表着每個中心點與所屬簇內各個數據點的距離之和；D的
每一行也對應一個數據點，行中的數值依次是該數據點與各個中心點之間的距離，Kmeans默認使用的距離是歐幾里得距離（參考資料[3]）的平方值。
kmeans函數使用的距離，也可以是曼哈頓距離（L1-距離），以及其他類型的距離，可以通過添加參數指定。
kmeans有幾個缺點（這在很多資料上都有說明）：
1、最終簇的類別數目（即中心點或者說種子點的數目）k並不一定能事先知道，所以如何選一個合適的k的值是一個問題。
2、最開始的種子點的選擇的好壞會影響到聚類結果。
3、對噪聲和離群點敏感。
4、等等。
2、kmeans++算法的基本思路
kmeans++算法的主要工作體現在種子點的選擇上，基本原則是使得各個種子點之間的距離儘可能的大，但是又得排除噪聲的影響。 以下為基本思路：
1、從輸入的數據點集合（要求有k個聚類）中隨機選擇一個點作為第一個聚類中心
2、對於數據集中的每一個點x，計算它與最近聚類中心(指已選擇的聚類中心)的距離D(x)
3、選擇一個新的數據點作為新的聚類中心，選擇的原則是：D(x)較大的點，被選取作為聚類中心的概率較大
4、重複2和3直到k個聚類中心被選出來
5、利用這k個初始的聚類中心來運行標準的k-means算法
假定數據點集合X有n個數據點，依次用X(1)、X(2)、……、X(n)表示，那麼，在第2步中依次計算每個數據點與最近的種子點（聚類中心）的
距離，依次得到D(1)、D(2)、……、D(n)構成的集合D。在D中，為了避免噪聲，不能直接選取值最大的元素，應該選擇值較大的元素，然後將其對應
的數據點作為種子點。
如何選擇值較大的元素呢，下面是一種思路（暫未找到最初的來源，在資料[2]等地方均有提及，筆者換了一種讓自己更好理解的說法）：
把集合D中的每個元素D(x)想象為一根線L(x)，線的長度就是元素的值。將這些線依次按照L(1)、L(2)、……、L(n)的順序連接起來，組成長
線L。L(1)、L(2)、……、L(n)稱為L的子線。根據概率的相關知識，如果我們在L上隨機選擇一個點，那麼這個點所在的子線很有可能是比較長的子
線，而這個子線對應的數據點就可以作為種子點。下文中kmeans++的兩種實現均是這個原理。
3、python版本的kmeans++
在 中能找到多種編程語言版本的Kmeans++實現。下面的內容是基於python的實現（中文注釋是筆者添加的）：
複製代碼 代碼如下:
from math import pi, sin, cos
from collections import namedtuple
from random import random, choice
from copy import copy
try:
import psyco
psyco.full()
except ImportError:
pass
FLOAT_MAX = 1e100
class Point:
__slots__ = [“x”, “y”, “group”]
def __init__(self, x=0.0, y=0.0, group=0):
self.x, self.y, self.group = x, y, group
def generate_points(npoints, radius):
points = [Point() for _ in xrange(npoints)]
# note: this is not a uniform 2-d distribution
for p in points:
r = random() * radius
ang = random() * 2 * pi
p.x = r * cos(ang)
p.y = r * sin(ang)
return points
def nearest_cluster_center(point, cluster_centers):
“””Distance and index of the closest cluster center”””
def sqr_distance_2D(a, b):
return (a.x – b.x) ** 2 + (a.y – b.y) ** 2
min_index = point.group
min_dist = FLOAT_MAX
for i, cc in enumerate(cluster_centers):
d = sqr_distance_2D(cc, point)
if min_dist d:
min_dist = d
min_index = i
return (min_index, min_dist)
”’
points是數據點，nclusters是給定的簇類數目
cluster_centers包含初始化的nclusters個中心點，開始都是對象-(0,0,0)
”’
def kpp(points, cluster_centers):
cluster_centers[0] = copy(choice(points)) #隨機選取第一個中心點
d = [0.0 for _ in xrange(len(points))] #列表，長度為len(points)，保存每個點離最近的中心點的距離
for i in xrange(1, len(cluster_centers)): # i=1…len(c_c)-1
sum = 0
for j, p in enumerate(points):
d[j] = nearest_cluster_center(p, cluster_centers[:i])[1] #第j個數據點p與各個中心點距離的最小值
sum += d[j]
sum *= random()
for j, di in enumerate(d):
sum -= di
if sum 0:
continue
cluster_centers[i] = copy(points[j])
break
for p in points:
p.group = nearest_cluster_center(p, cluster_centers)[0]
”’
points是數據點，nclusters是給定的簇類數目
”’
def lloyd(points, nclusters):
cluster_centers = [Point() for _ in xrange(nclusters)] #根據指定的中心點個數，初始化中心點，均為(0,0,0)
# call k++ init
kpp(points, cluster_centers) #選擇初始種子點
# 下面是kmeans
lenpts10 = len(points) 10
changed = 0
while True:
# group element for centroids are used as counters
for cc in cluster_centers:
cc.x = 0
cc.y = 0
cc.group = 0
for p in points:
cluster_centers[p.group].group += 1 #與該種子點在同一簇的數據點的個數
cluster_centers[p.group].x += p.x
cluster_centers[p.group].y += p.y
for cc in cluster_centers: #生成新的中心點
cc.x /= cc.group
cc.y /= cc.group
# find closest centroid of each PointPtr
changed = 0 #記錄所屬簇發生變化的數據點的個數
for p in points:
min_i = nearest_cluster_center(p, cluster_centers)[0]
if min_i != p.group:
changed += 1
p.group = min_i
# stop when 99.9% of points are good
if changed = lenpts10:
break
for i, cc in enumerate(cluster_centers):
cc.group = i
return cluster_centers
def print_eps(points, cluster_centers, W=400, H=400):
Color = namedtuple(“Color”, “r g b”);
colors = []
for i in xrange(len(cluster_centers)):
colors.append(Color((3 * (i + 1) % 11) / 11.0,
(7 * i % 11) / 11.0,
(9 * i % 11) / 11.0))
max_x = max_y = -FLOAT_MAX
min_x = min_y = FLOAT_MAX
for p in points:
if max_x p.x: max_x = p.x
if min_x p.x: min_x = p.x
if max_y p.y: max_y = p.y
if min_y p.y: min_y = p.y
scale = min(W / (max_x – min_x),
H / (max_y – min_y))
cx = (max_x + min_x) / 2
cy = (max_y + min_y) / 2
print “%%!PS-Adobe-3.0\n%%%%BoundingBox: -5 -5 %d %d” % (W + 10, H + 10)
print (“/l {rlineto} def /m {rmoveto} def\n” +
“/c { .25 sub exch .25 sub exch .5 0 360 arc fill } def\n” +
“/s { moveto -2 0 m 2 2 l 2 -2 l -2 -2 l closepath ” +
” gsave 1 setgray fill grestore gsave 3 setlinewidth” +
” 1 setgray stroke grestore 0 setgray stroke }def”)
for i, cc in enumerate(cluster_centers):
print (“%g %g %g setrgbcolor” %
(colors[i].r, colors[i].g, colors[i].b))
for p in points:
if p.group != i:
continue
print (“%.3f %.3f c” % ((p.x – cx) * scale + W / 2,
(p.y – cy) * scale + H / 2))
print (“\n0 setgray %g %g s” % ((cc.x – cx) * scale + W / 2,
(cc.y – cy) * scale + H / 2))
print “\n%%%%EOF”
def main():
npoints = 30000
k = 7 # # clusters
points = generate_points(npoints, 10)
cluster_centers = lloyd(points, k)
print_eps(points, cluster_centers)
main()
上述代碼實現的算法是針對二維數據的，所以Point對象有三個屬性，分別是在x軸上的值、在y軸上的值、以及所屬的簇的標識。函數lloyd是
kmeans++算法的整體實現，其先是通過kpp函數選取合適的種子點，然後對數據集實行kmeans算法進行聚類。kpp函數的實現完全符合上述
kmeans++的基本思路的2、3、4步。
一段代碼，求教.k-means算法的分割
A=imread(‘1.jpg’);
figure;
imshow(A);
title(‘Hawk’);
cform=makecform(‘srgb2lab’);
lab_A=applycform(A,cform); 這裡為什麼要轉去lab空間，其他的轉換不好用嗎？對於顏色分割的吧 lab空間相互分量聯繫性比較小 利於分割
ab = double(lab_A(:,:,2:3));
nrows = size(ab,1);
ncols = size(ab,2);
ab = reshape(ab,nrows*ncols,2);矩陣轉換類型轉換為double型，這裡的轉換有其他的靈活用法嗎？
nColors =2;
% 採用k-means方法實現聚類，重複三次
[cluster_idx cluster_center] = kmeans(ab,nColors,’distance’,’sqEuclidean’, …
‘Replicates’,3); 這一段東西後面的省略號是啥意思啊？省略號表示一行寫不完 分行的 意思就是kmeans(ab,nColors,’distance’,’sqEuclidean’, ‘Replicates’,3); 一樣的
%對不同的類別進行標誌
pixel_labels = reshape(cluster_idx,nrows,ncols); 這裡也是矩陣轉換嗎？恩師矩陣轉化 你最好看看help
figure;
imshow(pixel_labels,[]), title(‘聚類以後的現實圖片’);
%分類後的矩陣
segmented_images = cell(1,3);
rgb_label = repmat(pixel_labels,[1 1 3]);
for k = 1:nColors
color = A;
color(rgb_label ~= k) = 0;
segmented_images{k} = color;
end
figure;
imshow(segmented_images{1}), title(‘objects in cluster 1’);
figure;
imshow(segmented_images{2}), title(‘objects in cluster 2’);
這段代碼運行，對於圖片有什麼要求嗎，這點很重要，請高手一定要指點下，小弟感恩不盡。我運行後顯示
ans =
KMEANS算法。哪位高手指點一下啊。知道kmeans算法但看不懂下面代碼。請盡量多注釋一下啊。謝謝啦！在線等
程序需要一個數據文件
格式如下：
5 2 3
2 3 4 5 10 12 5 1 12 10
其中，5表示數據的數量，2表示數據的維度，3表示聚類的數量。
後面每兩個實數對應一個數據點。
不過這個程序始數據維數固定為2，後來想改成4以下的任意維度，但沒有改完，所以其實只能為2維。
我已經對程序做了注釋。
#include stdio.h
#include stdlib.h
#include string.h
#include conio.h
#include math.h
#define SUCCESS 1
#define FAILURE 0
#define TRUE 1
#define FALSE 0
#define MAXVECTDIM 4 // 數據最大維數 (看來這個程序寫了一半，維數實際上只能為2)
#define MAXPATTERN 1588 // 數據數量最大值
#define MAXCLUSTER 10 // 聚類最大值
// 聚類結構
struct aCluster {
double Center[MAXVECTDIM]; // 中心/引力數據對象
int Member[MAXPATTERN]; // 該聚類中數據在Pattern中的索引
int NumMembers; // 數據的數量
};
struct aVector {
double Center[MAXVECTDIM];
int Size;
};
static double Pattern[MAXPATTERN][MAXVECTDIM + 1]; // 所有數據存放在這個數組中
// 所以的東西都擱System類裡面了
class System {
private :
aCluster Cluster[MAXCLUSTER]; // 聚類數組
int NumPatterns; // 輸入數據的數量
int SizeVector; // 數據的維數
int NumClusters; // 數據的聚類數
void DistributeSamples(); // 根據中心聚類，重新分配數據到不同的聚類
int CalcNewClustCenters(); // 重新計算新的聚類中心
double EucNorm(int, int); // 誤差準則
int FindClosestCluster(int); // 查找最接近的聚類
public :
System() {};
int LoadPatterns(char * fname); // 從文件中讀取數據
void InitClusters(); // 初始化聚類
void RunKMeans(); // 執行K-Means算法
void ShowClusters(); // 顯示聚類
void SaveClusters(char * fname); // 保存聚類到文件中
void ShowCenters(); // 顯示聚類中心數據
};
void System::ShowCenters() {
int i;
printf(“Cluster centers:\n”);
for (i = 0; i NumClusters; i++) {
Cluster[i].Member[0] = i;
printf(“ClusterCenter[%d]=(%f,%f)\n”, i, Cluster[i].Center[0],Cluster[i].Center[1]);
int b=0;
}
printf(“\n”);
}
int System::LoadPatterns(char * fname) {
FILE * InFilePtr;
int i, j;
double x;
if ( (InFilePtr = fopen(fname, “r”)) == NULL)
return FAILURE;
// 讀入數據的數量，維度和聚類數的數量
fscanf(InFilePtr, “%d”, NumPatterns);
fscanf(InFilePtr, “%d”, SizeVector);
fscanf(InFilePtr, “%d”, NumClusters);
// 讀入數據
for (i = 0; i NumPatterns; i++) {
for (j = 0; j SizeVector; j++) {
fscanf(InFilePtr, “%lg”, x);
Pattern[i][j] = x;
}
}
// 打印讀入的數據
printf(“Input patterns:\n”);
for (i = 0; i NumPatterns; i++) {
printf(“Pattern[%d]=(%2.3f,%2.3f,%d,%d)\n”, i, Pattern[i][0], Pattern[i][1],Pattern[i][2], Pattern[i][3]);
}
printf(“\n——————–\n”);
return SUCCESS;
}
void System::InitClusters() {
int i, j;
SizeVector=2; // 看來開始數據維數固定為2，後來想改成4以下的任意維度，但沒有改完
printf(“Initial cluster centers:\n”);
// 把前NumClusters個數據作為NumClusters個聚類的數據中心
for (i = 0; i NumClusters; i++) {
Cluster[i].Member[0] = i; // 記錄這個數據的索引到第i個聚類中
for (j = 0; j SizeVector; j++) {
Cluster[i].Center[j] = Pattern[i][j]; // 把這個數據作為數據中心
}
}
// 打印聚類的數據中心
for (i = 0; i NumClusters; i++) {
printf(“ClusterCenter[%d]=(%f,%f)\n”, i, Cluster[i].Center[0], Cluster[i].Center[1]);
}
printf(“\n”);
}
void System::RunKMeans() {
int converged; // 是否收斂
int pass; // 計算的趟數
pass = 1; // 第一趟
converged = FALSE; // 沒有收斂
while (converged == FALSE) { // 沒有收斂的情況下反覆跑
printf(“PASS=%d\n”, pass++); // 打印趟數
DistributeSamples(); // 重新分配數據
converged = CalcNewClustCenters(); // 計算新的聚類中心，如果計算結果和上次相同，認為已經收斂
ShowCenters(); // 顯示聚類中心
}
}
// 第p個數據到第c個聚類中心的誤差準則(距離的平方)
double System::EucNorm(int p, int c) {
double dist, x; // x可能是調試用，沒有實際作用
int i;
dist = 0;
// 將每個維度的差的平方相加，得到距離的平方
for (i = 0; i SizeVector; i++) {
x = (Cluster[c].Center[i] – Pattern[p][i]) *
(Cluster[c].Center[i] – Pattern[p][i]);
dist += (Cluster[c].Center[i] – Pattern[p][i]) *
(Cluster[c].Center[i] – Pattern[p][i]);
}
return dist;
}
// 查找第pat個數據的最近聚類
int System ::FindClosestCluster(int pat) {
int i, ClustID/*最近聚類的ID*/;
double MinDist/*最小誤差*/, d;
MinDist = 9.9e+99; // 初始為一個極大的值
ClustID = -1;
// 依次計算3個聚類到第pat個數據的誤差，找出最小值
for (i = 0; i NumClusters; i++) {
d = EucNorm(pat, i);
printf(“Distance from pattern %d to cluster %d is %f\n”, pat, i, sqrt(d));
if (d MinDist) { // 如果小於前最小值，將改值作為當前最小值
MinDist = d;
ClustID = i;
}
}
if (ClustID 0) { // 沒有找到？？！ —— 這個應該不可能發生，如果出現表示出現了不可思議的錯誤
printf(“Aaargh”);
exit(0);
}
return ClustID;
}
void System ::DistributeSamples() {
int i, pat, Clustid, MemberIndex;
// 將上次的記錄的該聚類中的數據數量清0，重新開始分配數據
for (i = 0; i NumClusters; i++) {
Cluster[i].NumMembers = 0;
}
// 找出每個數據的最近聚類數據中心，並將該數據分配到該聚類
for (pat = 0; pat NumPatterns; pat++) {
Clustid = FindClosestCluster(pat);
printf(“patern %d assigned to cluster %d\n\n”, pat, Clustid);
MemberIndex = Cluster[Clustid].NumMembers; // MemberIndex是當前記錄的數據數量，也是新加入數據在數組中的位置
Cluster[Clustid].Member[MemberIndex] = pat; // 將數據索引加入Member數組
Cluster[Clustid].NumMembers++; // 聚類中的數據數量加1
}
}
int System::CalcNewClustCenters() {
int ConvFlag, VectID, i, j, k;
double tmp[MAXVECTDIM]; // 臨時記錄新的聚類中心，因為需要比較，不能直接記錄
char xs[255];
char szBuf[255];
ConvFlag = TRUE;
printf(“The new cluster centers are now calculated as:\n”);
// 逐個計算NumClusters個聚類
for (i = 0; i NumClusters; i++) {
strcpy(xs,””);
printf(“Cluster Center %d (1/%d):\n”,i,Cluster[i].NumMembers);
// tmp所有維度數值清0
for (j = 0; j SizeVector; j++) {
tmp[j] = 0.0;
}
// 計算聚類中所有數據的所有維度數值的和，為下一步計算均值做準備
for (j = 0; j Cluster[i].NumMembers; j++) {
VectID = Cluster[i].Member[j];
for (k = 0; k SizeVector; k++) {
tmp[k] += Pattern[VectID][k];
sprintf(szBuf,”%d “,Pattern[VectID][k]);
strcat(xs,szBuf);
}
printf(“%s\n”,xs); // 輸出剛才計算的數據
strcpy(xs,””);
}
// 求出均值，並判斷是否和上次相同
for (k = 0; k SizeVector; k++) {
if(Cluster[i].NumMembers!=0)
tmp[k] = tmp[k] / Cluster[i].NumMembers;
if (tmp[k] != Cluster[i].Center[k]) // 如果不同，則認為沒有收斂
ConvFlag = FALSE;
Cluster[i].Center[k] = tmp[k]; // 用新值代替舊值
}
printf(“%s,\n”, xs);
}
return ConvFlag; // 返回收斂情況
}
// 顯示聚類中心數據
void System::ShowClusters() {
int cl;
for (cl = 0; cl NumClusters; cl++) {
printf(“\nCLUSTER %d ==[%f,%f]\n”, cl, Cluster[cl].Center[0],
Cluster[cl].Center[1]);
}
}
// 沒有實現的函數
void System::SaveClusters(char * fname) {
}
#include windows.h
void main(int argc, char * argv[]) {
System kmeans;
// 如果沒有提供參數，顯示用法
if (argc 2) {
printf(“USAGE: KMEANS PATTERN_FILE\n”);
exit(0);
}
// 參數1 為數據文件名，從中讀入數據
if (kmeans.LoadPatterns(argv[1]) == FAILURE) {
printf(“UNABLE TO READ PATTERN_FILE:%s\n”, argv[1]);
exit(0);
}
kmeans.InitClusters();
kmeans.RunKMeans();
kmeans.ShowClusters();
kmeans.ShowCenters();
return ;
}
原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-hant/n/155148.html
微信掃一掃 
支付寶掃一掃 