## 卷积神经网络Lenet-5实现 > 原文地址：[http://blog.csdn.net/hjimce/article/details/47323463](http://blog.csdn.net/hjimce/article/details/47323463) > 作者：hjimce 卷积神经网络算法是n年前就有的算法，只是近年来因为深度学习相关算法为多层网络的训练提供了新方法，然后现在电脑的计算能力已非当年的那种计算水平，同时现在的训练数据很多，于是神经网络的相关算法又重新火了起来，因此卷积神经网络就又活了起来，再开始前，我们需要明确的是网上讲的卷积神经网络的相关教程一般指的是神经网络的前向传导过程，反向传播都是用梯度下降法进行训练。 ###一、理论阶段 讲解这个算法，没有打算啰嗦太多的东西，因为什么权值共享、局部感受野什么的，讲那么多，都是那些生物学的相关理论。卷积神经网络的相关博文也是一大堆，但是讲的，基本上都是抄过来抄过去，就像我之前不理解从S2层到C3层是怎么实现的，网上看了一大堆教程，没有一个解答这个问题的。我的个人感觉整个过程，就只有S2到C3是最难理解的。接着我将结合我的理解进行讲解。 **1、卷积** 卷积的概念这个我想只要学过图像处理的人都懂的概念了，这个不解释。我们知道对于给定的一幅图像来说，给定一个卷积核，卷积就是根据卷积窗口，进行像素的加权求和。  卷积神经网络与我们之前所学到的图像的卷积的区别，我的理解是：我们之前学图像处理遇到卷积，一般来说，这个卷积核是已知的，比如各种边缘检测算子、高斯模糊等这些，都是已经知道卷积核，然后再与图像进行卷积运算。然而深度学习中的卷积神经网络卷积核是未知的，我们训练一个神经网络，就是要训练得出这些卷积核，而这些卷积核就相当于我们学单层感知器的时候的那些参数W，因此你可以把这些待学习的卷积核看成是神经网络的训练参数W。 **2、池化** 刚开始学习CNN的时候，看到这个词，好像高大上的样子，于是查了很多资料，理论一大堆，但是实践、算法实现却都没讲到，也不懂池化要怎么实现？其实所谓的池化，就是图片下采样。这个时候，你会发现CNN每一层的构建跟图像高斯金字塔的构建有点类似，因此你如果已经懂得了图像金字塔融合的相关算法，那么就变的容易理解了。在高斯金子塔构建中，每一层通过卷积，然后卷积后进行下采样，而CNN也是同样的过程。废话不多说，这里就讲一下，CNN的池化： CNN的池化(图像下采样)方法很多：Mean pooling(均值采样)、Max pooling(最大值采样)、Overlapping (重叠采样)、L2 pooling(均方采样)、Local Contrast Normalization(归一化采样)、Stochasticpooling(随即采样)、Def-pooling(形变约束采样)。其中最经典的是最大池化，因此我就解释一下最大池化的实现：  原图片 为了简单起见，我用上面的图片作为例子，假设上面的图片大小是4*4的，如上图所示，然后图片中每个像素点的值是上面各个格子中的数值。然后我要对这张4*4的图片进行池化，池化的大小为(2,2)，跨步为2，那么采用最大池化也就是对上面4*4的图片进行分块，每个块的大小为2*2，然后统计每个块的最大值，作为下采样后图片的像素值，具体计算如下图所示：  也就是说我们最后得到下采样后的图片为：  这就是所谓的最大池化。当然以后你还会遇到各种池化方法，比如均值池化，也就是对每个块求取平均值作为下采样的新像素值。还有重叠采样的池化，我上面这个例子是没有重叠的采样的，也就是每个块之间没有相互重叠的部分，上面我说的跨步为2，就是为了使得分块都非重叠，等等，这些以后再跟大家解释池化常用方法。这里就先记住最大池化就好了，因为这个目前是最常用的。 **3、feature maps** 这个单词国人把它翻译成特征图，挺起来很专业的名词。那么什么叫特征图呢？其实一张图片经过一个卷积核进行卷积运算，我们可以得到一张卷积后的结果图片，而这张图片就是特征图。在CNN中，我们要训练的卷积核并不是仅仅只有一个，这些卷积核用于提取特征，卷积核个数越多，提取的特征越多，理论上来说精度也会更高，然而卷积核一堆，意味着我们要训练的参数的个数越多。在LeNet-5经典结构中，第一层卷积核选择了6个，而在AlexNet中，第一层卷积核就选择了96个，具体多少个合适，还有待学习。 回到特征图概念，CNN的每一个卷积层我们都要人为的选取合适的卷积核个数，及卷积核大小。每个卷积核与图片进行卷积，就可以得到一张特征图了，比如LeNet-5经典结构中，第一层卷积核选择了6个，我们可以得到6个特征图，这些特征图也就是下一层网络的输入了。我们也可以把输入图片看成一张特征图，作为第一层网络的输入。 **4、CNN的经典结构** 对于刚入门CNN的人来说，我们首先需要现在的一些经典结构： **(1)LeNet-5**。这个是n多年前就有的一个CNN的经典结构，主要是用于手写字体的识别，也是刚入门需要学习熟悉的一个网络，我的这篇博文主要就是要讲这个网络  **(2)AlexNet。**  在imagenet上的图像分类challenge上大神Alex提出的alexnet网络结构模型赢得了2012届的冠军，振奋人心，利用CNN实现了图片分类，别人用传统的神经网络调参跳到半死也就那样，Alex利用CNN精度远超传统的网络。 其它的还有什么《Network In Network》，GoogLeNet、Deconvolution Network，在以后的学习中我们会遇到。比如利用Deconvolution Network反卷积网络实现图片的去模糊，牛逼哄哄。     OK，理论阶段就啰嗦到这里就好了，接着就讲解 LeNet-5， LeNet-5是用于手写字体的识别的一个经典CNN：  **LeNet-5结构** **输入：**32*32的手写字体图片，这些手写字体包含0~9数字，也就是相当于10个类别的图片 **输出：**分类结果，0~9之间的一个数 因此我们可以知道，这是一个多分类问题，总共有十个类，因此神经网络的最后输出层必然是SoftMax问题，然后神经元的个数是10个。LeNet-5结构： 输入层：32*32的图片，也就是相当于1024个神经元 **C1层：**paper作者，选择6个特征卷积核，然后卷积核大小选择5*5，这样我们可以得到6个特征图，然后每个特征图的大小为32-5+1=28，也就是神经元的个数由1024减小到了28*28=784。 **S2层：**这就是下采样层，也就是使用最大池化进行下采样，池化的size，选择(2,2)，也就是相当于对C1层28*28的图片，进行分块，每个块的大小为2*2，这样我们可以得到14*14个块，然后我们统计每个块中，最大的值作为下采样的新像素，因此我们可以得到S1结果为：14*14大小的图片，共有6个这样的图片。 **C3层**：卷积层，这一层我们选择卷积核的大小依旧为5*5，据此我们可以得到新的图片大小为14-5+1=10，然后我们希望可以得到16张特征图。那么问题来了？这一层是最难理解的，我们知道S2包含：6张14*14大小的图片，我们希望这一层得到的结果是：16张10*10的图片。这16张图片的每一张，是通过S2的6张图片进行加权组合得到的，具体是怎么组合的呢？问题如下图所示：  为了解释这个问题，我们先从简单的开始，我现在假设输入6特征图的大小是5*5的，分别用6个5*5的卷积核进行卷积，得到6个卷积结果图片大小为1*1，如下图所示：      为了简便起见，我这里先做一些标号的定义：我们假设输入第i个特征图的各个像素值为x1i，x2i……x25i，因为每个特征图有25个像素。因此第I个特征图经过5*5的图片卷积后，得到的卷积结果图片的像素值Pi可以表示成：  这个是卷积公式，不解释。因此对于上面的P1~P6的计算方法，这个就是直接根据公式。然后我们把P1~P6相加起来，也就是： P=P1+P2+……P6 把上面的Pi的计算公式，代入上式，那么我们可以得到： P=WX 其中X就是输入的那6张5*5特征图片的各个像素点值，而W就是我们需要学习的参数，也就相当于6个5*5的卷积核，当然它包含着6*（5*5）个参数。因此我们的输出特征图就是： Out=f(P+b) 这个就是从S2到C3的计算方法，其中b表示偏置项，f为激活函数。 我们回归到原来的问题：有6张输入14*14的特征图片，我们希望用5*5的卷积核，然后最后我们希望得到一张10*10的输出特征图片？ 根据上面的过程，也就是其实我们用5*5的卷积核去卷积每一张输入的特征图，当然每张特征图的卷积核参数是不一样的，也就是不共享，因此我们就相当于需要6*(5*5)个参数。对每一张输入特征图进行卷积后，我们得到6张10*10，新图片，这个时候，我们把这6张图片相加在一起，然后加一个偏置项b，然后用激活函数进行映射，就可以得到一张10*10的输出特征图了。     而我们希望得到16张10*10的输出特征图，因此我们就需要卷积参数个数为16*(6*(5*5))=16*6*(5*5)个参数。总之，C3层每个图片是通过S2图片进行卷积后，然后相加，并且加上偏置b,最后在进行激活函数映射得到的结果。 **S4层：**下采样层，比较简单，也是知己对C3的16张10*10的图片进行最大池化，池化块的大小为2*2。因此最后S4层为16张大小为5*5的图片。至此我们的神经元个数已经减少为：16*5*5=400。 **C5层：**我们继续用5*5的卷积核进行卷积，然后我们希望得到120个特征图。这样C5层图片的大小为5-5+1=1，也就是相当于1个神经元，120个特征图，因此最后只剩下120个神经元了。这个时候，神经元的个数已经够少的了，后面我们就可以直接利用全连接神经网络，进行这120个神经元的后续处理，后面具体要怎么搞，只要懂多层感知器的都懂了，不解释。 上面的结构，只是一种参考，在现实使用中，每一层特征图需要多少个，卷积核大小选择，还有池化的时候采样率要多少，等这些都是变化的，这就是所谓的CNN调参，我们需要学会灵活多变。 比如我们可以把上面的结构改为:C1层卷积核大小为7*7，然后把C3层卷积核大小改为3*3等，然后特征图的个数也是自己选，说不定得到手写字体识别的精度比上面那个还高，这也是有可能的，总之一句话：需要学会灵活多变，需要学会CNN的调参。 ###二、实战阶段 **1、训练数据获取** 在theano学习库中有手写字体的库，可以从网上下载到，名为：mnist.pkl.gz的手写字体库，里面包含了三个部分的数据，训练数据集train_set：50000个训练样本，验证集valid_set，我们可以用如下的代码读取这些数据，然后用plot显示其中的一张图片: ~~~ <span style="font-size:18px;">import cPickle import gzip import numpy as np import matplotlib.pyplot as plt f = gzip.open('mnist.pkl.gz', 'rb') train_set, valid_set, test_set = cPickle.load(f) f.close() tx,ty=train_set; #查看训练样本 print np.shape(tx)#可以看到tx大小为（50000,28*28）的二维矩阵 print np.shape(ty)#可以看到ty大小为（50000,1）的矩阵 #图片显示 A=tx[8].reshape(28,28)#第八个训练样本 Y=ty[8] print Y plt.imshow(A,cmap='gray')#显示手写字体图片</span> ~~~ 在上面的代码中我显示的是第8张图片，可以看到如下结果：  第八个样本是数字1。 **2、LeNet-5实现** 首先你要知道mnist.pkl.gz这个库给我们的图片的大小是28*28的，因此我们可以第一步选择5*5的卷积核进行卷积得到24*24，同时我们希望C1层得到20张特征图，等等，具体的代码实现如下; ~~~ import os import sys import timeit import numpy import theano import theano.tensor as T from theano.tensor.signal import downsample from theano.tensor.nnet import conv from logistic_sgd import LogisticRegression, load_data from mlp import HiddenLayer #卷积神经网络的一层，包含：卷积+下采样两个步骤 #算法的过程是：卷积-》下采样-》激活函数 class LeNetConvPoolLayer(object): #image_shape是输入数据的相关参数设置 filter_shape本层的相关参数设置 def __init__(self, rng, input, filter_shape, image_shape, poolsize=(2, 2)): """ :type rng: numpy.random.RandomState :param rng: a random number generator used to initialize weights 3、input: 输入特征图数据，也就是n幅特征图片 4、参数 filter_shape: (number of filters, num input feature maps, filter height, filter width) num of filters：是卷积核的个数，有多少个卷积核，那么本层的out feature maps的个数 也将生成多少个。num input feature maps：输入特征图的个数。 然后接着filter height, filter width是卷积核的宽高，比如5*5,9*9…… filter_shape是列表，因此我们可以用filter_shape[0]获取卷积核个数 5、参数 image_shape: (batch size, num input feature maps, image height, image width)， batch size：批量训练样本个数 ，num input feature maps：输入特征图的个数 image height, image width分别是输入的feature map图片的大小。 image_shape是一个列表类型，所以可以直接用索引，访问上面的4个参数，索引下标从 0~3。比如image_shape[2]=image_heigth image_shape[3]=num input feature maps 6、参数 poolsize: 池化下采样的的块大小，一般为(2,2) """ assert image_shape[1] == filter_shape[1]#判断输入特征图的个数是否一致，如果不一致是错误的 self.input = input # fan_in=num input feature maps *filter height*filter width #numpy.prod(x)函数为计算x各个元素的乘积 #也就是说fan_in就相当于每个即将输出的feature map所需要链接参数权值的个数 fan_in = numpy.prod(filter_shape[1:]) # fan_out=num output feature maps * filter height * filter width fan_out = (filter_shape[0] * numpy.prod(filter_shape[2:]) / numpy.prod(poolsize)) # 把参数初始化到[-a,a]之间的数，其中a=sqrt(6./(fan_in + fan_out)),然后参数采用均匀采样 #权值需要多少个？卷积核个数*输入特征图个数*卷积核宽*卷积核高？这样没有包含采样层的链接权值个数 W_bound = numpy.sqrt(6. / (fan_in + fan_out)) self.W = theano.shared( numpy.asarray( rng.uniform(low=-W_bound, high=W_bound, size=filter_shape), dtype=theano.config.floatX ), borrow=True ) # b为偏置，是一维的向量。每个输出特征图i对应一个偏置参数b[i] #,因此下面初始化b的个数就是特征图的个数filter_shape[0] b_values = numpy.zeros((filter_shape[0],), dtype=theano.config.floatX) self.b = theano.shared(value=b_values, borrow=True) # 卷积层操作，函数conv.conv2d的第一个参数为输入的特征图，第二个参数为随机出事化的卷积核参数 #第三个参数为卷积核的相关属性，输入特征图的相关属性 conv_out = conv.conv2d( input=input, filters=self.W, filter_shape=filter_shape, image_shape=image_shape ) # 池化操作，最大池化 pooled_out = downsample.max_pool_2d( input=conv_out, ds=poolsize, ignore_border=True ) #激励函数，也就是说是先经过卷积核再池化后，然后在进行非线性映射 # add the bias term. Since the bias is a vector (1D array), we first # reshape it to a tensor of shape (1, n_filters, 1, 1). Each bias will # thus be broadcasted across mini-batches and feature map # width & height self.output = T.tanh(pooled_out + self.b.dimshuffle('x', 0, 'x', 'x')) # 保存参数 self.params = [self.W, self.b] self.input = input #测试函数 def evaluate_lenet5(learning_rate=0.1, n_epochs=200, dataset='mnist.pkl.gz', nkerns=[20, 50], batch_size=500): """ Demonstrates lenet on MNIST dataset :learning_rate: 梯度下降法的学习率 :n_epochs: 最大迭代次数 :type dataset: string :param dataset: path to the dataset used for training /testing (MNIST here) :nkerns: 每个卷积层的卷积核个数，第一层卷积核个数为 nkerns[0]=20,第二层卷积核个数 为50个 """ rng = numpy.random.RandomState(23455) datasets = load_data(dataset)#加载训练数据，训练数据包含三个部分 train_set_x, train_set_y = datasets[0]#训练数据 valid_set_x, valid_set_y = datasets[1]#验证数据 test_set_x, test_set_y = datasets[2]#测试数据 # 计算批量训练可以分多少批数据进行训练，这个只要是知道批量训练的人都知道 n_train_batches = train_set_x.get_value(borrow=True).shape[0]#训练数据个数 n_valid_batches = valid_set_x.get_value(borrow=True).shape[0] n_test_batches = test_set_x.get_value(borrow=True).shape[0] n_train_batches /= batch_size#批数 n_valid_batches /= batch_size n_test_batches /= batch_size # allocate symbolic variables for the data index = T.lscalar() # index to a [mini]batch # start-snippet-1 x = T.matrix('x') # the data is presented as rasterized images y = T.ivector('y') # the labels are presented as 1D vector of # [int] labels # Reshape matrix of rasterized images of shape (batch_size, 28 * 28) # to a 4D tensor, compatible with our LeNetConvPoolLayer # (28, 28) is the size of MNIST images. layer0_input = x.reshape((batch_size, 1, 28, 28)) '''''构建第一层网络： image_shape：输入大小为28*28的特征图，batch_size个训练数据，每个训练数据有1个特征图 filter_shape：卷积核个数为nkernes[0]=20，因此本层每个训练样本即将生成20个特征图 经过卷积操作，图片大小变为(28-5+1 , 28-5+1) = (24, 24) 经过池化操作，图片大小变为 (24/2, 24/2) = (12, 12) 最后生成的本层image_shape为(batch_size, nkerns[0], 12, 12)''' layer0 = LeNetConvPoolLayer( rng, input=layer0_input, image_shape=(batch_size, 1, 28, 28), filter_shape=(nkerns[0], 1, 5, 5), poolsize=(2, 2) ) '''''构建第二层网络：输入batch_size个训练图片，经过第一层的卷积后，每个训练图片有nkernes[0]个特征图，每个特征图 大小为12*12 经过卷积后，图片大小变为(12-5+1, 12-5+1) = (8, 8) 经过池化后，图片大小变为(8/2, 8/2) = (4, 4) 最后生成的本层的image_shape为(batch_size, nkerns[1], 4, 4)''' layer1 = LeNetConvPoolLayer( rng, input=layer0.output, image_shape=(batch_size, nkerns[0], 12, 12), filter_shape=(nkerns[1], nkerns[0], 5, 5), poolsize=(2, 2) ) # the HiddenLayer being fully-connected, it operates on 2D matrices of # shape (batch_size, num_pixels) (i.e matrix of rasterized images). # This will generate a matrix of shape (batch_size, nkerns[1] * 4 * 4), # or (500, 50 * 4 * 4) = (500, 800) with the default values. layer2_input = layer1.output.flatten(2) '''''全链接：输入layer2_input是一个二维的矩阵，第一维表示样本，第二维表示上面经过卷积下采样后 每个样本所得到的神经元，也就是每个样本的特征，HiddenLayer类是一个单层网络结构 下面的layer2把神经元个数由800个压缩映射为500个''' layer2 = HiddenLayer( rng, input=layer2_input, n_in=nkerns[1] * 4 * 4, n_out=500, activation=T.tanh ) # 最后一层：逻辑回归层分类判别，把500个神经元，压缩映射成10个神经元，分别对应于手写字体的0~9 layer3 = LogisticRegression(input=layer2.output, n_in=500, n_out=10) # the cost we minimize during training is the NLL of the model cost = layer3.negative_log_likelihood(y) # create a function to compute the mistakes that are made by the model test_model = theano.function( [index], layer3.errors(y), givens={ x: test_set_x[index * batch_size: (index + 1) * batch_size], y: test_set_y[index * batch_size: (index + 1) * batch_size] } ) validate_model = theano.function( [index], layer3.errors(y), givens={ x: valid_set_x[index * batch_size: (index + 1) * batch_size], y: valid_set_y[index * batch_size: (index + 1) * batch_size] } ) #把所有的参数放在同一个列表里，可直接使用列表相加 params = layer3.params + layer2.params + layer1.params + layer0.params #梯度求导 grads = T.grad(cost, params) # train_model is a function that updates the model parameters by # SGD Since this model has many parameters, it would be tedious to # manually create an update rule for each model parameter. We thus # create the updates list by automatically looping over all # (params[i], grads[i]) pairs. updates = [ (param_i, param_i - learning_rate * grad_i) for param_i, grad_i in zip(params, grads) ] train_model = theano.function( [index], cost, updates=updates, givens={ x: train_set_x[index * batch_size: (index + 1) * batch_size], y: train_set_y[index * batch_size: (index + 1) * batch_size] } ) # end-snippet-1 ############### # TRAIN MODEL # ############### print '... training' # early-stopping parameters patience = 10000 # look as this many examples regardless patience_increase = 2 # wait this much longer when a new best is # found improvement_threshold = 0.995 # a relative improvement of this much is # considered significant validation_frequency = min(n_train_batches, patience / 2) # go through this many # minibatche before checking the network # on the validation set; in this case we # check every epoch best_validation_loss = numpy.inf best_iter = 0 test_score = 0. start_time = timeit.default_timer() epoch = 0 done_looping = False while (epoch < n_epochs) and (not done_looping): epoch = epoch + 1 for minibatch_index in xrange(n_train_batches):#每一批训练数据 cost_ij = train_model(minibatch_index) iter = (epoch - 1) * n_train_batches + minibatch_index if (iter + 1) % validation_frequency == 0: # compute zero-one loss on validation set validation_losses = [validate_model(i) for i in xrange(n_valid_batches)] this_validation_loss = numpy.mean(validation_losses) print('epoch %i, minibatch %i/%i, validation error %f %%' % (epoch, minibatch_index + 1, n_train_batches, this_validation_loss * 100.)) # if we got the best validation score until now if this_validation_loss < best_validation_loss: #improve patience if loss improvement is good enough if this_validation_loss < best_validation_loss * \ improvement_threshold: patience = max(patience, iter * patience_increase) # save best validation score and iteration number best_validation_loss = this_validation_loss best_iter = iter # test it on the test set test_losses = [ test_model(i) for i in xrange(n_test_batches) ] test_score = numpy.mean(test_losses) print((' epoch %i, minibatch %i/%i, test error of ' 'best model %f %%') % (epoch, minibatch_index + 1, n_train_batches, test_score * 100.)) if patience <= iter: done_looping = True break end_time = timeit.default_timer() print('Optimization complete.') print('Best validation score of %f %% obtained at iteration %i, ' 'with test performance %f %%' % (best_validation_loss * 100., best_iter + 1, test_score * 100.)) print >> sys.stderr, ('The code for file ' + os.path.split(__file__)[1] + ' ran for %.2fm' % ((end_time - start_time) / 60.)) if __name__ == '__main__': evaluate_lenet5() def experiment(state, channel): evaluate_lenet5(state.learning_rate, dataset=state.dataset) ~~~ 训练结果：  **参考文献：** 1、http://blog.csdn.net/zouxy09/article/details/8775360/ 2、http://www.deeplearning.net/tutorial/lenet.html#lenet 作者：hjimce   时间：2015.8.6  联系QQ：1393852684   地址：[http://blog.csdn.net/hjimce](http://blog.csdn.net/hjimce) 转载请保留本行信息

    注明：转载自博客http://blog.csdn.net/datoubo/article/details/8577366

