OpenCV4機器學習（六）：K-means原理及實作

前言：

本專欄主要結合OpenCV4，來實作一些基本的影像處理操作、經典的機器學習演算法（比如K-Means、KNN、SVM、決策樹、貝葉斯分類器等），以及常用的深度學習演算法，

系列文章，持續更新：

• OpenCV4機器學習（一）：OpenCV4+VS2017環境搭建與配置
• OpenCV4機器學習（二）：影像的讀取、顯示與存盤
• OpenCV4機器學習（三）：顏色空間（RGB、HSI、HSV、Lab、Gray）之間的轉換
• OpenCV4機器學習（四）：影像的幾何變換、仿射變換
• OpenCV4機器學習（五）：標注文字和矩形框

一、基本介紹

K-means，即K均值， 是一種迭代求解的聚類演算法，聚類是一個將資料集中在某些方面相似的資料成員進行分類組織的程序，聚類就是一種發現這種內在結構的技術，聚類技術經常被稱為無監督學習，

K 均值聚類是最著名的劃分聚類演算法，由于簡潔和效率使得他成為所有聚類演算法中最廣泛使用的，給定一個資料點集合和需要的聚類數目 K，K 由用戶指定，K 均值演算法根據某個距離函式反復把資料分入 K 個聚類中，

二、演算法原理

對于給定的資料集，通過K-means方法進行聚類的流程如下：

• 初始化K個聚類中心，
• 樣本分配，將每個樣本放入與其最近的類別中心所在的集合，通過設定的距離函式來判斷樣本距離哪個中心最近，并放入對應的樣本中，距離函式一般采用：歐式距離、曼哈頓距離、閔可夫斯基距離、漢明距離，
• 更新類別中心，對分配在每個集合中樣本，求樣本均值，并作為當前的類別中心，
• 判斷終止條件， 判斷類別標簽是否達到收斂精度或達到訓練輪數，

三、函式解釋

在 OpenCV4 中，cv::kmeans 函式實作了 K-means，該演算法找到 K 個類別的中心，并對類別周圍的輸入樣本進行分組，

cv::kmeans 函式定義如下：

double cv::kmeans(InputArray data,  //樣本
				  int K, //類別數
				  InputOutputArray bestLabels,  //輸出整數陣列，用于存盤每個樣本的聚類類別索引
				  TermCriteria criteria,  //演算法終止條件：即最大迭代次數或所需精度
				  int attempts,  //用于指定使用不同初始標記執行演算法的次數
				  int flags,  //初始化均值點的方法
				  OutputArray centers = noArray()  //聚類中心的輸出矩陣，每個聚類中心占一行
				  )

四、實戰演示

下面將演示一個示例，采用 OpenCV 中的 kmeans() 方法對二維坐標點集進行聚類，

#include<iostream>
#include<opencv.hpp>
using namespace std;
using namespace cv;

int main() {
	const int MAX_CLUSTERS = 5; //最大類別數
	Scalar colorTab[] = {   //繪圖顏色
						 Scalar(0, 0, 255),
						 Scalar(0, 255, 0),
						 Scalar(255, 100, 100),
						 Scalar(255, 0, 255),
						 Scalar(0, 255, 255)
						};

	Mat img(500, 500, CV_8UC3); //新建畫布
	img = Scalar::all(255); //將畫布設定為白色
	RNG rng(35345); //亂數產生器

	//初始化類別數
	int clusterCount = rng.uniform(2, MAX_CLUSTERS + 1);
	//在指定區間，隨機生成一個整數,樣本數
	int sampleCount = rng.uniform(1, 1001);
	//輸入樣本矩陣：sampleCount行x1列, 浮點型，2通道
	Mat points(sampleCount, 1, CV_32FC2);
	Mat labels; 
	//聚類類別數 < 樣本數
	clusterCount = MIN(clusterCount, sampleCount); 

	//聚類結果索引矩陣
	vector<Point2f> centers;

	//隨機生成多高斯分布的樣本
	//for (int k = 0; k < clusterCount; k++) {
	Point center;
	center.x = rng.uniform(0, img.cols);
	center.y = rng.uniform(0, img.rows);

	//對樣本points指定進行賦值
	Mat pointChunk = points.rowRange(0, sampleCount / clusterCount);
			
	//以center為中心，產生高斯分布的隨機點,把坐標點保存在 pointChunk 中
	rng.fill(pointChunk, RNG::NORMAL, Scalar(center.x, center.y), Scalar(img.cols*0.05, img.rows*0.05));
	//打亂points中的值
	randShuffle(points, 1, &rng);

	//執行k-means
	double compactness = kmeans(points,  //樣本
								clusterCount, //類別數
								labels,  //輸出整數陣列，用于存盤每個樣本的聚類類別索引
								TermCriteria(TermCriteria::EPS + TermCriteria::COUNT, 10, 1.0),  //演算法終止條件：即最大迭代次數或所需精度
								3, //用于指定使用不同初始標記執行演算法的次數
								KMEANS_PP_CENTERS, //初始化均值點的方法
								centers); //聚類中心的輸出矩陣，每個聚類中心占一行
			
	//繪制或輸出聚類結果
	for (int i = 0; i < sampleCount; i++) {
		int clusterIdx = labels.at<int>(i);

		Point ipt = points.at<Point2f>(i);
		circle(img, ipt, 2, colorTab[clusterIdx], FILLED, LINE_AA);
	}

	//以聚類中心為圓心繪制圓形
	for (int i = 0; i < (int)centers.size(); ++i) {
		Point2f c = centers[i];
		circle(img, c, 40, colorTab[i], 1, LINE_AA);
	}

	cout << "Compactness: " << compactness << endl;
	imshow("clusters", img);
	waitKey(0);

	return 0;
}

聚類結果如下圖所示：

本專欄所有完整的代碼將在我的GitHub倉庫上更新，歡迎大家前往學習：

• https://github.com/Keyird/OpenCV4-Machine-Learning

進入GitHub倉庫，點擊 star (紅色箭頭所示)，第一時間獲取干貨：

最好的關系是互相成就，各位的「三連」就是【AI 菌】創作的最大動力，我們下期見！