k-近邻算法

概述：k-近邻算法采用测量不同特征值之间的距离方法进行分类
优点：精度高、对于异常值不敏感，无数据输入假定
缺点：计算复杂度高，空间复杂度高,并且它没有办法各处基础数据的一些内部信息数据。
算法描述：存在一个准确的数据集合样本，称作训练样本集，样本集合中每个item都附带自己所属分类标签。当需要判断新数据的分类是，只需要计算特征数据和样本数据中最相似的分类标签，选择k个最相似的标签，k个标签中占比最多的即为目标标签。

具体分类算法

    #-*- coding=utf-8 -*-
    from numpy import *
    import operator

    ##简单的kNN算法实现
    #dataSet是训练数据集合，每行代表每个训练数据的每个特征值
    #labels 对应dataSet每个训练数据的class标签
    #inX 表示待分类的特征数据
    def classify0(inX, dataSet, labels, k):
        dataSetSize = dataSet.shape[0] # 获取测试集合大小
        #求每个输入特征值和每个测试集合总的特征值的超时
        #首先需要使用tile将特征值扩展为和测试集合相等大小的矩阵
        diffMat = tile(inX, (dataSetSize, 1)) - dataSet
        #取平方
        sqlDiffMat = diffMat ** 2
        sumMat = sqlDiffMat.sum(axis=1)
        distances = sumMat ** 0.5
        #获取排序信息
        #例如:array([9,1,3,0]) -> array([3,1,2,0]) 升序标签
        sortIndicies = distances.argsort()

        classCount = {}
        #取距离最小的前k个对应的标签统计信息
        for i in range(k):
            label = labels[sortIndicies[i]]
            classCount[label] = classCount.get(label,0) + 1

        #取最大的

        sortedClassCount = sorted(classCount.iteritems(), key = operator.itemgetter(1), reverse=True) 
        return sortedClassCount[0][0]

关于特征数据

不同的特征，具体的数据值波动区间是不同的，例如特征A取值范围在[1000,10000],但是特征B取值范围在[0,10]，如果直接使用这样的特征数据进行KNN算法运算，会出现的一个问题，高区间的特征对结果的影响远远大于低区间的特征值，因此我们需要对我们的特征数据做归一化处理，即将所有特征值处理到相同的区间范围中。
具体算法：((特征值-min)/(max - min)) -> [0,1]区间范围

    from numpy import *
    import operator
    #用于将一个不同范围域的特征值归一化到统一的[0,1]之间
    def normData(dataSet):
        #获取每个特征的最大值
        maxValue = http://www.mamicode.com/dataSet.max(0)
        #获取每个特征的最小值
        minValue = http://www.mamicode.com/dataSet.min(0)
        ranges=maxValue-minValue
        #将数据归一到同一个范围
        normalDataSet = zeros(shape(dataSet))
        m = dataSet.shape[0]
        normalDataSet = dataSet - tile(ranges,(m,1))
        #除于最大值
        normalDataSet = normalDataSet/tile(maxValue,(m,1))

        return normalDataSet, ranges, minValues

关于可视化特征数据

如何判别我们取得的特征数据集合适合使用knn进行分类训练？
在做数据观察时我们往往需要通过可视化方式去观察我们的特征数据和label的分布，这个时候就需要用到Python的一个图形工具matplotlib。
特征和分类数据：testSet.txt
3.542485 1.977398 -1
3.018896 2.556416 -1
7.551510 -1.580030 1
2.114999 -0.004466 -1
8.127113 1.274372 1
7.108772 -0.986906 1
8.610639 2.046708 1
2.326297 0.265213 -1
3.634009 1.730537 -1
0.341367 -0.894998 -1
3.125951 0.293251 -1
2.123252 -0.783563 -1
0.887835 -2.797792 -1
7.139979 -2.329896 1
1.696414 -1.212496 -1
8.117032 0.623493 1
8.497162 -0.266649 1
4.658191 3.507396 -1
8.197181 1.545132 1
1.208047 0.213100 -1
1.928486 -0.321870 -1
2.175808 -0.014527 -1
7.886608 0.461755 1
3.223038 -0.552392 -1
3.628502 2.190585 -1
7.407860 -0.121961 1
7.286357 0.251077 1

