2019独角兽企业重金招聘Python工程师标准>>>

介绍

历史背景

决策树算法是最早的机器学习算法之一。早在 1966 年 Hunt,Marin 和 Stone 提出的CLS 学习系统就有了决策树算法的概念。但到了 1979 年， J.R. Quinlan 才给出了 ID3算法的原型， 1983 年和 1986 年他对 ID3 算法进行了总结和简化，正式确立了决策树
学习的理论。 从机器学习的角度来看，这是决策树算法的起点。到 1986 年， Schlimmer和 Fisher 在此基础上进行改造，引入了节点缓冲区，提出了 ID4 算法。在 1993 年，Quinlan 进一步发展了 ID3 算法，改进成 C4.5 算法，成为机器学习的十大算法之一。
ID3 的另一个分支是分类回归决策树算法(Classification Regression Tree)，与 C4.5 不同的是， CART 的决策树主要用于预测，这样决策树理论完整地覆盖了机器学习中分类和回归两个领域了。

基本思想

决策树的思想来源非常朴素，每个人大脑中都有类似 if-then 这样的判断逻辑，其中 if 表示条件， then 就是选择或决策。程序设计中，最基本的语句条件分支结构就是if-then 结构。而最早的决策树就是利用这类结构分隔数据的一种分类学习方法。

例子说明

假定某间 IT 公司销售笔记本电脑产品，为了提高销售收入，公司对各类客户建立了统一的调查表，统计了几个月销售数据之后收集到中的数据，为了提高销售的效率，公司希望通过上表对潜在客户进行分类，并根据上述特征制作简单的销售问卷。以利于销售人员的工作。这就出现两个问题：
- 如何对客户分类？
- 如何根据分类的依据，并给出销售人员指导的意见？

调查表的结果如下

计数	年龄	收入	学生	信誉	是否购
64	青	高	否	良	不买
64	青	高	否	优	不买
128	青	中	否	良	不买
64	青	低	是	良	买
64	青	中	是	优	买
128	中	高	否	良	买
64	中	低	是	优	买
32	中	中	否	优	买
32	中	高	是	良	买
60	老	中	否	良	买
64	老	低	是	良	买
64	老	低	是	优	不买
132	老	中	是	良	买
64	老	中	否	优	不买

现在，将年龄特征等于青年的选项剪切出一张表格，选择第二个特征：收入，并根据收入排序

计数	年龄	收入	学生	信誉	是否购
64	青	高	否	良	不买
64	青	高	否	优	不买
128	青	中	否	良	不买
64	青	中	是	优	买
64	青	低	是	良	买

其中，高收入和低收入的特征值只有一个类别标签买。将其作为叶子节点。然后继续划分中等收入的下一个特征：学生，于是有了下表

计数	年龄	收入	学生	信誉	是否购
128	青	中	否	良	不买
64	青	中	是	优	买

学生特征只有两个取值，当取否时，对应的标签为不买；当取是时，对应的标签为买。此时，学生特征就生成了决策树左侧分支的所有节点。

下图中的圆角矩阵为根节点或内部节点：就是可以继续划分的节点；图中的椭圆形节点就是叶子节点，即不能在划分的节点，一般叶子节点都指向一个分类标签，即产生一种决策。

在上面图的基础上，我们再进行如下操作：
- 接下来，我们继续右侧的分支的划分，但在划分时我们做一个简单的变化，划分的顺序为信誉>收入>学生>计数。
这样整个划分过程就变得简单了，当信誉取值为良时，类别标签仅有一个选项就是买。那么信誉为良就是叶子节点。当信誉取值为优时，类别标签仅有一个选项就是不买

• 在展示最终的结果前，再对图做一点调整，为了便于做出判断，我们对这棵树的方向做了调整，即将所有确定购买的叶子节点都放到了树的右侧，不买的节点都放到了树的左侧

• 到目前为止，都是从定性的角度对潜在用户的判断，为了便于从量上进行考量，在图的节点上加上量的标识

最终结果如下

从上面的图，我们得到如下结论
- 如果是中年人，一般会购买本公司的产品；
- 如果是青年人，低收入层都会购买，中等收入层还需要做进一步判断，如果是学生就会购买。
- 如果是老年客户，那么首先看一下他们的信誉，如果是良就会购买，如果信誉为优，多数不会购买。
- 全部的计数特征总数为 1024，将上图中路径边的数据除以 1024 这个总数，就得到了每个节点的购买概率

决策树的执行过程

决策树框架主要包含下面4个部分

决策树主函数

各种决策树的主函数都大同小异，本质上是个递归函数。该函数主要的功能是按照某种规则生长出决策树的各个分支节点，并根据终止条件结束算法。一般来讲，主函数需要完成如下几个功能：
1. 输入需要分类的数据集和类别标签；
2. 根据某种分类规则得到最优的划分特征，并创建特征的划分节点—计算最优特征子函数；
3. 按照该特征的每个取值划分数据集为若干部分—划分数据集子函数；
4. 根据划分子函数的计算结果构建出新的节点，作为树生长出的新分支；
5. 检验是否符合递归的终止条件
6. 将划分的新节点包含的数据集和类别标签作为输入，递归执行上述步骤

计算最优特征子函数

