【数据挖掘】十大经典数据挖掘算法R语言实践

来自 http://www.wangluqing.com

陆勤

十大经典数据挖掘算法是那些？

民间流传，学习和应用数据挖掘算法，就从这十大经典数据挖掘算法入手，若是把这top 10 算法吃透了，数据挖掘也就有了根基了。我甚是赞同此种说法，并且经典的东西，美好的东西，需要优先学习、研究和实践。

数据挖掘十大经典算法可以分为以下情况。

1 与分类相关的算法：C4.5, CART, 朴素贝叶斯， K近邻， 支持向量， 最大期望, AdaBoost

2 与聚类相关的算法：K均值

3 与关联规则相关的算法：Apriori

4与搜索引擎相关的算法：PageRank

关于这些算法的原理和思想，每本数据挖掘方面的书籍都会有介绍，推荐两本数据挖掘经典书籍《数据挖掘导论》 和《数据挖掘：概念与技术》。

本文介绍C4.5这个分类算法如何在R语言中使用。这些算法能够用R语言方便的用起来，这要得益于包含这些算法R包和感谢设计与实现这些算法的R贡献者们。

做数据挖掘，需要数据，我们用iris数据集，简单，典型的分类数据集，便于我么解释。

iris数据集

help(iris)

head(iris)

C4.5算法的R语言实践

C5.0算法是C4.5算法的延续和升级，SPSS Modeler建模选项卡中也提供这种算法。在此，我们用R语言中的C50包所提供的C5.0函数实现C5.0算法。

第一步：加载相应包

library(C50)

## Warning: package ‘C50′ was built under R version 3.1.3

library(printr)

温馨提示：若是没有安装上述包，请在加载前，先安装这些包。

第二步：把iris数据集分为训练集和测试集，按着2:1划分，即训练集100个，测试集50个

train.indeces <- sample(1:nrow(iris), 100)

iris.train <- iris[train.indeces, ]

iris.test <- iris[-train.indeces, ]

第三步：构建C5.0算法模型

model.C5.0 <- C5.0(Species ~ ., data = iris.train)

第四步：交叉验证，使用测试数据集测试模型

results.C5.0 <- predict(object = model.C5.0, newdata = iris.test, type = “class”)

第五步：生成混淆矩阵

table(results.C5.0, iris.test$Species)

C4.5 算法的原理

C4.5算法是数据挖掘算法中的一种分类决策树算法,其核心算法是ID3 算法. C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：

1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；

2) 在树构造过程中进行剪枝；

3) 能够完成对连续属性的离散化处理；

4) 能够对不完整数据进行处理。

C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。

 

---

 

本文介绍支持向量机算法在R语言中如何使用。

数据集，采用R语言内置的iris数据集。

查看数据集前六个观测

head(iris)

第一步：加载SVM算法的R包e1071

library(e1071)

## Warning: package ‘e1071′ was built under R version 3.1.3

library(printr)

第二步：把iris按着2:1的比例分为训练集和测试集

index <- sample(1:nrow(iris), 100)

iris.train <- iris[index, ]

iris.test <- iris[-index, ]

第三步：在训练集上用SVM构建模型

model.SVM <- svm(Species ~ ., data=iris.train)

第四步：在测试集上对模型做测试

results.SVM <- predict(object=model.SVM, newdata=iris.test, type=”class”)

第五步：生成混淆矩阵，理解测试结果

table(results.SVM, iris.test$Species)

SVM原理

支持向量机，英文为Support Vector Machine，简称SV机（论文中一般简称SVM）。它是一种监督式学习的方法，它广泛的应用于统计分类以及回归分析中。

SVM 的主要思想可以概括为两点：

(1) 它是针对线性可分情况进行分析，对于线性不可分的情况，通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使 其线性可分，从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能；

(2) 它基于结构风险最小化理论之上在特征空间中建构最优分割超平面，使得学习器得到全局最优化,并且在整个样本空间的期望风险以某个概率满足一定上界。 在学习这种方法时，首先要弄清楚这种方法考虑问题的特点，这就要从线性可分的最简单情况讨论起，在没有弄懂其原理之前，不要急于学习线性不可分等较复杂的情况，支持向量机。在设计时，需要用到条件极值问题的求解，因此需用拉格朗日乘子理论，但对多数人来说，以前学到的或常用的是约束条件为等式表示的方式，但在此要用到以不等式作为必须满足的条件，此时只要了解拉格朗日理论的有关结论就行。

---

 

 

本文中介绍朴素贝叶斯算法在R语言中如何使用。

数据集，采用R语言内置的iris数据集。

