聚类算法-最大最小距离算法(实例+代码)

落日映苍穹つ 2022-07-13 00:44 651阅读 0赞

## 聚类算法-最大最小距离算法(实例+代码) ##

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

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

二、算法实现步骤

1.最大最小距离聚类算法（Matlab版本）

2.最大最小距离聚类算法（Python版本）

3.最大最小距离聚类算法（OpenCV C++版本）

4.最大最小距离聚类算法（C++版本）

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

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

最大最小距离法是模式识别中一种基于试探的类聚算法，它以欧式距离为基础，取尽可能远的对象作为聚类中心。因此可以避免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][]

PS：上面的算法内容都是写在Word文档，然后截图放出来的，需要原版Word文档，留言发给你便是~

### **1.最大最小距离聚类算法（Matlab版本）** ###

【[源码下载][Link 2]，可直接运行使用】http://download.csdn.net/detail/guyuealian/9714195

测试代码：test.m

clear all
    clc
    x=[0,0; 3,8; 2,2;1,1; 5,3; 4,8; 6,3; 5,4;  6,4;  7,5]
    Theta=0.5;
    [pattern,centerIndex]=MaxMinDisFun(x,0.5)

%%%%%%%%%%%%%%%%%
    %函数名称 MaxMinDisFun(x,Theta)
    %输入参数：
    %           x  ： x为n*m的特征样本矩阵，每行为一个样本，每列为样本的特征
    %         Theta：即θ，可用试探法取一固定分数，如：1/2
    %输出参数：
    %       pattern：输出聚类分析后的样本类别
    %   centerIndex：聚类中心点
    %函数功能 ：利用最大最小距离算法聚类样本数据，
    %%%%%%%%%%%%%%%%%%%%%
    function [classes,centerIndex]=MaxMinDisFun(x,Theta)
    maxDistance=0;
    start=1;    %初始选一个中心点
    index=start;%相当于指针指示新中心点的位置
    k=1;        %中心点计数，也即是类别
    dataNum=size(x,1);  %输入的样本数
    centerIndex=zeros(dataNum,1); %保存中心点
    distance=zeros(dataNum,1);    %表示所有样本到当前聚类中心的距离
    minDistance=zeros(dataNum,1); %取较小距离
    classes=zeros(dataNum,1);     %表示类别
    
    centerIndex(1)=index;%保存第一个聚类中心
    classes(:)=k;        %初始类别全为k
    %%
    for i=1:dataNum
        distance(i)=sqrt((x(i,:)-x(centerIndex(1),:))*(x(i,:)-x(centerIndex(1),:))');%欧氏距离，与第1个聚类中心的距离
        classes(i)=k;%第1类
        if(maxDistance<distance(i))
            maxDistance=distance(i);%与第一个聚类中心的最大距离
            index=i;%与第一个聚类中心距离最大的样本
        end
    end
    %%
    minDistance=distance;
    % minDistance(index,1)=0;
    maxVal=maxDistance;
    while(maxVal>(maxDistance*Theta))%判断新的聚类中心是否满足条件
        k=k+1;
        centerIndex(k)=index;%判断新的聚类中心是否满足条件,若满足则新增聚类中心
        for i=1:dataNum 
                distance(i)=sqrt((x(i,:)-x(centerIndex(k),:))*(x(i,:)-x(centerIndex(k),:))');%与第k个聚类中心的距离
               if(minDistance(i)>distance(i))
                   minDistance(i)=distance(i);
                   classes(i)=k;%按照当前最近临方式分类，哪个近就分哪个类别
               end
        end
        %查找minDistance中最大值
        maxVal=0;
        for i=1:dataNum
            if((maxVal<minDistance(i))) 
                maxVal=minDistance(i);
                index=i;
            end
        end
    %     centerIndex(k+1)=index;%新的聚类中心
        aaa=0;
    end
    end

**运行结果：**

x =
         0     0
         3     8
         2     2
         1     1
         5     3
         4     8
         6     3
         5     4
         6     4
         7     5
    pattern =
         1
         2
         1
         1
         3
         2
         3
         3
         3
         3
    centerIndex =
         1
         6
         7
         0
         0
         0
         0
         0
         0
         0

### **2.最大最小距离聚类算法（Python版本）** ###

# -*-coding: utf-8 -*-
    """
        @Project: IntelligentManufacture
        @File   : maxmin_distance.py
        @Author : panjq
        @E-mail : pan_jinquan@163.com
        @Date   : 2019-02-14 18:41:30
    """
    import math
    import numpy as np
    def calcuDistance(data1, data2):
        '''
        计算两个模式样本之间的欧式距离
        :param data1:
        :param data2:
        :return:
        '''
        distance = 0
        for i in range(len(data1)):
            distance += pow((data1[i]-data2[i]), 2)
        return math.sqrt(distance)
    
    def maxmin_distance_cluster(data, Theta):
        '''
        :param data: 输入样本数据,每行一个特征
        :param Theta:阈值，一般设置为0.5，阈值越小聚类中心越多
        :return:样本分类，聚类中心
        '''
        maxDistance = 0
        start = 0#初始选一个中心点
        index = start#相当于指针指示新中心点的位置
        k = 0 #中心点计数，也即是类别
    
        dataNum=len(data)
        distance=np.zeros((dataNum,))
        minDistance=np.zeros((dataNum,))
        classes =np.zeros((dataNum,))
        centerIndex=[index]
    
        # 初始选择第一个为聚类中心点
        ptrCen=data[0]
        # 寻找第二个聚类中心，即与第一个聚类中心最大距离的样本点
        for i in range(dataNum):
            ptr1 =data[i]
            d=calcuDistance(ptr1,ptrCen)
            distance[i] = d
            classes[i] = k + 1
            if (maxDistance < d):
                maxDistance = d
                index = i #与第一个聚类中心距离最大的样本
    
        minDistance=distance.copy()
        maxVal = maxDistance
        while maxVal > (maxDistance * Theta):
            k = k + 1
            centerIndex+=[index] #新的聚类中心
            for i in range(dataNum):
                ptr1 = data[i]
                ptrCen=data[centerIndex[k]]
                d = calcuDistance(ptr1, ptrCen)
                distance[i] = d
                #按照当前最近临方式分类，哪个近就分哪个类别
                if minDistance[i] > distance[i]:
                    minDistance[i] = distance[i]
                    classes[i] = k + 1
            # 寻找minDistance中的最大距离，若maxVal > (maxDistance * Theta)，则说明存在下一个聚类中心
            index=np.argmax(minDistance)
            maxVal=minDistance[index]
        return classes,centerIndex
    
    if __name__=='__main__':
        data = [[0, 0], [3, 8], [2, 2],[1, 1], [5, 3], [4, 8], [6, 3], [5, 4], [6, 4], [7, 5]]
        Theta = 0.6
        classes,centerIndex = maxmin_distance_cluster(data, Theta)
        print(classes)
        print(centerIndex)

### **3.最大最小距离聚类算法（OpenCV C++版本）** ###

**    ** 强势推荐鄙人的博客：《[OpenCV实现最大最小距离聚类算法][OpenCV]》https://blog.csdn.net/guyuealian/article/details/80255524

### **4.最大最小距离聚类算法（C++版本）** ###

// MaxMinDisTest.cpp : 
    #include "stdafx.h"
    #include <iostream>
    #include <math.h>
    using namespace std;
    const int N=10;
    void main(void)
    { int center[20];
      float s[2][N]={
       {0,3,2,1,5,4,6,5,6,7},
                     {0,8,2,1,3,8,3,4,4,5}};
      float D[20][N];
      float min[N];
      int minindex[N];
      int clas[N];
      float theshold;
      float theta=0.5;
      float D12=0.0;
      float tmp=0;
      int index=0;
      center[0]=0;//first center
      int i,k=0,j,l;
      for(j=0;j<N;j++)
      { tmp=(s[0][j]-s[0][0])*(s[0][j]-s[0][0])+(s[1][j]-s[1][0])*(s[1][j]-s[1][0]);
    	D[0][j]=(float)sqrt(tmp);
        if(D[0][j]>D12) {D12=D[0][j];index=j;}
      }
      center[1]=index;//second center
      k=1;
      index=0;
      theshold=D12;
      while(theshold>theta*D12){
    	   for(j=0;j<N;j++){
    	       tmp=(s[0][j]-s[0][center[k]])*(s[0][j]-s[0][center[k]])+
    		          (s[1][j]-s[1][center[k]])*(s[1][j]-s[1][center[k]]);
               D[k][j]=(float)sqrt(tmp);}
    	   for(j=0;j<N;j++){
    		   float tmp=D12;
               for(l=0;l<=k;l++)
    			   if (D[l][j]<tmp) {tmp=D[l][j];index=l;};
               min[j]=tmp;minindex[j]=index;
    		  }//min-operate
    	   float max=0;index=0;
           for(j=0;j<N;j++)
             if(min[j]>max) {max=min[j];index=j;}
    	   if (max>theta*D12){k++;center[k]=index;}// add a center
    	   theshold=max;// prepare to loop next time
    	 }  //求出所有中心,final array min[] is still useful
       for(j=0;j<N;j++)  clas[j]=minindex[j];
       for(i=0;i<2;i++)
       {for(j=0;j<N;j++)
           cout<<s[i][j]<<"  ";
        cout<<"\n";
       }
       cout<<"k="<<k+1<<" ";
       cout<<"center(s):";
       for(l=0;l<k;l++) cout<<center[l]+1<<"--";cout<<center[k]+1;
       cout<<"\n";
       for(j=0;j<N;j++)
    	   cout<<clas[j]+1<<"  ";
       cout<<"\n";
    }

![Center 3][]

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

![70][]

[Link 1]: http://blog.csdn.net/guyuealian/article/details/53708042
[Center]: /images/20220713/484bf2fc5c0349ddafedb060c6b1e956.png
[Center 1]: /images/20220713/55094559e44b40daa3027e9727050599.png
[Center 2]: /images/20220713/5762296c05be48099d4c5554bbcc35d8.png
[Link 2]: http://download.csdn.net/detail/guyuealian/9714195
[OpenCV]: https://blog.csdn.net/guyuealian/article/details/80255524
[Center 3]: /images/20220713/2f87d9d1ad084b12b35b83b249585c27.png
[70]: /images/20220713/b033e344cddd40b484714011320dc9ff.png