该函数是继主函数外最重要的函数。每种决策树之所以不同一般都因为最优特征选择的标准上有所差异，不同的标准导致不同类型的决策树，例如 ID3 的最优特征选择标准是信息增益、C4.5 是信息增益率，
CART 是节点方差的大小等等。后面所讲的理论部分，都是对特征选择标准而言的。算法逻辑上，一般选择最优特征需要遍历整个数据集，评估每个特征，找到最优的那一个返回。

划分数据集

划分数据集函数的主要功能是分隔数据集，有的需要删除某个特征轴所在的数据列，返回剩余的数据集。有的干脆就将数据集一份为二。
虽然实现有所不同，但基本含义都是一致的。

分类器

所有的机器学习算法要用于分类或回归预测。决策树的分类器就是将测试遍历整个生成的决策树，并找到最终的叶子节点的类别标签。这个标签就是返回的结果。

信息熵测度

虽然我们手工实现了上例的决策过程，但是将这种实现方法使用编程形式自动计算还存在一些问题。首先，特征集中的数据常常表现为定性字符串数据，称为标称数据，使用这些数据的算法缺乏泛化能力，在实际计算中需要将这些数据定量化为数字，也就是所谓的离散化。

我们可以将年龄、收入、学生、信誉这些特征的特征值转换为 0,1,2,…,n的形式。这样，年龄={0（青） ,1（中） ,2（老） }；收入={0（高） ,1（中） ,2（低） }；学生={0（是） ,1（否） }；信誉={0（优） ,1（良） }
完成了特征离散化，回顾一下前面的手工计算过程，我们可以总结出这样一条规律，数据特征的划分过程是一个将数据集从无序变为有序的过程。这样我们就可以处理特征的划分依据问题，即对于一个有多维特征构成的数据集，如何优选出某个特征作为根节点。进一步扩展这个问题，如何每次都选择出特征集中无序度最大的那列特
征作为划分节点。

为了衡量一个事物特征取值的有(无)序程度，下面我们引入一个重要的概念：信息熵。

熵是事物不确定性的度量标准，也称为信息的单位或“测度”。在决策树中它不仅能用来度量类别的不确性，可以来度量包含不同特征的数据样本与类别的不确定性。即某个特征列向量的信息熵越大，就说明该向量的不确定性程度越大，即混乱
程度越大，就应优先考虑从该特征向量着手来进行划分。信息熵为决策树的划分提供最重要的依据和标准。

不同决策树算法的差异，基本都体现在“熵”的计算方法不同，下面对各种算法的计算思路做一个简单的介绍

主要算法以及介绍

ID3算法

ID3 是比较早的机器学习算法，于 1979 年 Quinlan 就提出了算法的思想。它以信息熵为度量标准，划分出决策树特征节点，每次优先选取信息量最多的属性，即使信息熵变为最小的属性，以构造一棵信息熵下降最快的决策树。

但在另一方面， ID3 在使用中也暴露除了一些问题：
- ID3 算法的节点划分度量标准采用的是信息增益，信息增益偏向于选择特征
值个数较多的特征，而取值个数较多的特征并不一定是最优的特征。所以需
要改进选择属性的节点划分度量标准。
- ID3 算法递归过程中依次需要计算每个特征值的，对于大型数据会生成比较
复杂的决策树：层次和分支都很多，而其中某些分支的特征值概率很小，如
果不加忽略就造成了过拟合的问题。即决策树对样本数据的分类精度较高，
但在测试集上，分类的结果受决策树分支的影响很大。

C4.5算法

针对 ID3 算法存在的一些问题， 1993 年， Quinlan 将 ID3 算法改进为 C4.5 算法。该算法成功的解决了 ID3 遇到的诸多问题。在业界得到广泛的应用，并发展成为机器学习的十大算法之一。

C4.5 并没有改变 ID3 的算法逻辑，基本的程序结构仍与 ID3 相同，但在节点的划分标准上做了改进。 C4.5 使用信息增益率（ GainRatio）来替代信息增益（ Gain）进行特征的选择，克服了信息增益选择特征时偏向于特征值个数较多的不足

CART(Classification And Regression Tree)

CART（ Classification And RegressionTree）算法是目前决策树算法中最为成熟的一类算法，应用范围也比较广泛。它既可用于分类，也可用于预测.
西方预测理论一般都是基于回归的， CART 是一种通过决策树方法实现回归的算
法，它有很多其他全局回归算法不具有的特性。
在创建回归模型时， 样本的取值分为观察值和输出值两种，观察值和输出值都是
连续的， 不像分类函数那样有分类标签，只有根据数据集的数据特征来创建一个预测的模型，反应曲线的变化趋势。

在预测中， CART 使用最小剩余方差(Squared Residuals Minimization)来判定回归树的最优划分， 这个准则期望划分之后的子树与样本点的误差方差最小。 这样决策树
将数据集切分成很多子模型数据，然后利用线性回归技术来建模。如果每次切分后的数据子集仍然难以拟合就继续切分。在这种切分方式下，创建出的预测树，每个叶子节点都是一个线性回归模型。 这些线性回归模型反应了样本集合（观测集合）中蕴含的模式，也被称为模型树。因此， CART 不仅支持整体预测，也支持局部模式的预测，并有能力从整体中找到模式，或根据模式组合成一个整体。整体与模式之间的相互结
合，对于预测分析非常有价值。因此 CART 决策树算法在预测中的应用非常广泛。

代码样例

本章节只通过Scikit-Learn 库中的CART实现，来演示如果通过CART来达到预测的效果

