MMD(最大最小距离)与均值聚类的K_Means算法实现与性能比较

文章目录

  • 一. MMD算法简介与实现
    • 1.1 MMD算法简介
    • 1.2 算法实现
      • 1.2.1 算法
      • 1.2.2 程序
    • 1.3 算法性能
  • 二. 均值聚类算法简介与实现
    • 1.1 均值聚类算法简介
    • 1.2 算法实现
      • 1.2.1 算法
      • 1.2.2 程序
        • sklearn简单实现
        • 手动实现
    • 1.3 算法性能
  • 三. 两类算法性能比较

一. MMD算法简介与实现

1.1 MMD算法简介

   MMD(最大最小距离算法)最大最小距离法是模式识别中一种基于试探的类聚算法,它以欧式距离为基础,取尽可能远的对象作为聚类中心。因此可以避免K-means法初值选取时可能出现的聚类种子过于临近的情况。
  也就是说,如果采用随机选取初始点的算法,如果两个初始聚类中心点非常接近,那么会导致收敛时间过长而降低性能,因此MMD算法可以最大可能地使点的选取避免这种情况。

1.2 算法实现

  使用的是iris数据集,然后分成三类,可以自行调整

1.2.1 算法

MMD(最大最小距离)与均值聚类的K_Means算法实现与性能比较_第1张图片

1.2.2 程序

 数据处理(以Anaconda为编程环境)

import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
import random
import math
from sklearn.cluster import KMeans
from sklearn.preprocessing import MinMaxScaler

data = []
with open('./iris.dat', 'r') as f:
    while True:
        thisline = f.readline()
        if not thisline:
            break
        else:
            thisline = thisline.strip('\n')
            thisline = thisline.split('\t')
            data.append(thisline)
            
#查找缺失值
def findNullVal(data):
	df = pd.DataFrame(data)
	print(df, df.shape)
	null_sum = 0 #find out whether there are some null values
	for i in range(df.shape[1]):
	    null_sum += df[i].isnull().sum()
	print(null_sum)#打印缺失值的和
	return df

#数据归一化
def dataProcess(df):
	data = np.array(df).astype('float')
	random.seed(0)
	X, y = data[:, 0:4], data[:, 4]
	MMS = MinMaxScaler().fit(X)
	X = MMS.transform(X)
	y.astype('int')
	return X, y
#此时的x,y为输入的标准格式
class K_means:
    def __init__(self, x, y, theta = 0.5, iteration = 100):
    #x为训练数据,y为了计算准确率,theta为MMD阈值,iteration为迭代次数
        self.x = x
        self.y = y
        self.theta = theta
        self.center = []
        self.center_indices = []
        self.iteration = iteration
        print("完成初始化")
    def computeDis(self, x1, x2):#计算两点之间的欧式距离
        return math.sqrt(np.sum(np.square(np.array(x1) - np.array(x2))))
    def MMDInitialzation(self):#MMD算法
        self.center_indices.append(random.choice(np.arange(self.x.shape[0])))
        self.center.append(self.x[self.center_indices[0]])#选择第一个初始聚类点
        print("初始中心点0:" + str(self.center[0]))
        max_dis = -1
        max_dis_indice = None
        for i in range(self.x.shape[0]):
            temp_dis = self.computeDis(self.x[i], self.center[0])
            if temp_dis > max_dis:
                max_dis = temp_dis
                max_dis_indice = i
        self.center.append(self.x[max_dis_indice])
        self.center_indices.append(max_dis_indice)
        print("初始中心点1:" + str(self.center[1]))
        #第三个初始点选择
        disB01 = self.computeDis(self.center[0] , self.center[1])
        max_dis = -3
        max_dis_indice = None
        for i in range(self.x.shape[0]):
            disMin =  min(self.computeDis(self.x[i] , self.center[0]),self.computeDis(self.x[i] , self.center[1]))
            if disMin > max_dis:
                max_dis = disMin
                max_dis_indice = i
        if max_dis > self.theta * disB01:
            print("找到第三个点")
            self.center.append(self.x[max_dis_indice])
            self.center_indices.append(max_dis_indice)
        print("初始中心点2:" + str(self.center[2]))
        #进行聚类
        self.category = []
        for j in range(self.x.shape[0]):
            dis = list([0, 0, 0])
            for k in range(3):
                dis[k] = self.computeDis(self.x[j] , self.center[k])
            self.category.append(self.y[self.center_indices[dis.index(max(dis))]])
        #print(self.y)
        #print(self.category)
        print((np.sum(self.y == self.category)) / len(self.y))
        return self.center_indices#返回的是中心点的索引

