k-medoidsクラスタリングアルゴリズム

引用する
前回のブログでは、効率的で高速ですが、異常点の影響が大きく、サンプルに異常点がある場合、クラスタリング結果に大きなばらつきが生じるk-meansクラスタリングアルゴリズムを紹介しました.クラスタリング結果に及ぼす異常点の影響について,k−medoidsクラスタリングアルゴリズムを紹介し,k−medoidsアルゴリズムは異常点の影響を効果的に弱めることができる.
k-medoidsアルゴリズム
k-mediodsが選択するたびに選択する中心点は、サンプル点でなければならないが、k-meansが選択するたびに選択する中心点は、中位数と平均値の違いのようなサンプル点以外の点であってもよい.
k-medoidsアルゴリズムステップ:1.k個の初期中心点medoidsを任意に選択する.2.medoidsに最も近い原則に従って、現在の最適なmedoidsが表すクラスに残りの点を割り当てる.3.各クラスにおいて、各サンプル点と他の点との距離の和を計算し、距離の和の最小の点を新しいmedoidsとして選択する.4.すべてのmedoids点が変化しないか、設定された最大反復回数に達するまで2-3のプロセスを繰り返す.k-medoidsアルゴリズムクラスタの中心点を選択する準則関数は、現在のクラスタ内の他のすべての点からその中心点までの距離の和が最小であるため、クラスタ内のすべての点を遍歴する必要がある.
アルゴリズムまとめ1)「代表オブジェクト」に基づくクラスタリング方法;2)データ変数が数値型のクラスタリングアルゴリズム;3)異常点はクラスタリング結果に深刻な影響を及ぼさない.4)時間的複雑度はk−meansアルゴリズムより高い.
python実装

#      
import numpy as np
from numpy import *
import sys
from sklearn import metrics
from sklearn.preprocessing import StandardScaler
import pandas as pd
import matplotlib.pyplot as plt

#          
def func_of_dis(x, y):
	return np.sqrt(sum(np.square(x - y)))

#k-medoids    
def KMedoids(df, k_num_center):
    """
                 
    :param df:    ，pd.DataFrame  
    :param k_num_center:   
    """
    print('   ',k_num_center, '    ')
    data = df.values
    #data = StandardScaler().fit_transform(df) #     
    indexs = list(range(len(data)))
    random.shuffle(indexs)  #       
    init_centroids_index = indexs[:k_num_center]
    centroids = data[init_centroids_index, :]   #      
    #       
    levels = list(range(k_num_center))
    print('    ')
    #sample_target = [] #      
    if_stop = False
    while(not if_stop):
        if_stop = True
        classify_points = [[centroid] for centroid in centroids] #          
        sample_target = [] #      
        
        #     
        for sample in data:
            #     ，           ，        
            distances = [func_of_dis(sample, centroid) for centroid in centroids] #               
            cur_level = np.argmin(distances) #                       
            sample_target.append(cur_level)
            #   ，              
            classify_points[cur_level].append(sample) #              
        
        #       
        distances_res = [] #                  ，k     k  
        for i in range(k_num_center):  #             
            distances = [func_of_dis(point_1, centroids[i]) for point_1 in classify_points[i]] #                       
            now_distances = sum(distances)   #                      
            for point in classify_points[i]:
                distances = [func_of_dis(point_1, point) for point_1 in classify_points[i]] #              
                new_distance = sum(distances)
                #                    ，                ，     
                if new_distance < now_distances:
                    now_distances = new_distance
                    centroids[i] = point    #     
                    if_stop = False
                    distances_res.append(now_distances)
    return(sample_target,distances_res)

#  k 
def k_value_sse(k_value_list):
	#  SSE  k
	SSE = []  #             
	sse_df = pd.DataFrame()
	for i in k_value_list:
		estimator = KMedoids(df,i)  #      
		distances_res = estimator[1]
		dist_sum = sum(distances_res)
		SSE.append(dist_sum)

	return(k_value_list,SSE)

異なるk値はSSEに対応する価値があり、最終的には人間の肘に相当する曲線を描き、肘に対応する点が最適なk値点、すなわち曲線の曲がり点である.

#     k  
best_model = KMedoids(data,k)

#    ,      
labels = KMedoids(data,k)[0]
score = silhouette_score(data,labels,metric='euclidean')