快捷導(dǎo)航

利用python實(shí)現(xiàn)聚類分析K-means算法的詳細(xì)過程

更新時(shí)間：2021年11月18日 14:36:16 作者：橙序員一號(hào)

K-means算法是很典型的基于距離的聚類算法，采用距離作為相似性的評價(jià)指標(biāo)，即認(rèn)為兩個(gè)對象的距離越近，其相似度就越大，下面通過本文給大家介紹利用python實(shí)現(xiàn)聚類分析K-means算法的詳細(xì)過程，感興趣的朋友一起看看吧

K-means算法介紹

K-means算法是很典型的基于距離的聚類算法，采用距離作為相似性的評價(jià)指標(biāo)，即認(rèn)為兩個(gè)對象的距離越近，其相似度就越大。該算法認(rèn)為簇是由距離靠近的對象組成的，因此把得到緊湊且獨(dú)立的簇作為最終目標(biāo)。

算法過程如下：

1）從N個(gè)文檔隨機(jī)選取K個(gè)文檔作為中心點(diǎn)；

2）對剩余的每個(gè)文檔測量其到每個(gè)中心點(diǎn)的距離，并把它歸到最近的質(zhì)心的類；

3）重新計(jì)算已經(jīng)得到的各個(gè)類的中心點(diǎn)；

4）迭代2～3步直至新的質(zhì)心與原質(zhì)心相等或小于指定閾值，算法結(jié)束。

算法優(yōu)缺點(diǎn)：

優(yōu)點(diǎn)：

原理簡單
速度快
對大數(shù)據(jù)集有比較好的伸縮性

缺點(diǎn)：

需要指定聚類數(shù)量K
對異常值敏感
對初始值敏感代碼實(shí)現(xiàn)：

首先我們隨機(jī)生成200個(gè)點(diǎn)，就?。?,2000）之間的，并確定質(zhì)心個(gè)數(shù)，這里就取個(gè)3個(gè)質(zhì)心，也是隨機(jī)生成（可以根據(jù)需求改變）如下：

import random
import matplotlib.pyplot as plt
 
random_x = [random.randint(0,2000) for _ in range(200)]
random_y = [random.randint(0,2000) for _ in range(200)]
random_poinsts = [(x, y) for x, y in zip(random_x, random_y)]
 
def generate_random_point(min_,max_):
    return random.randint(min_,max_),random.randint(min_,max_)
k1,k2,k3 = generate_random_point(-100,100),generate_random_point(-100,100),generate_random_point(-100,100)
 
plt.scatter(k1[0],k1[1],color = 'red',s=100)
plt.scatter(k2[0],k2[1],color = 'blue',s=100)
plt.scatter(k3[0],k3[1],color = 'green',s=100)
plt.scatter(random_x,random_y)

結(jié)果如下：

接著導(dǎo)入numpy，來計(jì)算各個(gè)點(diǎn)與質(zhì)心的距離，并根據(jù)每個(gè)點(diǎn)與質(zhì)心的距離分類，與第一個(gè)點(diǎn)近則分配在列表的第一個(gè)位置，離第二個(gè)近則分配到第二個(gè)位置，以此類推，如下

import numpy as np
def dis(p1,p2):  #這里的p1,p2是一個(gè)列表[number1,number2]  距離計(jì)算
    return np.sqrt((p1[0] - p2[0])**2 + (p1[1]-p2[1])**2)
random_poinsts = [(x, y) for x, y in zip(random_x, random_y)] #將100個(gè)隨機(jī)點(diǎn)塞進(jìn)列表
groups = [[],[],[]]  #100個(gè)點(diǎn)分成三類
for p in random_poinsts: #k1,k2,k3是隨機(jī)生成的三個(gè)點(diǎn)
    distances = [dis(p,k) for k in [k1,k2,k3]]
    min_index = np.argmin(distances)#取距離最近質(zhì)心的下標(biāo)
    groups[min_index].append(p)
groups
 
