K-means聚类算法(附Python实现代码)

这篇具有很好参考价值的文章主要介绍了K-means聚类算法(附Python实现代码)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

本文的代码与数据地址已上传至github:https://github.com/helloWorldchn/MachineLearning

一、K-means算法基本思想

1、基于划分的聚类

划分算法的思想是,将给定待挖掘数据集中的数据对象划分成K组(k≤N,N代表数据集中对象数目),每一组表示一个聚类的簇。并且要满足任何一个数据对象仅可以属于一个聚类,每个聚类中至少具有一个数据对象。
此算法通常要求算法开始之前,给定参数K以决定聚类后的聚类的个数。算法根据参数k建立一个初始的分组,以后算法反复运用迭代重定位技术将数据对象在各个簇中重新分配,进而得到最终的相对满意的聚类结果。簇内部数据对象之间差距尽量小,簇之间数据对象差距尽量大才称得上是一个好的聚类分析算法。K-medoids和K-means算法是划分算法中两个比较经典的算法。其他很多划分算法都是从这两个算法演变改进而来的。

2、K-means简介

1957 年 Lloyd首次在文献中提出 k-均值算法,1967 年 MacQueen 在文献中给出了经典的 k-均值算法,描述 k-均值算法的完整理论并进行了详细的研究。 作为最经典的划分聚类算法,k-均值算法的实现并不复杂,具有较高的可伸缩性,同时 k-均值算法具有良好的可靠性和高效性,是一种广泛应用的聚类算法。

3、K-means算法流程

K-means(K均值)算法接受一个参数K用以决定结果中簇的数目。算法开始时,要在数据集中随机选择K个数据对象用来当做k个簇的初始中心,而将剩下的各个数据对象就根据他们和每个聚类簇心的距离选择簇心最近的簇分配到其中。然后重新计算各个聚类簇中的所有数据对象的平均值,并将得到的结果作为新的簇心;逐步重复上述的过程直至目标函数收敛为止。

下面介绍该算法的具体步骤:

  1. 对于给定的一组数据,随机初始化K个聚类中心(簇中心)
  2. 计算每个数据到簇中心的距离(一般采用欧氏距离),并把该数据归为离它最近的簇。
  3. 根据得到的簇,重新计算簇中心。
  4. 对步骤2、步骤3进行迭代直至簇中心不再改变或者小于指定阈值。
    K-means聚类算法(附Python实现代码)
    K-means算法的流程图

4、K-means伪代码

输入 n 个数据对象集合Xi ;输出 k 个聚类中心 Zj 及K 个聚类数据对象集合 Cj .
Procedure K -means(s , k)
S ={x 1 ,x 2 ,,x n };
m =1;for j =1 to k 初始化聚类中心 Zj ;
do {for i =1 to n
  for j=1 to k
   {D(Xi ,Zj)= Xi -Zj ;if D(Xi ,Zj)=Min{D(Xi ,Zj)}then Xi ∈Cj ;}//归类
   if m=1 then Jc(m)=∑kj=1∑ Xi -Zj
2
  m =m+1;for j =1 to k
  Zj =(∑
n
i=1 (Xi)
j )/n;//重置聚类中心
  }while J c (m)-J c (m -1) >ξ

二、K-means代码实现

本文使用的数据集为UCI数据集,分别使用鸢尾花数据集Iris、葡萄酒数据集Wine、小麦种子数据集seeds进行测试,本文从UCI官网上将这三个数据集下载下来,并放入和python文件同一个文件夹内即可。同时由于程序需要,将数据集的列的位置做出了略微改动。数据集具体信息如下表:

数据集 样本数 属性维度 类别个数
Iris 150 4 3
Wine 178 3 3
Seeds 210 7 3

数据集在我主页资源里有,免积分下载,如果无法下载,可以私信我。

1、Python3代码实现

import time

import pandas as pd
import matplotlib.pyplot as plt
import numpy as np
from numpy import nonzero, array
from sklearn.cluster import KMeans
from sklearn.metrics import f1_score, accuracy_score, normalized_mutual_info_score, rand_score, adjusted_rand_score
from sklearn.preprocessing import LabelEncoder
from sklearn.decomposition import PCA

# 数据保存在.csv文件中
iris = pd.read_csv("dataset/Iris.csv", header=0)  # 鸢尾花数据集 Iris  class=3
wine = pd.read_csv("dataset/wine.csv")  # 葡萄酒数据集 Wine  class=3
seeds = pd.read_csv("dataset/seeds.csv")  # 小麦种子数据集 seeds  class=3
wdbc = pd.read_csv("dataset/wdbc.csv")  # 威斯康星州乳腺癌数据集 Breast Cancer Wisconsin (Diagnostic)  class=2
glass = pd.read_csv("dataset/glass.csv")  # 玻璃辨识数据集 Glass Identification  class=6
df = iris  # 设置要读取的数据集
# print(df)

