`
deepfuture
  • 浏览: 4410222 次
  • 性别: Icon_minigender_1
  • 来自: 湛江
博客专栏
073ec2a9-85b7-3ebf-a3bb-c6361e6c6f64
SQLite源码剖析
浏览量:80115
1591c4b8-62f1-3d3e-9551-25c77465da96
WIN32汇编语言学习应用...
浏览量:70281
F5390db6-59dd-338f-ba18-4e93943ff06a
神奇的perl
浏览量:103553
Dac44363-8a80-3836-99aa-f7b7780fa6e2
lucene等搜索引擎解析...
浏览量:286476
Ec49a563-4109-3c69-9c83-8f6d068ba113
深入lucene3.5源码...
浏览量:15037
9b99bfc2-19c2-3346-9100-7f8879c731ce
VB.NET并行与分布式编...
浏览量:67759
B1db2af3-06b3-35bb-ac08-59ff2d1324b4
silverlight 5...
浏览量:32276
4a56b548-ab3d-35af-a984-e0781d142c23
算法下午茶系列
浏览量:46061
社区版块
存档分类
最新评论

k均值

 
阅读更多

k均值(k-means)是聚类算法的一种,聚类分析是根据在数据中发现的描述对象及其关系的信息,将数据对象分组。其目标是,组内的对象相互之间是相似的,而不同组中的对象是不同的。组内的相似性越大,组间差别越大,聚类就越好。

举个例子,在二维平面上有几百个点,在笛卡儿坐标系中有(x,y)坐标,把它们点到纸上,问题是如何把它们分成不同组,每个组里点彼此之前都比较相近,而离其它组的成员又比较远。下面介绍的k均值就能干这种事。

 

基本k均值

基本k均值思想很简单,首先,选择k个初始质心,其中k是用户指定的参数,即所期望的簇的个数。每个点被指派到最近的质心,而指派到一个质心的点集为一个簇。然后根据指派到簇的点,更新每个簇的质心。重复指派和更新步骤,直到簇不发生变化,或等价的,直到质心不发生变化。

伪代码:

 


1:指派点到最近的质心。为了将点指派到最近的质心,我们需要邻近性度量来量化所考虑的数据的“最近”的概念。判断两项的相似度,在上篇文章里已经提到过,可以选择一个合适的算法。通常,对欧式空间里的点适用欧几里德距离,对文档用余弦相似性

选择k个点作为初始质心。
repeat
  将每个点指派到最近的质心,形成k个簇
  重新计算每个簇的质心
util 质心不发生变化

 

2:质心和目标函数。因为在计算k均值的过程中要迭代计算每个簇的质心,我们用均值来当作一个簇的质心,例如第一个簇有点(1,2) (1,1),(2,1),那么我们就用 ( (1 + 1 + 2) / 3, (2 + 1 + 1) /3 )作为质心(相当于各维数据相加,然后除以这组的点数)。而目标函数是我们用来计算产生n个组的算法效果:当我们产生n个组后,计算每个组的所有点的中心点(各维数据相加,然后除以这组的点数),我们称这个点为质心,然后计算每个组中每个点到这个质心的距离,把这个距离相加得到一个组内的距离之和Sum_1,再把每个组这种距离之后相加,即Sum_1 + Sum_2 + … Sum_n,得到这个总距离和就可以判定这次分组质量的好坏,显然,这个值越小越好。

列下k均值常用的邻近度,质心和目标函数的选择:

  • 邻近度函数:曼哈顿距离。质心:中位数。目标函数:最小化对象到其簇质心的距离和
  • 邻近度函数:平方欧几里德距离。质心:均值。目标函数:最小化对象到其簇质心的距离的平方和
  • 邻近度函数:余弦。质心:均值。最大化对象与其质心的余弦相似度和
  • 邻近度函数:Bregman 散度。质心:均值。目标函数:最小化对象到其簇质心的Bregman散度和

选择适当的初始质心是基本k均值的关键步骤。常见的方法是随机地选取初始质心,但是簇地质量会比较差。一个方法是多次运行,每次适用一组不同的随机初始质心,然后选取具有最小目标函数和的簇集。但是这样也只是取得多次运行中较好的,仍然非常依赖开始时质心的位置。

在我的测试数据中,随机产生了100个点,其中每10点给它们一个范围,例如第一组点的横坐标和纵坐标都在10~20之间随机,第二组点的都在40~50之间随机,这样就人为产生了10个簇点。然后适用基本k均值算法,指定k=10,得到的10个簇。如此运行50次。我们期望的结果是分成10个簇后,每个簇有10个点,和我们想的数据相符。但是即使运行50次,得到的也是非常不均匀的,有的簇点有20~30个,有的簇的点只有2,3个,甚至产生了空簇,这说明本来应该在这个簇的点被划到了其它簇。可见对于初始点的指定还是很重要的。

而k均值的变种---二分k均值则对初始化问题不大敏感。

二分k均值

基本思想是:为了得到k个簇,将所有点的集合分裂成两个簇,从这些簇中选取一个继续分裂,如此下去,直到产生k个簇。

伪代码:

 

初始化簇表,使之包含由所有的点组成的簇。
repeat
   从簇表中取出一个簇。
   {对选定的簇进行多次二分试验}
   for i=1 to 试验次数 do
       使用基本k均值,二分选定的簇。
   endfor
   从二分试验中选择具有最小误差的两个簇。
   将这两个簇添加到簇表中。
until 簇表中包含k个簇

 

比如要分成5个组,第一次分裂产生2个组,然后从这2个组中选一个目标函数产生的误差比较大的,分裂这个组产生2个,这样加上开始那1个就有3个组了,然后再从这3个组里选一个分裂,产生4个组,重复此过程,产生5个组。这算是一中基本求精的思想。二分k均值不太受初始化的困扰,因为它执行了多次二分试验并选取具有最小误差的试验结果,还因为每步只有两个质心。

同样是上面的那组数据,当我使用二分k均值算法时,产生的10个簇正好每个都是10个点,就是和我们预想的簇一样,非常均匀。

优点与缺点

k均值简单并且可以用于各种数据类型,它相当有效,尽管常常多次运行。然后k均值并不适合所有的数据类型。它不能处理非球形簇,不同尺寸和不同密度的簇。对包含离群点(噪声点)的数据进行聚类时,k均值也有问题。

基本k均值和二分k均值的代码,由于比较长就不贴了,通过看上面的伪代码,理解了其思想,代码还是比较容易写出来的。

分享到:
评论

相关推荐

    k均值算法实现,约束种子k均值的python算法实现

    **k均值算法详解** k均值算法(K-Means)是一种常见的无监督学习方法,主要用于数据聚类。在机器学习和数据分析领域,k均值因其简单、快速且易于理解的特点而广受欢迎。该算法的目标是将n个样本点划分到k个类别中,...

    K均值聚类算法

    K均值聚类算法是一种广泛应用的数据挖掘技术,用于无监督学习中的分类问题。它通过将数据集中的对象分配到预定义数量的类别(或“簇”)中,以实现最佳的相似性。在这个过程中,算法的目标是使得同一簇内的对象间...

    模式识别大作业K均值算法matlab平台实现

    在模式识别领域,K均值算法(K-Means)是一种广泛应用的无监督学习方法,主要用于数据聚类。本项目是基于MATLAB平台实现的K均值算法,它旨在将一组未标记的数据集划分到K个预定义的类别中。MATLAB作为强大的科学计算...

    k均值聚类、数据等,学习模式识别的可以参考下

    在模式识别领域,k均值聚类是一种广泛应用的无监督机器学习算法,它主要用于将数据集分割成k个互不重叠的簇。这个算法基于一个简单的目标:最小化簇内的平方误差和,即所有数据点到其所属簇中心的距离平方和。下面...

    均值聚类_k均值聚类_K均值_K._聚类算法_writing6op_

    **K均值聚类算法详解** K均值(K-Means)聚类是一种广泛应用的数据挖掘技术,用于无监督学习中的数据分类。该算法的基本思想是通过迭代将数据集中的样本点分配到预设数量(K)的聚类中,以最小化各聚类内部的平方...

    基于K均值聚类RBF网络程序

    基于K均值聚类RBF(Radial Basis Function)网络程序是机器学习领域的一个重要算法,主要用于模式识别、数据分类和函数逼近等任务。RBF网络是一种前馈神经网络,其设计灵感来源于生物神经系统,通过径向基函数作为...

    k均值聚类算法分类

    《K均值聚类算法在MATLAB中的应用与实践》 K均值聚类算法,是一种广泛应用的数据挖掘技术,主要用于无监督学习中的数据分类。它通过迭代过程将数据集中的样本点分配到预设数量的类别中,使得每个类别的内部紧密度...

    K均值算法(非监督分类)

    K均值算法是一种广泛应用的非监督机器学习方法,主要用于数据的聚类分析。在该算法中,数据点被分配到最近的聚类中心所属的类别,然后聚类中心被更新为该类别内所有数据点的均值。这个过程会迭代进行,直到聚类中心...

    k均值聚类算法的原理与matlab实现

    k均值聚类算法是一种广泛应用的数据分析方法,尤其在无监督学习中占据重要地位。算法的核心思想是将数据集划分为K个簇,使得每个簇内的数据点彼此相似,而不同簇之间的数据点差异较大。这里,相似性通常通过距离度量...

    利用K均值进行图像分割

    本教程将深入探讨如何利用K均值聚类算法进行图像分割,并通过一个名为`kmeans_segment.m`的MATLAB程序实例来展示其实现过程。 K均值是一种非监督学习算法,主要用于数据聚类,其目标是将数据集分成K个类别,使得每...

    MKKM(多核k均值聚类算法)KKM(核k均值聚类算法)

    本文将深入探讨"MKKM(多核k均值聚类算法)"和"KKM(核k均值聚类算法)"这两种先进的聚类技术。 首先,让我们理解核k均值算法(Kernel k-Means,简称KKM)。该算法是k均值算法的一种变体,它通过核函数(如高斯核、...

    K均值算法_K._图像分割_图像分割K均值算法_

    K均值算法是一种广泛应用的数据聚类方法,尤其在图像处理领域中的图像分割任务上表现出色。这个算法的主要目的是将数据集分成K个不同的类别,使得每个数据点尽可能地属于其所属类别的中心,同时与其他类别的中心保持...

    《模式识别》中K均值聚类的实现

    用C++实现模式识别中K均值聚类。算法优点: 1、算法采用平均值初始化聚类中心,这样可以更加接近最后的结果,减少迭代次数。 2、算法采用精度为0.000001,使运行结果更为精确。 3、算法对其它数据适应良好。 4、算法...

    数据挖掘聚类算法--k均值算法

    K均值算法(K-Means)是一种广泛应用的迭代式聚类算法,适用于处理数值型数据。下面将详细阐述K均值算法的核心原理、步骤、优缺点以及其在数据挖掘中的应用。 K均值算法的基本思想是通过迭代过程将数据点分配到最近...

    K均值聚类课程设计_C课程设计K均值聚类_

    K均值聚类(K-Means Clustering)是一种广泛应用的无监督学习方法,主要用于数据的聚类分析。在数据挖掘、图像处理、市场分割等领域都有它的身影。在这个C语言的课程设计中,我们将深入探讨K均值聚类算法的原理、...

    利用鸢尾花数据进行K均值分类

    **K均值聚类算法详解** K均值(K-Means)算法是一种常见的无监督学习方法,用于数据的聚类分析。它旨在将数据集分成K个互不重叠的类别,使得每个数据点尽可能地归属于与其最近的类中心。在鸢尾花数据集中,我们将...

    k均值聚类算法

    k均值聚类算法是一种广泛应用的数据挖掘技术,主要用于无监督学习中的分类问题。它通过迭代过程将数据集分成k个不同的类别,使得每个类别内的数据点彼此相似,而类别间差异较大。在本项目中,该算法实现了97%以上的...

    k均值图像分割

    **k均值图像分割** k均值算法是一种常见的无监督机器学习方法,广泛应用于数据聚类分析。在图像处理领域,k均值被用于图像分割,即把图像划分为多个区域,每个区域内的像素具有相似的特征。这种方法可以帮助揭示...

    C#实现k均值聚类算法(调试通过)

    K均值(K-Means)是广泛应用的一种聚类算法,尤其在大数据分析和机器学习中占据重要地位。本文将详细讨论如何使用C#语言来实现K均值聚类算法,并探讨其原理、步骤以及实际应用。 一、K均值算法原理 K均值算法基于...

    k均值聚类python实现

    k-means(k均值)算法的python代码实现,可以显示聚类效果与聚类的迭代次数,初学者使用更方便。

Global site tag (gtag.js) - Google Analytics