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数据表

　　--城市GDPCREATE TABLE CITY_GDP_T(CITY VARCHAR2(100),--城市名POPULATION NUMBER ,--人口AREA NUMBER,--面积GDP_YEAR NUMBER,--年GDPGDP_PER_CAPITA NUMBER ,--人均GDPGDP_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，处处是集合，或许，只有你想不到的。

　　加入"云和恩墨大讲堂"微信群，参与讨论学习

　　搜索盖国强（Eygle）微信号：eyygle，或者扫描下面二维码，备注：云和恩墨大讲堂，即可入群。每周与千人共享免费技术分享，与讲师在线讨论。

　　关注公众号，获得后续精彩分享