# encoding:utf-8
"""CART 的实现有很多种，源码在很多地方都可以找到，相信读者在阅读完前面的
部分之后，有能力看懂，并且实现出 CART 的算法，
这里使用 Scikit-Learn 中的决策树算法来看一下 CART 的预测效果，使读者有一个
直观的认识。"""

__author__ = 'eric.sun'

import matplotlib.pyplot as plt
import numpy as np
from numpy import *
from sklearn.tree import DecisionTreeRegressor

def plotfigure(X,X_test,y,yp):
    plt.figure()
    plt.scatter(X, y, c="k", label="data")
    plt.plot(X_test, yp, c="r", label="max_depth=5", linewidth=2)
    plt.xlabel("data")
    plt.ylabel("target")
    plt.title("Decision Tree Regression")
    plt.legend()
    plt.show()

x = np.linspace(-5,5,200)
print x
siny = np.sin(x) # 给出 y 与 x 的基本关系
X = mat(x).T
y = siny+np.random.rand(1,len(siny))*1.5 # 加入噪声的点集
y = y.tolist()[0]
# Fit regression model
clf = DecisionTreeRegressor(max_depth=4) # max_depth 选取最大的树深度，类似前剪枝
clf.fit(X, y)
# Predict
X_test = np.arange(-5.0, 5.0, 0.05)[:, np.newaxis]
yp = clf.predict(X_test)
plotfigure(X,X_test,y,yp)

介绍

背景

随着互联网行业的井喷式发展，获取信息的方式越来越多，人们从主动获取信息逐渐变成了被动接受信息，信息量也在以几何倍数式爆发增长。举一个例子，PC时代用google reader，常常有上千条未读博客更新；如今的微信公众号，也有大量的红点未阅读。垃圾信息越来越多，导致用户获取有价值信息的成本大大增加。为了解决这个问题，我个人就采取了比较极端的做法：直接忽略所有推送消息的入口。但在很多时候，有效信息的获取速度极其重要。

由于信息的爆炸式增长，对信息获取的有效性，针对性的需求也就自然出现了。推荐系统应运而生。

推荐形式

电商网站常见的推荐形式包括三种：
- 针对用户的浏览、搜索等行为所做的相关推荐；
- 根据购物车或物品收藏所做的相似物品推荐；
- 根据历史会员购买行为记录，利用推荐机制做EDM或会员营销。

前面2种表现形式是大家可以在网站上看到，而第3种表现形式只有体验后才能知晓，一封邮件，一条短信，一条站内消息都是它的表现方式。

下面将对亚马逊中国的前两种表现形式进行简单说明：

• 对于非登录用户，亚马逊中国在网站首页和类目栏，会根据各个类目畅销品的情况做响应的推荐，其主要表现形式为排行榜。搜索浏览页面以及具体的产品页面的推荐形式则有关联推荐（“经常一起购买的商品”）和基于人群偏好的相似性推荐（“购买此物品的顾客也购买了”、“看过此商品的顾客购买的其他商品”）。

• 对于登录用户，亚马逊中国则给出了完全不同的推荐方式，网站会根据用户的历史浏览记录在登入界面首屏展现出一个今日推荐的栏目，紧接着是最近一次浏览商品的记录和根据该物品所给的产品推荐（“根据浏览推荐给我的商品”、“浏览XX产品的用户会买XX的概率”），值得注意的是，每个页面最下方网站都会根据用户的浏览行为做响应推荐，如果没有浏览记录则会推荐“系统畅销品”（13页，50款商品）。

推荐系统的架构

推荐系统常见的架构体系如下：

从架构图可以看出，一个简单的推荐系统通常包括三个部分

• 数据来源
  该部分至少包括三部分内容:（1）物品信息 （2）用户信息，例如用户爱好，浏览记录，购买记录等 （3）用户的物品的偏好，例如 商品评分，商品评论等

• 算法处理：常见的算法类型主要包括

  • 人口统计学推荐：主要是根据用户资料信息，发现和物品的相关程度
  • 物品内容推荐：根据用户的偏好，推荐相似的物品给用户
  • 协同过滤推荐：根据用户对物品的偏好，发现物品或是用户的相关性，然后基于相关性进行推荐，主要包括:1:基于用户的推荐 2:基于物品的推荐
  • SVD(奇异值分解):相当于协同过滤的相似度计算模型，主要基于用户和物品信息构成的矩阵，矩阵中的值是用户对商品的评分，这个矩阵通常是一个比较稀疏的矩阵，通过SVD算法可以得到用户与物品的特征向量PU(用户的偏好)，PI（物品的偏好）通过PU*PI得到用户对物品的评分预测

• 结果展示：对推荐结果进行展示

主要算法以及介绍

本章节主要介绍协同过滤，SVD,K-Means三种算法

协同过滤模型

模型介绍

协同过滤Collaborative Filtering (CF)算法是推荐算法的一个大分支，基本思想是推荐相似的物品，或者推荐相似用户（隐式或者显式）评分过的物品。CF方法主要可以分为两类：基于邻域和基于隐语义。