2015 深度学习、自编码器、低照度图像增强 Lore, Kin Gwn, Adedotun Akintayo, and Soumik Sarkar. "LLNet: A Deep Autoencoder Approach to Natural Low-light Image Enhancement." arXiv preprint arXiv:1511.03995 (2015). 利用深度学习的自编码器方法训练不同低照度图像信号的特征来实现自适应变亮和去噪，主要是通过非线性暗化和添加高斯噪声的方法来模拟低照度环境，进行图像对比度增强和去噪。 2014 深度学习、深度卷积神经网络、图像去卷积 Xu, Li, et al. "Deep convolutional neural network for image deconvolution."Advances in Neural Information Processing Systems. 2014. 利用深度卷积神经网络进行图像去卷积，实现图像复原，优点：相比于当前其他方法，有更好的PSNR值和视觉效果。 2014 深度学习、稀疏编码、自编码器、图像去噪 Li, HuiMing. "Deep Learning for Image Denoising." International Journal of Signal Processing, Image Processing and Pattern Recognition 7.3 (2014): 171-180. 利用稀疏编码（sparsecoding）与自编码器（Auto-encoder）两种方法结合来实现图像去噪，不足之处是只对图像进行处理，没有涉及视频。 2014 深度学习、rectified linear函数、深度神经网络、图像去噪 Wu, Yangwei, Haohua Zhao, and Liqing Zhang. "Image Denoising with Rectified Linear Units." Neural Information Processing. Springer International Publishing, 2014. 利用rectified linear (Re L) 函数代替sigmoid 函数作为深度神经网络的隐藏层的激活函数，来实现图像去噪；利用随机梯度下降的方法训练含噪图像和无噪图像来估计神经网络的参数；优点：和sigmoid函数作为激活函数的深度神经网络相比，能得到更好的去噪效果和更快的收敛速度。 2013 深度学习、堆叠式稀疏去噪自编码器SSDAs、深度神经网络DNN、图像去噪 Agostinelli, Forest, Michael R. Anderson, and Honglak Lee. "Robust image denoising with multi-column deep neural networks." Advances in Neural Information Processing Systems. 2013. 利用改进的堆叠式稀疏去噪自编码器(Stacked sparse denoising autoencoders (SSDAs))，通过组合多个SSDAs，求解一个非线性优化方程计算每个SSDAs的最优权重，同时训练单独的网络去预测最优权重，实现视频去噪。优点：解决了SSDAs只能处理训练集中出现的噪声，这种方法可以处理训练集未出现的噪声类型。 2012 深度学习、多层感知器、图像去噪 Burger, Harold C., Christian J. Schuler, and Stefan Harmeling. "Image denoising: Can plain Neural Networks compete with BM3D?." Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on. IEEE, 2012. 利用普通的多层感知器plain multi layer perceptron(MLP)实现图像去噪。 2012 深度学习、稀疏编码、去噪自编码器、图像去噪 Xie, Junyuan, Linli Xu, and Enhong Chen. "Image denoising and  inpainting with deep neural networks." Advances in Neural Information Processing Systems. 2012. 将稀疏编码（sparse coding）与去噪自编码器(denoising auto-encoders)预训练的深度神经网络相结合进行图像去噪，噪声类型：高斯白噪声的灰度图像，但是稍微扩展下也可以处理彩色图，优点：比线性稀疏编码去除高斯白噪声的效果要好，不足之处：非常依赖有监督的训练，只能除去训练集中出现的噪声。 2012 深度学习、多层感知器、图像去噪 Burger, Harold Christopher, Christian J. Schuler, and Stefan Harmeling. "Image denoising with multi-layer perceptrons, part 1: comparison with existing algorithms and with bounds." arXiv preprint arXiv:1211.1544 (2012). 利用多层感知器Multi-layer perceptions(MLP) 的方法实现图像去噪，噪声类型：This approach is easily adapted to less extensively studied types of noise, such as mixed Poisson-Gaussian noise, JPEG artifacts, salt-and-pepper noise and noise resembling stripes. 2010 深度学习、堆叠式去噪自编码器、图像去噪 Vincent, Pascal, et al. "Stacked denoising autoencoders: Learning useful representations in a deep network with a local denoising criterion." The Journal of Machine Learning Research 11 (2010): 3371-3408. 利用堆叠式去噪自编码器（SDA）的方法进行图像去噪，堆叠式自编码器这种方法是深度学习中构建深度架构的重要方法之一。当训练出一个自编码器后，就可以在此基础上通过将第一个自编码器的输出作为第二个自编码器的输入继续训练出一个新的自编码器。这样继续训练下去就可以得到一个多层的堆叠式自编码器（Stacked  Autoencoders）。 2009 深度学习、卷积网络、图像去噪 Jain, Viren, and Sebastian Seung. "Natural image denoising with convolutional networks." Advances in Neural Information Processing Systems. 2009. 利用卷积网络实现自然图像去噪。

