机器学习算法之决策树

什么是决策树

决策树(Decision Tree)是一种简单但是广泛使用的分类器。通过训练数据构建决策树,可以高效的对未知的数据进行分类。决策数有两大优点:1)决策树模型可以读性好,具有描述性,有助于人工分析;2)效率高,决策树只需要一次构建,反复使用,每一次预测的最大计算次数不超过决策树的深度。

继续阅读机器学习算法之决策树

感知机、逻辑回归、支持向量机- 伯克利机器学习入门教程 翻译二

原文:Machine Learning Crash Course: Part 2

在这一节中我们将介绍机器学习算法中的一个:感知机算法,这个算法是现在大多机器学习算法的基础,最知名的神经网络也在内,此外,我们还将探讨感知机算法的兄弟-逻辑回归算法,然后我们会简单介绍一下支持向量机(这可能是如今使用的最灵活的算法)

继续阅读感知机、逻辑回归、支持向量机- 伯克利机器学习入门教程 翻译二

分类、回归-伯克利机器学习入门教程翻译一

原文:Machine Learning Crash Course: Part 1

什么是机器学习?

几乎所有的机器学习算法都是在完成一个任务:画线。 机器学习从一堆数据中学习,画一条线(或面..)以区分或者预测未知的输入。
继续阅读分类、回归-伯克利机器学习入门教程翻译一

监督学习(Supervised Learning)-局部线性回归(Locally Weighted Linear Regression)

线性回归的一个可能是由可能出现欠拟合现象,因为它求的是具有最小均方误差的无偏估计。显而易见,如果模型欠拟合将不能取得很好的预测效果,所以有些方法允许在估计中引入一些偏差,从而降低预测的均方误差。

其中一个方法就是lwlr,在这个方法中,给待预测点附近的每个点赋予一个权重,距离近的权重更大,然后就和之前提到的线性回归一样,求最小均方差来进行普通的回归。显而易见,这样子每次我们算的权重都会不一样(只要输入的参数不一样。)

算回归系数的式子为:

 

lmlr_e

其中:

lrlm

其中t是唯一需要我们去确认的参数,可以参考下图:

lmlr-func

 

图1是原始数据的情况,图2是t=0.5时,整个权重函数的分布情况,图3是t=0.1时,权重函数的分布情况,图4是t=0.01时,整个权重函数的分布情况。

可以看见,t越小,则离待预测点的权重影响越大,而远离预待测点的权重影响越小。

很明显,局部加权回归在每一次预测新样本时都会重新确定参数,以达到更好的预测效果。当数据规模比较大的时候计算量很大,学习效率很低。并且局部加权回归也不是一定就能避免欠拟合。

sklearn并没有提供局部加权线性回归可以直接使用的函数,所以我这里给大家提供一个python写的,数据集还是用的sklearn里面带的糖尿病人的那个数据:

__author__ = 'qing'
# -*- coding: utf8 -*-
# !/usr/bin/env python

from numpy import *
from sklearn import datasets
import matplotlib.pyplot as plt


def lwlr(testPoint, xArr, yArr, k):  #这里的k即上文的t, 为了与.T区分开
    xMat = mat(xArr); yMat = mat(yArr).T  #T是转置矩阵
    m = shape(xMat)[0]
    weights = mat(eye((m))) #创建一个单位矩阵
    for j in range(m):                      #根据该点建立权重
        diffMat = testPoint - xMat[j,:]
        weights[j,j] = exp(diffMat*diffMat.T/(-2.0*k**2))
    xTx = xMat.T * (weights * xMat)
    if linalg.det(xTx) == 0.0:#先检测行列式是否为0,0则不存在逆
        print "This matrix is singular, cannot do inverse"
        return
    ws = xTx.I * (xMat.T * (weights * yMat))  #I是矩阵的逆
    return testPoint * ws

def lwlrTest(testArr, xArr, yArr, k):  #loops over all the data points and applies lwlr to each one
    m = shape(testArr)[0]
    yHat = zeros(m)
    for i in range(m):
        yHat[i] = lwlr(testArr[i],xArr,yArr,k)
    return yHat

# 图形化显示局部加权线性回归结果, 包括数据集及它的最佳拟合直线
def lwlrPlot(xArr, yArr, yHat):
    xMat = mat(xArr)
    srtInd = xMat[:, 3].argsort(0)
    xSort = xMat[srtInd][:, 0, :]
    # 画线
    fig = plt.figure()
    ax = fig.add_subplot(111)
    ax.plot(xSort[:, 3], yHat[srtInd])
    # 画点
    ax.scatter(xMat[:, 3].flatten().A[0],
               mat(yArr).T[:, 0].flatten().A[0],
               s=2, c='red')
    plt.show()

def rssError(yArr, yHat):
    return ((yArr - yHat)**2).sum()