columns = list(df.columns)  # 获取数据集的第一行,第一行通常为特征名,所以先取出
features = columns[:len(columns) - 1]  # 数据集的特征名(去除了最后一列,因为最后一列存放的是标签,不是数据)
dataset = df[features]  # 预处理之后的数据,去除掉了第一行的数据(因为其为特征名,如果数据第一行不是特征名,可跳过这一步)
attributes = len(df.columns) - 1  # 属性数量(数据集维度)
original_labels = list(df[columns[-1]])  # 原始标签


def initialize_centroids(data, k):
    # 从数据集中随机选择k个点作为初始质心
    centers = data[np.random.choice(data.shape[0], k, replace=False)]
    return centers


def get_clusters(data, centroids):
    # 计算数据点与质心之间的距离,并将数据点分配给最近的质心
    distances = np.linalg.norm(data[:, np.newaxis] - centroids, axis=2)
    cluster_labels = np.argmin(distances, axis=1)
    return cluster_labels


def update_centroids(data, cluster_labels, k):
    # 计算每个簇的新质心,即簇内数据点的均值
    new_centroids = np.array([data[cluster_labels == i].mean(axis=0) for i in range(k)])
    return new_centroids


def k_means(data, k, T, epsilon):
    start = time.time()  # 开始时间,计时
    # 初始化质心
    centroids = initialize_centroids(data, k)
    t = 0
    while t <= T:
        # 分配簇
        cluster_labels = get_clusters(data, centroids)

        # 更新质心
        new_centroids = update_centroids(data, cluster_labels, k)

        # 检查收敛条件
        if np.linalg.norm(new_centroids - centroids) < epsilon:
            break
        centroids = new_centroids
        print("第", t, "次迭代")
        t += 1
    print("用时:{0}".format(time.time() - start))
    return cluster_labels, centroids


# 计算聚类指标
def clustering_indicators(labels_true, labels_pred):
    if type(labels_true[0]) != int:
        labels_true = LabelEncoder().fit_transform(df[columns[len(columns) - 1]])  # 如果数据集的标签为文本类型,把文本标签转换为数字标签
    f_measure = f1_score(labels_true, labels_pred, average='macro')  # F值
    accuracy = accuracy_score(labels_true, labels_pred)  # ACC
    normalized_mutual_information = normalized_mutual_info_score(labels_true, labels_pred)  # NMI
    rand_index = rand_score(labels_true, labels_pred)  # RI
    ARI = adjusted_rand_score(labels_true, labels_pred)
    return f_measure, accuracy, normalized_mutual_information, rand_index, ARI


# 绘制聚类结果散点图
def draw_cluster(dataset, centers, labels):
    center_array = array(centers)
    if attributes > 2:
        dataset = PCA(n_components=2).fit_transform(dataset)  # 如果属性数量大于2,降维
        center_array = PCA(n_components=2).fit_transform(center_array)  # 如果属性数量大于2,降维
    else:
        dataset = array(dataset)
    # 做散点图
    label = array(labels)
    plt.scatter(dataset[:, 0], dataset[:, 1], marker='o', c='black', s=7)  # 原图
    # plt.show()
    colors = np.array(
        ["#FF0000", "#0000FF", "#00FF00", "#FFFF00", "#00FFFF", "#FF00FF", "#800000", "#008000", "#000080", "#808000",
         "#800080", "#008080", "#444444", "#FFD700", "#008080"])
    # 循换打印k个簇,每个簇使用不同的颜色
    for i in range(k):
        plt.scatter(dataset[nonzero(label == i), 0], dataset[nonzero(label == i), 1], c=colors[i], s=7, marker='o')
    # plt.scatter(center_array[:, 0], center_array[:, 1], marker='x', color='m', s=30)  # 聚类中心
    plt.show()

if __name__ == "__main__":
    k = 3  # 聚类簇数
    T = 100  # 最大迭代数
    n = len(dataset)  # 样本数
    epsilon = 1e-5
    # 预测全部数据
    labels, centers = k_means(np.array(dataset), k, T, epsilon)
    # print(labels)
    F_measure, ACC, NMI, RI, ARI = clustering_indicators(original_labels, labels)  # 计算聚类指标
    print("F_measure:", F_measure, "ACC:", ACC, "NMI", NMI, "RI", RI, "ARI", ARI)
    # print(membership)
    # print(centers)
    # print(dataset)
    draw_cluster(dataset, centers, labels=labels)