最近微信朋友圈很多人在转发的一个游戏叫做“微软小冰读心术”，游戏的规则很简单：参与游戏的一方在脑海里想好一个人的名字，然后微软小冰会问你15个问题，问题的答案只能用“是”、“不是”或者“不知道”回答。    微软小冰通过你的回答进行推断分解，逐步缩小待猜测人名的范围，决策树的工作原理与这些问题类似，用户输入一系列数据，然后会给出游戏的答案。 ###一、决策树简介 决策树（decision tree）是机器学习与数据挖掘中一种十分常用的分类和回归方法，属于有监督学习（supervised learning）算法。通俗来说，决策树分类的思想类似于找对象。现在想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话： 女儿：多大年纪了？ 母亲：26。 女儿：长的帅不帅？ 母亲：挺帅的。 女儿：收入高不？ 母亲：不算很高，中等情况。 女儿：是公务员不？ 母亲：是，在税务局上班呢。 女儿：那好，我去见见。 这个女孩的决策过程就是典型的决策树方法。相当于通过年龄、长相、收入和是否公务员对将男人分为两个类别：见和不见。假设这个女孩对男人的要求是：30岁以下、长相中等以上并且是高收入者或中等以上收入的公务员，那么这个可以用下图表示女孩的决策逻辑：  决策树是一种树型结构，其中每个内部结点表示在一个属性上的测试，每个分支代表一个测试输出，每个叶结点代表一个类别。 决策树学习是以实例为基础的归纳学习，决策树学习采用的是自顶向下的递归方法，其基本思想是以信息熵为度量构造一棵熵值（熵的概念请参考信息论的书籍）下降最快的树，到叶子结点处的熵值为零，此时，每个叶结点中的实例都属于同一类。 ###二、决策树的构造 1.创建分支 创建分支的伪代码函数createBranch()如下所示： 检测数据集中的每一个子项是否属于同一类； If so return 类标签； Else     寻找划分数据集的最好特征；     划分数据集；     创建分支结点；         for 每个划分的子集             调用函数createBranch()并增加返回结果到分支结点中      return 分支结点； 上面的伪代码createBranch()是一个递归函数，在倒数第二行直接调用了它本身。  上表的数据包含5个海洋生物，特征包括：不浮出水面是否可以生存，以及是否有脚蹼。 我们可以将这些生物分成两类：鱼类和非鱼类，现在我们想要决定依据第一个特征还是第二个特征来划分数据。 在讨论这个问题前，我们先了解决策树算法中的一些信息论概念： 1.信息量 定义事件X发生的信息量为：  某事件发生的概率越小，则该事件的信息量越大，一定发生和一定不会发生的必然事件的信息量为0。 例如，今天是22号，别人说明天是23号，这就没有一点信息量。 2.信息熵 信息熵是信息量的期望，定义为：  其中p(x)是，事件x发生的概率。信息熵一般用来表征事件或变量的不确定性，变量的不确定性越大，信息熵就越大。一个系统越有序，它的信息熵就越小，反之，一个混乱的系统信息熵越大，所以信息熵是系统有序化程度的一个度量。 3.联合熵和条件熵 两个随机变量X、Y的联合分布形成联合熵H(X,Y)，已知Y发生的前提下，X的熵叫做条件熵H(X|Y)。  4.互信息两个随机变量X、Y的互信息定义为X、Y的信息熵减去X、Y的联合熵。   5.信息增益 信息熵又称为先验熵，是在信息发送前信息量的数学期望，后验熵是指信息发送后，从信宿（即信息的接收者）角度对信息量的数学期望。一般先验熵大于后验熵，先验熵与后验熵的差就是信息增益，反映的是信息消除随机不确定性的程度。  决策树学习中的信息增益等价于训练集中类别与特征的互信息。 信息增益表示得知特征A的信息而使得类X的信息的不确定性减少的程度。 划分数据集的最大原则是：将无序的数据变得更加有序。划分数据集前后信息发送的变化就行信息增益，通过计算每个特征值划分数据集获得的信息增益，我们就可以根据获得信息增益最高的特征来选择其作为划分数据的特征。  信息增益的计算方法：  （1）计算给定数据集的信息熵 ~~~ from math import log def calcShannonEnt(dataSet): numEntries = len(dataSet) labelCounts = {} for featVec in dataSet: #the the number of unique elements and their occurance currentLabel = featVec[-1] if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0 labelCounts[currentLabel] += 1 shannonEnt = 0.0 for key in labelCounts: prob = float(labelCounts[key])/numEntries shannonEnt -= prob * log(prob,2) #log base 2 return shannonEnt ~~~ 代码解析：首先，计算数据集中实例的总数numEntries，然后创建一个字典，它的键值是最后一列的数值，如果当前键值不存在，则扩展字典并将当前键值加入字典，每个键值都记录了当前类别出现的次数labelCounts，最后，使用所有类别标签的发生频率计算类别出现的概率。 （2）创建数据集 利用createDataSet（）函数得到表3-1所示的简单鱼鉴定数据集： ~~~ def createDataSet(): dataSet = [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']] labels = ['no surfacing','flippers'] #change to discrete values return dataSet, labels ~~~  （3）划分数据集 对每个特征划分数据集的结果计算一次信息熵，然后判断按照哪个特征划分数据集是最后的划分方式。 ~~~ def splitDataSet(dataSet, axis, value): retDataSet = [] for featVec in dataSet: if featVec[axis] == value: reducedFeatVec = featVec[:axis] #chop out axis used for splitting reducedFeatVec.extend(featVec[axis+1:]) retDataSet.append(reducedFeatVec) return retDataSet ~~~ 代码解析：spiltDataSet()的三个输入参数分别是待划分数据集dataSet、划分数据集的特征axis、需要返回的特征的值。遍历数据集中的每个元素，一旦发现符合要求的值，则将其添加到新创建的列表中。  选择最好的数据集划分方式： ~~~ def chooseBestFeatureToSplit(dataSet): numFeatures = len(dataSet[0]) - 1 #the last column is used for the labels baseEntropy = calcShannonEnt(dataSet) bestInfoGain = 0.0; bestFeature = -1 for i in range(numFeatures): #iterate over all the features featList = [example[i] for example in dataSet]#create a list of all the examples of this feature uniqueVals = set(featList) #get a set of unique values newEntropy = 0.0 for value in uniqueVals: subDataSet = splitDataSet(dataSet, i, value) prob = len(subDataSet)/float(len(dataSet)) newEntropy += prob * calcShannonEnt(subDataSet) infoGain = baseEntropy - newEntropy #calculate the info gain; ie reduction in entropy if (infoGain > bestInfoGain): #compare this to the best gain so far bestInfoGain = infoGain #if better than current best, set to best bestFeature = i return bestFeature #returns an integer ~~~  代码运行结果告诉我们，第0个特征是最好的用于划分数据集的特征。数据集的数据来源于表3-1，  如果我们按照第一个特征属性划分数据，也就是说第一个特征为1的放在一组，第一个特征是0的放在另一个组，按照这种方式划分的话，第一个特征为1的海洋生物分组将有两个属于鱼类，一个属于非鱼类；另一个分组则全部属于非鱼类。 如果我们按照第二个特征分组，第一个海洋生物分组将有两个属于鱼类，两个属于非鱼类；另一个分组则只有一个非鱼类。 可以看出，第一种划分很好地处理了相关数据。 （4）递归构建决策树 ~~~ def majorityCnt(classList): classCount={} for vote in classList: if vote not in classCount.keys(): classCount[vote] = 0 classCount[vote] += 1 sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True) return sortedClassCount[0][0] ~~~ 创建决策树的函数代码： ~~~ def createTree(dataSet,labels): classList = [example[-1] for example in dataSet] if classList.count(classList[0]) == len(classList): return classList[0]#stop splitting when all of the classes are equal if len(dataSet[0]) == 1: #stop splitting when there are no more features in dataSet return majorityCnt(classList) bestFeat = chooseBestFeatureToSplit(dataSet) bestFeatLabel = labels[bestFeat] myTree = {bestFeatLabel:{}} del(labels[bestFeat]) featValues = [example[bestFeat] for example in dataSet] uniqueVals = set(featValues) for value in uniqueVals: subLabels = labels[:] #copy all of labels, so trees don't mess up existing labels myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels) return myTree ~~~  ###三、决策树的过拟合 决策树对训练属于有很好的分类能力，但对未知的预测数据未必有好的分类能力，泛化能力较弱，即可能发生过拟合现象。 解决过拟合的方法： 1.剪枝 2.随机森林