if __name__ == "__main__":
    diabetes = datasets.load_diabetes()
    diabetes_X_train = diabetes.data[:-20]
    diabetes_X_test  = diabetes.data[-20:]
    diabetes_y_train = diabetes.target[:-20]
    diabetes_y_test  = diabetes.target[-20:]
    lwlrResult = lwlrTest(diabetes_X_test, diabetes_X_train, diabetes_y_train, 0.14)
    print diabetes_y_test
    print lwlrResult
    print corrcoef(lwlrResult, diabetes_y_test)
    print rssError(lwlrResult, diabetes_y_test)
    lwlrPlot(diabetes_X_test, diabetes_y_test, lwlrResult)

最后我们可以看到,相关性的结果以及差平方和是:

[[ 1. 0.75591378]
[ 0.75591378 1. ]]

55830.0971546

plot
以及可以看到lwlr得到的拟合效果(对未知数据的预测,这里我任意选取了输入的一个特征作为横坐标)

代码开放在:

 https://github.com/ching1221/machine-learning

 

监督学习(Supervised Learning)-线性回归(Linear Regression)

打算开个系列把机器学习的基础算法都用心走一遍,顺手记录点东西,配套使用python的scikit-learn包。

先简要介绍下这个包,http://scikit-learn.org/stable/

About scikit-learn:

  • Simple and efficient tools for data mining and data analysis
  • Accessible to everybody, and reusable in various contexts
  • Built on NumPy, SciPy, and matplotlib
  • Open source, commercially usable – BSD license

要义:开源,机器学习、数据分析工具包,需要预装numpy,scipy,matplotlib等模块

scikit-learn的基本功能主要被分为六个部分,分类,回归,聚类,数据降维,模型选择,数据预处理。

今天先介绍它回归这一部分的功能。

线性回归

优点:结果易理解,计算不复杂。

缺点:对非线性数据拟合地不好。

适用数据类型:数值型以及标称型。

比如:你可能这样子来预测一个人的学习的成效:

score = 0.7*timeSpendOnStudy + 0.3*Gift

这就是一个回归方程,0.7和0.3在这里称为回归系数,我们利用一堆已知输入输出来求回归系数的过程就叫回归。

有了这些回归系数后,用回归系数乘以输入值,再将结果加在一起,就可以得到预测值了。

回归的一般方法

1、收集数据。

2、准备数据,回归需要数值型数据,标称型数据需要先转成二值型数据。

3、分析数据,数据可视化将有助于对数据做出理解和分析,在采用缩减法(shrinkage)求得新回归系数之后可以将新旧曲线绘在图上作对比。

4、训练算法:找到回归系数。

5、测试算法:使用R^2或者预测值和数据的拟合度,来分析模型的效果。

6、使用算法。

算法:

关于线性回归的最小二乘法矩阵求法,参考这篇博文,不再造轮子:http://blog.csdn.net/acdreamers/article/details/44662633

