《菜鸟搞科研》3:聚类分析——教授教你如何科学地选择备胎

备胎还要选,越多越好啊?!NO,NO,NO,教授告诉你备胎需要品种齐全,数量合理才行。聚类分析(Clustering)可以将备胎自动分组,使得同组的备胎之间特征相似度达到最大,同时不同组之间的备胎特征相似度最小。同时它帮助用户掌握备胎的种类和分布情况,从而做出最优的决策。Yeah!麻麻再也不用帮我去相亲了!

视频地址

http://v.youku.com/v_show/id_XMzA0ODA4ODU4OA==.html?spm=a2h3j.8428770.3416059.1

代码地址

http://7xl8wi.com1.z0.glb.clouddn.com/03-clustering-code.zip

 

03-01

各位网友大家好 我是砖家魏骁勇

03-02

今天我跟大家一起继续搬砖。大家在前面的特征空间看到,把对象的特征向量投射到特征空间以后,相似的对象之间就发生了聚集的现象。就好像我们说的“物以类聚,人以群分”。其实生活中很多情况下我们都需要进行分组,比如: 一家公司想知道他自己的客户主要由什么样人组成,简单的说高富帅有多少,土豪有多少,屌丝有多少,文艺青年有多少

03-03

如果只是小规模的数据,例如几百个客户,我们可以手工来归类

03-04

但是如果我们上千万,上亿的客户时就几乎不可能通过手工来完成。更有甚者,我们需要细分的目标人群可能不只4个,可能还有初级屌丝,中级屌丝,高级屌丝,带有文艺青年气质的屌丝等等。这个归类的规模就不是纯人工可以掌控的了。

03-05

今天我们要介绍一块新的板砖叫聚类分析, 它就可以帮我们完成这个任务。

03-06

我们来看看聚类分析的黑盒子模型。输入是一组对象和指定的归类个数K,输出是K个分组,它是由输入对象划分而来的。需要专门提一下的是,虽然这里我们输入了一个归类数目K,但是实际聚类算法并不能保证能帮你把对象分为你心目中想象的那K个类,聚类算法只能根据输入对象在特征空间中的分布情况来客观地帮你聚集出K个类来,而这K个类的具体意义是什么,需要在后期分析中得到。

03-07

这是一个关于聚类很重要也经常被误解的概念,我们先举一个理想情况下的例子。比如你输入了一组客户数据,和聚类数目4,你希望它帮你分出屌丝,高富帅,土豪,文艺青年4个组来。如果你输入的数据确实完整地涵盖了这4个类别,而且你所使用的特征在客观上的可区分性跟你的想法一致。那么最终的结果就会如你所愿。

03-08

但是,如果你的数据本身就没有完全包含这4个人群,也就是说采样不完全,那么结果可能不如你所想。例如,你的数据里面本身就只有土豪人群,最后分出的4个类可能是,初级土豪,中级土豪,高级土豪,高富帅土豪。总之,聚类是一种客观分组的工具,聚类结果的意义是聚类完成以后人为分析出来的。这种分析可以帮你查看你的采样是否完整,也可以用来发现新的,有意思的族群。

03-09

为了加深大家的理解,我们钻到黑盒子里面去看一下,因为其实聚类算法并没有那么神秘。首先,聚类算法需要其他几个砖块,前面我们已经介绍过。

03-10

让我们以最常用的K-Means为例吧。K-Means算法把输入的对象聚为K个组的思想是这样的

03-11

首先随机选定K个对象作为K个组的代表,叫做初始中心;用我们的示例数据做一下,假设K=4,现在这4个对象被选为初始的中心了,

03-12

然后把剩下未归类的对象都都加入到离它最近的那个代表对象的组中去,这里我们可以采用距离度量来做这件事情。

03-13

经过这个过程,我们的示例数据分组情况就成为这样

03-14

之后,对每个组,我们需要计算出每个组的新中心来,这个中心在几何上就是组内所有点的几何中心,或者说重心,计算方法很简单,其实就是把该组内每一个对象在每一维算一个平均值,回到我们的特征表格就是把求出相应列的平均值,然后用这些平均值构成一个虚拟的中心特征向量来代表整个组。

03-15

大家看到,经过计算,中心发生了一定的偏移,能更好地代表整个组。

03-16

然后我们再重复之前的过程,把剩下的对象加入到离它们最近的中心去。如此往复,理论上会达到一个收敛的状态,此时4个最佳中心被找到,也产生最佳的划分。

03-17

