数据挖掘笔记十:聚类算法

有个成语叫 物以类聚,人以群分,就比较形象的解释了聚类的现象。聚类属于无监督学习,提供数据时,只需要提供对应算法的分析参数,不需要提供每条数据所属的类别。

聚类的算算法有很多,用的最多的是 K-MeansDBScan 算法,这里也只简单介绍这两种。 其它的聚类算法也有很多,比如: K-medoids近领传播算法Birch等等。

K-means

K-Means 是比较常用的聚类方法之一。原理也很容易理解,K-Means算法必须有一个参数K,代表最终聚出类别的个数。其它参数可根据使用的算法库提供的API进行扩展,比如距离度量方式等,初始点的放置等。

K-Means 的流程如下

  1. 初始化数据,在数据所在的空间中放置K个点,(K个Label)
  2. 计算空间中所有的点分别到这K个点的距离,离每个点最近的那个( Label ),就是那个点的 Label
  3. 得到了K个簇(每个Label都有离自己最近的一群小弟了),每个簇的点,重新计算中心点,做为新的K个点的位置( Label 的新位置)
  4. 重新计算 2-3-2-3,最后结果差不多不变或变化很小时,聚类就稳定了。
阅读更多

数据挖掘笔记九:一些其它的分类算法

分类算法还有很多,但由于水平太菜, SVM神经网络没有办法表述的清,这两种分类算法的数学实现都很高深和精妙,一种算法写个几千页的书都没问题。

支持向量机

支持向量机 Support Vector Machines,多称 SVM,为什么算法的名字都这么奇怪?

先看看下面一张图,驾校考试科目二:曲线行驶

大家都知道考试时车不能压线,所以越往中间开越安全,这个和SVM的概念就很象了。

看下图,普通的分类器在理念上可能是一条线将两种不同的类别分开,而 SVM 则是使用一条可移动的线,线在中间往左移动 b 的距离或向右移动 b 的距离都可以很好的将两组数据分开,而这段可移动的距离称为 margin,支持这根线最高可以移动的点(绿色的部分),叫做 支持向量(Support Vector)

阅读更多

数据挖掘笔记八:贝叶斯

在概率论里面,贝叶斯可是鼎鼎大名,所以贝叶斯是基于概率的另一种分类器。

朴素贝叶斯

如果根据上面的贝叶斯公式,去计算一百条数据,条条数据十个属性,那么按照贝叶斯算法,每条数据的各个概率再联合另外的属性,另外的数据去计算,计算量会很大,如果是十万百万的数据是根本没有可能算完的。

我们知道在贝叶斯里面,如果两个事件相互独立,那么算起来就简单多了, P( A 交 B ) = P( A ) * P( B ) 。

而 Naive Bayesian(中文译朴素贝叶斯,为数不多的翻译的好听的词),实际上就是做了这样一个假设,假设所有数据里的各种属性是独立的,那么就可以运用独立事件的特性。可能结果并没有标准的贝叶斯那么精确,但计算量一下子降低 N 个指数级别!

阅读更多

数据挖掘笔记七:决策树

记得很久以前中学课堂上偷看杂志,就有一大堆“预测”,通常是第一个问题,回答几个选项,选项A跳到第二个问题,选项B跳到第三个问题…一直走下去,最后的答案就可以预测到一个结果,如果把这个题目的设计路线画出来,那么有可能就是决策树。

决策树

当然,那些杂志99%都是一两个小编胡编乱造随手一画,并没有训练数据支持,也没有决策树算法,所以看过那些预测大多是欣然一笑,然后就忘了~。

决策树,Decision Tree,算法如其名,给定训练集数据之后,通过算法对数据进行分析,就可以生成出根上面题目差不多的树了。决策树所需要用到的主要概念主要是信息熵,当然也可用其它信息增益算法来计算。

计算公式倒是简单,但有一点要记住,有些属性是没什么用的,千万不能拿去算信息增益,比如生日,身份证号等。每个人的身份证号都不一样,使用身份证会让信息增益的值会直接得到1,然而并没有什么卵用,相关导致树变的太大,过学习了,会直接导致模型高分低能。

阅读更多

数据挖掘笔记六:KNN分类

kNN,原名k-Nearest Neighbor (k近邻算法)。是最简单易懂的一个算法!原理也很简单,在已知的空间中(我们最常想到的就是二维坐标轴),中的一个点,找到K个最近的邻居,大多数邻居怎么样分类,它也就怎么样分类。

下图中,对Xu,k=5的情况下,找到Xu点上最近的5个邻居,有4个是w1类型,1个是w3类型,那么,XU的类型应该是更接近w1.

KNN

KNN算法是采用测量不同特征值之间的距离进行分类,下面手动造个轮子,自己实现一个KNN算法。

阅读更多

数据挖掘笔记五:相异性计算

在进入算各算法前,最后介绍一下相异性计算,是每种算法都需要用到的基础知识。

相异性计算

很多算法都是根据数据在空间中的位置进行分类与聚类,在你还不能把一条数据在脑海中映射到一个空间中去的时候。可以先看看这个:

相异性矩阵

我们的数据大致情况都是如以下矩阵所述:每行为一条数据,每列为一个属性

阅读更多