本文主要利用k-近邻分类器实现手写识别系统，训练数据集大约2000个样本，每个数字大约有200个样本，每个样本保存在一个txt文件中，手写体图像本身是32X32的二值图像，如下图所示：  首先，我们需要将图像格式化处理为一个向量，把一个32X32的二进制图像矩阵通过img2vector()函数转换为1X1024的向量： ~~~ def img2vector(filename): returnVect = zeros((1,1024)) fr = open(filename) for i in range(32): lineStr = fr.readline() for j in range(32): returnVect[0,32*i+j] = int(lineStr[j]) return returnVect ~~~  手写数字识别系统的测试代码： ~~~ def handwritingClassTest(): hwLabels = [] trainingFileList = listdir('trainingDigits') #load the training set m = len(trainingFileList) trainingMat = zeros((m,1024)) for i in range(m): fileNameStr = trainingFileList[i] fileStr = fileNameStr.split('.')[0] #take off .txt classNumStr = int(fileStr.split('_')[0]) hwLabels.append(classNumStr) trainingMat[i,:] = img2vector('trainingDigits/%s' % fileNameStr) testFileList = listdir('testDigits') #iterate through the test set errorCount = 0.0 mTest = len(testFileList) for i in range(mTest): fileNameStr = testFileList[i] fileStr = fileNameStr.split('.')[0] #take off .txt classNumStr = int(fileStr.split('_')[0]) vectorUnderTest = img2vector('testDigits/%s' % fileNameStr) classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3) print "the classifier came back with: %d, the real answer is: %d" % (classifierResult, classNumStr) if (classifierResult != classNumStr): errorCount += 1.0 print "\nthe total number of errors is: %d" % errorCount print "\nthe total error rate is: %f" % (errorCount/float(mTest)) ~~~ 在Python命令提示符中输入kNN.handwritingClassTest()，测试该函数的输出结果：    注：本文的相关代码均来源于Peter Harringtor的《机器学习实战》