可视化脚本:

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

##read file
fr = open(‘testSet.txt‘)
lines = fr.readlines()
dataSet = zeros((len(lines),1))
labels = []
index = 0
for line in lines:
    items = line.strip().split(‘\t‘)
    dataSet[index:] = items[0:2]
    labels.append(items[-1])
#matplot
fx = plt.figure()
ax = fx.add_subplot(111)
#将数组转换为矩阵
dataSet = matrix(dataSet)
colora = tile(50, len(lines))
#这里的colora是为了通过颜色区分不同的labels， cmap代表颜色map，默认是yard， s是每个点的大小，alpha是每个点的透明度
ax.scatter(dataSet[:,0], dataSet[:,1], c=colora * labels, cmap=‘autum‘, s=50, alpha=0.3)

plt.show()

决策树

概述：通过分析每个数据特征项在分类过程中所起到的所用比重，将数据划分为几个数据子集，如果某个数据子集数据同一类型，则无需再继续划分数据分类，如果不属于同一分类，则需要在对数据子集进行分割。
优点：计算复杂度不高。
缺点：可能会出现由于样本特征值对应的样本数量不统一导致结果偏向于数量多的样本对应的分类。

具体分类算法 ID3算法

在每次划分数据集时我们会取一个特征属性来进行划分，那么这里有一个问题，例如训练样本里面有20个特征值，我们如何从这些特征中选择当前用于划分的最适合的特征项呢？我们需要找到一个有效的量化方法来划分数据。

信息熵

样本id	是否需要浮出水面	是否有脚蹼	属于鱼
1	是	是	是
2	是	是	是
3	是	否	是
4	否	是	否
5	否	是	否

我们划分数据的原则是将无须的数据变得更加有序，这里有一个信息增益的概念：即数据在划分前后的信息发生的变化成为信息增益。因此我们需要计算每个特征值的数据划分之后的信息增益值，选取最大的信息增益特征值作为当前数据划分特征。集合信息的度量方式成为熵，我们需要计算我们的信息集合熵值。
熵的计算公式：H = -log(p(i),2) 对于集合的熵计算公式：H = -for(i in n)p(i)log(p(i),2)

计算信息熵算法

#-*- coding=utf-8 -*-
from numpy import *
from math import log
import operator

def calcShannonEnt(dataSet):
    labelCounts = {} #统计每个标签的次数
    for line in dataSet:
        label = line[-1]
        labelCounts[label] = labelCounts.get(label, 0) + 1
    shannonEnt = 0.0
    #统计信息熵
    for key in labelCounts:
        prob = float(labelCounts[key])/len(dataSet)
        shannonEnt -= prob * log(prob, 2)
    return shannonEnt

数据划分code

由于是决策树因此我们需要将集合划分为不同的子集

#例如上面的通过是否浮出水面划分数据就能得到两个子集
#子集1
#是否有脚蹼|属于鱼类
#是 | 是
#是 | 是
#否 | 是
#子集2
#是 | 否
#是 | 否
#axis表示特征项，value表示需要匹配的特征值
def splitDataSet(dataSet, axis, value):
    resultDataSet = []
    for line in dataSet:
        if line[axis] == value:
            reduceValue = http://www.mamicode.com/line[:axis]"hljs-number">1 : ])
            resultDataSet.append(reduceValue)

    return resultDataSet

选择最优的划分属性

由于有上面两个方法作为基础，我们可以通过下面的代码来寻找最适合划分的特征值