2、聚类结果分析

本文选择了F值(F-measure,FM)、准确率(Accuracy,ACC)、标准互信息(Normalized Mutual Information,NMI)和兰德指数(Rand Index,RI)作为评估指标,其值域为[0,1],取值越大说明聚类结果越符合预期。

F值结合了精度(Precision)与召回率(Recall)两种指标,它的值为精度与召回率的调和平均,其计算公式见公式:

P r e c i s i o n = T P T P + F P Precision=\frac{TP}{TP+FP} Precision=TP+FPTP

R e c a l l = T P T P + F N Recall=\frac{TP}{TP+FN} Recall=TP+FNTP

F − m e a s u r e = 2 R e c a l l × P r e c i s i o n R e c a l l + P r e c i s i o n F-measure=\frac{2Recall \times Precision}{Recall+Precision} Fmeasure=Recall+Precision2Recall×Precision

ACC是被正确分类的样本数与数据集总样本数的比值,计算公式如下:

A C C = T P + T N T P + T N + F P + F N ACC=\frac{TP+TN}{TP+TN+FP+FN} ACC=TP+TN+FP+FNTP+TN

其中,TP(True Positive)表示将正类预测为正类数的样本个数,TN (True Negative)表示将负类预测为负类数的样本个数,FP(False Positive)表示将负类预测为正类数误报的样本个数,FN(False Negative)表示将正类预测为负类数的样本个数。

NMI用于量化聚类结果和已知类别标签的匹配程度,相比于ACC,NMI的值不会受到族类标签排列的影响。计算公式如下:

N M I = I ( U , V ) H ( U ) H ( V ) NMI=\frac{I\left(U,V\right)}{\sqrt{H\left(U\right)H\left(V\right)}} NMI=H(U)H(V) I(U,V)

其中H(U)代表正确分类的熵,H(V)分别代表通过算法得到的结果的熵。

其具体实现代吗如下:
由于数据集中给定的正确标签可能为文本类型而不是数字标签,所以在计算前先判断数据集的标签是否为数字类型,如果不是,则转化为数字类型

def clustering_indicators(labels_true, labels_pred):
    if type(labels_true[0]) != int:
        labels_true = LabelEncoder().fit_transform(df[columns[len(columns) - 1]])  # 如果数据集的标签为文本类型,把文本标签转换为数字标签
    f_measure = f1_score(labels_true, labels_pred, average='macro')  # F值
    accuracy = accuracy_score(labels_true, labels_pred)  # ACC
    normalized_mutual_information = normalized_mutual_info_score(labels_true, labels_pred)  # NMI
    rand_index = rand_score(labels_true, labels_pred)  # RI
    return f_measure, accuracy, normalized_mutual_information, rand_index


F_measure, ACC, NMI, RI = clustering_indicators(class_labels, label)
print("F_measure:", F_measure, "ACC:", ACC, "NMI", NMI, "RI", RI)

如果需要计算出聚类分析指标,只要将以上代码插入K-means实现代码中即可。

3、聚类结果

  1. 鸢尾花数据集Iris
    K-means聚类算法(附Python实现代码)

    Iris鸢尾花数据集原图
    K-means聚类算法(附Python实现代码)
    Iris鸢尾花数据集K-means聚类效果图
  2. 葡萄酒数据集Wine
    K-means聚类算法(附Python实现代码)

    Wine葡萄酒数据集原图
    K-means聚类算法(附Python实现代码)
    Wine葡萄酒数据集K-means聚类效果图
  3. 小麦种子数据集Seeds
    K-means聚类算法(附Python实现代码)

    Seeds小麦种子数据集原图
    K-means聚类算法(附Python实现代码)
    Seeds小麦种子数据集K-means聚类效果图

4、K-means算法的不足

K-means算法的核心步骤就是通过不断地迭代,更新聚类簇中心,达到簇内距离最小。算法的时间复杂度很低,因此该算法得到了广泛应用,但是该算法存在着许多不足,主要不足如下:文章来源地址https://www.toymoban.com/news/detail-471595.html

  1. K-means聚类的簇数目需要用户指定。K-means算法首先需要用户指定簇的数目K值,K值的确定直接影响聚类的结果,通常情况下,K值需要用户依据自己的经验和对数据集的理解指定,因此指定的数值未必理想,聚类的结果也就无从保证。
  2. K-means算法的初始中心点选取上采用的是随机的方法。K-means算法极为依赖初始中心点的选取:一旦错误地选取了初始中心点,对于后续的聚类过程影响极大,很可能得不到最理想的聚类结果,同时聚类迭代的次数也可能会增加。而随机选取的初始中心点具有很大的不确定性,也直接影响着聚类的效果。
  3. K-means采用欧氏距离进行相似性度量,在非凸形数据集中难以达到良好的聚类效果。