[利用KNN算法改进约会网站的配对效果](http://blog.csdn.net/geekmanong/article/details/50523331) ### 一、案例背景 我的朋友海伦一直使用在线约会网站寻找合适自己的约会对象。尽管约会网站会推荐不同的人选，但她并不是喜欢每一个人。经过一番总结，她发现曾交往过三种类型的人： （1）不喜欢的人； （2）魅力一般的人； （3）极具魅力的人； 尽管发现了上述规律，但海伦依然无法将约会网站推荐的匹配对象归入恰当的分类，她觉得可以在周一到周五约会那些魅力一般的人，而周末则更喜欢与那些极具魅力的人为伴。海伦希望我们的分类软件可以更好地帮助她将匹配对象划分到确切的分类中。此外，海伦还收集了一些约会网站未曾记录的数据信息，她认为这些数据更助于匹配对象的归类。 ### 二、案例分析 （1）收集数据：提供文本文件； （2）准备数据：使用Python解析文本文件； （3）分析数据：使用Matplotlib画二维扩散图； （4）训练算法：此步骤不适用于K-近邻算法； （5）测试算法：使用海伦提供的部分数据作为测试样本，          测试样本和非测试样本的区别在于：测试样本是已经完成分类的数据，如果预测分类与实际类别不同，则标记为一个错误。 （6）使用算法：产生简单的命令行程序，然后海伦可以输入一些特征数据以判断对方是否为自己喜欢的类型。 ### 三、准备数据：从文本文件中解析数据 海伦收集约会数据已经有了一段时间，她把这些数据存放在文本文件datingTestSet.txt中，每个样本数据占据一行，总共有1000行。海伦的样本主要包括以下3种特征： 1.每年获得的飞行常客里程数； 2.玩视频游戏所耗时间百分比； 3.每周消费的冰淇淋公升数； 在将上述特征数据输入到分类器之前，必须将待处理数据的格式改变为分类器可以接受的格式。在kNN.py中创建名为file2matrix的函数，以此来处理输入格式问题。该函数的输入为文本文件名字符串，输出为训练样本矩阵和类标签向量。 将下面的代码增加到kNN.py中：  ### 四、分析数据：使用Matplotlib创建散点图 首先我们使用Matplotlib制作原始数据的散点图，在Python命令行环境中，输入下列命令： ~~~ #!/usr/bin/python278 # _*_ coding: utf-8 _*_ import kNN reload(kNN) datingDataMat,datingLabels=kNN.file2matrix('datingTestSet2.txt') import matplotlib import matplotlib.pyplot as plt zhfont = matplotlib.font_manager.FontProperties(fname='C:\Windows\Fonts\ukai.ttc') fig=plt.figure() ax=fig.add_subplot(111) from numpy import * ax.scatter(datingDataMat[:,1],datingDataMat[:,2]) plt.xlabel(u'玩游戏所耗时间百分比', fontproperties=zhfont) plt.ylabel(u'每周消费的冰淇淋公升数', fontproperties=zhfont) plt.show() ~~~  上图是没有样本标签的约会数据散点图，难以辨识图中的点究竟属于哪个样本分类，我们可以利用Matplotlib库提供的scatter函数来用彩色标记散点图上的点。重新输入上面的代码，调用scatter函数： ~~~ #!/usr/bin/python278 # _*_ coding: utf-8 _*_ import kNN reload(kNN) datingDataMat,datingLabels=kNN.file2matrix('datingTestSet2.txt') import matplotlib import matplotlib.pyplot as plt zhfont = matplotlib.font_manager.FontProperties(fname='C:\Windows\Fonts\ukai.ttc') fig=plt.figure() ax=fig.add_subplot(111) from numpy import * ax.scatter(datingDataMat[:,1],datingDataMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels)) plt.xlabel(u'玩游戏所耗时间百分比', fontproperties=zhfont) plt.ylabel(u'每周消费的冰淇淋公升数', fontproperties=zhfont) plt.show() ~~~  上图是带有样本分类标签的约会数据散点图，虽然能够比较容易地区分数据点从属类别，但依然很难根据这张图得出结论信息。 上图使用了datingDataMat矩阵属性列2和列3展示数据，虽然也可以区别，但下图采用列1和列2的属性值却可以得到更好的效果： ~~~ #!/usr/bin/env python # _*_ coding: utf-8 _*_ import kNN reload(kNN) import matplotlib import matplotlib.pyplot as plt matrix, labels = kNN.file2matrix('datingTestSet2.txt') print matrix print labels zhfont = matplotlib.font_manager.FontProperties(fname='C:\Windows\Fonts\ukai.ttc') plt.figure(figsize=(8, 5), dpi=80) axes = plt.subplot(111) # 将三类数据分别取出来 # x轴代表飞行的里程数 # y轴代表玩视频游戏的百分比 type1_x = [] type1_y = [] type2_x = [] type2_y = [] type3_x = [] type3_y = [] print 'range(len(labels)):' print range(len(labels)) for i in range(len(labels)): if labels[i] == 1: # 不喜欢 type1_x.append(matrix[i][0]) type1_y.append(matrix[i][1]) if labels[i] == 2: # 魅力一般 type2_x.append(matrix[i][0]) type2_y.append(matrix[i][1]) if labels[i] == 3: # 极具魅力 print i, '：', labels[i], ':', type(labels[i]) type3_x.append(matrix[i][0]) type3_y.append(matrix[i][1]) type1 = axes.scatter(type1_x, type1_y, s=20, c='red') type2 = axes.scatter(type2_x, type2_y, s=40, c='green') type3 = axes.scatter(type3_x, type3_y, s=50, c='blue') # plt.scatter(matrix[:, 0], matrix[:, 1], s=20 * numpy.array(labels), # c=50 * numpy.array(labels), marker='o', # label='test') plt.xlabel(u'每年获取的飞行里程数', fontproperties=zhfont) plt.ylabel(u'玩视频游戏所消耗的事件百分比', fontproperties=zhfont) axes.legend((type1, type2, type3), (u'不喜欢', u'魅力一般', u'极具魅力'), loc=2, prop=zhfont) plt.show() ~~~  图中清晰的标识了三个不同的样本分类区域，具有不同爱好的人其类别区域也不同，可以看出用图中展示的“每年获取飞行常客里程数”和“玩视频游戏所耗时间百分比”两个特征更容易区分数据点从属的类别。 ### 五、准备数据：归一化数值 为了防止特征值数量上的差异对预测结果的影响，比如计算距离时，量值较大的特征值对结果影响较大，所以我们对数据所有的特征值会进行归一化到[0,1]的预处理。 ~~~ def autoNorm(dataSet): minVals = dataSet.min(0) maxVals = dataSet.max(0) ranges = maxVals - minVals normDataSet = zeros(shape(dataSet)) m = dataSet.shape[0] normDataSet = dataSet - tile(minVals, (m,1)) normDataSet = normDataSet/tile(ranges, (m,1)) #element wise divide return normDataSet, ranges, minVals ~~~ 代码讲解：函数autoNorm()中，每列的最小值放在变量minVals中，最大值放在maxVals中，其中dataSet.min(0)中的参数0使得函数可以从列中选取最小值，而不是选取当前行的最小值。因为特征值矩阵dataSet是1000X3，而minVals和range都是1X3，所以需要利用tile()函数将minVals和range的内容复制成输入矩阵同样大小的矩阵。 ~~~ >>> import kNN >>> reload(kNN) <module 'kNN' from 'kNN.pyc'> >>> datingDataMat,datingLabels=kNN.file2matrix('datingTestSet2.txt') >>> normMat,ranges,minVals=kNN.autoNorm(datingDataMat) >>> normMat array([[ 0.44832535, 0.39805139, 0.56233353], [ 0.15873259, 0.34195467, 0.98724416], [ 0.28542943, 0.06892523, 0.47449629], ..., [ 0.29115949, 0.50910294, 0.51079493], [ 0.52711097, 0.43665451, 0.4290048 ], [ 0.47940793, 0.3768091 , 0.78571804]]) >>> ranges array([ 9.12730000e+04, 2.09193490e+01, 1.69436100e+00]) >>> minVals array([ 0. , 0. , 0.001156]) ~~~ ### 六、测试算法 机器学习算法中一个很重要的工作就是评估算法的正确率，通常我们会将已有数据的90%作为训练样本来训练分类器，而使用其余10%的数据去测试分类器，检测分类器的正确率。 1.分类器对约会网站的测试代码： ~~~ def datingClassTest(): hoRatio = 0.50 #hold out 10% datingDataMat,datingLabels = file2matrix('datingTestSet2.txt') #load data setfrom file normMat, ranges, minVals = autoNorm(datingDataMat) m = normMat.shape[0] numTestVecs = int(m*hoRatio) errorCount = 0.0 for i in range(numTestVecs): classifierResult = classify0(normMat[i,:],normMat[numTestVecs:m,:],datingLabels[numTestVecs:m],3) print "the classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i]) if (classifierResult != datingLabels[i]): errorCount += 1.0 print "the total error rate is: %f" % (errorCount/float(numTestVecs)) print errorCount ~~~ ~~~ >>> kNN.datingClassTest() the classifier came back with: 3, the real answer is: 3 the classifier came back with: 2, the real answer is: 2 the classifier came back with: 1, the real answer is: 1 the classifier came back with: 1, the real answer is: 1 the classifier came back with: 1, the real answer is: 1 the classifier came back with: 1, the real answer is: 1 the classifier came back with: 3, the real answer is: 3 the classifier came back with: 3, the real answer is: 3 the classifier came back with: 1, the real answer is: 1 the classifier came back with: 3, the real answer is: 3 the classifier came back with: 1, the real answer is: 1 the classifier came back with: 1, the real answer is: 1 ~~~ ~~~ the classifier came back with: 1, the real answer is: 1 the classifier came back with: 1, the real answer is: 1 the classifier came back with: 1, the real answer is: 1 the classifier came back with: 3, the real answer is: 3 the classifier came back with: 1, the real answer is: 1 the classifier came back with: 2, the real answer is: 1 the classifier came back with: 2, the real answer is: 2 the classifier came back with: 1, the real answer is: 1 the classifier came back with: 1, the real answer is: 1 the classifier came back with: 2, the real answer is: 2 the total error rate is: 0.064000 ~~~ ### 七、使用算法 输入某人信息，预测出海伦对对方喜欢程度： ~~~ def classifyPerson(): resultList=['not at all','in small doses','in large doses'] percentTats=float(raw_input("percentage of time spent playing video games?")) ffMiles=float(raw_input("frequent flier miles earned per year?")) iceCream=float(raw_input("liters of ice cream consumed per year?")) datingDataMat,datingLabels=file2matrix('datingTestSet2.txt') normMat,ranges,minVals=autoNorm(datingDataMat) inArr=array([ffMiles,percentTats,iceCream]) classifierResult=classify0((inArr-minVals)/ranges,normMat,datingLabels,3) print "You will probably like this person:",resultList[classifierResult-1] ~~~ 代码讲解：Python中的raw_input()允许用户输入文本行命令并返回用户所输入的命令 ~~~ >>> import kNN >>> reload(kNN) <module 'kNN' from 'kNN.py'> >>> kNN.classifyPerson() percentage of time spent playing video games?10 frequent flier miles earned per year?10000 liters of ice cream consumed per year?0.5 You will probably like this person: in small doses ~~~

### 一、KNN算法描述 KNN（K-nearest neighbor algorithm），也就是K近邻算法，顾名思义，可以形象的理解为求K个最近的邻居。当K=1时，KNN算法就成了最近邻算法，即寻找最近的那个邻居。 所谓K近邻算法，就是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例（就是上面提到的K个邻居），如果这K个实例的多数属于某个类，就将该输入实例分类到这个类中，如下图所示。  在上图中，有两类不同的样本数据，分别用正方形和三角形表示，而图正中间的那个圆标示的数据则是待分类的数据。换句话说就是，我们不知道中间那个圆标示的数据是从属于哪一类（是正方形还是三角形）？下面我们就要解决这个问题：给这个圆分类。 我们常说“物以类聚，人以群分”。判别一个人是一个什么样品质特征的人常常可以从他身边的朋友入手，所谓“观其友，而识其人”。要判别上图中那个圆是属于哪一类数据？好，从它的邻居下手。但是一次看多少个邻居呢？ 从图中还能看出：如果K=3，圆的最近的3个邻居是2个三角形和1个正方形，少数从属于多数，基于统计的方法，判定圆标示的这个待分类数据属于三角形一类。但是如果K=5，圆的最近的5个邻居是2个三角形和3个正方形，还是少数从属于多数，判定圆标示的这个待分类数据属于正方形这一类。 由此我们可以看到，当无法判定当前待分类数据从属于已知分类中的哪一类时，可以看它所处的位置特征，衡量它周围邻居的权重，而把它归为权重更大的一类，这就是K近邻算法分类的核心思想。 ### 二、Python代码实现 算法步骤： （1）计算已知类别数据集中的点与当前点之间的距离； （2）按照距离递增依次排序； （3）选取与当前点距离最小的K个点； （4）确定前k个点所在类别的出现频率； （5）返回前k个点出现频率最高的类别作为当前点的预测分类 ~~~ kNN: k Nearest Neighbors Input: inX: vector to compare to existing dataset (1xN) dataSet: size m data set of known vectors (NxM) labels: data set labels (1xM vector) k: number of neighbors to use for comparison (should be an odd number) Output: the most popular class label from numpy import * import operator from os import listdir def classify0(inX, dataSet, labels, k): dataSetSize = dataSet.shape[0] diffMat = tile(inX, (dataSetSize,1)) - dataSet #将inX重复成dataSetSize行1列，tile(A,n)，功能是将数组A重复n次，构成一个新的数组 sqDiffMat = diffMat**2 sqDistances = sqDiffMat.sum(axis=1) #sum(axis=1)就是将矩阵的每一行向量相加 distances = sqDistances**0.5 sortedDistIndicies = distances.argsort() #argsort()得到的是排序后数据原来位置的下标 classCount={} for i in range(k): voteIlabel = labels[sortedDistIndicies[i]]#确定前k个距离最小元素所在的主要分类labels classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1 #计算各个元素标签的出现次数(频率)，当voteIlabel在classCount中时，classCount.get()返回1，否则返回0 #operator.itemgetter(1)表示按照第二个元素的次序对元组进行排序，reverse=True表示为逆序排序，即从大到小排序 sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True) return sortedClassCount[0][0] #最后返回发生频率最高的元素标签 ~~~ 新建一个kNN.py文件，将上面的KNN的核心代码加到里面，同时加入创建数据集函数createDataSet(): ~~~ #创建数据集和标签 def createDataSet(): group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]]) labels = ['A','A','B','B'] return group, labels ~~~ K-近邻算法：带有四个数据点的简单例子   上图的实现代码是Matlab实现的，因为是Python新手，绘制带标签A，B的图还不会，所以只要用强大的Matlab来实现了。 ~~~ x=[1,1,0,0]; y=[1.1,1,0,0.1]; L={'A','A','B','B'}; %4个标注 plot(x,y,'.'); %画4个点 axis([-0.2 1.2 -0.2 1.2]) for ii=1:4 text(x(ii)+0.01,y(ii)+0.01,L{ii}); %利用4个点的坐标添加对应标注 %适当增加一些距离，让文字和点分开会美观一些 end figure(gcf); ~~~ 预测数据所在分类的测试： ~~~ >>> kNN.classify0([0,0],group,labels,3) 'B' >>> kNN.classify0([1,0],group,labels,3) 'B' >>> kNN.classify0([2,2],group,labels,3) 'A' ~~~ 参考文献： 1.July.《编程之法.面试和算法心得》 2.Peter Harrington.《Machine Learning in Action》

原始图像大小为32 X 32=1024像素，利用SVD来对数据降维，实现图像的压缩 新建一个svdRec.py文件，加入如下代码： ~~~ #printMat()函数用于打印矩阵 def printMat(inMat, thresh=0.8): for i in range(32): for k in range(32): if float(inMat[i,k]) > thresh: print 1, else: print 0, print '' #imgCompress()实现图像压缩 def imgCompress(numSV=3, thresh=0.8): myl = [] for line in open('0_5.txt').readlines(): newRow = [] for i in range(32): newRow.append(int(line[i])) myl.append(newRow) myMat = mat(myl) print "****original matrix******" printMat(myMat, thresh) U,Sigma,VT = la.svd(myMat) SigRecon = mat(zeros((numSV, numSV))) for k in range(numSV):#construct diagonal matrix from vector SigRecon[k,k] = Sigma[k] reconMat = U[:,:numSV]*SigRecon*VT[:numSV,:] print "****reconstructed matrix using %d singular values******" % numSV printMat(reconMat, thresh) ~~~ 先打开存储图像像素值的文本文件‘0_5.txt’，并从文件中以数值的方式读入字符，然后对原始图像进行SVD分解并重构图像。 运行效果： ~~~ >>> reload(svdRec) <module 'svdRec' from 'svdRec.py'> >>> svdRec.imgCompress(2) ****original matrix****** 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 ****reconstructed matrix using 2 singular values****** 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 >>> Sigma array([ 9.72140007e+00, 5.29397912e+00, 6.84226362e-01, 1.67441533e-15, 3.39639411e-16]) ~~~ 可以看出，只需要两个奇异值就能相当精确地对图像实现重构，U和V.T都是32X2的矩阵，有两个奇异值，因此总数字数目为64+64+2=130，和原始图像像素数目1024相比，实现了几乎10倍的压缩比。

SVD(Singular Value Decomposition)奇异值分解，可以用来简化数据，去除噪声，提高算法的结果。 ###一、SVD与推荐系统 下图由餐馆的菜和品菜师对这些菜的意见组成，品菜师可以采用1到5之间的任意一个整数来对菜评级，如果品菜师没有尝过某道菜，则评级为0  建立一个新文件svdRec.py并加入如下代码： ~~~ def loadExData(): return[[0, 0, 0, 2, 2], [0, 0, 0, 3, 3], [0, 0, 0, 1, 1], [1, 1, 1, 0, 0], [2, 2, 2, 0, 0], [5, 5, 5, 0, 0], [1, 1, 1, 0, 0]] ~~~ ~~~ >>> import svdRec >>> Data=svdRec.loadExData() >>> Data [[0, 0, 0, 2, 2], [0, 0, 0, 3, 3], [0, 0, 0, 1, 1], [1, 1, 1, 0, 0], [2, 2, 2, 0, 0], [5, 5, 5, 0, 0], [1, 1, 1, 0, 0]] >>> U,Sigma,VT=linalg.svd(Data) >>> Sigma array([ 9.64365076e+00, 5.29150262e+00, 8.05799147e-16, 2.43883353e-16, 2.07518106e-17]) ~~~ 我们可以发现得到的特征值，前两个比其他的值大很多，所以可以将最后三个值去掉，因为他们的影响很小。 可以看出上图中前三个人，喜欢烤牛肉和手撕猪肉，这些菜都是美式烧烤餐馆才有的菜，这两个特征值可以分别对应到美食BBQ和日式食品两类食品上，所以可以认为这三个人属于一类用户，下面四个人属于一类用户，这样推荐就很简单了。 建立一个新文件svdRec.py并加入如下代码： ~~~ def loadExData(): return[[1, 1, 1, 0, 0], [2, 2, 2, 0, 0], [1, 1, 1, 0, 0], [5, 5, 5, 0, 0], [1, 1, 0, 2, 2], [0, 0, 0, 3, 3], [0, 0, 0, 1, 1]] ~~~ SVD分解： ~~~ >>> reload(svdRec) <module 'svdRec' from 'svdRec.py'> >>> Data=svdRec.loadExData() >>> Data [[1, 1, 1, 0, 0], [2, 2, 2, 0, 0], [1, 1, 1, 0, 0], [5, 5, 5, 0, 0], [1, 1, 0, 2, 2], [0, 0, 0, 3, 3], [0, 0, 0, 1, 1]] >>> U,Sigma,VT=linalg.svd(Data) >>> Sigma array([ 9.72140007e+00, 5.29397912e+00, 6.84226362e-01, 1.67441533e-15, 3.39639411e-16]) ~~~ 我们可以发现得到的特征值，前3个比其他的值大很多，所以可以将最后2个值去掉，因为他们的影响很小。    上面例子就可以将原始数据用如下结果近似：  ###二、基于协同过滤的推荐引擎 协同过滤（collaborative filtering）是通过将用户与其他用户的数据进行对比来实现推荐的。 1.相似度计算  ~~~ from numpy import * from numpy import linalg as la def eulidSim(inA,inB): return 1.0/(1.0+la.norm(inA,inB)) def pearsSim(inA,inB): if len(inA<3):return 1.0 return 0.5+0.5*corrcoef(inA,inB,rowvar=0)[0][1] def cosSim(inA,inB): num=float(inA.T*inB) denom=la.norm(inA)*la.norm(inB) return 0.5+0.5*(num/denom) ~~~ 2.基于物品的相似度与基于用户的相似度 当用户数目很多时，采用基于物品的相似度计算方法更好。 3.示例：基于物品相似度的餐馆菜肴推荐引擎  ~~~ from numpy import * from numpy import linalg as la def loadExData(): return[[1, 1, 1, 0, 0], [2, 2, 2, 0, 0], [1, 1, 1, 0, 0], [5, 5, 5, 0, 0], [1, 1, 0, 2, 2], [0, 0, 0, 3, 3], [0, 0, 0, 1, 1]] def loadExData2(): return[[0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 5], [0, 0, 0, 3, 0, 4, 0, 0, 0, 0, 3], [0, 0, 0, 0, 4, 0, 0, 1, 0, 4, 0], [3, 3, 4, 0, 0, 0, 0, 2, 2, 0, 0], [5, 4, 5, 0, 0, 0, 0, 5, 5, 0, 0], [0, 0, 0, 0, 5, 0, 1, 0, 0, 5, 0], [4, 3, 4, 0, 0, 0, 0, 5, 5, 0, 1], [0, 0, 0, 4, 0, 4, 0, 0, 0, 0, 4], [0, 0, 0, 2, 0, 2, 5, 0, 0, 1, 2], [0, 0, 0, 0, 5, 0, 0, 0, 0, 4, 0], [1, 0, 0, 0, 0, 0, 0, 1, 2, 0, 0]] def ecludSim(inA,inB): return 1.0/(1.0 + la.norm(inA - inB)) def pearsSim(inA,inB): if len(inA) < 3 : return 1.0 return 0.5+0.5*corrcoef(inA, inB, rowvar = 0)[0][1] def cosSim(inA,inB): num = float(inA.T*inB) denom = la.norm(inA)*la.norm(inB) return 0.5+0.5*(num/denom) #计算在给定相似度计算方法的条件下，用户对物品的估计评分值 #standEst()函数中：参数dataMat表示数据矩阵，user表示用户编号，simMeas表示相似度计算方法，item表示物品编号 def standEst(dataMat,user,simMeas,item): n=shape(dataMat)[1] #shape用于求矩阵的行列 simTotal=0.0; ratSimTotal=0.0 for j in range(n): userRating=dataMat[user,j] if userRating==0:continue #若某个物品评分值为0，表示用户未对物品评分，则跳过，继续遍历下一个物品 #寻找两个用户都评分的物品 overLap=nonzero(logical_and(dataMat[:,item].A>0,dataMat[:,j].A>0))[0] if len(overLap)==0:similarity=0 else: similarity=simMeas(dataMat[overLap,item],dataMat[overLap,j]) #print'the %d and%d similarity is: %f' %(item,j,similarity) simTotal+=similarity ratSimTotal+=similarity*userRating if simTotal==0: return 0 else: return ratSimTotal/simTotal def recommend(dataMat,user,N=3,simMeas=cosSim,estMethod=standEst): #寻找未评级的物品 unratedItems=nonzero(dataMat[user,:].A==0)[1] if len(unratedItems)==0: return 'you rated everything' itemScores=[] for item in unratedItems: estimatedScore=estMethod(dataMat,user,simMeas,item) #对每一个未评分物品，调用standEst()来产生该物品的预测得分 itemScores.append((item,estimatedScore)) #该物品的编号和估计得分值放入一个元素列表itemScores中 #对itemScores进行从大到小排序，返回前N个未评分物品 return sorted(itemScores,key=lambda jj:jj[1],reverse=True)[:N] def svdEst(dataMat, user, simMeas, item): n = shape(dataMat)[1] simTotal = 0.0; ratSimTotal = 0.0 U,Sigma,VT = la.svd(dataMat) Sig4 = mat(eye(4)*Sigma[:4]) #arrange Sig4 into a diagonal matrix xformedItems = dataMat.T * U[:,:4] * Sig4.I #create transformed items for j in range(n): userRating = dataMat[user,j] if userRating == 0 or j==item: continue similarity = simMeas(xformedItems[item,:].T,\ xformedItems[j,:].T) print 'the %d and %d similarity is: %f' % (item, j, similarity) simTotal += similarity ratSimTotal += similarity * userRating if simTotal == 0: return 0 else: return ratSimTotal/simTotal ~~~ 其中dataMat[:,item].A，表示找出item列，因为是matrix，用.A转成array，logical_and，其实就是找出最item列和j列都>0，只有都大于0才会是true，nonzero会给出其中不为0的index。 进行SVD分解： ~~~ >>>from numpy import linalg as la >>> U,Sigma,VT=la.svd(mat(svdRec.loadExData2())) >>> Sigma array([ 1.38487021e+01, 1.15944583e+01, 1.10219767e+01, 5.31737732e+00, 4.55477815e+00, 2.69935136e+00, 1.53799905e+00, 6.46087828e-01, 4.45444850e-01, 9.86019201e-02, 9.96558169e-17]) ~~~ 如何决定r？有个定量的方法是看多少个奇异值可以达到90%的能量，其实和PCA一样，由于奇异值其实是等于data×dataT特征值的平方根，所以总能量就是特征值的和 ~~~ >>> Sig2=Sigma**2 >>> sum(Sig2) 541.99999999999932 ~~~ 而取到前4个时，发现总能量大于90%，因此r=4 ~~~ >>> sum(Sig2[:3]) 500.50028912757909 ~~~ SVD分解的关键在于，降低了user的维度，从n变到了4 ~~~ def svdEst(dataMat, user, simMeas, item): n = shape(dataMat)[1] simTotal = 0.0; ratSimTotal = 0.0 U,Sigma,VT = la.svd(dataMat) Sig4 = mat(eye(4)*Sigma[:4]) #arrange Sig4 into a diagonal matrix xformedItems = dataMat.T * U[:,:4] * Sig4.I #create transformed items for j in range(n): userRating = dataMat[user,j] if userRating == 0 or j==item: continue similarity = simMeas(xformedItems[item,:].T,\ xformedItems[j,:].T) print 'the %d and %d similarity is: %f' % (item, j, similarity) simTotal += similarity ratSimTotal += similarity * userRating if simTotal == 0: return 0 else: return ratSimTotal/simTotal ~~~ 其中关键一步，dataMat.T * U[:,:4] * Sig4.I 将m×n的dataMat用特征值缩放转换为n×4的item和user类的矩阵 ~~~ >>> myMat=mat(svdRec.loadExData2()) >>> myMat matrix([[0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 5], [0, 0, 0, 3, 0, 4, 0, 0, 0, 0, 3], [0, 0, 0, 0, 4, 0, 0, 1, 0, 4, 0], [3, 3, 4, 0, 0, 0, 0, 2, 2, 0, 0], [5, 4, 5, 0, 0, 0, 0, 5, 5, 0, 0], [0, 0, 0, 0, 5, 0, 1, 0, 0, 5, 0], [4, 3, 4, 0, 0, 0, 0, 5, 5, 0, 1], [0, 0, 0, 4, 0, 4, 0, 0, 0, 0, 4], [0, 0, 0, 2, 0, 2, 5, 0, 0, 1, 2], [0, 0, 0, 0, 5, 0, 0, 0, 0, 4, 0], [1, 0, 0, 0, 0, 0, 0, 1, 2, 0, 0]]) >>> svdRec.recommend(myMat,1,estMethod=svdRec.svdEst) the 0 and 3 similarity is: 0.490950 the 0 and 5 similarity is: 0.484274 the 0 and 10 similarity is: 0.512755 the 1 and 3 similarity is: 0.491294 the 1 and 5 similarity is: 0.481516 the 1 and 10 similarity is: 0.509709 the 2 and 3 similarity is: 0.491573 the 2 and 5 similarity is: 0.482346 the 2 and 10 similarity is: 0.510584 the 4 and 3 similarity is: 0.450495 the 4 and 5 similarity is: 0.506795 the 4 and 10 similarity is: 0.512896 the 6 and 3 similarity is: 0.743699 the 6 and 5 similarity is: 0.468366 the 6 and 10 similarity is: 0.439465 the 7 and 3 similarity is: 0.482175 the 7 and 5 similarity is: 0.494716 the 7 and 10 similarity is: 0.524970 the 8 and 3 similarity is: 0.491307 the 8 and 5 similarity is: 0.491228 the 8 and 10 similarity is: 0.520290 the 9 and 3 similarity is: 0.522379 the 9 and 5 similarity is: 0.496130 the 9 and 10 similarity is: 0.493617 [(4, 3.3447149384692283), (7, 3.3294020724526967), (9, 3.328100876390069)] ~~~

> 原文出处：[机器学习实战笔记](http://blog.csdn.net/column/details/mlinaction.html) 作者：[geekmanong](http://blog.csdn.net/geekmanong) **本系列文章经作者授权在看云整理发布，未经作者允许，请勿转载！** # 机器学习实战笔记 > 机器学习是人工智能研究领域中一个极其重要的研究方向，在当前的大数据时代背景下，捕获数据并从中获取有价值的信息或模式，成为各行业求生存、谋发展的决定性手段，机器学习算法也成为数据分析的重要技术方法。