#查看数据集前六个观测
head(iris)

Sepal.Length	Sepal.Width	Petal.Length	Petal.Width	Species
5.1	3.5	1.4	0.2	setosa
4.9	3.0	1.4	0.2	setosa
4.7	3.2	1.3	0.2	setosa
4.6	3.1	1.5	0.2	setosa
5.0	3.6	1.4	0.2	setosa
5.4	3.9	1.7	0.4	setosa

朴素贝叶斯算法R代码

第一步：加载包e1071

library(e1071)
library(printr)

 

第二步：iris数据集分为训练集和测试集

index <-sample(1:nrow(iris), 100)
iris.train <-iris[index, ]
iris.test <-iris[-index, ]

 

第三步：利用朴素贝叶斯算法构建模型

model.NaiveBayes <-naiveBayes(x =subset(iris.train,select=-Species), y= iris.train$Species)

 

第四步：用模型对测试集做测试

results.NaiveBayes <-predict(object = model.NaiveBayes, newdata =iris.test, type=”class”)

第五步：混淆矩阵

table(results.NaiveBayes, iris.test$Species)

results.NaiveBayes/	setosa	versicolor	virginica
setosa	18	0	0
versicolor	0	15	1
virginica	0	0	16

朴素贝叶斯算法思想

贝叶斯分类的基础是概率推理，就是在各种条件的存在不确定，仅知其出现概率的情况下，如何完成推理和决策任务。概率推理是与确定性推理相对应的。而朴素贝叶斯分类器是基于独立假设的，即假设样本每个特征与其他特征都不相关。

贝叶斯分类器特点

1、需要知道先验概率，先验概率是计算后验概率的基础。在传统的概率理论中，先验概率可以由大量的重复实验所获得的各类样本出现的频率来近似获得，其基础是“大数定律”，这一思想称为“频率主义”。而在称为“贝叶斯主义”的数理统计学派中，他们认为时间是单向的，许多事件的发生不具有可重复性，因此先验概率只能根据对置信度的主观判定来给出，也可以说由“信仰”来确定。

2、按照获得的信息对先验概率进行修正在没有获得任何信息的时候，如果要进行分类判别，只能依据各类存在的先验概率，将样本划分到先验概率大的一类中。而在获得了更多关于样本特征的信息后，可以依照贝叶斯公式对先验概率进行修正，得到后验概率，提高分类决策的准确性和置信度。

3、分类决策存在错误率由于贝叶斯分类是在样本取得某特征值时对它属于各类的概率进行推测，并无法获得样本真实的类别归属情况，所以分类决策一定存在错误率，即使错误率很低，分类错误的情况也可能发生。

 

---

本文介绍K近邻算法在R语言中如何使用。

数据集，采用R语言内置的iris数据集。

#查看数据集前六个观测
head(iris)

Sepal.Length	Sepal.Width	Petal.Length	Petal.Width	Species
5.1	3.5	1.4	0.2	setosa
4.9	3.0	1.4	0.2	setosa
4.7	3.2	1.3	0.2	setosa
4.6	3.1	1.5	0.2	setosa
5.0	3.6	1.4	0.2	setosa
5.4	3.9	1.7	0.4	setosa

 

K近邻算法R语言实践

第一步：数据集分为训练集和测试集

index <-sample(1:nrow(iris), 100)
iris.train <-iris[index, ]
iris.test <-iris[-index, ]

第二步：加载能够做k近邻的class包

library(class)

## Warning: package ‘class’was built under R version 3.1.3

第三步：利用kNN算法对测试集进行分类

result.KNN <-knn(train=subset(iris.train,select=-Species), test=subset(iris.test,select=-Species), cl=iris.train$Species)

第四步：生成结果集的混淆矩阵

table(result.KNN, iris.test$Species)

result.KNN/	setosa	versicolor	virginica
setosa	21	0	0
versicolor	0	11	1
virginica	0	1	16

kNN算法原理

