欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

python中k-means和k-means++原理及實(shí)現(xiàn)

 更新時(shí)間:2022年05月11日 11:30:01   作者:雷恩Layne  
本文主要介紹了python中k-means和k-means++原理及實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

前言

k-means算法是無監(jiān)督的聚類算法,實(shí)現(xiàn)起來較為簡(jiǎn)單,k-means++可以理解為k-means的增強(qiáng)版,在初始化中心點(diǎn)的方式上比k-means更友好。

k-means原理

k-means的實(shí)現(xiàn)步驟如下:

  • 從樣本中隨機(jī)選取k個(gè)點(diǎn)作為聚類中心點(diǎn)
  • 對(duì)于任意一個(gè)樣本點(diǎn),求其到k個(gè)聚類中心的距離,然后,將樣本點(diǎn)歸類到距離最小的聚類中心,直到歸類完所有的樣本點(diǎn)(聚成k類)
  • 對(duì)每個(gè)聚類求平均值,然后將k個(gè)均值分別作為各自聚類新的中心點(diǎn)
  • 重復(fù)2、3步,直到中心點(diǎn)位置不在變化或者中心點(diǎn)的位置變化小于閾值

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

  • 原理簡(jiǎn)單,實(shí)現(xiàn)起來比較容易
  • 收斂速度較快,聚類效果較優(yōu)

缺點(diǎn):

  • 初始中心點(diǎn)的選取具有隨機(jī)性,可能會(huì)選取到不好的初始值。

k-means++原理

k-means++是k-means的增強(qiáng)版,它初始選取的聚類中心點(diǎn)盡可能的分散開來,這樣可以有效減少迭代次數(shù),加快運(yùn)算速度,實(shí)現(xiàn)步驟如下:

  • 從樣本中隨機(jī)選取一個(gè)點(diǎn)作為聚類中心
  • 計(jì)算每一個(gè)樣本點(diǎn)到已選擇的聚類中心的距離,用D(X)表示:D(X)越大,其被選取下一個(gè)聚類中心的概率就越大
  • 利用輪盤法的方式選出下一個(gè)聚類中心(D(X)越大,被選取聚類中心的概率就越大)
  • 重復(fù)步驟2,直到選出k個(gè)聚類中心
  • 選出k個(gè)聚類中心后,使用標(biāo)準(zhǔn)的k-means算法聚類

這里不得不說明一點(diǎn),有的文獻(xiàn)中把與已選擇的聚類中心最大距離的點(diǎn)選作下一個(gè)中心點(diǎn),這個(gè)說法是不太準(zhǔn)確的,準(zhǔn)的說是與已選擇的聚類中心最大距離的點(diǎn)被選作下一個(gè)中心點(diǎn)的概率最大,但不一定就是改點(diǎn),因?yàn)榭偸侨∽畲笠膊惶茫ㄓ龅教厥鈹?shù)據(jù),比如有一個(gè)點(diǎn)離某個(gè)聚類所有點(diǎn)都很遠(yuǎn))。

一般初始化部分,始終要給些隨機(jī)。因?yàn)閿?shù)據(jù)是隨機(jī)的。

盡管計(jì)算初始點(diǎn)時(shí)花費(fèi)了額外的時(shí)間,但是在迭代過程中,k-mean 本身能快速收斂,因此算法實(shí)際上降低了計(jì)算時(shí)間。

現(xiàn)在重點(diǎn)是利用輪盤法的方式選出下一個(gè)聚類中心,我們以一個(gè)例子說明K-means++是如何選取初始聚類中心的。

假如數(shù)據(jù)集中有8個(gè)樣本,分布分布以及對(duì)應(yīng)序號(hào)如下圖所示:

在這里插入圖片描述

我們先用 k-means++的步驟1選擇6號(hào)點(diǎn)作為第一個(gè)聚類中心,然后進(jìn)行第二步,計(jì)算每個(gè)樣本點(diǎn)到已選擇的聚類中心的距離D(X),如下所示:

在這里插入圖片描述

  • D(X)是每個(gè)樣本點(diǎn)與所選取的聚類中心的距離(即第一個(gè)聚類中心)
  • P(X)每個(gè)樣本被選為下一個(gè)聚類中心的概率
  • Sum是概率P(x)的累加和,用于輪盤法選擇出第二個(gè)聚類中心。

然后執(zhí)行 k-means++的第三步:利用輪盤法的方式選出下一個(gè)聚類中心,方法是隨機(jī)產(chǎn)生出一個(gè)0~1之間的隨機(jī)數(shù),判斷它屬于哪個(gè)區(qū)間,那么該區(qū)間對(duì)應(yīng)的序號(hào)就是被選擇出來的第二個(gè)聚類中心了

在上圖1號(hào)點(diǎn)區(qū)間為[0,0.2),2號(hào)點(diǎn)的區(qū)間為[0.2, 0.525),4號(hào)點(diǎn)的區(qū)間為[0.65,0.9)

從上表可以直觀的看到,1號(hào),2號(hào),3號(hào),4號(hào)總的概率之和為0.9,這4個(gè)點(diǎn)正好是離第一個(gè)初始聚類中心(即6號(hào)點(diǎn))較遠(yuǎn)的四個(gè)點(diǎn),因此選取的第二個(gè)聚類中心大概率會(huì)落在這4個(gè)點(diǎn)中的一個(gè),其中2號(hào)點(diǎn)被選作為下一個(gè)聚類中心的概率最大。

k-means及k-means++代碼實(shí)現(xiàn)

這里選擇的中心點(diǎn)是樣本的特征(不是索引),這樣做是為了方便計(jì)算,選擇的聚類點(diǎn)(中心點(diǎn)周圍的點(diǎn))是樣本的索引。

k-means實(shí)現(xiàn)

# 定義歐式距離
import numpy as np
def get_distance(x1, x2):
    return np.sqrt(np.sum(np.square(x1-x2)))
import random
# 定義中心初始化函數(shù),中心點(diǎn)選擇的是樣本特征
def center_init(k, X):
    n_samples, n_features = X.shape
    centers = np.zeros((k, n_features))
    selected_centers_index = []
    for i in range(k):
        # 每一次循環(huán)隨機(jī)選擇一個(gè)類別中心,判斷不讓centers重復(fù)
        sel_index = random.choice(list(set(range(n_samples))-set(selected_centers_index)))
        centers[i] = X[sel_index]
        selected_centers_index.append(sel_index)
    return centers
# 判斷一個(gè)樣本點(diǎn)離哪個(gè)中心點(diǎn)近, 返回的是該中心點(diǎn)的索引
## 比如有三個(gè)中心點(diǎn),返回的是0,1,2
def closest_center(sample, centers):
    closest_i = 0
    closest_dist = float('inf')
    for i, c in enumerate(centers):
        # 根據(jù)歐式距離判斷,選擇最小距離的中心點(diǎn)所屬類別
        distance = get_distance(sample, c)
        if distance < closest_dist:
            closest_i = i
            closest_dist = distance
    return closest_i
# 定義構(gòu)建聚類的過程
# 每一個(gè)聚類存的內(nèi)容是樣本的索引,即對(duì)樣本索引進(jìn)行聚類,方便操作
def create_clusters(centers, k, X):
    clusters = [[] for _ in range(k)]
    for sample_i, sample in enumerate(X):
        # 將樣本劃分到最近的類別區(qū)域
        center_i = closest_center(sample, centers)
        # 存放樣本的索引
        clusters[center_i].append(sample_i)
    return clusters