1. 基于邻域的方法利用“两个用户共同评分过的物品”(user-based)或者“共同评价两个物品的用户”（item-based）分别计算用户间的相似度和物品间的相似度。而相似度的计算有余弦相似度，皮尔逊相似度和一种被称为“Conditional Probability-Based“的Similarity。皮尔逊系数与余弦相似度的不同在于，皮尔逊系数还能捕捉负关系,第三个方法的弊端在于由于每个物品（人）邻域的大小不同，流行物品或评分多的用户会引起问题。因此，实际中一般采用带权的皮尔逊相似度(P. 2) 。但基于邻域方法的缺点是：由于实际用户评分的数据是十分稀疏，用户之间可能根本没有相同的评论；而且用启发式的方法很难考虑全面用户和物品之间的所有关系。

2. 基于隐语义的方法则不依赖于共同评分。其基本思想是将用户和物品分别映射到某种真实含义未知的feature向量。用户feature代表用户对不同类别电影的喜好程度（如：动作片5，惊悚片5），物品feature代表电影中大致属于哪类电影（如：爱情片3，喜剧片5）。然后通过两个feature向量的内积来判断用户对一个物品的喜好程度。虽然这个方法不要求共同评分，但推荐系统还是面临很大的数据稀疏问题。

算法逻辑

作为CF的两大基本分类，邻域的相关算法比较简单不再介绍，本文主要介绍SVD，不过在介绍SVD之前，先对K-Means做个简单的说明

K-means

算法介绍

推荐系统大多数都是基于海量的数据进行处理和计算，要在海量数据的基础上进行协同过滤的相关处理，运行效率会很低，为了解决这个问题通常是先使用K-means对数据进行聚类操作，说白了，就是按照数据的属性通过K-Means算法把数据先分成几大类，然后再在每个大类中通过邻域或是隐语义算法进行推荐

算法逻辑

网上有很多关于K-Means算法的描述，个人觉得大多数都很拗口，不容易理解，下面这个图中举例的方式，感觉比较容易理解

在Python的sklearn库中已经实现了该算法，如果有兴趣也可以实现一个自己的K-Means算法。

K-Means算法在实际运行的过程中存在以下几个问题
1. 最大问题是：K值对最后的结果影响较大，但是该值是由用户确定的，且不同的数据集，该值没有可借鉴性
2. 对离群数据点敏感，就算少量的离群数据也能对结果造成较大的影响
3. 算法初始化中心点的选择好坏，会直接影响到最终程序的效率

为了解决上面的问题，出现了二分KMeans算法，有兴趣的读者，可以自行寻找相关的资料 ，本文不做详细介绍

SVD

算法介绍

特征值分解是一个提取矩阵特征很不错的方法，但是它只是对方阵而言的，在现实的世界中，我们看到的大部分矩阵都不是方阵，比如说有N个学生，每个学生有M科成绩，这样形成的一个N*M的矩阵就不可能是方阵，我们怎样才能描述这样普通的矩阵呢的重要特征呢？奇异值分解可以用来干这个事情，奇异值分解是一个能适用于任意的矩阵的一种分解的方法

算法逻辑

算法公式：

公式说明：假设A是一个N * M的矩阵，那么得到的U是一个N * N的方阵（里面的向量是正交的，U里面的向量称为左奇异向量），Σ是一个N * M的矩阵（除了对角线的元素都是0，对角线上的元素称为奇异值），V’(V的转置)是一个N * N的矩阵，里面的向量也是正交的，V里面的向量称为右奇异向量），从图片来反映几个相乘的矩阵的大小可得下面的图片

那么奇异值和特征值是怎么对应起来的呢？首先，我们将一个矩阵A的转置 *

A，将会得到一个方阵，我们用这个方阵求特征值可以得到：

这里得到的v，就是我们上面的右奇异向量。此外我们还可以得到：

这里的σ就是上面说的奇异值，u就是上面说的左奇异向量。奇异值σ跟特征值类似，在矩阵Σ中也是从大到小排列，而且σ的减少特别的快，在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上了。也就是说，我们也可以用前r大的奇异值来近似描述矩阵，这里定义一下部分奇异值分解

r是一个远小于m、n的数，这样矩阵的乘法看起来像是下面的样子

边的三个矩阵相乘的结果将会是一个接近于A的矩阵，在这儿，r越接近于n，则相乘的结果越接近于A。而这三个矩阵的面积之和（在存储观点来说，矩阵面积 越小，存储量就越小）要远远小于原始的矩阵A，我们如果想要压缩空间来表示原矩阵A，我们存下这里的三个矩阵：U、Σ、V就好了。

在Numpy的linalg中，已经对SVD进行了实现，可直接进行使用

代码样例

公共函数

该部分主要是用来加载样本数据的代码

def load_test_data():
    matrix=[[0.238,0,0.1905,0.1905,0.1905,0.1905],[0,0.177,0,0.294,0.235,0.294],[0.2,0.16,0.12,0.12,0.2,0.2],[0.2,0.16,0.12,0.12,0.2,0.1]]
    return matrix

• 1
• 2
• 3

使用邻域法进行推荐

# 夹角余弦距离公式
def cosdist(vector1,vector2):
    return dot(vector1,vector2)/(linalg.norm(vector1)*linalg.norm(vector2))