1.3 算法性能

df = findNullVal(data)#返回dataFrame格式的数据,打印缺失值个数,如果有缺失值,则使用pandas进行处理:均值填充或者其他都可以
X, y = dataProcess(df)
k = K_means(X, y, 0.4, 1000)#创建K-Means类
#均值聚类效果
k.averageCluster()
#MMD聚类效果
next_center_indices = k.MMDInitialzation()
#输出
完成初始化
0.24#这是均值聚类算法输出(sklearn迭代200次后的准确率)
#开始MMD聚类算法输出
初始中心点0:[0.22222222 0.20833333 0.33898305 0.41666667]
初始中心点1:[0.94444444 0.75       0.96610169 0.875     ]
找到第三个点
初始中心点2:[0.38888889 1.         0.08474576 0.125     ]
0.13333333333333333#这是MMD算法聚类的准确率,可以通过调整theta调整准确率

二. 均值聚类算法简介与实现

1.1 均值聚类算法简介

    K-Means算法主要是通过随机选定初始值,后经过多次迭代不断选择聚类中心点并重新分类来达到分类的目的。但是,K-Means主要最重大的缺陷——都和初始值有关:K是事先给定的,这个K值的选定是非常难以估计的。很多时候,事先并不知道给定的数据集应该分成多少个类别才最合适,同时,初始值也决定了分类收敛的性能,如果两个初始点在一起会影响迭代。

1.2 算法实现

1.2.1 算法

  1. 从数据中选择k个对象作为初始聚类中心;
  2. 计算每个聚类对象到聚类中心的距离来划分;
  3. 再次计算每个聚类中心
  4. 计算标准测度函数,直到达到最大迭代次数,则停止,否则,继续操作。
  5. 确定最优的聚类中心

1.2.2 程序

sklearn简单实现

    def averageCluster(x, y, iteration):
        y_pred = KMeans(n_clusters=3, max_iter = iteration, random_state=9).fit_predict(x)
        print(np.sum(y_pred == y) / len(y))#计算准确率

手动实现

def cluster(x, y, k, iters = 200, method = 0, thresh = 0.4):#method进行方法选择
    initial_center_indices = []
    #首先进行初始化方法的选择
    if method == 0:#选择随机初始化方法
        initial_center_indices = random.sample(range(x.shape[0]), k)
        #这里调用了上面K-Means类的初始化中心点,不再进行计算
    elif method == 1:
        initial_center_indices = next_center_indices
    print(initial_center_indices)#打印选择的初始中心点
    center = [x[i] for i in initial_center_indices]
    #print(center)
    #开始聚类
    for i in range(iters):#开始迭代循环
        #划定模式类别
        category = [[], [], []]
        for j in range(x.shape[0]):
            dis = []
            for m in range(k):
                dis.append(computeDis(x[j], center[m]))
            category[dis.index(min(dis))].append(j)
        #计算新的中心点
        for m in range(k):
            for i in category[m]:
                center[m] += x[i]
            center[m] /= len(category[m])
        #print(center)
    #聚类完成,更新类别
    y_pred = [0 for i in range(150)]
    for i in range(len(category)):
        #print(len(category[i]))
        for j in range(len(category[i])):
            #print(len(category[i]))
            y_pred[category[i][j]] = i
    p_rate = np.sum(y == y_pred)/ len(y)
    return y_pred, p_rate

    测试

print(cluster(X, y, 3, 200, 0))
print(cluster(X, y, 3, 200, 1))

1.3 算法性能

#输出
[107, 10, 66]#均值聚类初始化中心点的索引
 0.3466666666666667#准确率
 
[98, 117, 15]#MMD初始化中心点的索引
0.32666666666666666#准确率

    可以看出,通过选定不同的初始化方法,K-means算法在经过同样的迭代次数后准确率是不同的。

三. 两类算法性能比较

  1. 对于初始化方法而言,同样的K-means算法在不同的初始化方法:随机初始化,MMD初始化方法所显示出来的准确率是不一样的。MMD方法可以显然地克服随机初始化方法的一些缺点:例如初始化点过近而导致的收敛慢等问题。
  2. 对于MMD聚类算法与均值聚类算法而言,MMD聚类算法虽然克服了一部分问题,但是其性能取决于常数θ的选取。最大最小距离算法实现简单,处理大数据集的能力较强,但是算法对噪音数据敏感,在存在噪音数据的情况下,聚类中心可能偏移真正的类别中心较远。

参考:
聚类算法分析及其性能比较

你可能感兴趣的