def chooseBestSplitFeature(dataSet):
    featureCount = len(dataSet[0]) - 1
    #计算当前的熵值
    currentShannonEnt = calcShannonEnt(dataSet)
    #定义信息增益
    bestInfoGain = 0.0
    #定义返回值
    bestAxis = -1
    #遍历每个特征项
    for i in range(featureCount):
        featureValues = set([value[i] for value in dataSet])
        subShannonEnt = 0.0
        for featureValue in featureValues:
            subDataSet = splitDataSet(dataSet, i, featureValues)
            subDataSetProb = float(subDataSet)/len(dataSet)
            subShannonEnt += subDataSetProb * calcShannonEnt(subDataSet)

        subInfoGain = currentShannonEnt - subShannonEnt
        #判断当先最优的划分特征
        if subInfoGain > bestInfoGain :
            bestInfoGain = subInfoGain
            bestAxis = i

    return bestAxis

构建决策树

我们可以通过一个map来表示我们的决策树

def createTree(dataSet):
    classList = [value[-1] for value in dataSet]
    #如果所有的classList一致则直接返回
    if classList.count(classList[0]) == len(classList):
        return classList[0]

    if len(dataSet[0]) == 1:
        ##这里的case场景是，已经没有可用的特征项时，针对剩余的分类如何决定目标分类
        #return dataSet[0]
        #这里采用取占比最多的值
        return major(dataSet)
    #选择分类属性
    axis = chooseBestSplitFeature(dataSet)
    #定义tree树 属性 index->Map
    myTree = {axis:{}}  
    featureList = set([value[axis] for value in dataSet])
    for feature in featureList :
        mytree[axis][feature] = createTree(splitDateSet(dataSet, axis, feature))

    return mytree