# kNN 分类器
# 测试集： testdata；训练集： trainSet；类别标签： listClasses； k:k 个邻居数
def classify(testdata, trainSet, listClasses, k):
    dataSetSize = trainSet.shape[0] # 返回样本集的行数
    distances = array(zeros(dataSetSize))
    for indx in xrange(dataSetSize): # 计算测试集与训练集之间的距离：夹角余弦
        distances[indx] = cosdist(testdata,trainSet[indx])
        # 根据生成的夹角余弦按从大到小排序,结果为索引号
        sortedDistIndicies = argsort(-distances)
    classCount={}
    for i in range(k): # 获取角度最小的前 k 项作为参考项
        # 按排序顺序返回样本集对应的类别标签
        voteIlabel = listClasses[sortedDistIndicies[i]]
        # 为字典 classCount 赋值,相同 key，其 value 加 1
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
    # 对分类字典 classCount 按 value 重新排序
    # sorted(data.iteritems(), key=operator.itemgetter(1), reverse=True)
    # 该句是按字典值排序的固定用法
    # classCount.iteritems()：字典迭代器函数
    # key：排序参数； operator.itemgetter(1)：多级排序
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0] # 返回序最高的一项

if __name__ == '__main__':
    # 使用领域算法进行推荐
    recommand_by_distance()

使用SVD进行推荐

def comsSim(vecA,vecB):
    eps=1.0e-6
    a=vecA[0]
    b=vecB[0]
    return dot(a,b)/((np.linalg.norm(a)*np.linalg.norm(b))+eps)

def recommand_by_svd():
    r=1
    dataset=np.mat(load_test_data())
    data_point=np.mat([[0.2174,0.2174,0.1304,0,0.2174,0.2174]])
    m,n=np.shape(dataset)
    limit=min(m,n)
    if r>limit:r=limit
    U,S,VT=np.linalg.svd(dataset.T) #SVD 分解
    V=VT.T
    Ur=U[:,:r]
    Sr=np.diag(S)[:r,:r]  #取前r个U,S,V的值
    Vr=V[:,:r]
    testresult=data_point*Ur*np.linalg.inv(Sr)  # 计算data_point的坐标
    resultarray=array([comsSim(testresult,vi) for vi in Vr]) # 计算距离
    descindx=argsort(-resultarray)[:1]
    print descindx
    # print resultarray
    print resultarray[descindx]

if __name__ == '__main__':
    # 使用SVD算法进行推荐
    recommand_by_svd()

背景说明

可以说在分析机器学习的数据源中最常见的知识发现主题是把数据对象或事件转换为预定的类别，再根据类别进行专门的处理，这是分类系统的基本任务。

文本分类也如此：其实就是为用户给出的每个文档找到所属的正确类别（主题或概念）。想要实现这个任务，首先需要给出一组类别，然后根据这些类别收集相应的文本集合，构成训练数据集，训练集既包括分好类的文本文件也包括类别信息。

今天，在互联网的背景下自动化的文本分类被广泛的应用于，包括文本检索，垃圾邮件过滤，网页分层目录，自动生成元数据，题材检测，以及许多其他的应用领域，是文本挖掘最基础也是应用最广范的核心技术。

目前， 有两种主要的文本分类方法，一是基于模式系统（通过运用知识工程技术），二是分类模型（通过使用统计和/或机器学习技术）。专家系统的方法是将专家的知识以规则表达式的形式编码成分类系统。机器学习的方法是一个广义归纳过程，采用由一组预分类的例子，通过训练建立分类。由于文件数量以指数速度的增加和知识专家的可用性变得越来越小，潮流趋势正在转向机器学习 - 基于自动分类技术。

文本分类操作的基本步骤

不同语言的文本分类系统的现实过程可能存在一定的差异，但是大的流程基本是相同的，下面主要说明中文分类系统涉及到的几个主要的步骤

样本的预处理

去除样本中的噪声数据，例如：如果样本数据来源于网页，需要去处掉网页上的标签等操作。

文本处理的核心任务要把 非结构化和半结构 化的文本转化为结构 化的形式, 即向量空间模型。这之前,必须要对不同类型的文 本进行预处理。在大多 数文本挖掘 任务中,文本预处理的步骤都是相似的,基本步骤如下

确定需要处理的文本数据范围

有时间语料库里面的文件可能会很大，根据处理目的的不同，对文本的处理范围可能也不同，例如，如果需要使用语料库的训练结果，来做文本的分类预测，就需要处理语料库中文件的全部内容，如果只是用来做情感分析，可能只要分析每个文件的摘要部分

样本库的建立