好了,聚类算法就此完成,我们来做一个实际的例子。比如小芳同学有20多个备胎,但是小芳是个很有头脑的菇娘,她知道数量多不一定保险,你需要有各种类型的备胎保持队伍的多样性才能可持续性发展。

03-18

于是聪明的小芳把总结出了几个特征,帅,有钱,说话风趣,会写作业,xx,然后对20个对象打分。

03-19

03-20

最后使用聚类算法把备胎们聚成5个类。她惊奇的发现队伍里面屌丝太多了,需要削减,同时学霸类备胎奇缺,需要继续引进。有了方向,小芳再也不用迷茫了。。。。

03-21

好了,时间到了,今天暂且说这么多,对我们这个系列有兴趣的工友请关注我们的微博 @搬砖搞科研,欢迎大家提出宝贵的意见。另外,为了提高这个系列的观赏性,如果有懂动画和美工的工友请与我们联系。

《菜鸟搞科研》2:度量——教你如何计算自己和高富帅之间的距离

《搬砖搞科研》正式改名为《菜鸟搞科研》。
换汤不换药,我们依然延续咱民工界简单粗暴的风格,还是熟悉的配方,还是熟悉的味道。
今天要给大家带来的可以说是计算机科学最核心的一部分,什么?你不信,这么快就迎来了最核心的内容。不但如此,通过这期的学习,你很快就能算出你和高富帅之间的距离,也能简单知晓谷歌和百度视图的基本原理。是不是有点小激动,那么这一期你一定不能错过.

视频地址

http://v.youku.com/v_show/id_XMjc0MDkwNTM1Ng==.html?spm=a2h0k.8191407.0.0&from=s1.8-1-1.2

代码地址

http://7xl8wi.com1.z0.glb.clouddn.com/02-metrics-code.rar

 

各位网友大家好,我是砖家魏骁勇,砖是砖头的砖!

上次我们介绍了特征向量和特征空间,我们看到当我们把对象都投射到特征空间以后,很多属性都一目了然。

那我们今天继续搬砖,在上次特征空间的基础上,我们再加一块新的砖,叫做“度量”。

在特征空间里面,我们发现离得近的对象之间总是比离得远的对象更加相似一些。这个发现的过程是我们人类与生俱来的一种能力,它非常地快,快到连我们都不知道具体的计算过程是什么样子的。那对于计算机来说,是怎么判断这种相似或者不相似度的呢?为了方便计算,计算机需要用一个数值来标识这种相似或者不相似度。那么获取这个值的过程就叫做度量。英文叫做Metrics或Measures。

我们再来看看度量黑盒吧,这个黑盒的输入是两个特征向量,输出是一个值,这个值可能是距离,也可能是相似度,这是两个相对的概念。

我们先讲距离的度量,因为它是我们在二维空间中,也就是在一个平面上能够得到的最直观的印象。

在这一张坐标系当中,我们如果要计算高富帅和屌丝之间的距离,我们可以采用平面几何里面的方法,也就是我们可以计算这个三角形的长边的长,那么首先我们需要知道另外两条直角边的长度是多少。

为了得到这两条直角边的长度,我们需要回到特征表格中来寻找对象的坐标,这个时候我们就会发现这两条直角边的长度对应的是两个对象在相应维度上坐标差异的绝对值。

好了现在我们回到特征空间里面,根据勾股定理我们现在可以很容易地计算出三角形长边的长,它也就是高富帅和屌丝之间的差距。如果你感兴趣的话,你也可以把自己的数据投到这个空间里面,你就知道自己离高富帅到底有多远了。那么新的问题也来了,因为以上例子我们都是在二维空间当中做的,那么当特征向量是多维的时候该怎么办呢?

其实计算的方法差不多,假设我们现在多了一维,也就是特征表格里面多了一列,那么我们只需要如法炮制,把每一列的差异计算出来,求平方,然后开根就可以了。

这样做的几何意义非常直观,在3维空间里面,它计算的其实是立方体对角线的长度,我们把它泛化到多维空间里面,这样得到的距离就叫做欧几里德距离。

距离度量的是不相似度,相对的概念就是相似度。一种常用的方法叫做余弦相似度,也就是cosine similarity。