1、K最近邻(k-NearestNeighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。

2、KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。

3、KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。

---

本文介绍CART（分类决策回归树）算法在R语言中如何使用。

数据集

采用R语言内置的iris数据集。

#查看数据集前六个观测
head(iris)

Sepal.Length	Sepal.Width	Petal.Length	Petal.Width	Species
5.1	3.5	1.4	0.2	setosa
4.9	3.0	1.4	0.2	setosa
4.7	3.2	1.3	0.2	setosa
4.6	3.1	1.5	0.2	setosa
5.0	3.6	1.4	0.2	setosa
5.4	3.9	1.7	0.4	setosa

CART算法R语言实践

第一步：数据集划分训练集和测试，比例是2:1

set.seed(1234)
index <-sample(1:nrow(iris),100)
iris.train <-iris[index,]
iris.test <-iris[-index,]

第二步：加载包含CART算法的R包

library(rpart)

第三步：构建CART模型

model.CART <-rpart(Species~.,data=iris.train)

第四步：模型应用到测试集

results.CART <-predict(model.CART,newdata=iris.test, type=”class”)

第五步：生成混淆矩阵

table(results.CART, iris.test$Species)

results.CART/	setosa	versicolor	virginica
setosa	12	0	0
versicolor	0	21	3
virginica	0	0	14

CART算法原理

1 分类回归树(CART,ClassificationAnd Regression Tree)也属于一种决策树，分类回归树是一棵二叉树，且每个非叶子节点都有两个孩子。

2 决策树生长的核心是确定决策树的分枝准则。

1）如何从众多的属性变量中选择一个当前的最佳分支变量；也就是选择能使异质性下降最快的变量。异质性的度量：GINI、TWOING、least squared deviation。前两种主要针对分类型变量，LSD针对连续性变量。

2）如何从分支变量的众多取值中找到一个当前的最佳分割点（分割阈值）。 A、数值型变量——对记录的值从小到大排序，计算每个值作为临界点产生的子节点的异质性统计量。能够使异质性减小程度最大的临界值便是最佳的划分点。 B、分类型变量——列出划分为两个子集的所有可能组合，计算每种组合下生成子节点的异质性。同样，找到使异质性减小程度最大的组合作为最佳划分点。

3 在决策树的每一个节点上我们可以按任一个属性的任一个值进行划分。按哪种划分最好呢？有3个标准可以用来衡量划分的好坏：GINI指数、双化指数、有序双化指数。

---

本文介绍Adboost算法在R语言中如何使用。

数据集

采用R语言内置的iris数据集。

#查看数据集前六个观测
head(iris)

Adboost算法R语言实践

第一步：数据集划分训练集和测试集，比例2:1

index <-sample(1:nrow(iris), 100)
iris.train <-iris[index, ]
iris.test <-iris[-index, ]

第二步：加载实现Adboost算法的R包

library(adabag)

## Loading required package:rpart
## Loading required package: mlbench
## Loading required package: caret
## Loading required package: lattice
## Loading required package: ggplot2

第三步：构建Adboos算法模型

model.Adboost <-boosting(Species~., data=iris.train)

第四步：模型应用于测试集

results.Adboost <-predict(model.Adboost,newdata=iris.test, type=”class”)

第五步：查看混淆矩阵

results.Adboost$confusion

Adboost算法原理

1 AdaBoost，是英文”AdaptiveBoosting”（自适应增强）的缩写，是一种机器学习方法，由Yoav Freund和Robert Schapire提出。

2 AdaBoost方法的自适应在于：前一个分类器分错的样本会被用来训练下一个分类器。AdaBoost方法对于噪声数据和异常数据很敏感。但在一些问题中，AdaBoost方法相对于大多数其它学习算法而言，不会很容易出现过拟合现象。

3 AdaBoost方法中使用的分类器可能很弱（比如出现很大错误率），但只要它的分类效果比随机好一点（比如两类问题分类错误率略小于0.5），就能够改善最终得到的模型。而错误率高于随机分类器的弱分类器也是有用的，因为在最终得到的多个分类器的线性组合中，可以给它们赋予负系数，同样也能提升分类效果。

4 AdaBoost方法是一种迭代算法，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率。每一个训练样本都被赋予一个权重，表明它被某个分类器选入训练集的概率。

---

本文介绍K-means算法在R语言中如何使用。

数据集

采用R语言内置的iris数据集。

#查看数据集前六个观测
head(iris)

K-means算法R语言实践

第一步：加载R包

library(stats)#该包属于默认包，会自动加载

第二步：构建K-means聚类模型

model.Kmeans <-kmeans(x =subset(iris, select =-Species), centers=3)

第三步：生成混淆矩阵

table(model.Kmeans$cluster, iris$Species)

K-means算法原理

算法描述

输入：簇的数目k；包含n个对象的数据集D。

输出：k个簇的集合。

方法：

从D中任意选择k个对象作为初始簇中心；

repeat;

根据簇中对象的均值，将每个对象指派到最相似的簇；

更新簇均值，即计算每个簇中对象的均值；

计算准则函数；

until准则函数不再发生变化。

思考：K-means的优点和缺点？如何改进K-means算法？

---

本文介绍EM算法在R语言中如何使用。

数据集

采用R语言内置的iris数据集。

#查看数据集前六个观测
head(iris)

##   Sepal.Length Sepal.Width Petal.Length Petal.Width Species
## 1          5.1         3.5          1.4         0.2  setosa
## 2          4.9         3.0          1.4         0.2  setosa
## 3          4.7         3.2          1.3         0.2  setosa
## 4          4.6         3.1          1.5         0.2  setosa
## 5          5.0         3.6          1.4         0.2  setosa
## 6          5.4         3.9          1.7         0.4  setosa

EM算法R语言实践

第一步：加载实现EM算法的R包

library(mclust)

第二步：构建EM算法模型

model.EM <-Mclust(subset(iris, select = -Species))

第三步：生成混淆矩阵

table(model.EM$classification, iris$Species)

##
##     setosa versicolor virginica
##   1     50          0         0
##   2      0         50        50

思考：如何解读这个混淆矩阵里面的结果？？

EM算法原理

1 最大期望算法（Expectation-maximizationalgorithm，又译期望最大化算法）在统计中被用于寻找，依赖于不可观察的隐性变量的概率模型中，参数的最大似然估计。

2 在统计计算中，最大期望（EM）算法是在概率模型中寻找参数最大似然估计或者最大后验估计的算法，其中概率模型依赖于无法观测的隐藏变量（LatentVariable）。最大期望经常用在机器学习和计算机视觉的数据聚类（DataClustering）领域。最大期望算法经过两个步骤交替进行计算，第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值；第二步是最大化（M），最大化在 E 步上求得的最大似然值来计算参数的值。M步上找到的参数估计值被用于下一个 E 步计算中，这个过程不断交替进行。

---

 

本文介绍Apriori算法在R语言中如何使用。

数据集

采用arules包中的Adult数据集。

Adult数据集属于事务型数据集。

Apriori算法R语言实践

第一步：加载实现Apriori算法的R包

library(arules)
data(“Adult”)

第二步：利用Apriori算法构建关联规则模型

rules.Apriori <-apriori(Adult, parameter =list(support=0.4, confidence=0.7), appearance =list(rhs=c(“race=White”, “sex=Male”), default=”lhs”))

第三步：利用提升度对规则排序，获取前top-5项

rules.sorted <-sort(rules.Apriori, by=”lift”)
top5.rules <-head(rules.sorted, 5)
as(top5.rules, “data.frame”)

Apriori算法原理

1 Apriori算法是种最有影响的挖掘布尔关联规则频繁项集的算法。它的核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集。

思考：Apriori算法如何寻找频繁项集？对于大规模数据，Apriori算法会有什么表现？？

---

本文介绍PageRank算法在R语言中如何使用。

数据集

利用人工构造的数据集，随机地生成具有10个对象的有向图

PageRank算法R语言实践

第一步：加载R包

library(igraph)

library(dplyr)

第二步：随机生成具有10个对象的有向图

g <-random.graph.game(n =10, p.or.m =1/4, directed =TRUE)

第三步：画有向图

plot(g)

第四步：计算PageRank

pr <-page.rank(g)$vector

第五步：显示每个对象的 PageRank

df <-data.frame(Object =1:10, PageRank = pr)
arrange(df, desc(PageRank))

Object   PageRank
1       4      0.20150298
2       3     0.17785416
3       7     0.15485863
4       5    0.14621124
5       2    0.11995916
6       1    0.09424444
7       6    0.06036938
8       8    0.01500000
9       9    0.01500000
10     10  0.01500000

PageRank算法原理

1 PageRank，网页排名，又称网页级别、Google左侧排名或佩奇排名，是一种由搜索引擎根据网页之间相互的超链接计算的技术，而作为网页排名的要素之一，以Google公司创办人拉里·佩奇（Larry Page）之姓来命名。Google用它来体现网页的相关性和重要性，在搜索引擎优化操作中是经常被用来评估网页优化的成效因素之一。Google的创始人拉里·佩奇和谢尔盖·布林于1998年在斯坦福大学发明了这项技术。

2 PageRank通过网络浩瀚的超链接关系来确定一个页面的等级。Google把从A页面到B页面的链接解释为A页面给B页面投票，Google根据投票来源（甚至来源的来源，即链接到A页面的页面）和投票目标的等级来决定新的等级。简单的说，一个高等级的页面可以使其他低等级页面的等级提升。

参考资料

1 《数据挖掘导论》和《数据挖掘：概念与技术》

2 数据挖掘十大经典算法（详解）

3 Top 10 data mining algorithms in plain R

 

中国数据人QQ群：290937046，使命：让更多人懂数据、用数据。陆勤微信：luqin360 ,多交流。