聚类算法-最大最小距离算法(实例+代码)
目录
聚类算法-最大最小距离算法(实例+代码)
一、最大最小距离算法基本思想
二、算法实现步骤
1.最大最小距离聚类算法（Matlab版本）
2.最大最小距离聚类算法（Python版本）
3.最大最小距离聚类算法（OpenCV C++版本）
4.最大最小距离聚类算法（C++版本）
一、最大最小距离算法基本思想
最大最小距离法是模式识别中一种基于试探的类聚算法，它以欧式距离为基础，取尽可能远的对象作为聚类中心。因此可以避免K-means法初值选取时可能出现的聚类种子过于临近的情况，它不仅能智能确定初试聚类种子的个数，而且提高了划分初试数据集的效率。
该算法以欧氏距离为基础，首先初始一个样本对象作为第1个聚类中心，再选择一个与第1个聚类中心最远的样本作为第2个聚类中心，然后确定其他的聚类中心，直到无新的聚类中心产生。最后将样本按最小距离原则归入最近的类。
二、算法实现步骤
样本分布如图所示：
最大最小距离聚类算法步骤如下：
该算法的聚类结果与参数和起始点的选取关系重大。若无先验样本分布知识，则只有用试探法通过多次试探优化，若有先验知识用于指导和选取，则算法可很快收敛。
为了方便看解计算过程，下面以表格的方式列出：
PS：上面的算法内容都是写在Word文档，然后截图放出来的，需要原版Word文档，留言发给你便是~
1.最大最小距离聚类算法（Matlab版本）
【源码下载，可直接运行使用】
测试代码：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 : [email protected]
@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实现最大最小距离聚类算法》
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";
}
