OpenCV实现最大最小距离聚类算法

- 日理万妓 2022-05-25 06:37 194阅读 0赞

## OpenCV实现最大最小距离聚类算法 ##

【[尊重][Link 1][原创，转载请注明出处][Link 1]】https://blog.csdn.net/guyuealian/article/details/80255524

本博客提供多版本的最大最小距离聚类算法：《[聚类算法-最大最小距离算法(实例+代码)][-]》，提供C++，Python，OpenCV以及Matlab版本的最大最小距离聚类算法的实现

**目录**

OpenCV实现最大最小距离聚类算法

一、最大最小距离算法基本思想

二、算法实现步骤

1.C++ OpenCV实现方法

2.C++，Python以及Matlab版本

--------------------

## 一、最大最小距离算法基本思想 ##

最大最小距离法是模式识别中一种基于试探的类聚算法，它以欧式距离为基础，取尽可能远的对象作为聚类中心。因此可以避免K-means法初值选取时可能出现的聚类种子过于临近的情况，它不仅能智能确定初试聚类种子的个数，而且提高了划分初试数据集的效率。  
    该算法以欧氏距离为基础，首先初始一个样本对象作为第1个聚类中心，再选择一个与第1个聚类中心最远的样本作为第2个聚类中心，然后确定其他的聚类中心，直到无新的聚类中心产生。最后将样本按最小距离原则归入最近的类。

## 二、算法实现步骤 ##

假设有10个模式样本点：\{x1(0 0), x2(3 8), x3(2 2), x4(1 1), x5(5 3), x6(4 8), x7(6 3), x8(5 4), x9(6 4), x10(7 5)\}，其样本分布如图所示：

![Center][]

**    最大最小距离聚类算法步骤如下：**

![Center 1][]

该算法的聚类结果与参数和起始点的选取关系重大。若无先验样本分布知识，则只有用试探法通过多次试探优化，若有先验知识用于指导和选取，则算法可很快收敛。

**为了方便看解计算过程，下面以表格的方式列出：**

![Center 2][]

### **1.C++ OpenCV实现方法** ###

#include <opencv2/opencv.hpp>
    
    using namespace cv;
    using namespace std;
    
    /*计算欧式距离*/
    float calcuDistance(uchar* ptr, uchar* ptrCen, int cols) {
    	float d = 0.0;
    	for (size_t j = 0; j < cols; j++)
    	{
    		d += (double)(ptr[j] - ptrCen[j])*(ptr[j] - ptrCen[j]);
    	}
    	d = sqrt(d);
    	return d;
    }
    
    /** @brief   最大最小距离算法
     @param data  输入样本数据，每一行为一个样本，每个样本可以存在多个特征数据
     @param Theta 阈值，一般设置为0.5，阈值越小聚类中心越多
     @param centerIndex 聚类中心的下标
     @return 返回每个样本的类别，类别从1开始，0表示未分类或者分类失败
    */
    cv::Mat  MaxMinDisFun(cv::Mat data, float Theta, vector<int> ¢erIndex) {
    	double maxDistance = 0;
    	int start = 0;    //初始选一个中心点
    	int index = start; //相当于指针指示新中心点的位置
    	int k = 0;        //中心点计数，也即是类别
    	int dataNum = data.rows; //输入的样本数
    							 //vector<int>	centerIndex;//保存中心点
    	cv::Mat distance = cv::Mat::zeros(cv::Size(1, dataNum), CV_32FC1); //表示所有样本到当前聚类中心的距离
    	cv::Mat minDistance = cv::Mat::zeros(cv::Size(1, dataNum), CV_32FC1); //取较小距离
    
    
    	cv::Mat classes = cv::Mat::zeros(cv::Size(1, dataNum), CV_32SC1);     //表示类别
    	centerIndex.push_back(index); //保存第一个聚类中心
    	
    	for (size_t i = 0; i < dataNum; i++)
    	{
    		uchar* ptr1 = data.ptr<uchar>(i);
    		uchar* ptrCen = data.ptr<uchar>(centerIndex.at(0));
    		float d= calcuDistance(ptr1, ptrCen, data.cols);
    		distance.at<float>(i, 0) = d;
    		classes.at<int>(i, 0) = k + 1;
    		if (maxDistance < d)
    		{
    			maxDistance = d;
    			index = i; //与第一个聚类中心距离最大的样本
    		}
    	}
    
    	minDistance = distance.clone();
    	double minVal; double maxVal; cv::Point minLoc; cv::Point maxLoc;
    	maxVal = maxDistance;
    	while (maxVal > (maxDistance*Theta)) {
    		k = k + 1;
    		centerIndex.push_back(index); //新的聚类中心
    		for (size_t i = 0; i < dataNum; i++)
    		{
    			uchar* ptr1 = data.ptr<uchar>(i);
    			uchar* ptrCen = data.ptr<uchar>(centerIndex.at(k));
    			float d = calcuDistance(ptr1, ptrCen, data.cols);
    			distance.at<float>(i, 0) = d;
    			//按照当前最近临方式分类，哪个近就分哪个类别
    			if (minDistance.at<float>(i, 0) > distance.at<float>(i, 0))
    			{
    				minDistance.at<float>(i, 0) = distance.at<float>(i, 0);
    				classes.at<int>(i, 0) = k + 1;
    			}
    		}
    		//查找minDistance中最大值
    		cv::minMaxLoc(minDistance, &minVal, &maxVal, &minLoc, &maxLoc);
    		index = maxLoc.y;
    	}
    	return classes;
    }
    
    
    
    int main()
    {
    	cv::Mat data = (cv::Mat_<uchar>(2, 10) << 0, 3, 2, 1, 5, 4, 6, 5, 6, 7, 0, 8, 2, 1, 3, 8, 3, 4, 4, 5);
    	//cv::Mat data = (cv::Mat_<uchar>(4, 10) << 0, 3, 2, 1, 5, 4, 6, 5, 6, 7, 0, 8, 2, 1, 3, 8, 3, 4, 4, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1);
    	data = data.t();
    	cout << "原始数据data=\n" << data << endl;
    	vector<int> centerIndex;
    	float Theta = 0.6;
    	cv::Mat classes = MaxMinDisFun(data, 0.5, centerIndex);
    	cout << "类别classes=\n" << classes << endl;
    
    	system("pause");
    	waitKey();
    	return 0;
    }

运行结果：

原始数据data=
    [  0,   0;
       3,   8;
       2,   2;
       1,   1;
       5,   3;
       4,   8;
       6,   3;
       5,   4;
       6,   4;
       7,   5]
    类别classes=
    [1;
     2;
     1;
     1;
     3;
     2;
     3;
     3;
     3;
     3]

### **2.**C++，Python以及Matlab版本 ###

请参考鄙人的博客：《[聚类算法-最大最小距离算法(实例+代码)][-]》https://blog.csdn.net/guyuealian/article/details/53708042

如果你觉得该帖子帮到你，还望贵人多多支持，鄙人会再接再厉，继续努力的~

![70][]

[Link 1]: https://blog.csdn.net/guyuealian/article/details/80255524
[-]: https://blog.csdn.net/guyuealian/article/details/53708042
[Center]: /images/20220525/ae17242783d94e968f7e88e174dba757.png
[Center 1]: /images/20220525/288844800a464b31aaeb428ee40d6550.png
[Center 2]: /images/20220525/cc67cf973a224fdfaeb32da847ba7bb1.png
[70]: /images/20220525/b6043428d57b461b9d41efb264882bd7.png