美文网首页
二分 KMeans,Bisecting KMeans 代码实现

二分 KMeans,Bisecting KMeans 代码实现

作者: cooooper | 来源:发表于2020-01-19 16:37 被阅读0次

    算法原理:
    由于传统KMeans算法的聚类结果易受初始聚类中心点选择的影响,因此在传统的KMeans算法的基础上进行改进。
    二分KMeans(Bisecting KMeans)算法的主要思想是:首先将所有点作为一个簇,然后将该簇一分为二。之后选择能最大限度降低聚类代价函数(误差平方和SSE)的簇划分为两个簇。以此进行下去,直到簇的数目等于给定的数目K为止。

    代码实现:
    基于DataFrame

    def bi_kmeans(data: 'DataFrame', K: int) -> 'DataFrame':
        """二分KMeans
        data: data['embedding'] 输入x的向量
        K: 聚类类别数
        """
    
        def sse(error):
            """计算误差平方和"""
            return np.square(np.linalg.norm(error))
    
        def euclidean_dist(v1, v2):
            """计算两个向量间的欧氏距离"""
            return np.linalg.norm(v1 - v2)
    
        def dist_from_center(label, embedding, cluster_center, offset=0):
            """计算每个元素与其类别中心的欧氏距离
            offset: label的偏移量
            return: float"""
            center = cluster_center[label - offset]
            dist = euclidean_dist(embedding, center)
            return dist
        
        # 初始化类的中心
        cluster_center = [np.mean(data.embedding)]
        # 初始化每个item的label和到聚类中心的距离
        data['label'] = 0
        data['dist_from_center'] = data.apply(lambda x: dist_from_center(x['label'], x['embedding'], cluster_center), axis=1)
    
        # 当前k小于给定K值时
        k = 1
        while k < K :
            print('Current Cluster Number: {}  >>>'.format(k))
    
            # 计算当前sse
            total_sse = sse(data.dist_from_center)
            sharp_drop = 0
    
            # 遍历当前每个簇,将其一分为二,计算新的sse
            keep_i = -1
            for i in range(k):
                # 第i簇数据
                group_i = data[data.label == i]
                if group_i.shape[0] > 2:
                    pre_sse = sse(group_i.dist_from_center)
                    # 二分当前簇
                    bi_kmeans = KMeans(n_clusters=2).fit(group_i.embedding.tolist())
                    # 更新label和dist
                    group_i['label'] = bi_kmeans.labels_
                    new_center = bi_kmeans.cluster_centers_
                    group_i['dist_from_center'] = group_i.apply(lambda x: dist_from_center(x['label'], x['embedding'], new_center), axis=1)
                    # 计算当前sse
                    post_sse = sse(group_i.dist_from_center)
                    # sse下降程度
                    drop = pre_sse - post_sse
                    # 保留最大下降ssd的i
                    if drop > sharp_drop:
                        keep_i = i
                        sharp_drop = drop
    
            # 选出待二分的数据
            group_i = data[data.label == keep_i]
            group_i_index = data[data.label == keep_i].index
            # 二分,更新label
            bi_kmeans = KMeans(n_clusters=2).fit(group_i.embedding.tolist())
            group_i['label'] = bi_kmeans.labels_ + k
            data.loc[group_i_index, 'label'] = bi_kmeans.labels_ + k
            new_center = bi_kmeans.cluster_centers_
            # 更新距中心距离
            data.loc[group_i_index, 'dist_from_center'] = group_i.apply(lambda x: dist_from_center(x['label'], x['embedding'], new_center, offset=k), axis=1)
            # 更新超出k的label为原有label
            k_plus_1_index = data[data.label == k + 1].index
            data.loc[k_plus_1_index, 'label'] = keep_i
            # 更新类别数
            k += 1
        return data
    

    相关文章

      网友评论

          本文标题:二分 KMeans,Bisecting KMeans 代码实现

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