这里我们先要回到特征空间里面看一下每个对象的特征向量,虽然一直以来我们使用了向量这个术语,但实际我们在传递的是一个点的概念,它在每个维度上都具有坐标。我们高中学过,一个向量应该是具有方向和长度的东西,那么我们这里可以简单地从坐标轴原点到相应的特征点画一个箭头,它就变成一个向量了。这就是当前对象的特征向量。对于初级民工来说,暂时不用特别区分特征到底是一个点还是一个向量,现在大家可以看到这个向量的指向其实表明了一种趋向,当它指向高富帅的时候,那么对象的特征就更趋向高富帅,当它指向土豪的时候,当前对象更像土豪。所以,对于两个对象的特征向量,我们可以用它们的指向差异来衡量它们的相似度。最直观的方式其实就是看它们之间的夹角大小,越小越相似。为了衡量的方便,我们通常计算夹角的余弦值。

在计算余弦相似度的时候,我们可以利用向量分析的优势来避免使用复杂的平面几何方法。这里我们就先直接给出公式,有兴趣的网友可以自行推导一下它跟平面几何方法之间的关系。公式的分子部分其实就是两个向量的内积,也就是在它们相应维度上的值相乘然后相加,分母部分其实是两个向量的长度,也就是一个向量从原点到顶点的欧几里德距离。

好了,到这里关于度量我们就介绍完了。恭喜大家,你已经掌握了计算机科学里面最核心的问题。听起来有点不可思议,但其实大部分计算机科学的问题到最后都是在衡量对象之间的相似或者不相似度。计算机科学家的任务就是要根据不同的情况来选择不同的度量,或者对已有的度量进行改进来适应新的情况。如果没有特殊的要求,今天我们介绍的两个度量就完全够用了。

现在我们就来检验一下,利用我们已经学到的知识来做一个简单的图像检索引擎,Google和百度都有类似的功能,只要给定一副图像作为查询的条件,系统会返回一系列跟这个查询条件相似的图片作为结果。

为了演示的目的,这个系统非常的简单。首先我们提取所有待查图像的颜色矩特征,然后当用户给定一个查询条件的时候,也就是一幅新的图片,我们再提取它的颜色矩特征,然后用这个特征跟我们数据库中所有的图像特征进行度量,最后根据相似度或者距离来排序,把相应的结果展示出来就可以了。

好了,由于时间的关系,我们先介绍这么多。相应的代码和图片可以从我们的公众号下载,当然也欢迎大家提出宝贵的意见,我们下次再见。

《菜鸟搞科研》1:特征提取——计算机怎么记录你和高富帅

作为一名搬砖界资深的民工,我经常被要求在各种场合介绍搬砖的经验或者心得。但在这些高大上的场合,动辄就会被要求讲够45分钟,这对于一个普通话非常不标准不顺溜的民工来说实在很有难度。但是我又迫切地想跟各位民工兄弟们交流,非常珍惜每一次发言的机会,所以就有了这个《搬砖搞科研》的系列。其中记录了当年我从一名初级民工,经历了被各种砖头虐后,终于了解了砖头的使用方法的故事。本系列的推出,就是希望各位新入行的兄弟姐妹工友们,不要再重蹈覆辙。本系列的宗旨就是发扬我们民工界简单粗暴的风格。

视频地址

http://v.youku.com/v_show/id_XMjc0MTg4NzY2NA==.html?spm=a2h0k.8191407.0.0&from=s1.8-1-1.2

代码地址

http://7xl8wi.com1.z0.glb.clouddn.com/feature.rar

cmd-markdown-logo

各位网友大家好,我是砖家魏骁勇,砖是砖头的砖!

cmd-markdown-logo

我在工地上用过很多的砖,PCA,LDA,SVM,Random Walk, Deep Learning等等等等。记得当初我第一次上工,老板一提到这些高大上的名字,我居然一个都没有听说过,我羞愧过,我堕落过,我想我搬了这么多年的砖居然还如此浅薄,我对不起父母。我看书,查资料,推公式,希望把这些砖里的每一颗沙子都了解得清清楚楚。我想很多工友都跟我有过类似的经历。

cmd-markdown-logo

然而,我今天要说的是:你可能在浪费时间。明白砖头的细节固然是件高大上的事情。但是,我相信大部分的工友只是砖头的使用者而不是做砖头的人。学习一种砖头最好的方法就是明白它的大体功能,然后去用它。如果你过早地陷入砖头的构成和细节中,很容易就会迷失方向和丧失信心。

cmd-markdown-logo