样本的来源主要包括两种
- 已经分类好且存在的样本
如果出于研究目的，对样本的要求不高，可以使用一些公开的样本库，可以使用复旦大学谭松波中文文本分类语料(下载地址: http://www.threedweb/thread-1292-1-1.html)和搜狗新闻分类语料库(下载地址: http://www.sogou/labs/dl/c.html)等。如果对于样本的质量要求较高，只能根据业务的要求对样本的质量逐步的进行改进

• 未分类的样本库
  互联网上很多的综合性的新闻网站，每个网站都会将自己的内容进行分类，可以根据开发的需求，通过爬虫从这些新闻网站上对内容进行爬取，并使用网站自身提供的分类标签对爬到的数据打上标签

中文分词

使用分词器对文本进行分词，并去处停用词，例如 “的”，”也”，”但是”等词

中文分词 (Chinese Word Segmentation) 指的是将一个汉字序列(句子)切分成一 个一个单独的词。分词就是将连续的字序列按照一定的规范重新组合成词序列的过程。 我们知道,在英文的行文中, 单词之间是以空格作 为自然分界符的,而中 文只是字、 句和段能通过明显的分界符来 简单划界,唯独词没 有一个形式上的分界符 ,虽然英文 也同样存在短语的划分问题, 不过在词这一层上, 中文比之英文要复杂的 多、困难的 多。中文分词,不仅是中文文 本分类的一大问题, 也是中文自然语言处理 的核心问题 之一。

在一定意义上,中文分词不完 全是个技术问题。 中文分词的难点也不 完全是算法 问题。因为关于到底什么是词 这个概念在中国理论 界已经争论了很多年。 一个著名的 例子就是:“鸡蛋”、“牛肉”、“下雨”是词吗,如果是那么“鸭蛋”、“驴肉”、 “下雪”、“鸟蛋”、“鱼肉 ”、“下雾”也应该 是词,按照这样规则组 合下去会产 生很多让人费解的结论。如果不是,这些字符串在我们日常生活中使用的频率非常高, 而且都有独立的意义。
分词是自然语言处 理中最基本、最底层 的模块,分 词精度对后续应用模块影响很 大,纵观整个自然语 言处理领域,文本或句 子的结构化 表示是语言处理最核心的任务 。
目前,文本的结构化表示简单分为四大类 :词向量空 间模型、主题模、主题模型、依存句法的树表示、RDF 的图表示。以上这四种文本表示都以分 词为基础的。

一般专业化大型的文本分类系统,为了提高精度,常常订制开发自己的分词系统。 一般算法都使用 CRF,语料资源则各有不同。现在开放出来的、比较成熟的、有商用 价值的分词工具有:理工大学张华平博士开发的中文分词系统:http://ictclas.nlpir/ (一年免费试用权);哈工大的语言云系统:http://w ww .ltp-c loud.c om/intro/(开源),Ansj的中文分词系统:http://www.nlpcn/(开源)等等。这类分词系统完整性强,稳定性、精度也不错。即使如此也不能满足搜索引擎 类公司对超大规模 分词的需求,一般像 新浪和百度这些公司的分词系统,仅扩展词汇要到五百多万,估计基础词汇不少于五十万。
以上这些分词系统与 Python 整合都比较麻烦,占用资源也大。因为分词不是本书讲解的重点,为了方便说明原理， 本文后面的例子使用 jieba 分词,它是专门使用 Python 语言开发的分词系统,占用资源 较小,常识类文档的分词精度较高。对于非专业文档绰绰有余。下载最新的jibes,分词算法使用的是 CRF,编写语言是 Python,基础词库 349046 个。

构建词的向量空间

主要是统计文本中词的频率
文本分类的结构化方法就是向量空间模型，虽然越来越多的实践已经证明，这种
模型存在着的局限，但是迄今为止，它仍是在文本分类中应用最广泛、最为流行的数据结构，也是很多相关技术的基础，例如：推荐系统、搜索引擎等。

向量空间模型把文本表示为一个向量，其中该向量的每个特征表示为文本中出现
的词。通常，把训练集中出现的每个不同的字符串都作为一个维度，包括常用词、专有词、词组和其他类型模式串，如电子邮件地址和URL。

目前，大多数文本挖掘系统，都把文本存储为向量空间的表示，因为它便于运用机器学习算法。这类算法适用并能有效处理高维空间的文本情况。但是，对于大规模文本分类，这会导致极高维的空间，即使是中等大小的文本文件集合，向量的维度也很轻易就达到数十万维。

由于文本在存储为向量空间时，维度比较高。 为节省存储空间和提高搜索效率，
在文本分类之前会自动过滤掉某些字或词，这些字或词即被称为停用词。 这类词一般都是意义模糊的常用词，还有一些语气助词，通常它们对文本起不了分类特征的意义。

在设计系统的时候，可以逐步建立自己的停词库，在对样本进行训练时，将其作为参数，从而降低处理数据的复杂程度

使用TF－IDF构建权重策略

通过TF—IDF方法选出能代表文本特征的一些词
计算文本的权重向量，应该选择一个有效的权重方案。最流行的方案是对 TF-IDF
权重的方法。 TF-IDF的含义是词频–逆文档频率，其含义是如果某个词或短语在一篇文章中出现的频率 TF高，并且在其他文章中很少出现，则认为此词或者短语具有很好的类别区分能力，适合用来分类。

TF-IDF 的假设是，高频率词应该具有高权重，除非它也是高文档频率。“ my”这个词在文本中是最经常出现的词汇之一。它不仅很多次发生在单一的文本中，但几乎也发生在每个文档中。逆文档频率就是使用词条的文档频率来抵消该词的词频对权重的影响，而得到一个较低的权重。

样本训练与预测

使用算法，对样本进行训练，构建出分类模型
最常用的文本分类方法有 kNN 最近邻算法，朴素贝叶斯算法和支持向量机算法。
这三类算法一般而言 kNN最近邻算法的原理最简单，分类精度尚可，但是速度最慢；

朴素贝叶斯对于短文本分类的效果最好，精度很高；支持向量机的优势是支持线性不可分的情况，精度上取中.

Scikit-Learn 的算法库中包含了一些常用算法的实现，如果不打算研究算法的细节，可以通过调用对应算法的API，传入TF-IDF产生的训练集词袋，产生向量空间模型，并用该模型对测试数据进行预测。详细的代码实现，将在后面的章节详细展示

优化

如果预测的结果不准确，则需要调整算法的参数重新进行样本训练以及预测，每种算法的优化参数都不同，具体优化方法要看算法的要求

例如，如果是贝叶斯算法，可以通过调整alpha达到更高的精度，

常用算法以及原理说明

朴素贝叶斯

朴素贝叶斯分类是一种十分简单的分类算法，叫它朴素是因为其思想基础的简单性： 就文本分类而言，它认为词袋中的两两词之间的关系是相互独立的，即一个对象的特征向量中每个维度都是相互独立的。例如，黄色是苹果和梨共有的属性，但苹果和梨是相互独立的。这是朴素贝叶斯理论的思想基础。该思想主要基于以下理论
已知某条件概率，如何得到两个事件交换后的概率，也就是在已知P(A|B)的情况下如何求得 P(B|A)：

算法步骤

• 设 x={a1,a2,…,am}为一个待分类项，而每个 a 为 x 的一个特征属性。
• 有类别集合 C={y1,y2,…,yn}。
• 计算 P( y1|x) ,P( y2|x),…, P( yn|x)。
• 如果 P( yk|x) =max{P( y1|x),P( y2|x),…, P( yn|x)}，则 x∈yk。

代码示例

# -*- coding: utf-8 -*-
__author__ = 'eric.sun'
import sys
import os
import jieba
import pickle
from sklearn.datasets.base import Bunch
from sklearn.feature_extraction.text import TfidfTransformer
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.naive_bayes import MultinomialNB




reload(sys)
sys.setdefaultencoding('utf-8')

ori_path='/others/ml_test_data/text_classification/fudan/small_ori'
#ori_path='E:\\others\\ml_test_data\\text_classification\\fudan\\small_ori'
seg_path='/others/ml_test_data/text_classification/fudan/small_seg'
train_data= '/others/ml_test_data/text_classification/train_set.dat'

#test_file 是用来被预测的数据，拷贝自sport450/10201.txt 以及medicine204/7173.txt,
# 以及一篇来自qq体育的新闻：http://sports.qq/a/20160828/014734.htm（放在medicine下）
#    一篇来自里约奥运会的新闻：
# ，结构如下
# .
# ├── medicine204
# │   ├── 7173.txt
# │   └── qq_news.txt
# └── sport450
#     ├── 10201.txt
#     └── rio_olympic.txt



test_file_path='/others/ml_test_data/text_classification/test_txt'
test_data= '/others/ml_test_data/text_classification/test_set.dat'

test_space_path= '/others/ml_test_data/text_classification/test_space.dat'
tf_idf_space_data='/others/ml_test_data/text_classification/tf_idf_space.dat'
stop_words_path='/others/ml_test_data/text_classification/stop_word.txt'
#seg_path='E:\\others\\ml_test_data\\text_classification\\fudan\\small_seg'

def save_file(path,content):
    fp=open(path,'wb')
    fp.write(content)
    fp.close()

def read_file(path):
    fp=open(path,'rb')
    content=fp.read()
    fp.close()
    return content

def save_object(path,content):
    fp=open(path,'wb')
    pickle.dump(content,fp)
    fp.close()

def read_object(path):
    fp=open(path,'rb')
    object=pickle.load(fp)
    fp.close()
    return object

#（1）对词库数据文件进行分词
def segment():
    """
    将ori_path的内容，通过jieba进行分词操作
    """
    for ori_dir in os.listdir(ori_path):
        seg_dir=os.path.join(seg_path,ori_dir)
        ori_subdir_path=os.path.join(ori_path,ori_dir)
        for ori_file in os.listdir(ori_subdir_path):
            if not os.path.exists(seg_dir):
                os.mkdir(seg_dir)
            ori_content=read_file(os.path.join(ori_subdir_path,ori_file))
            #对换行符进行替换
            ori_content.replace('\r\n','').strip()
            ori_content.replace('，','')
            seg_result=jieba.cut(ori_content)
            save_file(os.path.join(seg_dir,ori_file),' '.join(seg_result))

    print 'segment finished'
#将分词数据转换成文本向量
def segment_bunch():
    bunch=Bunch(target_name=[],label=[],filenames=[],contents=[])    
    catelist=os.listdir(seg_path)
    bunch.target_name.extend(catelist)
    for class_dir in catelist:
        for class_file in os.listdir(os.path.join(seg_path,class_dir)):
            #print class_file
            class_file_full_path=os.path.join(seg_path,class_dir,class_file)
            bunch.label.append(class_dir)
            bunch.filenames.append(class_file_full_path)
            bunch.contents.append(read_file(class_file_full_path).strip())

    save_object(train_data, bunch)
#停词对象
def load_stop_words():
    return read_file(stop_words_path).splitlines()

#（2）生成tf_idf 词向量空间
def gen_tf_idf_space():
    bunch=read_object(train_data)
    tf_idf_space=Bunch(target_name=bunch.target_name,label=bunch.label,filenames=bunch.filenames,vocabulary={})

    vectorizer=TfidfVectorizer(stop_words=load_stop_words(),sublinear_tf = True,max_df = 0.5)
    transformer=TfidfTransformer()

    tf_idf_space.tdm=vectorizer.fit_transform(bunch.contents)
    tf_idf_space.vocabulary=vectorizer.vocabulary_
    save_object(tf_idf_space_data,tf_idf_space)
    # print tf_idf_space

#（3）生成测试数据的data文件
def gen_test_data():
    bunch = Bunch(target_name=[], label=[], filenames=[], contents=[])
    catelist = os.listdir(test_file_path)
    bunch.target_name.extend(catelist)
    for class_dir in catelist:
        for class_file in os.listdir(os.path.join(test_file_path, class_dir)):
            # print class_file
            class_file_full_path = os.path.join(test_file_path, class_dir, class_file)
            bunch.label.append(class_dir)
            bunch.filenames.append(class_file_full_path)
            bunch.contents.append(read_file(class_file_full_path).strip())

    save_object(test_data, bunch)


#（4）使用多项贝叶斯进行预测
def execute_NM_predict():
    test_bunch=read_object(test_data)

    test_space=Bunch(target_name=test_bunch.target_name, label=test_bunch.label, filenames=test_bunch.filenames, tdm=[], vocabulary = {})

    tf_idf_bunch=read_object(tf_idf_space_data)
    vectorizer = TfidfVectorizer(stop_words=load_stop_words(), sublinear_tf=True, max_df=0.5,vocabulary=tf_idf_bunch.vocabulary)
    transformer = TfidfTransformer()

    test_space.tdm = vectorizer.fit_transform(test_bunch.contents)
    test_space.vocabulary = tf_idf_bunch.vocabulary

    clf=MultinomialNB(alpha=0.001).fit(tf_idf_bunch.tdm,tf_idf_bunch.label)
    #预测结果
    predicted=clf.predict(test_space.tdm)
    #对结果进行更加友好的打印
    for label,file_name,excect_cate in zip(test_bunch.label,test_bunch.filenames,predicted):
        print file_name,' 实际类别：',label,' 预测类别：',excect_cate

    # print predicted




if __name__ == '__main__':
    segment()
    segment_bunch()
    load_stop_words()
    gen_tf_idf_space()
    gen_test_data()
    execute_NM_predict()

kNN 算法

kNN 算法，一种基于向量间相似度的分类
算法。

k 最近邻（ k-Nearest Neighbor）算法是比较简单的机器学习算法。它采用测量不同特征值之间的距离方法进行分类。它的思想很简单：如果一个样本在特征空
间中的 k 个最邻近（最相似）的样本中的大多数都属于某一个类别，则该样本也属
于这个类别

算法步骤

算法的详细步骤如下：
- 第一阶段： 首先我们事先定下 k 值（就是指最近邻居的个数）。 一般是个奇数， 我们因为测试样本有限取 k 值为 3；

• 第二阶段： 确定的距离度量公式—文本分类一般使用夹角余弦，得出待分类数据点和所有已知类别的样本点中， 选择距离最近的 k 个样本。

• 第三阶段： 统计这 k 个样本点中，各个类别的数量。根据 k 个样本中，数量最多的样本是什么类别，我们就把这个数据点定为什么类别。

代码示例

# -*- coding: utf-8 -*-

from numpy import *
import numpy as np
import matplotlib.pyplot as plt
import operator
import sys

reload(sys)
sys.setdefaultencoding('utf-8')

train_data_set=[[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]]
train_data_label=['A','A','B','B']
test_data_point=[0.1,0.0]

#前面的4个点已经分好类了，且各自有自己的标签，最后一个点用来判断离哪个类别更近一点
def get_train_data_set():
    test_data=np.array(train_data_set)
    labels=train_data_label
    return test_data,labels

# 夹角余弦距离公式
def cosdist(vector1,vector2):
    return dot(vector1,vector2)/(linalg.norm(vector1)*linalg.norm(vector2))

# kNN 分类器
# 测试集： testdata；训练集： trainSet；类别标签： listClasses； k:k 个邻居数
def classify(testdata, trainSet, listClasses, k):
    dataSetSize = trainSet.shape[0] # 返回样本集的行数
    distances = array(zeros(dataSetSize))
    for indx in xrange(dataSetSize): # 计算测试集与训练集之间的距离：夹角余弦
        distances[indx] = cosdist(testdata,trainSet[indx])
        # 根据生成的夹角余弦按从大到小排序,结果为索引号
        sortedDistIndicies = argsort(-distances)
    classCount={}
    for i in range(k): # 获取角度最小的前 k 项作为参考项
        # 按排序顺序返回样本集对应的类别标签
        voteIlabel = listClasses[sortedDistIndicies[i]]
        # 为字典 classCount 赋值,相同 key，其 value 加 1
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
    # 对分类字典 classCount 按 value 重新排序
    # sorted(data.iteritems(), key=operator.itemgetter(1), reverse=True)
    # 该句是按字典值排序的固定用法
    # classCount.iteritems()：字典迭代器函数
    # key：排序参数； operator.itemgetter(1)：多级排序
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0] # 返回序最高的一项

def print_data(dataset,labels,test_data_point):
    fig=plt.figure()
    ax=fig.add_subplot(111)
    #print test data point
    ax.scatter(test_data_point[0],test_data_point[1],c='red',marker='^',linewidths=0,s=300)

    for point,label in zip(dataset,labels):
        #add point
        ax.scatter(point[0],point[1],c='blue',marker='o',linewidths=0,s=300)
        #add point common
        plt.annotate("("+str(point[0])+","+str(point[1])+' '+label+")",xy = (point[0],point[1]))
    #print figure
    plt.show()


def print_test():
    train_data,train_label=get_train_data_set()
    print_data(train_data,train_label,test_data_point)

if __name__ =='__main__':
    #打印测试
    print_test()
    print classify(np.array(test_data_point),np.array(train_data_set),train_data_label,1)

 

转载于:https://my.oschina/hblt147/blog/1596287