#去占比最多的分类值
def major(dataSet):
    labelCount={}
    for line in dataSet:
        labelCount[line[-1] = labelCount.get(line[-1], 0) + 1

    #排序
    return sorted(labelCount.iteritems(), key = operator.itemgetter(1), reverse=True)[0][0]

关于python的序列化

决策树构建完成之后，我们可以将决策树序列化到一个文件中，以便以后直接使用，这里就涉及到python的序列化模块pickle

import pickle
def storeTree(myTree, fileName):
    fw = open(fileName, ‘w‘)
    pickle.dumps(myTree, fw)
    fw.close()

def readTree(fileName):
    fr = open(fileName)
    return pickle.load(fr)

基于概率论的分类方法:朴素贝叶斯算法

如下图的点分布图：

给定单(x,y), 它属于红色区域c1概率p1, 蓝色区域c2概率p2
* 如果p1(x,y) > p2(x,y) , 那么类别为1
* 如果p1(x,y) < p2(x,y) , 那么类别为2
我们在判断(x,y)时会选择高概率所对应的类别，贝叶斯的理论就是选择最高概率的决策。
这里我们观察的两个公式
p(x|c) = p(x and c) / p(c)
p(c|x) = p(x|c)p(c) / p(x)
将这个公式应用到我们的分类算中，求上面的p1，p2 转换为 p(c1|x, y)，p(c2|x, y)通过上面的转换公式可以转换为 p(c1|x, y) = p(x,y |c1)p(c1) / p(x,y) , p(c2|x, y) = p(x, y| c2) p(c2) / p(x, y)
* 当p(c1|x,y) > p(c2|x,y) , 则（x,y）属于类别1
* 当p(c1|x,y) < p(c2|x,y) , 则（x,y）属于类别2
对于一个实例我们需要关心的可能是多个维度的特征值以及特征值在实例分类中的概率分布，因此我们将上面的p(c1|x, y)替换为 p(c1|w),其中w为一个多维的特征向量。上面的公式就转换为 p(c1|w) = p(w|c1)p(c1)/p(w) 和 p(c2|w) = p(w|c2)p(c2)/p(w)。
单独看p(w)在朴素贝叶斯理论中我们做的一个假设是，p(w1,w2,w3….wn)的每个特征向量不存在相关性，p(w1,w2,w3….wn)退化为计算p(w1)p(w2)p(3)…p(wn)。
下面通过一个垃圾邮件分类算法具体介绍如何使用朴素贝叶斯概率分布实现机器学习和垃圾邮件分类：
* 首先我们需要从训练文本中提取全量特征值，具体做法是将文本进行切分成单个词条
* 其次我们需要将每条训练数据的特征值转换为一个特征向量
* 通过计算训练数据的特征向量以及对应的分类数据获取整个分类在全量特征值中的概率分布
* 通过需要计算分类的条目的特征向量，计算出条目对应的每个分类的概率，选取概率大的分类作为目标分类

垃圾邮件过滤算法

训练集合：
[
[‘my’, ‘dog’, ‘has’, ‘flea’, ‘problems’, ‘help’, ‘please’],
[‘maybe’, ‘not’, ‘take’, ‘him’, ‘to’, ‘dog’, ‘park’, ‘stupid’],
[‘my’, ‘dalmation’, ‘is’, ‘so’, ‘cute’, ‘I’, ‘love’, ‘him’],
[‘stop’, ‘posting’, ‘stupid’, ‘worthless’, ‘garbage’],
[‘mr’, ‘licks’, ‘ate’, ‘my’, ‘steak’, ‘how’, ‘to’, ‘stop’, ‘him’],
[‘quit’, ‘buying’, ‘worthless’, ‘dog’, ‘food’, ‘stupid’]
]
训练集合对应的分类(0表示正常评论，1表示侮辱评论)：
[0, 1, 0, 1, 0, 1]

获取所有特征属性

代码实现：

#-*- coding=utf-8 -*-
form numpy import *
## 这里的dataSet每个item对应测试数据中的词条（单词）
def getVecList(dataSet):
    vecList = set([])
    for line in dataSet:
        vacList = vacList | set(line)

    return list(vecList)

##最终获得的所有特征属性
## set([‘cute‘, ‘love‘, ‘help‘, ‘garbage‘, ‘quit‘, ‘I‘, ‘problems‘, ‘is‘, ‘park‘, ‘stop‘, ‘flea‘, ‘dalmation‘, ‘licks‘, ‘food‘, ‘not‘, ‘him‘, ‘buying‘, ‘posting‘, ‘has‘, ‘worthless‘, ‘ate‘, ‘to‘, ‘maybe‘, ‘please‘, ‘dog‘, ‘how‘, ‘stupid‘, ‘so‘, ‘take‘, ‘mr‘, ‘steak‘, ‘my‘])

计算数据的特征向量

特征向量表示的每个训练item的一个特征分布
代码实现：

#-*- coding=utf-8 -*-
from numpy import *

def getVec(dataItem, vecList):
    #初始化特征向量，0 表示特征值不存在 1表示特征值存在
    vecResult = [0] * len(vecList)
    for feature in dataItem:
        if feature in vecList:
            ##特征值存在获取向量id
            vecResult[vecList.index(feature)] = 1

    return vecResult

#result:
#[0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1]
#[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0]
#[1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1]
#[0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0]
#[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1]
#[0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0]

分类训练算法

输入为上面方法得到的特征向量和每个特征向量对应的分类
代码实现：

#trainMatrix 特征向量举证
#trainCategory 特征分类
def trainNB0(trainMatrix, trainCategory):
        numTrainDocs = len(trainMatrix)
        numWords = len(trainMatrix[0])
        pAbusive = sum(trainCategory)/float(numTrainDocs)
        #p0Num = zeros(numWords)
        #p1Num = zeros(numWords)
        #p0Denom = 0.0
        #p1Denom = 0.0
        #如果按照上面的计算方法会得出特别多的0，这个时候在去算p0*p1..pn时就会出现乘0的情况
        #因此为了解决这个情况，采用下面的初始化方式
        #这种方式最终对于概率计算没有影响，因为大家的基数都是一样的
        p0Num = ones(numWords)
        p1Num = ones(numWords)
        p0Denom = 2.0
        p1Denom = 2.0
        for i in range(numTrainDocs):
            if trainCategory[i] == 1:
                p1Num += trainMatrix[i]
                p1Denom += sum(trainMatrix[i])
            else:
                p0Num += trainMatrix[i]
                p0Denom += sum(trainMatrix[i])

        #p1Vect = p1Num/p1Denom
        #p0Vect = p0Num/p0Denom
        #这里有个问题由于上面这种方式计算出来的概率都是小数位，因此采用这些小概率做p0*p1*....pn就会造成最终得到的概率四舍五入之后=0
        #为了解决这个问题采用对数的方式将所有的结果概率等条件的放大
        p1Vect = log(p1Num/p1Denom)
        p0Vect = log(p0Num/p0Denom)
        return p0Vect, p1Vect, pAbusive

 #Result :
 #p0Vect :
 #[-2.56494936, -2.56494936, -2.56494936, -3.25809654, -3.25809654,
       -2.56494936, -2.56494936, -2.56494936, -3.25809654, -2.56494936,
       -2.56494936, -2.56494936, -2.56494936, -3.25809654, -3.25809654,
       -2.15948425, -3.25809654, -3.25809654, -2.56494936, -3.25809654,
       -2.56494936, -2.56494936, -3.25809654, -2.56494936, -2.56494936,
       -2.56494936, -3.25809654, -2.56494936, -3.25809654, -2.56494936,
       -2.56494936, -1.87180218]
 #p1Vect :
 #[-3.04452244, -3.04452244, -3.04452244, -2.35137526, -2.35137526,
       -3.04452244, -3.04452244, -3.04452244, -2.35137526, -2.35137526,
       -3.04452244, -3.04452244, -3.04452244, -2.35137526, -2.35137526,
       -2.35137526, -2.35137526, -2.35137526, -3.04452244, -1.94591015,
       -3.04452244, -2.35137526, -2.35137526, -3.04452244, -1.94591015,
       -3.04452244, -1.65822808, -3.04452244, -2.35137526, -3.04452244,
       -3.04452244, -3.04452244]
 #pAbusive:
 #0.5

