第一部分：分类算法 目录
1. k-近邻算法 目录
算法概述：
存在一个样本数据集，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。
一般我们只选择样本数据集中前k个最相似的数据，通常k是不大于20的整数
1.1. 准备：导入数据 目录
import numpy as np
import operator
def createDataset():
group = np.array([[1.0,1.1],
[1.0,1.0],
[0,0],
[0,0.1]])
lables = ['A','A','B','B']
return group,lables
保存为kNN.py，为下一步将该函数作为模块导入做好准备
1.2. 实施kNN分类算法 目录
import numpy as np
import operator
def kNN_classify(inX,dataset,lables,k):
# 计算距离（欧式距离）
datasetSize = dataset.shape[0] # 训练样本数
diffMat = np.tile(inX,(datasetSize,1))-dataset # 将输入向量与训练集相减，得到每个特征的差值
sqdiffMat = diffMat**2
sqDistances = sqdiffMat.sum(axis=1) # axis指定相加的方向，默认全部相加，axis=0指定列相加，axis=1指定行相加
distances = sqDistances**0.5
# 按照距离递增进行排序
sortDistancesIndicies = distances.argsort() # 对向量进行排序得到排序后的索引
# 选择距离最小的k个点，并计算这k个点的lable的频率
classCount = {}
for i in range(k):
voteLable = lables[sortDistancesIndicies[i]]
classCount[voteLable] = classCount.get(voteLable,0) + 1
# 返回前k个点中出现频率最高的类别
## items()方法将classCount字典分解成元组列表
## key=operator.itemgetter(1)，导入operator模块的itemgetter()方法，按照第二个元素的次序对元组进行排序
## reverse=True，默认为从小到大排序，即reverse=False
sortedClassCount = sorted(classCount.items(),\
key=operator.itemgetter(1),\
reverse=True)
return sortedClassCount[0][0]
函数kNN_classify有4个参数：
- inX：用于分类的输入向量
- dataset：输入的训练样本集
- lables：标签向量，其向量元素数目好矩阵dataset的行数相同
- k：最近邻居数目
1.3. 示例1：使用kNN改进约会网站的配对效果 目录
问题描述：
海伦在约会网站上遇到的人可以分成以下三类：
- 不喜欢的人
- 魅力一般的人
- 极具魅力的人
想根据搜集到的数据将网站推荐的约会对象划分到这三个类别中
-
准备数据
海伦共搜集了1000个训练样本，每个样本包含以下3种特征：
- 每年获得的飞行常客里程数
- 玩游戏视频所耗时间百分比
- 每周消费的冰淇淋公升数
这些数据保存在
datingTestSet2.txt中，共四列，前三列为3种特征，最后一列为类别标签40920 8.326976 0.953952 3 14488 7.153469 1.673904 2 26052 1.441871 0.805124 1 75136 13.147394 0.428964 1 38344 1.669788 0.134296 1在将上述数据输入给分类器之前，必须将待处理的数据格式改变为分类器可以接受的格式
import numpy as np def file2matrix(filename): with open(filename,'r') as f: lines = f.readlines() numberOfLines = len(lines) featureMat = np.zeros((numberOfLines,3)) # 创建3列的0矩阵 labels = [] index = 0 for line in lines: line = line.strip() lineSplit = line.split('\t') featureMat[index,:] = lineSplit[0:3] labels.append(int(lineSplit[-1])) index +=1 return featureMat,labels -
分析数据：使用Matplotlib创建散点图
使用Matplotlib制作原始数据的散点图：
>>> import matplotlib >>> import matplotlib.pyplot as plt >>> fig = plt.figure() # 创建图片 >>> ax = fig.add_subplot(111) # 创建1*1的图表矩阵，并设置当前子图序号为1 >>> ax.scatter(dataset[:,1],dataset[:,2]) # 使用dataset矩阵中的第二、三列数据绘图 >>> plt.show()
为了从图中看出样本的分类信息，我们采用彩色或来标记不同的样本分类
>>> ax.scatter(dataset[:,1],dataset[:,2],15.0*np.array(labels),15.0*np.array(labels))
若采用第一、二列数据绘制散点图，分类效果更好
-
准备数据：归一化数值
飞行里程 游戏时间比例 冰淇淋 类别 40920 8.326976 0.953952 3 14488 7.153469 1.673904 2 26052 1.441871 0.805124 1 75136 13.147394 0.428964 1 38344 1.669788 0.134296 1计算样本之间的距离时，数字差值最大的属性对计算结果的影响最大，很明显飞行里程数对于计算结果的影响将远远大于其他两个特征，而产生这种现象的唯一原因，仅仅是因为飞行里程数远远大于其他特征值。
但是海伦认为这三个特征同等重要，因此作为等权重的三个特征之一，飞行里程数不应该如此严重地影响计算结果
处理这种不同取值范围的特征值，通常采用数值归一化方法：
newValue = (oldValue-min)/(max-min)def autoNorm(dataset): minVals = dataset.min(0) maxVals = dataset.max(0) ranges = maxVals-minVals normDataset = np.zeros(dataset.shape) normDataset = (dataset-tile(minVals,(dataset.shape[0],1)))/tile(ranges,(dataset.shape[0],1)) # 对应特征值相除，并非矩阵除法 return normDataset,ranges,minVals -
测试算法
提供已有数据的10%作为测试集，90%作为训练集，计算算法的预测正确率
# 将该函数加入kNN.py中作为kNN模块的一部分 ## 需要指定数据集文件，已经指定测试集比例 def datingClassTest(filename,testPercent): dataset,labels = file2matrix(filename) normDataSet,ranges,minVals = autoNorm(dataset) totalNum = normDataSet.shape[0] testNum = totalNum*testPercent # 测试集的样本数 for i in range(testNum): result = kNN_classify(normDataSet[i,:],normDataSet[testNum:totalNum,:],labels[testNum:totalNum],3) print("The classifiler came back with:%d, the real answer is:%d",result,labels(i)) if(result != labels(i)): errorCount += 1 errorRate = errorCount/totalNum print("The total error rate is: %f",errorRate)
1.4. 示例2：手写识别系统 目录
问题描述：
为了简单起见，这里构造的系统只能识别数字0到9
需要识别的数字已经用图像处理软件处理成宽高32*32的黑白图像
-
准备数据：将图像转换为测试向量
def img2vec(filename): with open(filename,"r") as f: returnVec = np.zeros(1,1024) for i in range(32): line = f.readline() for j in range(32): returnVec[0,32*i+j] = line[j] return returnVec -
测试算法：使用kNN识别手写数字
import os
def handwriteClassifierTest(trainDir,testDir,testPercent):
hwLabels = []
# 读进训练集
trainFileList = os.listdir(trainDir)
trainNum = len(trainFileList)
trainMat = np.zeros(m,1024)
for i in range(trainNum):
trainFileName = trainFileList[i]
classNumStr = trainFileName.split('_')[0] # 从文件名中获得分类数字
hwLabels.append(classNumStr) # 保存分类数字
trainMat[i,:] = img2vec(trainFileName)
# 读进测试集并进行测试
testFileList = os.listdir(testDir)
testNum = len(testFileList)
for i in range(testFileList):
testFileName = testFileList[i]
classNumStr = testFileName.split('_')[0]
testVec = img2vec(testFileName)
result = kNN_classifier(testVec,trainMat,hwLabels,3)
print("The classifiler came back with:%d, the real answer is:%d",result,hwLabels(i))
if(result != hwLabels(i)):
errorCount += 1
errorRate = errorCount/totalNum
print("The total error rate is: %f",errorRate)
2. 决策树 目录
决策树的一个重要任务就是为了理解数据中所蕴含的知识信息，因此决策树可以使用不熟悉的数据集合，并从中提取出一系列规则，这种机器根据数据集创建规则的过程，就是机器学习的过程
def createBranch():
检测数据集中的每个子项是否等于同一分类：
If so return 类标签
Else
寻找划分数据集的最好特征
创建分支节点，划分数据集
for 每个划分的子集
调用createBranch函数
return 分支节点
2.1. 构造决策树 目录
-
计算给定数据集的香农熵
from math import log import numpy as np # 要求输入的矩阵最后一列是类标签，前面的是各个特征 def calcShannonEnt(dataset): numEntries = dataset.shape[0] # 计算每个类标签的频率 labelCount = {} for label in dataset[:,-1]: labelCount[label] = labelCount.get(label,0)+1 # 计算信息熵 shannonEnt = 0 for key in labelCount: prob = labelCount[key]/numEntries shannonEnt -= pro*log(prob,2) return shannonEnt -
寻找划分数据集的最好特征：信息增益
先划分数据集：将dataset中的按照某一个特征（某一列）进行划分，将该特征中为某一个值的样本挑出来
def splitDataset(dataset,col,value): returnDataset = [] for featureVec in dataset: if featureVec[col] == value: remainVec = featureVec[:col] remainVec.extend(featureVec[col+1:]) returnDataset.append(remainVec) return returnDataset对各个特征进行划分，计算信息增益，寻找信息增益最大的那个特征
# 返回的bestFeature是该特征所对应的列序号 def choseBestFeature(dataset): baseEnt = calcShannonEnt(dataset) numEntries = dataset.shape[0] numFeatures = dataset.shape[1] - 1 bestInfoGain = 0 bestFeature = -1 # 对各个特征进行划分 for col in range(numFeatures): featureList = [ example[col] for example in dataset ] uniqueFeature = set(featureList) newEnt = 0 # 计算用该特征进行划分得到的信息熵 for value in uniqueFeature: subDataset = splitDataset(dataset,col,value) prob = subDataset.shape[0]/numEntries newEnt += prob*calcShannonEnt(subDataset) # 计算信息增益 InfoGain = baseEnt - newEnt # 寻找最大信息增益 if (InfoGain > bestInfoGain): bestInfoGain = InfoGain bestFeature = col return bestFeature -
递归构建决策树
递归结束的条件：
- 遍历完所有划分数据集的特征
- 每个分支下的所有实例都属于同一个类别
但可能出现一个问题是：已经遍历网所有划分数据集的特征后，该分支下的示例还属于不同的类别，此时必须结束该分支为该分支选择一个类别标签，这个时候可以采用少数服从多数的原则为该分支选择一个类别
def majorityVote(labels): count={} for vote in labels: count = count.get(vote,0) + 1 sortCount = sorted(count.items(),key=operator.itemgetter(1),reverse=True) reture sortCount[0][0]开始执行递归构建决策树：
# 需要传入两个参数：数据集（最后一列为类标签，前面为多个特征列），特征名向量 def createTree(dataset，featureName): classList = dataset[,-1] uniqueClass = set(classList) # 如果该分支下的所有实例属于同一个类别 if len(uniqueClass) == 1: return uniqueClass # 如果已经遍历网所有的特征，即dataset中只有一列 if len(dataset.shape) == 1: return majorityVote(dataset) # 开始递归建树 ## 选择最优特征 bestFeature = choseBestFeature(dataset) beatFeatureName = featureName[bestFeature] del(featureName[bestFeature]) # 保证数据集划分之后，dataset的各个列的名称与featureName始终保持一一对应 myTree = {bestFeatureName:{}} bestFeatureList = dataset[:,bestFeature] uniqueValue = set(bestFeatureList) ## 以最优特征作为分支点，划分数据集 for value in uniqueValue: subDataset = splitDataset(dataset,bestFeature,value) # 划分数据得到子数据集 myTree[bestFeatureName][value] = creatTree(subDataset,featureName) # 对子数据集继续进行子树的构建 return myTree
2.2. 用Matplotlib绘制树形图 目录
参考资料：
(1) [美] Peter Harrington《机器学习实战》，人民邮电出版社