1.基本K-Means演算法

K-Means演算法是較為常用的聚類演算法,其目標是將資料點劃分為K個類簇。K-Means主要思想是選取K箇中心點,對最靠近它的物件進行歸類,透過迭代的方式不斷更新聚類結果,直到滿足使用者的要求。

(1)確定K值,將資料集劃分為K組,確定K值沒有最好的方法,一般情況下根據具體問題由人工進行選擇。(2)從資料集中選擇K個點作為資料中心(可隨機選擇,可由距離選擇)。(3)分別計算每個點到每個質心之間的距離,並將每個點劃分到離最近質心的小組。(4)當每個中心都聚集一些點後,根據規則重新選取新的資料中心。(5)跌倒(2)~(4),直到滿足終止條件為止。

K-Means主要包括獲取資料中心、獲取每個資料點到資料中心的距離、更新資料中心等主要功能,筆者實現時,還加入了一些處理函式,下面為大家逐一講解。

def get_center(data,k):    dim=np.shape(data)[1]#獲取原始資料的維度    center=np.zeros((k,dim))#k*n列矩陣    ocenter=sample(list(data),k)#隨機選取k個數據中心    for i in range(k):        center[i]=ocenter[i]#將資料中心寫入矩陣    #center=center.astype(np.int)    return center

上述程式碼主要實現了獲取資料中心的功能,輸入引數data為輸入的原始資料,K是想要分為K組。

def get_distance(a,b):    return math.sqrt(sum(pow(a-b,2)))#計算兩點之間距離

def detele_center(data,center,K):#將資料中心從原始資料中刪除    ex_data = data    for i in range(K):#遍歷維度        # print('centeri=',center[i],'\n')        for j in range(len(ex_data)):#遍歷資料行數            # print('exdataj=',ex_data[j],'\n')            if (center[i] == ex_data[j]).all:#若資料中心和原始資料相等,則刪除                ex_data = np.delete(ex_data, j, axis=0)  # 刪除整行資料                break    return ex_data

def delete_zero(a):#傳入分組結果,將分組沒用到的位置刪除    group=list(a)    index=[]    for j, each in enumerate(group):#若group=[2 2],則enumerate(group)可生成[(0,2),(1,2)]的list        if each == 0:#若值為0則刪除            index.append(j)            del group[j]    for k, each in enumerate(group):        each_int = int(each)        group[k] = each_int    group = np.array(group)    return group

def get_updatecenter(n_data,K):#輸入n_data的資料型別為(n,2)的list    # n行代表的是從原始資料剔除資料中心後的資料行數    #列1代表的是分組結果,列2代表的是資料點    center=[]    write = True#寫指標    for i in range(K):        exec("center_" + str(i) + "=[]")#生成K個list分別儲存k個組的資料點    while write:        for i in range(K):            for j in range(len(n_data)):                if i + 1 == n_data[j][0]:#索引從0開始,分組從1開始,將當前組的資料存入對應的list                    exec("center_" + str(i) + ".append(n_data[j][1])")                    n_data.remove(n_data[j])#移除該資料點                    break        if len(n_data) == 0:#若全部寫入對應list後,跳出迴圈            write = False    for i in range(K):#生成k個變數儲存k個數據中心        print("center_" + str(i) + "=")        exec("print(center_" + str(i) + ")")    ex_data = data#資料移除後,重新接收    for i in range(K):#從每組中隨機選擇1個新的資料中心        exec("center_0" + str(i) + "=get_center(center_" + str(i) + ",1)")        exec("center.append(center_0"+str(i)+")")    ex_data=detele_center(ex_data,center,K)#移除資料中心,獲取新的實驗資料    for i in range(K):#除錯用,檢視每個資料中心        print("center_0"+str(i)+"=")        exec("print(center_0"+str(i)+")")    return ex_data

def K_Means(data,K):#K-Means處理流程    center=get_center(data,K)#獲取資料中心    print("初始中心點座標為:\n", center)    ex_data=detele_center(data,center,K)#獲取實驗資料    print("實驗資料為:\n",ex_data)    n=np.shape(ex_data)[0]    flag=True#判斷符    ogroup = 0#用於儲存上一次的分組結果    while flag:        shorest_distance = float("inf")#初始化最短距離為無窮大        group = np.zeros((n, 1))  # 記錄組號,group記錄每一個數據點的組號        distance = 0        idex = 0        print("ex_data=",ex_data)        #print("")        #print("group=", len(group))        for i in range(len(ex_data)):#遍歷實驗資料行            for j in range(K):#遍歷維度                distance=get_distance(ex_data[i],center[j])#計算每個資料點到資料中心的距離                #print("distance=\n",distance)                if distance<shorest_distance:                    shorest_distance=distance                    idex=j+1  #記錄組號            #print("shorest_distance=\n",shorest_distance)            group[i]=idex#寫入group        group=group.astype(np.int)        group=delete_zero(group)        group=np.array(group)        print("ogroup=",ogroup)        if all(ogroup==group):#若上一次儲存結果和本次相同,表示迭代結果不會發生變化,跳出迴圈            flag=False        else:            ogroup=group        print("group=\n",group)        #若繼續迭代        n_data1=list(zip(group,ex_data))#將分組結果和實驗資料進行對應建立(n,2)的list        nlist=list(range(1,K+1))#生成一個1~k的list,1~k的編號        n_data2=list(zip(nlist,center))#將1~k的編號和資料中心對應        n_data=n_data1+n_data2#生成一個每個資料點的值和其分組結果對應的list        ex_data=get_updatecenter(n_data,K)#更新資料中心    return group

#testdata=np.array([[1,2],[7,8],[100,200],[50,70],[8,9],[30,12],[170,14],[189,768],[371,876],[876,476]])group=K_Means(data,3)print('group:\n',group)

優點:(1)實現簡單。(2)執行效率較高。(3)當結果簇是密集的,效果較好。缺點:(1)必須事先給出K值。(2)對孤立點和噪聲較為敏感。

感謝閱讀！！！

多說一句，很多人學Python過程中會遇到各種煩惱問題，沒有人解答容易放棄。小編是一名python開發工程師，這裡有我自己整理了一套最新的python系統學習教程，包括從基礎的python指令碼到web開發、爬蟲、資料分析、資料視覺化、機器學習等。想要這些資料的可以關注小編，並在後臺私信小編：“01”即可領取。