美文网首页数学原理
非监督学习之聚类算法(2)--基于划分

非监督学习之聚类算法(2)--基于划分

作者: Byte猫 | 来源:发表于2019-04-04 21:34 被阅读34次

    基于划分的方法(Partition-based Methods):其原理简单来说就是,想象你有一堆散点需要聚类,想要的聚类效果就是“类内的点都足够近,类间的点都足够远”。
    首先你要确定这堆散点最后聚成几类,然后挑选几个点作为初始中心点,再然后依据预先定好的启发式算法(Heuristic Algorithms)给数据点做迭代重置(Iterative Relocation),直到最后到达“类内的点都足够近,类间的点都足够远”的目标效果。
    基于划分的聚类多适用于中等体量的数据集,不妨理解成数据集越大,越有可能陷入局部最小。
    以下是几种常用的划分聚类算法

    一、K-means算法

    K-means算法(K均值聚类)是集简单和经典于一身的基于距离的聚类算法,采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大。
    k-means算法的基础是最小误差平方和准则,各类簇内的样本越相似,其与该类均值间的误差平方越小,对所有类所得到的误差平方求和,即可验证分为k类时,各聚类是否是最优的。

    1、执行步骤

    step 1:随机选取 k个聚类质心点
    我们需要选择最初的聚类点(或者叫质心),这里的选择一般是随机选择的(在数据范围内随机选择,或者是随机选择数据中的点)。这些点的选择会很大程度上影响到最终的结果,也就是说运气不好的话就到局部最小值去了。
    step 2:重复计算误差平方和过程直到收敛

    2、优缺点

    (1)优点

    • 简单,速度快,易于理解和实现;(容易解释,基于距离的聚类算法)
    • 时间复杂度低
      计算复杂度低,为O(Nmq),N是数据总量,m是类别(即k),q是迭代次数。一般来讲m、q会比N小得多,那么此时复杂度相当于O(N),在各种算法中是算很小的

    (2)缺点

    • 需要提前确定k值
      k-means初始簇中心点对算法影响较大,如果初始值不太好,可能对结果产生较大的影响
      改进算法为k-means++、intelligentk-means、genetick-means;
    • 对噪声和离群值非常敏感
      改进算法为k-medoids和k-medians;
    • 只能用于数值类型数据,不适用于标签类型数据
      改进算法为k-modes;
    • 不能解决非凸(non-convex)数据
      改进算法为kernelk-means。
    • 仅适用于球心数据分布,不能识别非球形的簇。
    • 对非均衡数据集(类别规模差异太明显)效果不好。比如总共有A、B两类,A类有1000个点,B类有100个点。
    • 数据比较大时收敛比较慢

    3、代码实现

    # coding=utf-8
    '''
    k-means算法
    '''
    import numpy as np
    import math
    import matplotlib.pyplot as plt
    
    flag = 1
    
    #==============================================
    # 计算距离
    #==============================================
    
    def euclidean_dist(p, q):
        ''' 
        欧式距离(L2范数)
        INPUT  -> 长度一致的向量1、向量2
        '''
        p = np.mat(p)
        q = np.mat(q)
        return math.sqrt(np.sum(np.power(p-q, 2))) 
    
    #==============================================
    # 初始化簇中心
    #==============================================
    
    def cluster_init(dataSet, k):
        ''' 
        中心点初始化
        INPUT  -> 数据集、聚类中心数
        '''
        centers = []
        while len(centers) < k:  # 总共要k个质心
            index = np.random.randint(0, len(dataSet)-1)
            if index not in centers:
                centers.append(index)
        return np.array([dataSet[i] for i in centers])
    
    #==============================================
    # 更新簇中心点
    #==============================================
    
    def cluster_update(dataset):
        '''
        计算簇的均值点
        INPUT  -> 簇集
        '''
        return sum(np.array(dataset)) / len(dataset)
    
    #==============================================
    # 算法核心部分
    #==============================================
    
    
    def kMeans(dataSet, center, k):
        ''' 
        k-Means算法
        INPUT  -> 数据集、初始化中心点、聚类中心数
        '''
        global flag
    
        # 聚类结果
        output = []
        for _ in range(k):
            temp = []
            output.append(temp)
    
        # 计算每个点到各中心点的距离  
        for i in dataSet:
            temp = []
            for j in center:
                temp.append(euclidean_dist(i, j))
            output[temp.index(min(temp))].append(i)
    
        # 更新聚类中心点
        updated_center = np.array([cluster_update(s) for s in output])
        
        # 打印聚类过程
        print('------------------------第'+str(flag)+'次迭代--------------------------')
        for i in range(k):
            print('第'+str(i+1)+'组:', output[i], end='\n')
    
        if (center == updated_center).all():
            print('已收敛,执行结束')
        else:
            flag += 1
            # 递归调用
            center = updated_center
            kMeans(dataSet, center, k)
    
        return updated_center, output
    
    #========================================================
    #  主程序
    #========================================================
    
    if __name__ == '__main__':
        x = [np.random.randint(0, 100) for _ in range(100)]
        y = [np.random.randint(0, 100) for _ in range(100)]
        points = [[i,j] for i,j in zip(x,y)]
    
        initial_center = cluster_init(dataSet=points, k=5)
        center, output = kMeans(dataSet=points, center=initial_center, k=5)
        print(center)
        print(output)
    

    二、k-modes算法

    为了解决K-means只能处理数值型数据的情况,有了K-means的变种算法——K-modes
    K-modes是数据挖掘中针对分类属性型数据进行聚类采用的方法,其算法思想比较简单,时间复杂度也比K-means、K-medoids低。
    将原本K-means使用的欧式距离替换成字符间的汉明距离。

    1、执行步骤

    假设有N个样本,共有M个属性,均为离散的,聚类目标数为K
    step 1:在总体n个样本点中任意选取k个点C1,C2...Ck(Ci是长度为M的向量,Ci=[Ci(1),Ci(2),...,Ci(M)])
    step 2:对于每个样本,分别比较其与这k个中心之间的距离
    step 3:将样本划分到距离最小的簇,在全部的样本都被划分完毕之后,重新确定簇中心,簇中心的每一个分量都更新为该簇中的众数
    step 4:重复步骤2和3,直到总距离(各个簇中样本与各自簇中心距离之和)不再降低,返回最后的聚类结果

    2、优缺点

    (1)优点

    • 支持处理非数值型数据

    (2)缺点

    • 不能反映对象间的潜在的相似关系,特别是当数据量很大或数据集很复杂时,不能更好的区分样本间的差异

    3、代码实现

    # coding=utf-8
    '''
    k-modes算法
    '''
    import numpy as np
    import math
    import matplotlib.pyplot as plt
    
    flag = 1
    
    #==============================================
    # 计算距离
    #==============================================
    
    def hanming_dist(p, q):
        ''' 
        汉明距离
        INPUT  -> 长度一致的向量1、向量2
        '''
        p = np.mat(p)
        q = np.mat(q)
        smstr = np.nonzero(p-q)
        return np.shape(smstr)[1]
    
    #==============================================
    # 初始化簇中心
    #==============================================
    
    def cluster_init(dataSet, k):
        ''' 
        中心点初始化
        INPUT  -> 数据集、聚类中心数
        '''
        centers = []
        while len(centers) < k:  # 总共要k个质心
            index = np.random.randint(0, len(dataSet)-1)
            if index not in centers:
                centers.append(index)
        return np.array([dataSet[i] for i in centers])
    
    #==============================================
    # 重新选定簇中心
    #==============================================
    
    def cluster_update(dataset):
        '''
        重新选定簇中心
        INPUT  -> 簇集
        '''
        dataset = np.array(dataset)
        dataset = dataset.T
        center = []
        for line in dataset:
            dictnum = {}
            for i in line:
                if i in dictnum.keys():
                    dictnum[i] += 1
                else:
                    dictnum.setdefault(i, 1)
            center.append(max(dictnum, key=dictnum.get))
        return np.array(center)
    
    #==============================================
    # 算法核心部分
    #==============================================
    
    
    def kModes(dataSet, center, k):
        ''' 
        k-Modes算法
        INPUT  -> 数据集、初始化中心点、聚类中心数
        '''
        global flag
    
        # 聚类结果
        output = []
        for _ in range(k):
            temp = []
            output.append(temp)
    
        # 计算每个点到各中心点的距离
        for i in dataSet:
            temp = []
            for j in center:
                temp.append(hanming_dist(i, j))
            output[temp.index(min(temp))].append(i)
    
        # 更新聚类中心点
        updated_center = np.array([cluster_update(s) for s in output])
        
        # 打印聚类过程
        print('------------------------第'+str(flag)+'次迭代--------------------------')
        for i in range(k):
            print('第'+str(i+1)+'组:', output[i], end='\n')
    
        if (center == updated_center).all():
            print('已收敛,执行结束')
        else:
            flag += 1
            # 递归调用
            center = updated_center
            kModes(dataSet, center, k)
    
        return updated_center, output
    
    #========================================================
    #  主程序
    #========================================================
    
    if __name__ == '__main__':
        a = [np.random.randint(0, 3) for _ in range(50)]
        b = [np.random.randint(0, 3) for _ in range(50)]
        c = [np.random.randint(0, 3) for _ in range(50)]
        d = [np.random.randint(0, 3) for _ in range(50)]
        e = [np.random.randint(0, 3) for _ in range(50)]
        points = [[a,b,c,d,e] for a,b,c,d,e in zip(a,b,c,d,e)]
    
        initial_center = cluster_init(dataSet=points, k=5)
        center, output = kModes(dataSet=points, center=initial_center, k=5)
        print(center)
        print(output)
    

    相关文章

      网友评论

        本文标题:非监督学习之聚类算法(2)--基于划分

        本文链接:https://www.haomeiwen.com/subject/aisqiqtx.html