Thinking in SQL系列之:数据挖掘K均值聚类算法与城市分级

引言:SQL做为一种编程语言,能够满足各类数据处理的需要,关键就在于算法与思维方式。以SQL会友,希望结交更多的数据库、数据分析领域的朋友。

作者简介:牛超

10多年数据库技术积累,长期从事ORACLE数据库管理与开发工作。精通企业级数据库应用设计、SQL、算法实现、异常分析、性能优化。目前就职于日立咨询(中国)有限公司。Mail:10867910@qq.com

SQL做为一种编程语言,能够满足各类数据处理的需要,关键就在于算法与思维方式。个人经常调侃SQL思考问题比大部分流行的开发语言多一个维度,因为SQL主要是二维思考(集合)、区别于一维(数据结构)的思维方式。对于ORACLE,通过以SQL(相对宏观)为主体、PLSQL(微观)为辅助,注入算法(灵魂),贯彻性能优化(章程),数据的价值能够充分有效发挥。

聚类问题,就是给定一个元素集合D,其中每个元素具有n个可观察属性,使用某种算法将D划分成k个子集,要求每个子集内部的元素之间相异度尽可能低,而不同子集的元素相异度尽可能高。其中每个子集叫做一个簇。本文将介绍聚类的经典算法K均值聚类算法,即K-MEANS,是一种观察类学习,通过以元素间的相异度迭代地划分簇并重新定位质心点重新聚类来达成的算法,找了如下的图以便加深理解。

算法本身较容易理解,但为了定量说明,还是先祭出几个数学公式

用来定义两个元素,各自具有n个度量属性。

用来标量X与Y的相异度(欧拉距离公式),本篇采用该公式。

曼哈顿距离,即街区非直线段距离,很容易理解。也可以用来标量元素间相异度。

标量规格化,为了平衡各个属性因取值单位不同对距离的影响而按比例映射到相同的取值区间。通常将各个属性均映射到[0,1]区间。

接着,我们来看看本次要用SQL实现的k-means算法示例:以2016年的GDP统计数据给中国城市分级:

目前这份是经个人简单加工的2016年真实国家统计数据,一共有100个城市的记录,共5个度量(人口、面积、年GDP、人均GDP、单位面积GDP)。

我们总是说不相信眼泪的北上广是一线城市,那么该如何给城市分成四线是个很有趣的问题,看了一下国家统计局的划分标准(此处省略1K字),但做为个人比较关心的是每个城市发达与市民富裕程度,于是简单地拍脑袋定义了如下模型:

X ={人口,人口密度,年GDP,人均GDP,单位面积GDP},共5个维度,权重都是1;

每个度量属性a的标量规格化区间定义为[0,1];

聚合点相异度需要以质心点为基准计算,初始质心点取GDP名次的4等分点,简化为MOD(名次,21)=0;元素相异度直接使用欧拉距离公式,即

准备工作:

1.定义表象性的业务表,即城市GDP数据表

--城市GDP
CREATE TABLE CITY_GDP_T
(
CITY VARCHAR2(100),--城市名
POPULATION NUMBER ,--人口
AREA NUMBER,--面积
GDP_YEAR NUMBER,--年GDP
GDP_PER_CAPITA NUMBER ,--人均GDP
GDP_PER_AREA NUMBER --单位面积GDP
);

2.加载数据后查询如下:

3.先预演一下质心点经过一次聚类后重新被选择的算法程序,其中第一代初始质心点根据GDP的分段城市的元素属性,TA1,再根据TA1的聚类点用算术平均法计算得到第二代质心点,SQL如下:

WITH TA AS --整理度量值
TB AS --规格化,以消除属性值单位不同造成的影响
TA1 AS --第一代质心点选择,根据GDP
TE AS --聚类选择,各元素取相异度最低的质心点

可以在集合TA1后面做一个SELECT看一下第一代的质心点,如下图:

执行SQL后看一下第二代的质心点,发现维值都发生了变化,说明质心点还是不稳定的,需要迭代地寻找下去。

通过上面的预演,脑子也做了预热。找到规律之后,霍然思路全部连通,K-MEANS聚类问题的关键就在于递归地寻找最稳定的质心点集合。为了保持算法的通用性,抽象出了如下8个维度的聚类训练集,同时定义了批次ID与初始质心标识(0,1):

为了能够传入父代质心点集合得到子代集合,需要定义如下对象:

最重要的算法实现,考虑到ORACLE自定义函数本身是可递归的,我们便来实现这么一个质心点选择的递归函数,相异度选用欧拉距离公式,为了防止迭代次数过多影响性能,可以指定参数P_MAX_GENERATIOIN NUMBER,即最大递归子代数,具体脚本如下:

  --计算修正后的质心点 D'
  TD AS--相异度排名
   --判断最大子代限制条件

虽然是PLSQL,可以看到全篇没有用到循环,质心点的计算主体是面向集合的,其中TC是原始点集与质心点的笛卡尔集,投影列DVALUE相异度计算利用欧拉距离公式,推到TD中利用统计函数为每个质心点按相异度排名,TE取排名第一即相异度最小的组合,最后将质心点周围的点集的算术平均值做为新质心集合返回。全程的集合思维,即Thinking in SQL,如何使用?当然是SQL了,请往下看。

