文章出處
文章列表
引入
作為練手，不妨用matlab實現K-means
要解決的問題：n個D維數據進行聚類（無監督），找到合適的簇心。
這里僅考慮最簡單的情況，數據維度D=2，預先知道簇心數目K（K=4）
理論步驟
關鍵步驟：
（1）根據K個簇心(clusters，下標從1到K)，確定每個樣本數據Di(D為所有數據整體，Di為某個數據，i=1...n)所屬簇，即歐氏距離最近的那個。
簇心編號:
c_i = arg min_{j} {D_i - clusters_j}， 即使得歐氏距離最近的那個j(2) 更新簇心：所屬簇編號c_i相同的樣本數據D_i的元素們，用他們均值來替代原有簇心（D維向量均值）
代碼
% my_kmeans
% By Chris, zchrissirhcz@gmail.com
% 2016年9月30日 19:13:43
% 簇心數目k
K = 4;
% 準備數據，假設是2維的,80條數據，從data.txt中讀取
%data = zeros(100, 2);
load 'data.txt'; % 直接存儲到data變量中
x = data(:,1);
y = data(:,2);
% 繪制數據，2維散點圖
% x,y: 要繪制的數據點 20:散點大小相同，均為20 'blue':散點顏色為藍色
s = scatter(x, y, 20, 'blue');
title('原始數據：藍圈；初始簇心：紅點');
% 初始化簇心
sample_num = size(data, 1); % 樣本數量
sample_dimension = size(data, 2); % 每個樣本特征維度
% 暫且手動指定簇心初始位置
clusters = zeros(K, sample_dimension);
clusters(1,:) = [-3,1];
clusters(2,:) = [2,4];
clusters(3,:) = [-1,-0.5];
clusters(4,:) = [2,-3];
hold on; % 在上次繪圖（散點圖）基礎上，準備下次繪圖
% 繪制初始簇心
scatter(clusters(:,1), clusters(:,2), 'red', 'filled'); % 實心圓點，表示簇心初始位置
c = zeros(sample_num, 1); % 每個樣本所屬簇的編號
PRECISION = 0.0001;
iter = 100; % 假定最多迭代100次
for i=1:iter
% 遍歷所有樣本數據，確定所屬簇。公式1
for j=1:sample_num
%t = arrayfun(@(item) item
%[min_val, idx] = min(t);
gg = repmat(data(j,:), K, 1);
gg = gg - clusters; % norm:計算向量模長
tt = arrayfun(@(n) norm(gg(n,:)), (1:K)');
[minVal, minIdx] = min(tt);
% data(j,:)的所屬簇心，編號為minIdx
c(j) = minIdx;
end
% 遍歷所有樣本數據，更新簇心。公式2
convergence = 1;
for j=1:K
up = 0;
down = 0;
for k=1:sample_num
up = up + (c(k)==j) * data(k,:);
down = down + (c(k)==j);
end
new_cluster = up/down;
delta = clusters(j,:) - new_cluster;
if (norm(delta) > PRECISION)
convergence = 0;
end
clusters(j,:) = new_cluster;
end
figure;
f = scatter(x, y, 20, 'blue');
hold on;
scatter(clusters(:,1), clusters(:,2), 'filled'); % 實心圓點，表示簇心初始位置
title(['第', num2str(i), '次迭代']);
if (convergence)
disp(['收斂于第', num2str(i), '次迭代']);
break;
end
end
disp('done');使用到的數據(data.txt)
1.658985 4.285136
-3.453687 3.424321
4.838138 -1.151539
-5.379713 -3.362104
0.972564 2.924086
-3.567919 1.531611
0.450614 -3.302219
-3.487105 -1.724432
2.668759 1.594842
-3.156485 3.191137
3.165506 -3.999838
-2.786837 -3.099354
4.208187 2.984927
-2.123337 2.943366
0.704199 -0.479481
-0.392370 -3.963704
2.831667 1.574018
-0.790153 3.343144
2.943496 -3.357075
-3.195883 -2.283926
2.336445 2.875106
-1.786345 2.554248
2.190101 -1.906020
-3.403367 -2.778288
1.778124 3.880832
-1.688346 2.230267
2.592976 -2.054368
-4.007257 -3.207066
2.257734 3.387564
-2.679011 0.785119
0.939512 -4.023563
-3.674424 -2.261084
2.046259 2.735279
-3.189470 1.780269
4.372646 -0.822248
-2.579316 -3.497576
1.889034 5.190400
-0.798747 2.185588
2.836520 -2.658556
-3.837877 -3.253815
2.096701 3.886007
-2.709034 2.923887
3.367037 -3.184789
-2.121479 -4.232586
2.329546 3.179764
-3.284816 3.273099
3.091414 -3.815232
-3.762093 -2.432191
3.542056 2.778832
-1.736822 4.241041
2.127073 -2.983680
-4.323818 -3.938116
3.792121 5.135768
-4.786473 3.358547
2.624081 -3.260715
-4.009299 -2.978115
2.493525 1.963710
-2.513661 2.642162
1.864375 -3.176309
-3.171184 -3.572452
2.894220 2.489128
-2.562539 2.884438
3.491078 -3.947487
-2.565729 -2.012114
3.332948 3.983102
-1.616805 3.573188
2.280615 -2.559444
-2.651229 -3.103198
2.321395 3.154987
-1.685703 2.939697
3.031012 -3.620252
-4.599622 -2.185829
4.196223 1.126677
-2.133863 3.093686
4.668892 -2.562705
-2.793241 -2.149706
2.884105 3.043438
-2.967647 2.848696
4.479332 -1.764772
-4.905566 -2.911070運行結果
缺點
非常naive的kmeans，對于K個簇心初始位置非常敏感，有時候會產生dead point，即有些簇心被孤立而沒有樣本數據歸屬它。
第一次改進：簇心向量的每個維度，在樣本數據的各自維度的最小值和最大值之間取值
clusters = zeros(K, sample_dimension);
minVal = min(data); % 各維度計算最小值
maxVal = max(data); % 各維度計算最大值
for i=1:K
clusters(i, :) = minVal + (maxVal - minVal) * rand();
end 效果：
第二次改進：在線K-means，使用隨機梯度下降SGD替代批量梯度下降BGD
思路是，每次僅僅取出一個樣本數據x_i，找出離他最近的簇心cluster_j，并把簇心往x_i的方向拉。這替代了原來使用“所有的、類別編號為c_j的樣本，算出一個均值，作為新簇心”策略.
同時考慮到收斂速度，每次將“最近的簇心”向數據項“拉取”的時候，乘以一個學習率eta，eta最好是隨著迭代次數增加而有所減小，即迭代次數t的減函數。此處代碼實現中使用倒數(eta = basic_eta/i)，你也可以用更精致的函數替代。
參考代碼:
% 簇心數目k
K = 4;
% 準備數據，假設是2維的,80條數據，從data.txt中讀取
%data = zeros(100, 2);
load 'data.txt'; % 直接存儲到data變量中
x = data(:,1);
y = data(:,2);
% 繪制數據，2維散點圖
% x,y: 要繪制的數據點 20:散點大小相同，均為20 'blue':散點顏色為藍色
s = scatter(x, y, 20, 'blue');
title('原始數據：藍圈；初始簇心：紅點');
% 初始化簇心
sample_num = size(data, 1); % 樣本數量
sample_dimension = size(data, 2); % 每個樣本特征維度
% 暫且手動指定簇心初始位置
% clusters = zeros(K, sample_dimension);
% clusters(1,:) = [-3,1];
% clusters(2,:) = [2,4];
% clusters(3,:) = [-1,-0.5];
% clusters(4,:) = [2,-3];
% 簇心賦初值：計算所有數據的均值，并將一些小隨機向量加到均值上
clusters = zeros(K, sample_dimension);
minVal = min(data); % 各維度計算最小值
maxVal = max(data); % 各維度計算最大值
for i=1:K
clusters(i, :) = minVal + (maxVal - minVal) * rand();
end
hold on; % 在上次繪圖（散點圖）基礎上，準備下次繪圖
% 繪制初始簇心
scatter(clusters(:,1), clusters(:,2), 'red', 'filled'); % 實心圓點，表示簇心初始位置
c = zeros(sample_num, 1); % 每個樣本所屬簇的編號
PRECISION = 0.001;
iter = 100; % 假定最多迭代100次
% Stochastic Gradient Descendant 隨機梯度下降（SGD）的K-means，也就是Competitive Learning版本
basic_eta = 0.1; % learning rate
for i=1:iter
pre_acc_err = 0; % 上一次迭代中，累計誤差
acc_err = 0; % 累計誤差
for j=1:sample_num
x_j = data(j, :); % 取得第j個樣本數據，這里體現了stochastic性質
% 所有簇心和x計算距離，找到最近的一個（比較簇心到x的模長）
gg = repmat(x_j, K, 1);
gg = gg - clusters;
tt = arrayfun(@(n) norm(gg(n,:)), (1:K)');
[minVal, minIdx] = min(tt);
% 更新簇心：把最近的簇心(winner)向數據x拉動。 eta為學習率.
eta = basic_eta/i;
delta = eta*(x_j-clusters(minIdx,:));
clusters(minIdx,:) = clusters(minIdx,:) + delta;
acc_err = acc_err + norm(delta);
end
if(rem(i,10) ~= 0)
continue
end
figure;
f = scatter(x, y, 20, 'blue');
hold on;
scatter(clusters(:,1), clusters(:,2), 'filled'); % 實心圓點，表示簇心初始位置
title(['第', num2str(i), '次迭代']);
if (abs(acc_err-pre_acc_err) < PRECISION)
disp(['收斂于第', num2str(i), '次迭代']);
break;
end
disp(['累計誤差：', num2str(abs(acc_err-pre_acc_err))]);
pre_acc_err = acc_err;
end
disp('done');因為學習率eta選得比較隨意，以及收斂條件的判斷也比較隨意，收斂效果只能說還湊合，運行結果：
文章列表
全站熱搜
留言列表
