1. K均值算法（K-Means）
是一種無監督的聚類學習算法，它嘗試找到樣本數據的自然類別，分類K是由用戶自己定義的，它在不需要任何其它先驗知識的情況下，依據算法的迭代規則，把樣本劃分為K類，通過不斷跌代和移動質心來完成分類。是一種硬分類的方法：即以距離為依據，離哪個點距離越近，它就應該標記為哪個編號，計算兩個點之間的距離，有可能是向量（x，y）或（x，y，z）。不斷的迭代，中心點不斷的變換，使得逐漸接近真實的結果，最後要求取前後兩次中心點的差值，或到達一定的迭代次數就結束。
API參數：
- 參數1：輸入的數據集合，可以是一維或多維，它是浮點數。
- 參數2：K 為分類的數目。
- 參數3：分類的標籤，分類索引編號。
- 參數4：停止條件，可以用迭代的次數或者我們指定的精度閾值。
- 參數5：attempts 嘗試幾次，有時候為了獲得最佳的分類效果，算法要用不同的初始分類進行嘗試。
- 參數6：flags 表示用哪一種方法進行初始化，最常用的是隨機選擇。
例子代碼：
<code>#include<opencv2>
#include<iostream>
using namespace std;
using namespace cv;
void test(){
Mat srcImg;
srcImg = imread("toux.jpg");
if (srcImg.empty())
{
cout < }
namedWindow("Original image", CV_WINDOW_AUTOSIZE);
imshow("Original image", srcImg);
//預定義分割的一些顏色
Scalar colorTab[] = {
Scalar(0, 0, 255),
Scalar(0, 255, 0),
Scalar(0, 0, 0),
Scalar(255, 0, 0),
Scalar(255, 0, 255),
};
//首先獲取圖像的寬和高，每一個像素對應一個數據點，要把數據進行轉換，
//kmeans 輸入參數是以所有的數據點為每一行，列為數據的維度（圖像為3 RGB顏色通道）
int width = srcImg.cols;
int height = srcImg.rows;
int dims = srcImg.channels();
int sampleCount = width*height; //總像素
int clusterCount = 4; //分為 4 類
//數據點，即把所有樣本裝到一個數據點（一行），每一行只有一個數據
Mat points(sampleCount, dims, CV_32F, Scalar(10));
Mat labels;
Mat centers(clusterCount, 1, points.type()); //中心點
//將 RGB 數據轉換到樣本數據
int index = 0;
for (int i = 0; i {
for (int j = 0; j {
index = i*width + j;
Vec3b bgr = srcImg.at<vec3b>(i, j); //獲取圖像上點像素的值
//把只作為樣本傳進去
points.at<float>(index, 0) = static_cast(bgr[0]); //把數據轉換 /<float>/<vec3b>/<iostream>/<opencv2>/<code>
points.at<float>(index, 1) = static_cast(bgr[1]); /<float>
points.at<float>(index, 2) = static_cast(bgr[2]); /<float>
}
}
//運行 kmeans
TermCriteria cirteria = TermCriteria(TermCriteria::EPS + TermCriteria::COUNT, 10, 0.1);
kmeans(points, clusterCount, labels, cirteria, 3, KMEANS_PP_CENTERS, centers);
//顯示分類的結果
Mat result = Mat::zeros(srcImg.size(), srcImg.type());
for (int i = 0; i {
for (int j = 0; j {
index = i*width + j; //把二維數組轉換到一維數組，找它裡面的index
//結果顯示通過label 獲取，根據聚類的編號
int label = labels.at(index, 0);
result.at<vec3b>(i, j)[0] = colorTab[label][0];
result.at<vec3b>(i, j)[1] = colorTab[label][1];
result.at<vec3b>(i, j)[2] = colorTab[label][2];
}
}
for (int i = 0; i {
int x = centers.at<float>(i, 0);
int y = centers.at<float>(i, 0);
cout < }
imshow("KMeans", result);
}/<float>/<float>/<vec3b>/<vec3b>/<vec3b>
效果圖：
2.高斯混合模型（GMM）
2.1 一些概念理解
2.1.1 協方差
統計學裡最基本的就是樣本的均值、方差和標準差。在一個含有n個樣本的集合X={X1 ,…,Xn}。
均值：
標準差：
方差：
均值描述的是樣本集合的中間點，它告訴我們的信息是很有限的，而標準差描述的是樣本集合的各個樣本點到均值的距離之平均。以這兩個集合為例，[0，8，12，20]和[8，9，11，12]，兩個集合的均值都是10，但顯然兩個集合差別是很大的，計算兩者的標準差，前者是8.3，後者是1.8，顯然後者較為集中，所以標準差小一點，標準差描述的就是這種“散佈度”。之所以除以n-1而不是除以n，是因為這樣能使我們以較小的樣本集更好的逼近總體的標準差，即統計上所謂的“無偏估計”。方差則僅僅是標準差的平方。
為什麼需要協方差？上面幾個統計量看似已經描述的差不多了，但注意到，標準差和方差一般是用來描述一維數據的，現實生活我們常常遇到含有多維數據的數據集，例如要統計多個學科的考試成績。面對這樣的數據集，可以按照每一維獨立的計算其方差，但是通常我們還想了解更多，比如，一個男孩子的猥瑣程度跟他受女孩子歡迎程度是否存在一些聯繫啊，嘿嘿~協方差就是這樣一種用來度量兩個隨機變量關係的統計量，我們可以仿照方差的定義：
來度量各個維度偏離其均值的程度，標準差可以這麼來定義：
如果協方差的結果的結果為正值，則說明兩者是正相關的(從協方差可以引出“相關係數”的定義)，也就是說一個人越猥瑣就越受女孩子歡迎，結果為負值就說明負相關的，越猥瑣女孩子越討厭，可能嗎？如果為0，也是就是統計上說的“相互獨立”。
2.1.2 高斯函數（模型）
高斯一維函數：
高斯概率分佈函數：
2.1.3 EM 算法
MLE 是用來求模型參數的，核心是“模型已知，求取參數”，模型的意思就是數據符合什麼函數，比如我們硬幣的正反就是二項分佈模型，再比如我們平時隨機生成的一類數據符合高斯模型,公式如下：
- L(Θ)：聯合概率分佈函數，就是每個樣本出現的概率乘積。
- x1,x2,x3….xn : 樣本
- Θ：模型的參數（比如高斯模型的兩個參數：μ、σ）
- p(xi ; Θ):第i個樣本的概率模型
- xi: 第i個樣本
平時使用的時候取對數，完全為了求解方便：
ê 為平均對數似然。而我們平時所稱的最大似然為最大的對數平均似然，即:
舉個例子：拋硬幣的簡單例子，現在有一個正反面不是很勻稱的硬幣，如果正面朝上記為H，方面朝上記為T，拋10次的結果如下：
求這個硬幣正面朝上的概率有多大？很顯然這個概率是0.2。現在我們用MLE的思想去求解它。我們知道每次拋硬幣都是一次二項分佈，設正面朝上的概率是μ；那麼似然函數為：
x=1表示正面朝上，x=0表示方面朝上。那麼有：
求導：
令導數為0，很容易得到：
也就是0.2 。
再舉個例子：
假如我們有一組連續變量的採樣值（x1,x2,…,xn），我們知道這組數據服從正態分佈，標準差已知。請問這個正態分佈的期望值為多少時，產生這個已有數據的概率最大？
P(Data | M) = ？
根據公式：
可得:
對μ求導可得：
則最大似然估計的結果為μ=(x1+x2+…+xn) / n
總結：其實我們用的很多函數都可以說是一個最大似然函數，比如符合y = x2、y = kx…都可以當做一個模型去求解一個極大似然函數，只不過我們得到的數據不符合這些模型而已。只要是求概率的問題，都會寫出一個函數，這個函數其實就是最大似然函數，可以說是目標函數，也可以說是似然函數，把每個數據出現的概率相乘就是似然函數，再求對數，再求均值，再求最值，這就是極大似然了，就是一個名字而已！
EM算法核心：猜（E-step）,反思（M-step）,重複；
算法理解：
問題一：
現在一個班裡有50個男生，50個女生，且男生站左，女生站右。我們假定男生的身高服從正態分佈:
N(μ1,σ1²)
女生的身高則服從另一個正態分佈：
N(μ2,σ2²)
這時候我們可以用極大似然法（MLE），分別通過這50個男生和50個女生的樣本來估計這兩個正態分佈的參數。
問題二：
但現在我們讓情況複雜一點，就是這50個男生和50個女生混在一起了。我們擁有100個人的身高數據，卻不知道這100個人每一個是男生還是女生。這時候情況就有點尷尬，因為通常來說，我們只有知道了精確的男女身高的正態分佈參數我們才能知道每一個人更有可能是男生還是女生。但從另一方面去考量，我們只有知道了每個人是男生還是女生才能儘可能準確地估計男女各自身高的正態分佈的參數。
問題二需要求解兩個問題：
- 假設a=（第k個樣本是男生還是女生）
- 假設b=（高斯模型的參數）
如果知道a，那用問題一的方法就可以求解b，如果知道b那也就可以分類a了，但是前提是兩個都不知道,比如y=x+1，現在讓你求解x和y的值，怎麼辦？
解決：
總結：其實EM算法就是先通過假設的參數把數據進行分類，然後通過分類的數據計算參數，接著對比計算的參數和假設的參數是否滿足精度，不滿足就返回去，滿足就結束。EM是一種思想，而不是像K-means等是一種算法。
高斯混合函數的原理：（1）單高斯分佈模型GSM：多維變量X服從高斯分佈時，它的概率密度函數為：
x是維度為d的列向量，u是模型期望，Σ是模型方差。在實際應用中u通常用樣本均值來代替，Σ通常用樣本方差來代替。很容易判斷一個樣x本是否屬於類別C。因為每個類別都有自己的u和Σ，把x代入（1）式，當概率大於一定閾值時我們就認為x屬於C類。從幾何上講，單高斯分佈模型在二維空間應該近似於橢圓，在三維空間上近似於橢球。遺憾的是在很多分類問題中，屬於同一類別的樣本點並不滿足“橢圓”分佈的特性。這就引入了高斯混合模型。
高斯混合模型GMM：GMM認為數據是從幾個GSM中生成出來的，即：
K需要事先確定好，就像K-means中的K一樣。πk是權值因子。其中的任意一個高斯分佈N(x;uk,Σk)叫作這個模型的一個component。這裡有個問題，為什麼我們要假設數據是由若干個高斯分佈組合而成的，而不假設是其他分佈呢？實際上不管是什麼分佈，只K取得足夠大，這個XX Mixture Model就會變得足夠複雜，就可以用來逼近任意連續的概率密度分佈。只是因為高斯函數具有良好的計算性能，所GMM被廣泛地應用。
樣本分類已知情況下的GMM:當每個樣本所屬分類已知時，GMM的參數非常好確定，直接利用Maximum Likelihood。設樣本容量為N，屬於K個分類的樣本數量分別是N1,N2,…,Nk，屬於第k個分類的樣本集合是L(k)。
樣本分類未知情況下的GMM:
EM求解：
例子代碼：
<code>#include<opencv2>
#include<iostream>
using namespace std;
using namespace cv;
//高斯混合方法
using namespace cv::ml;
void test(){
Mat srcImg;
srcImg = imread("toux.jpg");
if (srcImg.empty())
{
cout < }
namedWindow("Original image", CV_WINDOW_NORMAL);
imshow("Original image", srcImg);
//預定義分割的一些顏色
Scalar colors[] = {
Scalar(0, 0, 255), //紅
Scalar(0, 255, 0), //綠
Scalar(255, 0, 0), //藍
Scalar(0, 255, 255), // 黃
Scalar(255, 0, 255), //品紅
};
//首先獲取圖像的寬和高，每一個像素對應一個數據點，要把數據進行轉換，
//kmeans 輸入參數是以所有的數據點為每一行，列為數據的維度（圖像為3 RGB顏色通道）
int width = srcImg.cols;
int height = srcImg.rows;
int dims = srcImg.channels();
int numCount = width*height; //總像素點數
int numCluster = 3; //分為 3 類
//數據點，即把所有樣本裝到一個數據點（一行），每一行只有一個數據
Mat points(numCount, dims, CV_64FC1);
Mat labels;
//將圖像 RGB 數據轉換為樣本數據
int index = 0;
for (int row = 0; row {
for (int col = 0; col {
index = row*width + col;
Vec3b rgb = srcImg.at<vec3b>(row, col); //獲取圖像上點像素的rgb值
//把只作為樣本傳進去
points.at<double>(index, 0) = static_cast(rgb[0]); /<double>/<vec3b>/<iostream>/<opencv2>/<code>
points.at<double>(index, 1) = static_cast(rgb[1]); /<double>
points.at<double>(index, 2) = static_cast(rgb[2]); /<double>
}
}
// EM 訓練
PtremModel = EM::create(); //生成 EM 期望最大化，起圖像分割的方式是基於機器學習的方式
emModel->setClustersNumber(numCluster); //設置分類數
emModel->setCovarianceMatrixType(EM::COV_MAT_SPHERICAL); //協方差矩陣的類型
//迭代條件，EM 訓練比 KMeans 耗時，可能會不收斂，所以迭代次數設大點
emModel->setTermCriteria(TermCriteria(TermCriteria::EPS +
TermCriteria::COUNT, 10, 0.1));
//EM 訓練，獲得分類結果，參數 labels 與 KMeans 的 labels 參數意思一樣，速度比 KMeans 要慢很多
emModel->trainEM(points, noArray(), labels, noArray());
//對每個像素標記顏色與顯示
Mat resultNoPredict = Mat::zeros(srcImg.size(), CV_8UC3);
Mat resultPredict = Mat::zeros(srcImg.size(), CV_8UC3);
Mat sample(dims, 1, CV_64FC1);
double time = getTickCount();
int r = 0, g = 0, b = 0; //預言會用到
for (int row = 0; row {
for (int col = 0; col {
//獲取訓練的分類結果，放到 result 中
index = row*width + col; //把二維數組轉換到一維數組，找它裡面的index
//結果顯示通過label 獲取，根據聚類的編號
int label = labels.at(index, 0);
Scalar c = colors[label]; //label 上已經有顏色了
resultNoPredict.at<vec3b>(row, col)[0] = c[0];
resultNoPredict.at<vec3b>(row, col)[1] = c[1];
resultNoPredict.at<vec3b>(row, col)[2] = c[2];
//通過預言獲得分類結果，因為 EM 訓練用的是 srcImg 的顏色數據，所以用 srcImg 的顏色數據做預言，
//得到的結果與 result 是一模一樣的
b = srcImg.at<vec3b>(row, col)[0];
g = srcImg.at<vec3b>(row, col)[1];
r = srcImg.at<vec3b>(row, col)[2];
sample.at<double>(0) = b;
sample.at<double>(1) = g;
sample.at<double>(2) = r;
//預言
int response = cvRound(emModel->predict2(sample, noArray())[1]);
Scalar c2 = colors[response];
resultPredict.at<vec3b>(row, col)[0] = c2[0];
resultPredict.at<vec3b>(row, col)[1] = c2[1];
resultPredict.at<vec3b>(row, col)[2] = c2[2];
}
}
//打印所需要的時間
cout < namedWindow("EM-Segmentation nopredict", CV_WINDOW_NORMAL);
imshow("EM-Segmentation nopredict", resultNoPredict);
namedWindow("EM-Segmentation predict", CV_WINDOW_NORMAL);
imshow("EM-Segmentation predict", resultPredict);
}
int main(){
test();
waitKey(0);
return 0;
}/<vec3b>/<vec3b>/<vec3b>/<double>/<double>/<double>/<vec3b>/<vec3b>/<vec3b>/<vec3b>/<vec3b>/<vec3b>
效果圖：
遇到的問題：
我的解決辦法：
更換 OpenCV 版本:報錯時用的是3.1版本，更換成3.3版本，這裡要注意 OpenCV 版本與 VS 之間的對應版本即可。
閱讀更多 業餘天王 的文章