首先我们要把业务数据转换加载到训练集中,这是个简单的ETL过程,将城市GDP表数据经过抽取、维值[0,1]规格化转换、分配批次号3后最终加载到目标K-MEAN训练集:

  TB AS --规格化,以消除属性值单位不同造成的影响

接着我们可以用这个批次ID来得到我们需要的稳定质心点,执行SQL很简单:

SELECT *
FROM TABLE( FUN_DM_KMEANS_CENTROID(3)) A  ;

通过计算结果,我们可以看到质心点在第10代(GENERATION)才得以稳定下来,如果想看看第5代长什么样怎么办?简单,如下:

SELECT *
FROM TABLE( FUN_DM_KMEANS_CENTROID(3,5)) A  ;

接下来我们回到问题的初衷,如何把城市分成四线,具体哪些城市是一线,只需要下面这一个SQL,和质心点选择函数中功能大同小异:

是不是和我一样迫不及待地想看结果了,我所关心的城市到底被分到了哪一级,输出结果:

如此便计算出了我心目中的四线城市。对结果不喜的,莫争议,这就是个一个数字游戏,毕竟只是堆叠出来的度量模型没什么权威。简单分析一下,CUSTER_ID值的大小不能说明什么,只是用来给簇编号确定分类的。根据CLUSTER_ID分类,可以看到北上广深以及其他的直辖市都在最繁荣的分类中,苏州、成都能够挤进去说明很有实力。鄂尔多斯领跑二线。。。这个城市也很有趣。而我的家乡烟台只能搭上三线的边,难免有些失落。

至此,SQL版本的K-MEANS聚类算法已经介绍完,个人举的例子可能没有那么贴切。因为对数据挖掘来说,数据量太小,结果的偶然性会比较高。但麻雀虽小,却较为完整地用SQL表述了K-MEANS聚类的思想。实现这么个算法,全篇没有用到一个循环处理,还是那句话,数据处理,SQL为王。Thinking in SQL,处处是集合,或许,只有你想不到的。

原文发布于微信公众号 - 数据和云(OraNews)

原文发表时间:2017-03-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据科学与人工智能

【Python环境】利用 Python、SciKit 和文本分类来实现行为分析

简介 几乎所有人都会购物。从基本的必需品(比如食品)到娱乐产品(比如音乐专辑),我们会购买各种各样的物品。当购物时,我们不仅会寻找在生活中用到的东西,也会在表达...

22310
来自专栏PPV课数据科学社区

只需七步就能掌握Python数据准备

摘要: 本文主要讲述了如何在python中用七步就能完成中数据准备。 上图为CRISP-DM模型中的数据准备   下面七个步骤涵盖了数据准备的概念,个别任务...

2997
来自专栏数说工作室

机器学习/深度学习代码速查:6大工具库 &27种神经网络图览

Kailash Ahirwar,Mate Lab 联合创始人,Github的一位资深作者,也是一位活雷锋,近日在其Github个人主页上发表了一个机器学习/深度...

4465
来自专栏数据魔术师

运筹学教学 | 十分钟快速掌握最大流算法(附C++代码及算例)

—“运筹教科书到底能给你啥?” —“算法和实现离教科书有多远?” —“问题解决能力到底从哪来?” 今天刚起床就接到了BOSS的 提·问·三·连 小编表示 收到直...

3475
来自专栏PPV课数据科学社区

【从零开始学分词】严澜:数据挖掘入门——分词

谷歌4亿英镑收购人工智能公司DeepMind,百度目前正推进“百度大脑”项目,腾讯、阿里等各大巨头也在积极布局深度学习。随着社会化数据大量产生,硬件速度上升、成...

3214
来自专栏大数据挖掘DT机器学习

一个贯穿图像处理与数据挖掘的永恒问题

作者: 左飞 著有《算法之美——隐匿在数据结构背后的原理(C++版)》 原文 http://blog.csdn.net/baimafujinji/articl...

2263
来自专栏about云

使用Spark MLlib给豆瓣用户推荐电影

问题导读: 1.常用的推荐算法有哪些? 2.推荐系统是什么样的流程? 3.从这个推荐系统我们能学到什么? 推荐算法就是利用用户的一些行为,通过一些数学算法,推测...

5237
来自专栏生信技能树

【直播】我的基因组55:简单的PCA分析千人基因组的人群分布

好久不见,我们的直播又开始啦!今天,我们主要讲的是人群分布,先用简单的PCA来分析一下千人基因组的人群分布吧! PCA分析,就是主成分分析,我博客有讲过(点击最...

28911
来自专栏Vamei实验室

统计02:怎样描绘数据

统计最开始的主要任务就是描述数据。正如我们在统计概述中提到的,群体的数据可能包含大量的数字,往往让人读起来头昏脑涨。电影《美丽心灵》中,数学家纳什不自觉地沉浸在...

2117
来自专栏达观数据

技术干货 |“搜你所想”之用户搜索意图识别

人类自诞生以来就伴随着各种信息的生产和获取,如今这个信息爆炸的 DT 时代,人们更是被各种信息所包围。我们知道,人获取信息的方式主要有被动获取和主动获取两种,其...

3016

扫描关注云+社区