到了这里,关于K-means聚类算法(附Python实现代码)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • (python实现)一篇文章教会你k-means聚类算法(包括最优聚类数目k的确定)

    Kmeans算法中,K值所决定的是在该聚类算法中,所要分配聚类的簇的多少。Kmeans算法对初始值是⽐较敏感的,对于同样的k值,选取的点不同,会影响算法的聚类效果和迭代的次数。本文通过计算原始数据中的:手肘法、轮廓系数、CH值和DB值,四种指标来衡量K-means的最佳聚类数

    2024年02月05日
    浏览(63)
  • 【聚类算法】带你轻松搞懂K-means聚类(含代码以及详细解释)

    聚类是一个将数据集中 在某些方面相似的数据成员 进行分类组织的过程,聚类就是一种发现这种内在结构的技术,聚类技术经常被称为 无监督学习 。 k均值聚类是最著名的划分聚类算法,由于简洁和效率使得他成为所有聚类算法中最广泛使用的。给定一个数据点集合和需要

    2024年02月01日
    浏览(37)
  • K-means++聚类算法(matlab实现)

    K-means++算法:K-means++算法是K-means算法的改进版,其在选择初始质心时采用了一种更加聪明的方法,能够有效地避免局部最优解。具体来说,K-means++算法的初始质心是根据距离数据点最远的原则来选择的,这样可以保证初始质心的分布更加广泛,从而使得算法更容易找到全局最

    2024年02月07日
    浏览(99)
  • K-means聚类算法原理及实现

    1.1概念 聚类分析,也称为分割分析或分类分析,可将样本数据分成一个个组(即簇)。同一簇中的对象是相似的,不同簇中的对象则明显不同。 Statistics and Machine Learning Toolbox™ 提供了几种聚类方法和相似性度量(也称为距离度量)来创建簇。此外,簇计算可以按照不同的计

    2024年03月18日
    浏览(44)
  • Python实现简单k-means聚类

    目录 1.导入原始数据集  2.首次计算中心点 3.进行迭代循环,不断优化样本中心点和聚类结果 4.聚类可视化 通过手动书写k-means聚类算法的逻辑实现聚类(而非使用python内置的sklearn) 不了解k-means聚类算法的话可以先去了解以下这种算法的原理,下面就直接进入正题啦~ 首先我

    2024年02月03日
    浏览(44)
  • K-means聚类算法原理、步骤、评价指标和实现

    1、聚类 聚类与分类不同,聚类分析分通过分析大量含有一定规律但杂乱数据,得到数据间内在的逻辑,将杂乱的数据按照所得的数据规律划分成不同的种类。K-measn、DBSCAN和层次是当前广泛使用的三种聚类方法。以下对三种方法进行分析,选择适合的聚类方法。 方法 K-means

    2024年02月07日
    浏览(57)
  • 计算机视觉:聚类算法(K-Means)实现图像分割

    什么是K-means聚类? K-means聚类是一种无监督学习算法,用于将一组数据划分为K个不同的类别或簇。它基于数据点之间的相似性度量,将数据点分配到最接近的聚类中心。K-means算法的目标是最小化数据点与其所属聚类中心之间的平方距离和。 K-means聚类在图像分割中的应用 在

    2024年02月02日
    浏览(39)
  • python k-means聚类算法 物流分配预测实战(超详细,附源码)

    数据集和地图可以点赞关注收藏后评论区留下QQ邮箱或者私信博主要 聚类是一类机器学习基础算法的总称。 聚类的核心计算过程是将数据对象集合按相似程度划分成多个类,划分得到的每个类称为聚类的簇 聚类不等于分类,其主要区别在于聚类所面对的目标类别是未知的

    2024年02月02日
    浏览(78)
  • 数学建模--K-means聚类的Python实现

    目录 1.算法流程简介 2.1.K-mean算法核心代码 2.2.K-mean算法效果展示 3.1.肘部法算法核心代码  3.2.肘部法算法效果展示   

    2024年02月09日
    浏览(34)
  • Python | 实现 K-means 聚类——多维数据聚类散点图绘制

    客观吐槽:CSDN的富文本编辑器真是超级无敌难用 。首先要吐槽一下CSDN的富文本编辑器,好难用,好难用,好难用,好难用好难用,好难用,好难用,好难用!!!!!!!!!!!!!!!!!!前边的开头文字编辑了三四次,每次都是不小心按了ctrl+z,就完全消失了。

    2024年02月03日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包