# 根據(jù)上一步聚類結(jié)果計(jì)算新的中心點(diǎn)
def calculate_new_centers(clusters, k, X):
    n_samples, n_features = X.shape
    centers = np.zeros((k, n_features))
    # 以當(dāng)前每個(gè)類樣本的均值為新的中心點(diǎn)
    for i, cluster in enumerate(clusters):  # cluster為分類后每一類的索引
        new_center = np.mean(X[cluster], axis=0) # 按列求平均值
        centers[i] = new_center
    return centers
# 獲取每個(gè)樣本所屬的聚類類別
def get_cluster_labels(clusters, X):
    y_pred = np.zeros(np.shape(X)[0])
    for cluster_i, cluster in enumerate(clusters):
        for sample_i in cluster:
            y_pred[sample_i] = cluster_i
            #print('把樣本{}歸到{}類'.format(sample_i,cluster_i))
    return y_pred
# 根據(jù)上述各流程定義kmeans算法流程
def Mykmeans(X, k, max_iterations,init):
    # 1.初始化中心點(diǎn)
    if init == 'kmeans':
        centers = center_init(k, X)
    else: centers = get_kmeansplus_centers(k, X)
    # 遍歷迭代求解
    for _ in range(max_iterations):
        # 2.根據(jù)當(dāng)前中心點(diǎn)進(jìn)行聚類
        clusters = create_clusters(centers, k, X)
        # 保存當(dāng)前中心點(diǎn)
        pre_centers = centers
        # 3.根據(jù)聚類結(jié)果計(jì)算新的中心點(diǎn)
        new_centers = calculate_new_centers(clusters, k, X)
        # 4.設(shè)定收斂條件為中心點(diǎn)是否發(fā)生變化
        diff = new_centers - pre_centers
        # 說明中心點(diǎn)沒有變化,停止更新
        if diff.sum() == 0:
            break
    # 返回最終的聚類標(biāo)簽
    return get_cluster_labels(clusters, X)
# 測(cè)試執(zhí)行
X = np.array([[0,2],[0,0],[1,0],[5,0],[5,2]])
# 設(shè)定聚類類別為2個(gè),最大迭代次數(shù)為10次
labels = Mykmeans(X, k = 2, max_iterations = 10,init = 'kmeans')
# 打印每個(gè)樣本所屬的類別標(biāo)簽
print("最后分類結(jié)果",labels)
## 輸出為  [1. 1. 1. 0. 0.]
# 使用sklearn驗(yàn)證
from sklearn.cluster import KMeans
X = np.array([[0,2],[0,0],[1,0],[5,0],[5,2]])
kmeans = KMeans(n_clusters=2,init = 'random').fit(X)
# 由于center的隨機(jī)性,結(jié)果可能不一樣
print(kmeans.labels_)

k-means++實(shí)現(xiàn)

## 得到kmean++中心點(diǎn)
def get_kmeansplus_centers(k, X):
    n_samples, n_features = X.shape
    init_one_center_i = np.random.choice(range(n_samples))
    centers = []
    centers.append(X[init_one_center_i])
    dists = [ 0 for _ in range(n_samples)]

    # 執(zhí)行
    for _ in range(k-1):
        total = 0
        for sample_i,sample in enumerate(X):
            # 得到最短距離
            closet_i = closest_center(sample,centers)
            d = get_distance(X[closet_i],sample)
            dists[sample_i] = d
            total += d
        total = total * np.random.random()

        for sample_i,d in enumerate(dists): # 輪盤法選出下一個(gè)聚類中心
            total -= d
            if total > 0:
                continue
            # 選取新的中心點(diǎn)
            centers.append(X[sample_i])
            break
    return centers
X = np.array([[0,2],[0,0],[1,0],[5,0],[5,2]])
# 設(shè)定聚類類別為2個(gè),最大迭代次數(shù)為10次
labels = Mykmeans(X, k = 2, max_iterations = 10,init = 'kmeans++')
print("最后分類結(jié)果",labels)
## 輸出為  [1. 1. 1. 0. 0.]
# 使用sklearn驗(yàn)證
X = np.array([[0,2],[0,0],[1,0],[5,0],[5,2]])
kmeans = KMeans(n_clusters=2,init='k-means++').fit(X)
print(kmeans.labels_)