举个例子,老板今天让你给了一块砖头让你去修理下隔壁的二胖子。你拿到砖头后认真地开始研究起来,你查资料发现砖是由粘土成型后经过高温烧制而成,烧制前的粘土还要晾晒2个多月,烧制时间为10天,颜色成黄色,冷却后呈红色,粘土砖烧制成之后要在窑内冷却保持缓慢的气氛,最后冷却完全后出炉。看到这里你信心百倍,觉得自己是个有文化的民工。然后跟老板炫耀说他的砖是黑色,肯定是烧制过程中缺氧导致。老板一看砖头给你半个月了隔壁的二胖子还生龙活虎的,气就不打一处来,一下把砖拍你脑袋上就开骂:缺氧?我看你是缺脑子!你这头猪!

cmd-markdown-logo

这就是过早陷入细节迷失方向的例子。所以,我们这个系列要贯彻的第一个宗旨就是黑盒子,Blackbox, 黑盒子就是一个具有某种功能的装置,内部细节对用户进行了屏蔽,作为一名初级民工,我们只需要知道它输入什么,提供什么输出就可以了。比如,前面例子中的老板就是一个典型的黑盒子用户,他知道只要对一块砖头输入大于9.81牛顿的力,就可以把对方拍成个傻子,他不用关心一块砖的烧制过程和成色品质。不管黑砖红砖,能拍到二胖子就是好砖!

cmd-markdown-logo

好了,我们今天就开始介绍第一块砖,它是一种用来做地基的砖,以后我们用到的砖大都建立在它的基础之上,所以最先介绍它。它叫做特征提取,Feature Extraction。

cmd-markdown-logo

我们先来套用一下黑盒子。特征提取的输入是一个你正在研究的对象,比如一串文字,一副图像等等,它的输出则通常是一串数字。这串数字能代表输入对象的某些属性或者特质。对同一个对象,不同的特征提取模块,得到的数字是不同的。

cmd-markdown-logo

我们来举个例子,比如输入是包含一张人脸的图像,现在我们经过了一个肤色提取模块,得到一个一串数字,为了简化,我们只写一个数字,比如:2,为什么是2呢,可能肤色提取模块按颜色深浅来编号,比如白色为1,黄色为2, 棕色为3,黑色为4, 不知道什么色为5等等。这样就表达了每张人脸图像肤色深浅的一种特质。这样做有什么好处呢,那就是量化。量化以后计算机就可以很容易处理,而不用人来进行判断。

cmd-markdown-logo

当数据的规模变得非常大的时候,这种优势就越发明显。比如现在我们有很多个城市的人脸图像,我们就可以很容易分析出每个城市的人肤色深浅的比例,从而来决定我们到哪个城市去推销美白产品比较好。比如在成都美白产品就不如其他城市好卖,据说眼霜的销量不错。

cmd-markdown-logo

好了,总之特征提取就是把一个被研究对象的特质量化下来方便计算机处理。前面说过,但特征提取可以有很多的方法,并不一定借用计算机程序。比如银行对客户的收入进行分级,0-10,越大存款越多。

cmd-markdown-logo

HR面试以后,对被面试者的思维方式进行分级,0-10,越大越有想法。不管自动的,人工的方法都可以叫做特征提取。

cmd-markdown-logo

我们再把特征提取的概念进一步扩展。假设我们有多个特征提取模块同时作用于同一对象。那么我们就可以得到像这样的一张表格。表格的每一行就是一个对象的所有特征值,我们可以把这些特征值串起来,这串数字就反应了一个对象的综合特征,我们把它叫特征向量, Feature Vector。

cmd-markdown-logo

为了更好地理解Feature Vector,我们把这串数字当成一个坐标值绘制出来,大家就可以直观的看到待研究对象的分布情况了。我们现在绘制的这个图,其实是一个空间的表示,我们先不引入那些复杂的空间概念。你只需要记住这是一个直观表达了各个对象特征的空间,叫做特征空间,Feature Space.

cmd-markdown-logo

到此为止,我们可以把特征提取的概念进一步泛化一下,有了一个更大的黑盒子,暂且叫特征向量构造黑盒子好了。你可以想象这个黑盒子里面装着我们开始讲过的无数个特征提取小盒子。一个对象经过大盒子就输出了一个特征向量,多个对象的特征向量放在一起就组成了,其实应该叫张成,好了,懒得解释这个名字,算我没说,多个向量组成了特征空间。

cmd-markdown-logo

好了,时间到了,今天暂且说这么多,对我们这个系列有兴趣的工友请关注我们的微博 @搬砖搞科研,欢迎大家提出宝贵的意见。另外,为了提高这个系列的观赏性,如果有懂动画和美工的工友请与我们联系。