(转) K-Means聚类的Python实践

简介:   本文转自: http://python.jobbole.com/87343/ K-Means聚类的Python实践2017/02/11 · 实践项目 · K-means, 机器学习分享到:1原文出处: 搜不狐    K-Means应该是最简单的聚类算法之一了吧,理论上很简单,就是随即初始化几个中心点,不断的把他们周围的对象聚集起来,然后根据这群对象的重置中心点,不断的迭代,最终找到最合适的几个中心点,就算完成了。

 

 

本文转自: http://python.jobbole.com/87343/

 

K-Means聚类的Python实践

 

K-Means应该是最简单的聚类算法之一了吧,理论上很简单,就是随即初始化几个中心点,不断的把他们周围的对象聚集起来,然后根据这群对象的重置中心点,不断的迭代,最终找到最合适的几个中心点,就算完成了。

 

然后,真正实践的时候才会思考的更加深入一点,比如本文的实践内容就是一个失败的案例(算法是成功的,场景是失败的)。

什么是聚类


简单的说,就是对于一组不知道分类标签的数据,可以通过聚类算法自动的把相似的数据划分到同一个分类中。即聚类与分类的区别主要在于,聚类可以不必知道源数据的标签信息。

K-Means(K均值)


K均值是一种比较简单的聚类算法,下图是来自wiki:

从图中可以看出,K-Means首先在空间中随机选取三个点(彩色的),这些点可以是某个数据点所在的位置,也可以是纯粹的空间随机点。然后类似拉帮结派一样,到自己附近“抓人”。第一轮抓完之后形成了三个稳定的新“帮派”,这时候每一个帮派由于成员发生了变化,大家就重新投票选择新的“核心”,也就是中间点。选好新的核心之后,这个核心就又开始新一轮的拉帮结派。然后不断的循环迭代,直到整个空间稳定时停止。

K-Means算法描述


上面对K-Means的介绍已经比较详细了,现在,如果把K-Means算法总结成算法描述,其实只需要四步骤:

  1. 任意选择k个点,作为初始的聚类中心。
  2. 遍历每个对象,分别对每个对象求他们与k个中心点的距离,把对象划分到与他们最近的中心所代表的类别中去,这一步我们称之为“划分”。
  3. 对于每一个中心点,遍历他们所包含的对象,计算这些对象所有维度的和的中值,获得新的中心点。
  4. 计算当前状态下的损失(用来计算损失的函数叫做Cost Function,即价值函数),如果当前损失比上一次迭代的损失相差大于某一值(如1),则继续执行第2、3步,知道连续两次的损失差为某一设定值为止(即达到最优,通常设为1)。

距离函数


计算距离有很多种方式,我这里使用的是最简单的欧氏距离,其他的几种距离可以参考酷壳的这篇博客

损失函数(Cost Function)

每一次选取好新的中心点,我们就要计算一下当前选好的中心点损失为多少,这个损失代表着偏移量,越大说明当前聚类的效果越差,计算公式称为(Within-Cluster Sum of Squares, WCSS):

其中,$ x_{i} $ 表示某一对象,$c_{k}$表示该对象所属类别的中心点。整个式子的含义就是对各个类别下的对象,求对象与中心点的欧式距离的平方,把所有的平方求和就是$L(C)$。

评价标准


采用聚类的数据,通常没有已知的数据分类标签,所以通常就不能用监督学习中的正确率、精确度、召回度来计算了(如果有分类标签的话,也是可以计算的)。

常用于聚类效果评价的指标为:Davies Bouldin Index,它的表达式可以写为:

其中,$ rho_{i} $和 $ rho_{j} $ 都表示i,j两个分类中的所有对象到中心点的平均距离。而分母中的$c_{i}$和分别表示i,j两个分类的中心点之间的距离。整个表达式的含义就是,聚类效果越好,两个分类间的距离应该越远,分类内部越密集。

Python实践


#### 一、数据准备 — 如之前所写的朴素贝叶斯分类详解一样,我们的第一步依然是进行数据准备,所不同的是,由于我们不再需要对模型进行训练,所以不必拆分原始数据为训练和测试两部分。

数据向量化

这部分是要格外注意的,要根据不同的数据使用不同的度量单位,比如我们现在是对新闻进行聚类,最初我使用的是,每一个单词作为一个向量,单词的频度就是该维度上的值,但是后来发现结果非常差,经过请教前辈,发现对新闻聚类最好不要使用词频,而且要抛出新闻长度对结果的影响。

举个例子:假如一个新闻A包含Google,Baidu两个词各一次,而B分别包含两个单词歌两次,那么实际上他们属于同一种分类的概率应该是一样的,也就是距离为0才对。

另外,即便是不使用词频,也要注意抛弃总长度对结果的影响,比如A(Google,Baidu),而B是(Google,Baidu,Netease),那么A、B的欧式长度分别是根号2和根号3,这也不合理,我们需要正规化操作,让他们的欧氏距离总长度都相等(参看我代码里的normalize函数)。

