筆記：http://blog.csdn.net/linkin1005/article/details/39312735
參考：https://zhuanlan.zhihu.com/p/20432322
主要內(nèi)容--無監(jiān)督學(xué)習(xí)：
- K-means算法
- 混合高斯分布模型 MoG
- 求解MoG模型的EM算法
1. K-means算法
1.1 基本概念
是聚類算法的一種格嗅。聚類算法是指將一堆沒有標(biāo)簽的數(shù)據(jù)自動劃分成幾類的方法，這個方法要保證同一類的數(shù)據(jù)有相似的特征钟病。
K-Means算法的特點是類別的個數(shù)是人為給定的拱烁。
假設(shè)前提：數(shù)據(jù)之間的相似度可以使用歐氏距離度量疹瘦，如果不能使用歐氏距離度量崩哩，要先把數(shù)據(jù)轉(zhuǎn)換到能用歐氏距離度量，這一點很重要。
（注：可以使用歐氏距離度量的意思就是歐氏距離越小邓嘹，兩個數(shù)據(jù)相似度越高）
比如上圖就是非歐幾里得空間酣栈，同一類的點可能會距離很遠，這時候就需要使用KNN和最短路徑算法等工具實現(xiàn)非歐空間到歐氏空間轉(zhuǎn)化汹押。
K-Means算法有個很著名的解釋矿筝，就是牧師-村民模型，其實就是K-means算法的過程：
“有四個牧師去郊區(qū)布道棚贾，一開始牧師們隨意選了幾個布道點窖维，并且把這幾個布道點的情況公告給了郊區(qū)所有的居民，于是每個居民到離自己家最近的布道點去聽課妙痹。
聽課之后铸史，大家覺得距離太遠了，于是每個牧師統(tǒng)計了一下自己的課上所有的居民的地址怯伊，搬到了所有地址的中心地帶琳轿，并且在海報上更新了自己的布道點的位置。
牧師每一次移動不可能離所有人都更近耿芹，有的人發(fā)現(xiàn)A牧師移動以后自己還不如去B牧師處聽課更近崭篡，于是每個居民又去了離自己最近的布道點……
就這樣，牧師每個禮拜更新自己的位置吧秕，居民根據(jù)自己的情況選擇布道點琉闪，最終穩(wěn)定了下來≡冶颍”
偽代碼描述：
matlab代碼：
clear;clc;close all;
G1 = randn(100,2).*1+10;
G2 = randn(100,2).*1;
G3 = randn(100,2).*1-10;
X = [G1;G2;G3];
k = 3; %給出參數(shù)：聚三類
cls = kmeans(X,k);
figure(1)
subplot(1,2,2)
Legends = {'r.','b.','g.'};
hold on
for i = 1:3
plot(X(find(cls==i),1),X(find(cls==i),2),Legends{i})
end
hold off
title('聚類結(jié)果')
subplot(1,2,1)
plot(X(:,1),X(:,2),'.')
title('原始數(shù)據(jù)')
</br>
</br>
1.2 具體實現(xiàn)和改進
clear;clc;close all;
loli = imread('loli.jpg');
[x,y,channel] = size(loli);
loli_vec = reshape(loli,x*y,channel);
figure(1)
for i = 1:4
K=2^i;
[ ~,cls ] = k_means( double(loli_vec),[],K,[] );
centers = zeros(K,channel);
for k = 1:K
centers(k,:)=mean(loli_vec(find(cls==k),:));
end
centers = uint8(centers);
loli_vec_zip = centers(cls,:);
loli_zip = reshape(loli_vec_zip,x,y,channel);
subplot(1,4,i)
imshow(loli_zip)
imwrite(loli_zip,['loli_zip_' num2str(i) '.jpg'])
disp(['loli_zip_' num2str(i) '.jpg has saved.'])
end
function [ k_means_result,cls_vec ] = k_means( data_set,weight,K,plot2pos )
%% 說明的言葉
%{
data_set:輸入的數(shù)據(jù)集颠毙，以行向量為單位
weight:輸入的權(quán)重，如果是空就自動設(shè)為各個數(shù)據(jù)權(quán)值相等
K:K-Means的K還需要我明說么~拿霉，~
plot2pos:用來繪圖的向量吟秩，大小N*2的矩陣，如果是空就不繪圖了绽淘。(要不然超過三維怎么繪圖)
%}
%% 初始化各項參數(shù)
[N,dim] = size(data_set);
if isempty(weight)
weight = ones(N,1);
else
weight = weight(:);
end
if isempty(plot2pos)
isdisplay = 0;
else
isdisplay = 1;
end
% 初始化點集
group_center = mean(data_set);
group_range = range(data_set);
centers = (randn(K,dim).*repmat(group_range,K,1)./3+repmat(group_center,K,1));
%各個變量的初始化
dist_vec = zeros(N,K);
rep_tms = 0;
delay = 1e-3;
dumper = 0.1;
p2pc = zeros(K,2);
%J = 0;
logJ = [];
minJ = -1;
%% 如果畫圖，為畫圖設(shè)置各項Legend（顏色）
if isdisplay == 1
Style = {'o'};
Color = {'r','g','b','m','k','c','y'};
Legends = {};
for i = 1:length(Style)
for j = 1:length(Color)
Legends = [Legends;[Style{i},Color{j}]];
end
end
end
%% 迭代過程
while(1)
for i = 1:K
%求到每一個中心的距離向量闹伪，且不用張量求更加節(jié)約空間
dist_vec(:,i) = sqrt(sum(...
(data_set - repmat(centers(i,:),N,1)).^2,2)...
);
end
%求出每一個點離哪一個中心更近沪铭。
[~,cls_vec] = min(dist_vec,[],2);
lst_cnt = centers;
for i = 1:K
%根據(jù)權(quán)重重新計算中心
cls_idx = find(cls_vec==i);
if isempty(cls_idx)
centers(i,:) = (randn(1,dim).*group_range./3+group_center);
else
centers(i,:) = sum(data_set(cls_idx,:).*...
repmat(weight(cls_idx),1,dim))...
./sum(weight(cls_idx));
end
end
% 計算代價函數(shù)
CMat = (data_set-lst_cnt(cls_vec,:)).^2;
J = sum(CMat(:));
% 根據(jù)阻尼比更新
centers = (1-dumper).*centers + dumper.*lst_cnt;
if minJ<0 || J<minJ
minJ=J;
end
if J>=minJ
rep_tms = rep_tms+1;
else
rep_tms = 0;
end
if rep_tms>=5
break;
end
if isdisplay == 1
% 繪制代價函數(shù)及其差分
figure(2)
logJ = [logJ J]; %#ok<AGROW>
subplot(2,1,1)
plot(logJ)
axis tight
subplot(2,1,2)
plot(diff(logJ))
% 繪制分布圖
figure(1)
cla
hold on
for i = 1:K
cls_idx = find(cls_vec==i);
if isempty(cls_idx)
p2pc(i,:) = mean(plot2pos);
else
p2pc(i,:) = sum(...
plot2pos(cls_idx,:).*...
repmat(weight(cls_idx),1,2)...
)...
./sum(weight(cls_idx));
end
plot(p2pc(i,1),p2pc(i,2),Legends{1+mod(i,length(Legends))});
scatter(plot2pos(cls_idx,1),plot2pos(cls_idx,2),...坐標(biāo)
weight(cls_idx)./max(weight).*10,...大小
Color{1+mod(i,length(Color))},'filled');%顏色
end
hold off
pause(delay)
end
end
%% 輸出數(shù)據(jù)集
not_empty_cls = unique(cls_vec);
k_means_result = cell(length(not_empty_cls),1);
for i = 1:length(not_empty_cls)
cls = not_empty_cls(i);
sub_res = cell(3,1);
cls_idx = find(cls_vec==cls);
sub_res{1} = centers(cls,:);
sub_res{3} = cls_idx;
sub_res{2} = data_set(cls_idx,:);
k_means_result{i} = sub_res;
end
end
算法的擴展參考：https://zhuanlan.zhihu.com/p/20445085
</br></br>
2. 混合高斯分布模型 MoG
一種無監(jiān)督學(xué)習(xí)算法，常用于聚類偏瓤。
適用于聚類問題中各個類別的尺寸不同杀怠、聚類間有相關(guān)關(guān)系的時候。
多維高斯（正態(tài)）分布概率密度函數(shù)PDF定義如下：
-
單高斯模型（Single GaussianModel, SGM）
</br>
實際就是以一個單一的高斯密度函數(shù)來描述這些數(shù)據(jù)點的概率密度函數(shù)厅克。
其中K表示類別赔退，計算結(jié)果就是樣本屬于類別K的概率大小。從而將任意測試樣本輸入式子，均可以得到一個標(biāo)量硕旗，然后根據(jù)閾值t來確定該樣本是否屬于該類別窗骑，閾值t可以為經(jīng)驗值，也可以通過實驗確定漆枚。
</br>
-
高斯混合模型（GaussianMixture Model创译，GMM
為了解決的問題：
假設(shè)每個點均由一個單高斯分布生成（如圖 1(b)，具體參數(shù)墙基，未知）软族，而這一批數(shù)據(jù)共由M（明確）個單高斯模型生成，具體某個數(shù)據(jù)Xi屬于哪個單高斯模型未知残制，且每個單高斯模型在混合模型中占的比例ai未知立砸，將所有來自不同分布的數(shù)據(jù)點混在一起，該分布稱為高斯混合分布初茶。</br>
從數(shù)學(xué)上講颗祝，我們認(rèn)為這些數(shù)據(jù)的概率分布密度函數(shù)可以通過加權(quán)函數(shù)表示：
其中Nj的值表示第j個SGM的PDF：
令
GMM共有M個SGM，現(xiàn)在纺蛆，我們就需要通過樣本集X來估計GMM的所有參數(shù)：
樣本X的概率公式為：
對于GMM參數(shù)的估計我們就要用到EM算法吐葵。
3. EM算法(最大期望算法)
最大期望經(jīng)常用在機器學(xué)習(xí)和計算機視覺的數(shù)據(jù)聚類（Data Clustering）領(lǐng)域。
適用于含有隱變量或潛在變量的概率模型參數(shù)的估計桥氏。如果只有觀測變量而沒有隱含變量温峭，可以直接用極大似然估計參數(shù)。
為什么要用EM算法字支？凤藏？
</br>
EM算法就是這樣，假設(shè)我們估計知道A和B兩個參數(shù)堕伪，在開始狀態(tài)下二者都是未知的揖庄，并且知道了A的信息就可以得到B的信息，反過來知道了B也就得到了A欠雌√闵遥可以考慮首先賦予A某種初值，以此得到B的估計值富俄，然后從B的當(dāng)前值出發(fā)禁炒，重新估計A的取值，這個過程一直持續(xù)到收斂為止霍比。