參考文檔

K-means與K-means++
K-means原理、優(yōu)化及應(yīng)用

到此這篇關(guān)于python中k-means和k-means++原理及實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)python k-means和k-means++ 內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • 發(fā)布你的Python模塊詳解

    發(fā)布你的Python模塊詳解

    這篇文章主要介紹了發(fā)布你的Python模塊詳解的相關(guān)資料,需要的朋友可以參考下
    2016-09-09
  • 對(duì)python For 循環(huán)的三種遍歷方式解析

    對(duì)python For 循環(huán)的三種遍歷方式解析

    今天小編就為大家分享一篇對(duì)python For 循環(huán)的三種遍歷方式解析,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
    2019-02-02
  • Python3 json模塊之編碼解碼方法講解

    Python3 json模塊之編碼解碼方法講解

    這篇文章主要介紹了Python3 json模塊之編碼解碼方法講解,需要的朋友可以參考下
    2021-04-04
  • Linux 發(fā)郵件磁盤空間監(jiān)控(python)

    Linux 發(fā)郵件磁盤空間監(jiān)控(python)

    這篇文章主要介紹了Linux發(fā)郵件磁盤空間監(jiān)控功能,python實(shí)現(xiàn),需要的朋友可以參考下
    2016-04-04
  • python實(shí)現(xiàn)自主查詢實(shí)時(shí)天氣

    python實(shí)現(xiàn)自主查詢實(shí)時(shí)天氣

    這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)自主查詢實(shí)時(shí)天氣,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2018-06-06
  • 淺談python中頻繁的print到底能浪費(fèi)多長(zhǎng)時(shí)間

    淺談python中頻繁的print到底能浪費(fèi)多長(zhǎng)時(shí)間

    今天小編就為大家分享一篇淺談python中頻繁的print到底能浪費(fèi)多長(zhǎng)時(shí)間,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
    2020-02-02
  • Python yield 小結(jié)和實(shí)例

    Python yield 小結(jié)和實(shí)例

    yield的作用就是把一個(gè)函數(shù)變成一個(gè) generator,帶有 yield 的函數(shù)不再是一個(gè)普通函數(shù),Python 解釋器會(huì)將其視為一個(gè) generator(不知道什么是generator要先去理解一下Python的generator的了)
    2014-04-04
  • python文件轉(zhuǎn)為exe文件的方法及用法詳解

    python文件轉(zhuǎn)為exe文件的方法及用法詳解

    py2exe是一個(gè)將python腳本轉(zhuǎn)換成windows上的可獨(dú)立執(zhí)行的可執(zhí)行程序(*.exe)的工具,這樣,你就可以不用裝python而在windows系統(tǒng)上運(yùn)行這個(gè)可執(zhí)行程序。本文重點(diǎn)給大家介紹python文件轉(zhuǎn)為exe文件的方法,感興趣的朋友跟隨小編一起看看吧
    2019-07-07
  • python實(shí)現(xiàn)簡(jiǎn)易淘寶購(gòu)物

    python實(shí)現(xiàn)簡(jiǎn)易淘寶購(gòu)物

    這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)簡(jiǎn)易淘寶購(gòu)物,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2019-11-11
  • 報(bào)錯(cuò)No?module?named?numpy問題的解決辦法

    報(bào)錯(cuò)No?module?named?numpy問題的解決辦法

    之前安裝了Python,后來因?yàn)榫毩?xí)使用Python寫科學(xué)計(jì)算的東西,又安裝了Anaconda,但是安裝Anaconda之后又出現(xiàn)了一個(gè)問題,下面這篇文章主要給大家介紹了關(guān)于報(bào)錯(cuò)No?module?named?numpy問題的解決辦法,需要的朋友可以參考下
    2022-08-08

最新評(píng)論