二、初始化随机点


我们的新闻数据已知属于5个类别,所以我们就初始设定5个随机点,我使用了random.random()函数来随机选择,具体代码在initCenters函数部分。

在初始化过程完成的工作有:

  1. 第一次设定初始聚类中心
  2. 第一次为这些中心点分配对象
  3. 分配对象完成之后进行重新定位中心点
  4. 对定位后的中心点计算损失函数

三、迭代进行K-Means优化


如上面介绍K-Means算法的时候提到的,这部分需要不断的重新划分对象,重新定位中心点和计算损失函数,然后根据损失函数与上一次的对比决定是不是要继续迭代。

这部分代码在start函数内。

四、Cost Function


具体损失函数如何计算的,之前是在costFunction内,但是我发现分配对象到中心点的时候,可以顺便把损失计算出来,为了提升性能,我把costFunction的代码合并到了split函数内。

下面是完整的程序代码:

输出结果:

由于初始点是随机选择的,所以结果并不是很好,这点可以使用k-means++算法改进,以后再写吧。

1、对于运算速度非常慢:


瓶颈在于两个地方,主要就是计算欧氏距离的时候,需要所有对象分别与中心点求差平方,而中心点根据实际使用,发现维度高达2W或3W,2500个文章,相当于进行2500 * 3W次的(基本运算+乘法运算),目前网上有不少库专门做这个事情,但总结起来还是没法根本上解决此问题。

2、对于分类效果较差:


我选择的场景更适合用朴素贝叶斯这种概率分类或者SVM这种间隔分类,因为K-Means的效果对初始的几个点的依赖非常大,如果运气不好选在了边缘或者几个分类的中间,那效果就会奇差。

解决办法:

避免在新闻分类或其他高维数据下使用K-Means,除非能解决初始中心点的选择问题,关于这点,我们后面的高斯混合模型可以部分解决这个问题。

而对于性能问题我目前无解,暂时想不到合适的数据结构来简化计算,唯一能想到的就是用C函数替代欧氏距离和损失函数的计算部分。

如果您有好的解决办法,请联系我QQ:83534146 ,望不吝指导,多谢!

 
相关文章
|
2天前
|
开发框架 数据可视化 Java
探索Python的跨平台性:技术深度与实践
探索Python的跨平台性:技术深度与实践
|
2天前
|
存储 Python
Python中的函数与模块:核心概念与实践
Python中的函数与模块:核心概念与实践
|
2天前
|
存储 程序员 数据安全/隐私保护
Python面向对象编程:核心概念与实践
Python面向对象编程:核心概念与实践
|
2天前
|
测试技术 持续交付 数据处理
Python动态类型深度解析与实践
Python动态类型深度解析与实践
162 1
|
8天前
|
网络协议 网络架构 Python
Python 网络编程基础:套接字(Sockets)入门与实践
【5月更文挑战第18天】Python网络编程中的套接字是程序间通信的基础,分为TCP和UDP。TCP套接字涉及创建服务器套接字、绑定地址和端口、监听、接受连接及数据交换。UDP套接字则无连接状态。示例展示了TCP服务器和客户端如何使用套接字通信。注意选择唯一地址和端口,处理异常以确保健壮性。学习套接字可为构建网络应用打下基础。
26 7
|
9天前
|
缓存 Python
Python中的装饰器应用及实践
Python中的装饰器是一种强大的编程工具,它可以在不更改原函数代码的情况下,对函数进行扩展和修改。本文将介绍装饰器的基本概念,探讨其在Python开发中的实际应用,并结合示例代码进行详细解析。
|
9天前
|
网络协议 数据处理 调度
深入探索Python异步编程:asyncio库的应用与实践
在现代软件开发中,异步编程已成为处理并发和I/O密集型任务的重要策略。本文将带您深入探索Python的asyncio库,解析其背后的设计原理,并通过实例展示如何在实际项目中应用asyncio实现高效的异步编程。我们不仅会探讨asyncio的基本用法,还会分析其性能优势,并探讨其与其他并发模型的比较。此外,文章还将涵盖asyncio在Web开发、网络编程和数据处理等场景中的应用案例,帮助您更好地理解并掌握这一强大的异步编程工具。
|
9天前
|
Web App开发 Ubuntu Linux
Linux无图形界面环境使用Python+Selenium实践
【5月更文挑战第1天】Linux无图形界面环境使用Python+Selenium实践
56 2
|
12天前
|
Python
在Python中快捷引入缺失包的技巧和实践
在Python中快捷引入缺失包的技巧和实践
14 0
|
12天前
|
人工智能 Python
Python中的反对称矩阵:理论、应用与代码实践
Python中的反对称矩阵:理论、应用与代码实践
29 1