至此我们就得到了通过所有训练样本计算出来的样本特征值的概率分布信息，这个概率分布信息可以用于统计分类执行特征的分类。
例如具体使用Code：

def classifyNB(vec2Classify, p0Vec, p1Vec, pClass1):
            #这里使用的是ln(p(w|ci) * p(ci)) = ln(p(w|ci)) + ln(p(ci))
        #这里的算法公式是 p(ci|w) = p(w|ci) * p(ci)/p(w)
        p1 = sum(vec2Classify*p1Vec) + log(pClass1)
        p0 = sum(vec2Classify*p0Vec) + log(1-pClass1)
        if p1 > p0 :
            return 1
        else:
            return 0

分类算法测试

#对于贝叶斯分类的测试代码
def testingNB():
        listOPosts,listPostClasses = loadDataSet()
        vocabList = createVocabList(listOPosts)
        trainMatrix = []
        for line in listOPosts:
            trainMatrix.append(setOfWords2Vec(vocabList, line))
        p0V,p1V,pAb = trainNB0(trainMatrix, listPostClasses)
        testEntity = [‘love‘, ‘my‘, ‘dalmation‘]
        thisDoc = setOfWords2Vec(vocabList, testEntity)
        print testEntry, "classified as : ", classifyNB(thisDoc,p0V,p1V,pAb)

关于频率的问题

其实在实际使用分类算法时某一个词条出现的次数是有实际统计意义的，在上面的训练算法中并没有考虑频率对概率分布的作用参数。我们可以修改特征向量的生成方式让频率作为一个实际参数进入到我们的分类算法中。

def getVec(dataItem, vecList):
    #初始化特征向量，0 表示特征值不存在 1表示特征值存在
    vecResult = [0] * len(vecList)
    for feature in dataItem:
        if feature in vecList:
            ##如果特征值重复出现，这里对特征向量值做叠加
            vecResult[vecList.index(feature)] += 1

    return vecResult