(为什么这样做,可以参考这片博文:http://blog.csdn.net/acdreamers/article/details/44662823

最后推导的结果:

lm_result

 

x为m组*n个自变量输入的m*n维矩阵,y为m*1的对应因变量输出,得到n*1的参数矩阵,即利用最小二乘法得到的最佳参数估计。

数据:

sklearn自带的糖尿病人的一些数据:

该数据集包含了442个病人的10项特征(年龄,性别,体重,血型等),以及一年后他们的疾病指数。

程序:

import numpy as np
from sklearn import linear_model
from sklearn import datasets


diabetes = datasets.load_diabetes()
diabetes_X_train = diabetes.data[:-20]
diabetes_X_test  = diabetes.data[-20:]
diabetes_y_train = diabetes.target[:-20]
diabetes_y_test  = diabetes.target[-20:]
lm = linear_model.LinearRegression()
lm.fit(diabetes_X_train, diabetes_y_train)
print(lm.coef_)
# The mean square error
print np.mean((lm.predict(diabetes_X_test)-diabetes_y_test)**2)

 # Explained variance score: 1 is perfect prediction
 # and 0 means that there is no linear relationship
 # between X and Y.
print lm.score(diabetes_X_test, diabetes_y_test)

结果:

系数:

[ 3.03499549e-01

-2.37639315e+02

5.10530605e+02

3.27736980e+02

-8.14131709e+02

4.92814588e+02

1.02848452e+02

1.84606489e+02
7.43519617e+02

7.60951722e+01]

方差:
2004.56760269

预测的准确率:

0.585075302269

 

再给一个有趣的测试,用线性回归来做图像处理:

数据:

uci提供的钢笔手写数字的图像(8*8图像矩阵, 0-16的像素值)和对应的识别结果

http://archive.ics.uci.edu/ml/datasets/Pen-Based+Recognition+of+Handwritten+Digits

程序:

from sklearn import datasets
from sklearn.linear_model import LinearRegression

digits = datasets.load_digits()  # 自带上述数据

trainingInput = digits.data[:1300]  # 数据一共有1797条,抽取前1300行作为训练数据
trainingOutput = digits.target[:1300]
testInput = digits.data[1300:]
testOutput = digits.target[1300:]
lm = LinearRegression()
lm.fit(trainingInput, trainingOutput).score(trainingInput, trainingOutput)  # 训练数据
print lm.predict(testInput) # 预测结果
print "the accurate is: " + str(lm.score(testInput, testOutput))  # 输出准确率

然而你会发现,这两个例子用线性回归做的效果并不好,准确率很低。后面将用其他机器学习的方法去做测试。

 

代码开放在:

 https://github.com/ching1221/machine-learning

主成分分析(Principal factor analysis)

昨天回顾了特征值和奇异值的定义及应用意义,现在来看看与之非常相关的主成分分析,

真实的训练数据总是存在各种各样的问题:比如,拿到一个样本,特征非常多,而样例特别少,这样用回归去直接拟合非常困难,容易过度拟合。比如北京的房价:假设房子的特征是(大小、位置、朝向、是否学区房、建造年代、是否二手、层数、所在层数),搞了这么多特征,结果只有不到十个房子的样例。要拟合房子特征->房价的这么多特征,就会造成过度拟合。

PCA的思想是将n维特征映射到k维上(k<n),这k维是全新的正交特征。这k维特征称为主元,是重新构造出来的k维特征,而不是简单地从n维特征中去除其余n-k维特征。

pca计算过程

以下在matlab中进行:

假设data的两列数据分别是两个词在一个文档中的tf-idf值

>> data = [2.5 2.4;0.5 0.7;2.2 2.9;1.9 2.2;3.1 3.0; 2.3 2.7; 2 1.6;1 1.1;1.5 1.6;1.1 0.9];

假设第一列是x, 第二列是y。 我们有10个样例,两个特征,分别为x与y。

第一步分别求x和y的平均值,然后对于所有的样例,都减去对应的均值。(因为这里两个特征都是tf-idf值,所以没有做方差归一化,如果是两个不同的量䋄,那么方差归一化是必不可少的哈。(即减了平均值之后要除以标准差)

 

计算x与y的平均值

ux = sum(data(:,1))/size(data,1)

uy = sum(data(:,2))/size(data,1)

>> adjustdata(:,1) = data(:,1)-ux;
>> adjustdata(:,2) = data(:,2)-uy;

第二步,求特征协方差矩阵

在matlab中,有一个特别好用的 cov(x,y)即可:

cov(data(:,1),data(:,2))

ans =

0.6166 0.6154
0.6154 0.7166

对角线上分别是x和y的方差,非对角线上是协方差。协方差大于0表示x和y若有一个增,另一个也增;小于0表示一个增,一个减;协方差为0时,两者独立。协方差绝对值越大,两者对彼此的影响越大,反之越小。

第三步,求协方差的特征值和特征向量,得到

 

>> [covv,covd] = eig(covdata)

covv =

-0.7352 0.6779
0.6779 0.7352
covd =

0.0491
1.2840

第四步,将特征值按照从大到小的顺序排序,选择其中最大的k个,然后将其对应的k个特征向量分别作为列向量组成特征向量矩阵。

这里特征值只有两个,我们选择其中最大的那个,这里是1.28402771,对应的特征向量是

(0.6779; 0.7352)

eigv = covv(:,2);

第五步,将样本点投影到选取的特征向量上。假设样例数为m,特征数为n,减去均值后的样本矩阵为DataAdjust(m*n),协方差矩阵是n*n,选取的k个特征向量组成的矩阵为EigenVectors(n*k)。那么投影后的数据FinalData为

201104182110426374

 

finnaldata = adjustdata*eigv;

finnaldata =

0.8280
-1.7776
0.9922
0.2742
1.6758
0.9129
-0.0991
-1.1446
-0.4380
-1.2238

这样,就将原始样例的n维特征变成了k维,这k维就是原始特征在k维上的投影。(即2维变成了1维)

上面的数据可以认为是这两个词特征融合为一个新的特征,该特征基本上代表了这两个特征。

上述过程用图描述:

 

201104182110441716

正号表示预处理后的样本点,斜着的两条线就分别是正交的特征向量(由于协方差矩阵是对称的,因此其特征向量正交),最后一步的矩阵乘法就是将原始样本点分别往特征向量对应的轴上做投影。

 

最小方差理论解释pca

整个PCA过程貌似及其简单,就是求协方差的特征值和特征向量,然后做数据转换。但是有没有觉得很神奇,为什么求协方差的特征向量就是最理想的k维向量?其背后隐藏的意义是什么?整个PCA的意义是什么?

看下面5个点(假设都做了归一化)

1

 

下面将样本投影到某一维上,这里用一条过原点的直线表示(前面处理的过程找到特征向量,实质特征向量的方向可以说是让样本量最集中分布的方向)。

2

在信号处理中认为信号具有较大的方差,噪声有较小的方差,信噪比就是信号与噪声的方差比,越大越好。如前面的图,样本在横轴上的投影方差较大,在纵轴上的投影方差较小,那么认为纵轴上的投影是由噪声引起的。

因此我们认为,最好的k维特征是将n维样本点转换为k维后,每一维上的样本方差都很大。

而要使样本方差大,试想样本要通过新的特征向量进行投影,那么就要投影值够大的,即λ够大的,所以我们取了前k个λ最大的相应的特征向量。