結(jié)果如下：
[[(1000, 867),
  (1308, 840),
  (1999, 1598),
  (1606, 1289),
  (1324, 1044),
  (780, 923),
  (1915, 788),
  (443, 980),
  (687, 908),
  (1763, 1039),
  (1687, 1372),
  (1932, 1759),
  (1274, 739),
  (939, 1302),
  (790, 1169),
  (1776, 1572),
  (1637, 1042),
....

可以看到，這200個(gè)點(diǎn)根據(jù)與三個(gè)質(zhì)心的距離遠(yuǎn)近不同，已經(jīng)被分成了三類，此時(shí)groups里面有三個(gè)列表，這三個(gè)列表里分別是分配給三個(gè)質(zhì)心的點(diǎn)的位置，接著我們將其可視化，并且加入循環(huán)來迭代以此找到相對最優(yōu)的質(zhì)點(diǎn)，代碼如下：

previous_kernels = [k1,k2,k3]
circle_number = 10
for n in range(circle_number):
    plt.close() #將之前的生成的圖片關(guān)閉
    kernel_colors = ['red','yellow','green']
    new_kernels =[]
    plt.scatter(previous_kernels[0][0],previous_kernels[0][1],color = kernel_colors[0],s=200)
    plt.scatter(previous_kernels[1][0],previous_kernels[1][1],color = kernel_colors[1],s=200)
    plt.scatter(previous_kernels[2][0],previous_kernels[2][1],color = kernel_colors[2],s=200)
 
    groups = [[],[],[]]  #100個(gè)點(diǎn)分成三類
    for p in random_poinsts: #k1,k2,k3是隨機(jī)生成的三個(gè)點(diǎn)
        distances = [dis(p,k) for k in previous_kernels]
        min_index = np.argmin(distances)#取距離最近質(zhì)心的下標(biāo)
        groups[min_index].append(p)
    print('第{}次'.format(n+1))
    for i,g in enumerate(groups):
        g_x = [_x for _x,_y in g]  
        g_y = [_y for _x,_y in g]
        n_k_x,n_k_y = np.mean(g_x),np.mean(g_y)
        new_kernels.append([n_k_x,n_k_y])
        print('三個(gè)點(diǎn)之前的質(zhì)心和現(xiàn)在的質(zhì)心距離：{}'.format(dis(previous_kernels[i],[n_k_x,n_k_y])))
        plt.scatter(g_x,g_y,color = kernel_colors[i])
        plt.scatter(n_k_x,n_k_y,color = kernel_colors[i],alpha= 0.5,s=200)
    previous_kernels = new_kernels
 
結(jié)果如下：
第1次
三個(gè)點(diǎn)之前的質(zhì)心和現(xiàn)在的質(zhì)心距離：344.046783724601
三個(gè)點(diǎn)之前的質(zhì)心和現(xiàn)在的質(zhì)心距離：178.67567512699137
三個(gè)點(diǎn)之前的質(zhì)心和現(xiàn)在的質(zhì)心距離：85.51258602308063
第2次
三個(gè)點(diǎn)之前的質(zhì)心和現(xiàn)在的質(zhì)心距離：223.75162213961798
三個(gè)點(diǎn)之前的質(zhì)心和現(xiàn)在的質(zhì)心距離：41.23571511332308
三個(gè)點(diǎn)之前的質(zhì)心和現(xiàn)在的質(zhì)心距離：132.0752155320645
第3次
三個(gè)點(diǎn)之前的質(zhì)心和現(xiàn)在的質(zhì)心距離：87.82012730359548
三個(gè)點(diǎn)之前的質(zhì)心和現(xiàn)在的質(zhì)心距離：22.289121504444285
三個(gè)點(diǎn)之前的質(zhì)心和現(xiàn)在的質(zhì)心距離：33.55374236991017
第4次
三個(gè)點(diǎn)之前的質(zhì)心和現(xiàn)在的質(zhì)心距離：50.94506045880864
三個(gè)點(diǎn)之前的質(zhì)心和現(xiàn)在的質(zhì)心距離：25.754704854433683
三個(gè)點(diǎn)之前的質(zhì)心和現(xiàn)在的質(zhì)心距離：23.145028187286528
第5次
三個(gè)點(diǎn)之前的質(zhì)心和現(xiàn)在的質(zhì)心距離：66.35519842692533
三個(gè)點(diǎn)之前的質(zhì)心和現(xiàn)在的質(zhì)心距離：31.90944410706013
三個(gè)點(diǎn)之前的質(zhì)心和現(xiàn)在的質(zhì)心距離：36.247409926389686
第6次
三個(gè)點(diǎn)之前的質(zhì)心和現(xiàn)在的質(zhì)心距離：46.17069651194525
三個(gè)點(diǎn)之前的質(zhì)心和現(xiàn)在的質(zhì)心距離：15.076857795406966
三個(gè)點(diǎn)之前的質(zhì)心和現(xiàn)在的質(zhì)心距離：42.59620276776667
第7次
三個(gè)點(diǎn)之前的質(zhì)心和現(xiàn)在的質(zhì)心距離：36.7751709217284
三個(gè)點(diǎn)之前的質(zhì)心和現(xiàn)在的質(zhì)心距離：15.873333735074496
三個(gè)點(diǎn)之前的質(zhì)心和現(xiàn)在的質(zhì)心距離：23.469882661161705
第8次
三個(gè)點(diǎn)之前的質(zhì)心和現(xiàn)在的質(zhì)心距離：0.0
三個(gè)點(diǎn)之前的質(zhì)心和現(xiàn)在的質(zhì)心距離：0.0
三個(gè)點(diǎn)之前的質(zhì)心和現(xiàn)在的質(zhì)心距離：0.0
第9次
三個(gè)點(diǎn)之前的質(zhì)心和現(xiàn)在的質(zhì)心距離：0.0
三個(gè)點(diǎn)之前的質(zhì)心和現(xiàn)在的質(zhì)心距離：0.0
三個(gè)點(diǎn)之前的質(zhì)心和現(xiàn)在的質(zhì)心距離：0.0
第10次
三個(gè)點(diǎn)之前的質(zhì)心和現(xiàn)在的質(zhì)心距離：0.0
三個(gè)點(diǎn)之前的質(zhì)心和現(xiàn)在的質(zhì)心距離：0.0
三個(gè)點(diǎn)之前的質(zhì)心和現(xiàn)在的質(zhì)心距離：0.0

這里設(shè)置了總共迭代10次，可以看到在迭代到第八次的時(shí)候就找到了最優(yōu)的質(zhì)點(diǎn)，如圖所示：