ML入门学习笔记

[foresight]

ML入门学习笔记
参考：GoogleDeveloper、《机器学习实战》、《周志华机器学习》、《机器之心》等

[foresight]

基于贝叶斯决策理论的分类方法

概论

• 优点：在数据较少的情况下仍然有效，可以处理多类别问题
• 缺点：对于输入数据的准备方式较为敏感
• 适用数据类型：标称型数据

贝叶斯决策理论

• 核心思想：选择具有最高概率的决策
• p1(x,y) > p2(x,y) 则为类别1
• p1(x,y) < p2(x,y) 则为类别2

Bayes准则

• 一元：P(A∩B) = P(A)*P(B|A)=P(B)*P(A|B)如上公式也可变形为：P(A|B)=P(B|A)*P(A)/P(B)。

• 二元：p(c|x,y) = p(x,y|c)*p(c)/p(x,y)

使用朴素贝叶斯进行文档分类

• 准备数据

# 导入numpy
from numpy import *

# 测试用数据
def loadDataSet():
    postingList=[['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']]
    # 1表示含侮辱性词，0表示不含
    classVec = [0,1,0,1,0,1]    #1 is abusive, 0 not
    # 返回词条矩阵和标记向量
    return postingList,classVec

# 求词条的并集，也就是将所有单词不重复的添加到一个数组中
def createVocabList(dataSet):
  # 建空集，一个一个添加进去，最后返回
    vocabSet = set([])  #create empty set
    for document in dataSet:
      # ｜求并集,不重复的将单词加入数组
        vocabSet = vocabSet | set(document) #union of the two sets
    return list(vocabSet)

# 输入词汇表和某个文档，作用是检测文档中的单词在词汇表中是否出现，并返回向量
def setOfWords2Vec(vocabList, inputSet):
  # 词汇表等长0向量
    returnVec = [0]*len(vocabList)
    # 遍历文档
    for word in inputSet:
      # 若文档中单词在词汇表中存在
        if word in vocabList:
          # 向量相应位置为1
            returnVec[vocabList.index(word)] = 1
        else: print "the word: %s is not in my Vocabulary!" % word
    return returnVec

• 训练算法：朴素贝叶斯分类器

训练算法：
构建出词汇表
统计每种文档中出现的词语的数目，记录在词汇表向量中
对每个类别，分别统计每个词出现在该类别中的频率
对每个类别，出现在该类别概率大的就认定为这个词是该类的

 # 传入对于每个句子的词汇表是否存在的向量，向量和词汇表一样长；以及标记的句子是否含侮辱性词汇
  def trainNB0(trainMatrix,trainCategory):
    # 句子个数
    numTrainDocs = len(trainMatrix)
    # 词汇表长度
    numWords = len(trainMatrix[0])
    # 属于侮辱性文档概率
    pAbusive = sum(trainCategory)/float(numTrainDocs)
    
    # 将p初始化为1/2的目的是防止概率乘积为0
    p0Num = ones(numWords); p1Num = ones(numWords)#单位向量 
    p0Denom = 2.0; p1Denom = 2.0                 	#p初始化为1/2
    
    # 对于每个句子
    for i in range(numTrainDocs):
      # 如果这个句子被标有含侮辱性
        if trainCategory[i] == 1:
          	# 侮辱性句子的词汇向量
            p1Num += trainMatrix[i]
            # 侮辱性句子的词汇数
            p1Denom += sum(trainMatrix[i])
       # 句子被标为正常
        else:
          	# 正常句子的词汇向量
            p0Num += trainMatrix[i]
            # 正常句子的词汇数
            p0Denom += sum(trainMatrix[i])
    # 对于侮辱性句子的每一个词汇/侮辱性句子的词汇数
    # log避免下溢出或者被舍掉，p的乘积可以转化为对数加法
    p1Vect = log(p1Num/p1Denom)          #change to log()
    # 正常句子同上
    p0Vect = log(p0Num/p0Denom)          #change to log()
    return p0Vect,p1Vect,pAbusive
  # 可以大致知道哪一个词为侮辱性词

# 基于贝叶斯决策论
def classifyNB(vec2Classify, p0Vec, p1Vec, pClass1):
  # 乘法是对应位置元素相乘
  # 做过乘法后将每个元素相加加到该类别的对数概率上
  # p1Vec和p2Vec已经做过求log()
    p1 = sum(vec2Classify * p1Vec) + log(pClass1)# 条件概率，pClass1可以看作“前提条件”
    p0 = sum(vec2Classify * p0Vec) + log(1.0 - pClass1)
 
    # 依据贝叶斯决策论返回结果
    if p1 > p0:
        return 1
    else: 
        return 0

• 测试算法

# 封装好的测试算法
def testingNB():
  	# 构造训练集
    listOPosts,listClasses = loadDataSet()
    # 求的词汇表
    myVocabList = createVocabList(listOPosts)
    trainMat=[]
    # 每个句子的词汇表向量
    for postinDoc in listOPosts:
        trainMat.append(setOfWords2Vec(myVocabList, postinDoc))
    # 每个类别的对应的词汇的出现概率和这个文档是否为侮辱性文档
    p0V,p1V,pAb = trainNB0(array(trainMat),array(listClasses))
    
    # 测试集（正常句子）
    testEntry = ['love', 'my', 'dalmation']
    # 测试集对应的词汇表向量
    thisDoc = array(setOfWords2Vec(myVocabList, testEntry))
    # 打印结果
    print testEntry,'classified as: ',classifyNB(thisDoc,p0V,p1V,pAb)
    # 打印结果
    
    # 测试集（侮辱性句子）
    testEntry = ['stupid', 'garbage']
    thisDoc = array(setOfWords2Vec(myVocabList, testEntry))
    print testEntry,'classified as: ',classifyNB(thisDoc,p0V,p1V,pAb)

import payes
bayes.testingNB()

output:
['love', 'my', 'dalmation'] classified as:  0
['stupid', 'garbage'] classified as:  1

实战应用：使用朴素贝叶斯过滤垃圾邮件

• 训练算法：已经构建的trainNB()

  测试算法：classifyNB(),并构建新测试集

• 准备数据：切分文本

  用python.split类似Java(String.split())

def textParse(bigString):
    import re # 正则表达式库
    # 从任何不为单词数字的地方分割
    listOfTokens = re.split(r'\W', bigString) # 源书本上代码误为\W*
    # 将长度大于二的留下并小写
    return [tok.lower() for tok in listOfTokens if len(tok) > 2]

# 词袋模型，查看生成向量，input内单词出现几次
def bagOfWords2VecMN(vocabList, inputSet):
    returnVec = [0]*len(vocabList)
    for word in inputSet:
        if word in vocabList:
            returnVec[vocabList.index(word)] += 1
    return returnVec

• 测试算法

def spamTest():
  	# 每封邮件的词汇表，一封邮件一行
    # 按顺序，是否为垃圾邮件，和词汇表中邮件的排列一致
    # 所有邮件的词汇表汇总，但是有重复，只是简单的append
    docList=[]; classList = []; fullText =[]
    # 对于垃圾邮件和一般邮件
    for i in range(1,26):
      	# 对于垃圾邮件
        wordList = textParse(open('email/spam/%d.txt' % i).read())
        docList.append(wordList)
        fullText.extend(wordList)
        classList.append(1)
        # 对于一般邮件
        wordList = textParse(open('email/ham/%d.txt' % i).read())
        docList.append(wordList)
        fullText.extend(wordList)
        classList.append(0)
    # 创建所有邮件的词汇表，也就是求并集，单词不重复
    vocabList = createVocabList(docList)
    # 创建测试集,pyhton3.0
    trainingSet = list(range(50)); testSet=[]
    # 随机生成测试集索引，并设置训练集索引
    for i in range(10):
        randIndex = int(random.uniform(0,len(trainingSet)))
        testSet.append(trainingSet[randIndex])
        del(trainingSet[randIndex])  
    # 训练集词袋矩阵，训练集中每个词袋的对应的邮件的种类
    trainMat=[]; trainClasses = []
    # 生成训练集
    for docIndex in trainingSet:
    		trainMat.append(bagOfWords2VecMN(vocabList,docList[docIndex]))
    		trainClasses.append(classList[docIndex])
    # 训练模型
    p0V,p1V,pSpam = trainNB0(array(trainMat),array(trainClasses))
    # 测试
    errorCount = 0
    for docIndex in testSet:
        # 测试集的词袋矩阵
        wordVector = bagOfWords2VecMN(vocabList, docList[docIndex])
        if classifyNB(array(wordVector),p0V,p1V,pSpam) != classList[docIndex]:
            errorCount += 1
            print ("classification error",docList[docIndex])
    print ('the error rate is: ',float(errorCount)/len(testSet))
    return vocabList,fullText
  
# 基于贝叶斯决策论
def classifyNB(vec2Classify, p0Vec, p1Vec, pClass1):
  # 乘法是对应位置元素相乘
  # 做过乘法后将每个元素相加加到该类别的对数概率上
  # p1Vec和p2Vec已经做过求log()
  # p1Vec的一个元表示的意义是垃圾文件中每个词出现的概率
    p1 = sum(vec2Classify * p1Vec) + log(pClass1)# 条件概率，pClass1可以看作“前提条件”
    p0 = sum(vec2Classify * p0Vec) + log(1.0 - pClass1)
    # 依据贝叶斯决策论返回结果
    if p1 > p0:
        return 1
    else: 
        return 0

[foresight]

K-近邻算法

概述

• 采用测量不同特征值之间的距离方法进行分类
• 优点：精度高、异常值不敏感、无数据输入假定
• 缺点：复杂度高
• 适用：数值型、标称型

准备与实现

• kNN步骤

  • 计算已知类别数据集中点和当前点的距离
  • 按照距离递增次序排列
  • 选取与当前点距离最小的k个点
  • 确定前k个点所在类别的出现频率
  • 返回出现最高的类别作为当前类别

• # kNN
  def classify0(inX, dataSet, labels, k):
      dataSetSize = dataSet.shape[0]
      # 计算距离
      diffMat = tile(inX, (dataSetSize,1)) - dataSet
      sqDiffMat = diffMat**2
      sqDistances = sqDiffMat.sum(axis=1) #欧式距离公式
      distances = sqDistances**0.5
      sortedDistIndicies = distances.argsort() #返回排序索引
      # 选择距离最小的点
      classCount={}          
      for i in range(k):
          voteIlabel = labels[sortedDistIndicies[i]]
          classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
      # 排序
      sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
      #返回类
      return sortedClassCount[0][0]
  

[foresight]

Logistic回归

• 首次接触最优化算法

概述

• 利用Logistic回归进行分类的主要思想是：根据现有数据对分类边界线建立回归公式，由此进行分类

基于Logistic回归和Sigmoid函数的分类

• Logistic回归特点：

  • 优点：计算代价不高，易于理解和实现
  • 缺点：容易欠拟合，分类精度不高
  • 适用：数值型和标称型

• Sigmoid函数具有类似单位阶跃函数（海维赛德阶跃函数）的性质:$sigma(z) = 1/(1+exp(-z))$

• Logistic回归分类器：每一个特征上乘一个回归系数(weight)，相加后带入Sigmoid函数（是否也可以看作归一化思想呢？），最后与0.5判断。小于0.5判为0类，大于判为1类

基于最优化方法的最佳回归系数确定

• 带入Sigmoid函数的变量为：$z=w_0<em>x_0+w_1</em>x_1+w_2<em>x_2+w_3</em>x_3+...+w_n*x_n=W^TX$
• 向量W就是我们要找的最佳参数(weight)

梯度上升法

• 梯度上升法基于的思想是：要找到某函数的最大值，最好的方法是沿着该函数的梯度方向探寻
• 迭代公式： w := w + å*∆f(w) （å为步长，步长乘梯度）

训练算法：使用梯度上升找到最佳参数

梯度上升伪代码：
	每个回归系数初始化为1
	重复R次：
			计算整个数据集的梯度
			alpha * gradient更新回归系数向量
	返回回归系数

# 打开训练集
def loadDataSet():
  	# 数据矩阵，标签矩阵
    dataMat = []; labelMat = []
    # 数据文件
    # x1 x2 label
    # -0.017612	14.053064	0
    fr = open('testSet.txt')
    # 对于数据集中的每一个点
    for line in fr.readlines():
        lineArr = line.strip().split()
        dataMat.append([1.0, float(lineArr[0]), float(lineArr[1])])
        labelMat.append(int(lineArr[2]))
    return dataMat,labelMat

# Sigmoid函数
def sigmoid(inX):
    return 1.0/(1+exp(-inX))

# 求最佳回归系数
def gradAscent(dataMatIn, classLabels):
  	# 转换为Numpy矩阵
    dataMatrix = mat(dataMatIn)   
    # 转置Label向量（由行向量转置为列向量）
    labelMat = mat(classLabels).transpose()
    m,n = shape(dataMatrix)
    # 步长
    alpha = 0.001
    # 迭代次数
    maxCycles = 500
    # 初始化系数全部为单位矩阵
    weights = ones((n,1))
    for k in range(maxCycles):              #heavy on matrix operations
      
        h = sigmoid(dataMatrix*weights)     #matrix mult，返回列向量
        error = (labelMat - h)              #vector subtraction 求损失
        # 定性地说，这里其实就是计算真实类别和预测类别的差值，按照该差值的方向调整回归函数
        
        weights = weights + alpha * dataMatrix.transpose()* error #matrix mult 迭代
        # 运用梯度的思想，但其实计算起来并不是需要梯度
    return weights

分析数据：画出决策边界

def plotBestFit(weights):
    import matplotlib.pyplot as plt
    dataMat,labelMat=loadDataSet()
    dataArr = array(dataMat)
    n = shape(dataArr)[0] 
    xcord1 = []; ycord1 = []
    xcord2 = []; ycord2 = []
    for i in range(n):
        if int(labelMat[i])== 1:
            xcord1.append(dataArr[i,1]); ycord1.append(dataArr[i,2])
        else:
            xcord2.append(dataArr[i,1]); ycord2.append(dataArr[i,2])
    fig = plt.figure()
    ax = fig.add_subplot(111)
    ax.scatter(xcord1, ycord1, s=30, c='red', marker='s')
    ax.scatter(xcord2, ycord2, s=30, c='green')
    # python3
    x = [arange(-3.0, 3.0, 0.1)]
    y = (-weights[0]-weights[1]*x)/weights[2]
    ax.plot(x, y)
    plt.xlabel('X1'); plt.ylabel('X2');
    plt.show()

[foresight]

kMeans初步实现-基于iris数据集

• 随机选择K个中心点
• 把每个数据点分配到离它最近的中心点
• 重新计算每类中的点到该类中心点距离的平均值
• 分配每个数据到它最近的中心点；
• 重复步骤3和4，直到所有的观测值不再被分配或是达到最大的迭代次数

import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
import random
import collections



# 载入数据
def loadData():
    iris = pd.read_csv("../iris.csv",header=None)
    k = len(iris[4].value_counts())
    lables = iris.iloc[:,4:].values.tolist()
    dataMat = np.array(iris.iloc[:,0:4].values.tolist())
    return k,dataMat,lables


# # 欧式距离
def distance(mat1,mat2):
    return np.sqrt(sum((mat1-mat2)**2))
# def distance(mat1,mat2):
#     diffMat = mat1 - mat2
#     sqDiffMat = diffMat**2
#     sqDistance = sqDiffMat.sum(axis = 1)
#     distance = sqDistance**0.5
#     return distance


def randomPoint(k,dataMat):
    randomPointList = random.sample(range(0,150), k)
    point = np.zeros( (k,4) )
    index = 0
    for i in randomPointList:
        point[index] = dataMat[i]
        index+=1
    return point,randomPointList

# 簇个数，数据集，最大迭代次数
def kMeans(maxTimes):
    # 载入数据
    k,dataMat,lables = loadData()
    # 数据集长度
    length = dataMat.shape[0]
    # 随机产生的最开始的点
    point,cPoints = randomPoint(k,dataMat)
    # 第一次分配
    classes = []
    for i in range(0,k):
        classes.append([])
    for i in range(0,length):
        if( i in cPoints):
            continue 
        distanceList = []
        for x in cPoints:
            distanceList.append(distance(dataMat[i],dataMat[x]))
            max_index = distanceList.index(min(distanceList))
        classes[max_index].append(i)
    
    
    # 迭代次数
    count = 0
    while(count < maxTimes):
        pointTemp = np.zeros( (k,4) )
        for i in range(0,3):
            for index in classes[i]:
                pointTemp[i] += dataMat[index]
            classlength = float(len(classes[i]))
            pointTemp[i]/=classlength
            
        classes = []
        for i in range(0,k):
            classes.append([])
            
        for i in range(0,length):
            distanceList = []
            for x in pointTemp:
                distanceList.append(distance(dataMat[i],x))
                max_index = distanceList.index(min(distanceList))
            classes[max_index].append(i)

            
        # 如果收敛
        if((pointTemp == point).all()):
            break
        else:
            point = pointTemp
            count+=1
            
            
            
    # 票选出最终结果
    result = []
    for i in range(0,3):
        frequency = {}
        for index in classes[i]:
            if lables[index][0] not in frequency:
                frequency[lables[index][0]] = 1
            else:
                frequency[lables[index][0]] += 1
        result.append(max(frequency,key=frequency.get))
    
    return result,count,classes,lables

def test(result,classes,k,lables):
    error = 0 
    for i in range(0,k):
        for index in classes[i]:
            if(lables[index][0] != result[i]):
                error+=1
    print(1-error/150.0)
    return

result,count,classes,lables = kMeans(20)

test(result,classes,3,lables)

• iris数据集
• Iris数据集是常用的分类实验数据集，由Fisher, 1936收集整理。Iris也称鸢尾花卉数据集，是一类多重变量分析的数据集。数据集包含150个数据样本，分为3类，每类50个数据，每个数据包含4个属性。可通过花萼长度，花萼宽度，花瓣长度，花瓣宽度4个属性预测鸢尾花卉属于（Setosa，Versicolour，Virginica）三个种类中的哪一类。

5.1	3.5	1.4	0.2	Iris-setosa
4.9	3.0	1.4	0.2	Iris-setosa
4.7	3.2	1.3	0.2	Iris-setosa
4.6	3.1	1.5	0.2	Iris-setosa
5.0	3.6	1.4	0.2	Iris-setosa
5.4	3.9	1.7	0.4	Iris-setosa
4.6	3.4	1.4	0.3	Iris-setosa
5.0	3.4	1.5	0.2	Iris-setosa
4.4	2.9	1.4	0.2	Iris-setosa
4.9	3.1	1.5	0.1	Iris-setosa
5.4	3.7	1.5	0.2	Iris-setosa
4.8	3.4	1.6	0.2	Iris-setosa
4.8	3.0	1.4	0.1	Iris-setosa
4.3	3.0	1.1	0.1	Iris-setosa
5.8	4.0	1.2	0.2	Iris-setosa
5.7	4.4	1.5	0.4	Iris-setosa
5.4	3.9	1.3	0.4	Iris-setosa
5.1	3.5	1.4	0.3	Iris-setosa
5.7	3.8	1.7	0.3	Iris-setosa
5.1	3.8	1.5	0.3	Iris-setosa
5.4	3.4	1.7	0.2	Iris-setosa
5.1	3.7	1.5	0.4	Iris-setosa
4.6	3.6	1.0	0.2	Iris-setosa
5.1	3.3	1.7	0.5	Iris-setosa
4.8	3.4	1.9	0.2	Iris-setosa
5.0	3.0	1.6	0.2	Iris-setosa
5.0	3.4	1.6	0.4	Iris-setosa
5.2	3.5	1.5	0.2	Iris-setosa
5.2	3.4	1.4	0.2	Iris-setosa
4.7	3.2	1.6	0.2	Iris-setosa
4.8	3.1	1.6	0.2	Iris-setosa
5.4	3.4	1.5	0.4	Iris-setosa
5.2	4.1	1.5	0.1	Iris-setosa
5.5	4.2	1.4	0.2	Iris-setosa
4.9	3.1	1.5	0.1	Iris-setosa
5.0	3.2	1.2	0.2	Iris-setosa
5.5	3.5	1.3	0.2	Iris-setosa
4.9	3.1	1.5	0.1	Iris-setosa
4.4	3.0	1.3	0.2	Iris-setosa
5.1	3.4	1.5	0.2	Iris-setosa
5.0	3.5	1.3	0.3	Iris-setosa
4.5	2.3	1.3	0.3	Iris-setosa
4.4	3.2	1.3	0.2	Iris-setosa
5.0	3.5	1.6	0.6	Iris-setosa
5.1	3.8	1.9	0.4	Iris-setosa
4.8	3.0	1.4	0.3	Iris-setosa
5.1	3.8	1.6	0.2	Iris-setosa
4.6	3.2	1.4	0.2	Iris-setosa
5.3	3.7	1.5	0.2	Iris-setosa
5.0	3.3	1.4	0.2	Iris-setosa
7.0	3.2	4.7	1.4	Iris-versicolor
6.4	3.2	4.5	1.5	Iris-versicolor
6.9	3.1	4.9	1.5	Iris-versicolor
5.5	2.3	4.0	1.3	Iris-versicolor
6.5	2.8	4.6	1.5	Iris-versicolor
5.7	2.8	4.5	1.3	Iris-versicolor
6.3	3.3	4.7	1.6	Iris-versicolor
4.9	2.4	3.3	1.0	Iris-versicolor
6.6	2.9	4.6	1.3	Iris-versicolor
5.2	2.7	3.9	1.4	Iris-versicolor
5.0	2.0	3.5	1.0	Iris-versicolor
5.9	3.0	4.2	1.5	Iris-versicolor
6.0	2.2	4.0	1.0	Iris-versicolor
6.1	2.9	4.7	1.4	Iris-versicolor
5.6	2.9	3.6	1.3	Iris-versicolor
6.7	3.1	4.4	1.4	Iris-versicolor
5.6	3.0	4.5	1.5	Iris-versicolor
5.8	2.7	4.1	1.0	Iris-versicolor
6.2	2.2	4.5	1.5	Iris-versicolor
5.6	2.5	3.9	1.1	Iris-versicolor
5.9	3.2	4.8	1.8	Iris-versicolor
6.1	2.8	4.0	1.3	Iris-versicolor
6.3	2.5	4.9	1.5	Iris-versicolor
6.1	2.8	4.7	1.2	Iris-versicolor
6.4	2.9	4.3	1.3	Iris-versicolor
6.6	3.0	4.4	1.4	Iris-versicolor
6.8	2.8	4.8	1.4	Iris-versicolor
6.7	3.0	5.0	1.7	Iris-versicolor
6.0	2.9	4.5	1.5	Iris-versicolor
5.7	2.6	3.5	1.0	Iris-versicolor
5.5	2.4	3.8	1.1	Iris-versicolor
5.5	2.4	3.7	1.0	Iris-versicolor
5.8	2.7	3.9	1.2	Iris-versicolor
6.0	2.7	5.1	1.6	Iris-versicolor
5.4	3.0	4.5	1.5	Iris-versicolor
6.0	3.4	4.5	1.6	Iris-versicolor
6.7	3.1	4.7	1.5	Iris-versicolor
6.3	2.3	4.4	1.3	Iris-versicolor
5.6	3.0	4.1	1.3	Iris-versicolor
5.5	2.5	4.0	1.3	Iris-versicolor
5.5	2.6	4.4	1.2	Iris-versicolor
6.1	3.0	4.6	1.4	Iris-versicolor
5.8	2.6	4.0	1.2	Iris-versicolor
5.0	2.3	3.3	1.0	Iris-versicolor
5.6	2.7	4.2	1.3	Iris-versicolor
5.7	3.0	4.2	1.2	Iris-versicolor
5.7	2.9	4.2	1.3	Iris-versicolor
6.2	2.9	4.3	1.3	Iris-versicolor
5.1	2.5	3.0	1.1	Iris-versicolor
5.7	2.8	4.1	1.3	Iris-versicolor
6.3	3.3	6.0	2.5	Iris-virginica
5.8	2.7	5.1	1.9	Iris-virginica
7.1	3.0	5.9	2.1	Iris-virginica
6.3	2.9	5.6	1.8	Iris-virginica
6.5	3.0	5.8	2.2	Iris-virginica
7.6	3.0	6.6	2.1	Iris-virginica
4.9	2.5	4.5	1.7	Iris-virginica
7.3	2.9	6.3	1.8	Iris-virginica
6.7	2.5	5.8	1.8	Iris-virginica
7.2	3.6	6.1	2.5	Iris-virginica
6.5	3.2	5.1	2.0	Iris-virginica
6.4	2.7	5.3	1.9	Iris-virginica
6.8	3.0	5.5	2.1	Iris-virginica
5.7	2.5	5.0	2.0	Iris-virginica
5.8	2.8	5.1	2.4	Iris-virginica
6.4	3.2	5.3	2.3	Iris-virginica
6.5	3.0	5.5	1.8	Iris-virginica
7.7	3.8	6.7	2.2	Iris-virginica
7.7	2.6	6.9	2.3	Iris-virginica
6.0	2.2	5.0	1.5	Iris-virginica
6.9	3.2	5.7	2.3	Iris-virginica
5.6	2.8	4.9	2.0	Iris-virginica
7.7	2.8	6.7	2.0	Iris-virginica
6.3	2.7	4.9	1.8	Iris-virginica
6.7	3.3	5.7	2.1	Iris-virginica
7.2	3.2	6.0	1.8	Iris-virginica
6.2	2.8	4.8	1.8	Iris-virginica
6.1	3.0	4.9	1.8	Iris-virginica
6.4	2.8	5.6	2.1	Iris-virginica
7.2	3.0	5.8	1.6	Iris-virginica
7.4	2.8	6.1	1.9	Iris-virginica
7.9	3.8	6.4	2.0	Iris-virginica
6.4	2.8	5.6	2.2	Iris-virginica
6.3	2.8	5.1	1.5	Iris-virginica
6.1	2.6	5.6	1.4	Iris-virginica
7.7	3.0	6.1	2.3	Iris-virginica
6.3	3.4	5.6	2.4	Iris-virginica
6.4	3.1	5.5	1.8	Iris-virginica
6.0	3.0	4.8	1.8	Iris-virginica
6.9	3.1	5.4	2.1	Iris-virginica
6.7	3.1	5.6	2.4	Iris-virginica
6.9	3.1	5.1	2.3	Iris-virginica
5.8	2.7	5.1	1.9	Iris-virginica
6.8	3.2	5.9	2.3	Iris-virginica
6.7	3.3	5.7	2.5	Iris-virginica
6.7	3.0	5.2	2.3	Iris-virginica
6.3	2.5	5.0	1.9	Iris-virginica
6.5	3.0	5.2	2.0	Iris-virginica
6.2	3.4	5.4	2.3	Iris-virginica
5.9	3.0	5.1	1.8	Iris-virginica

[foresight]

决策树算法

1. 简单概括

利用熵将整个数据集进行分割

使得分割后数据集的熵最小

不断对子数据集进行递归

直至无法进一步分割或者子数据集里数据的标签都一致时递归结束

分割的过程会形成一棵决策树

利用决策树将输入的数据归类到某一分割后的数据集中

子数据集所带有的标签就是决策的结果

2. 熵的定义和实现

熵定义为信息的期望值

• 信息的计算公式为
  $l(x_i) = -log_2p(x_i) \quad$
  其中$p(x_i)$是选择某一分类的概率

• 信息的期望值为
  $H = -\sum_{i=1}^n p(x_i)log_2p(x_i)$

• 核心代码

  def calcShannon(dataSet):
      dataSetSize = len(dataSet)
      result = {}
      # 利用字典统计每一种标签的数据数量
      for data in dataSet:
          label = data[-1]
          result[label] = result.get(label, 0) + 1
      shannon = 0
      # 对于每一种分类计算其概率并统计信息熵
      for key in result:
          prob = result[key]/dataSetSize
          shannon -= prob * math.log(prob, 2)
      return shannon
  

3. 分割数据集

# 分割数据集，将维度axis且值为value的数据单独提取出来
def splitDataSet(dataSet, axis, value):
    result = []
    for data in dataSet:
        if data[axis] == value:
            # 使用axis分割后将axis这一列从数据中去掉
            tmp = data[:axis]
            # 这里通过entend拼接数组跳过了axis这一列
            tmp.extend(data[axis+1:])
            result.append(tmp)
    return result

4. 选择最好的分割维度

def chooseBestSplitAxis(dataSet):
    numOfAxis = len(dataSet[0]) - 1
    baseEntropy = calcShannon(dataSet)
    bestInfoGain = 0.0
    bestAxis = -1
    # 对所有维度都循环试验
    for axis in range(numOfAxis):
        allValue = [x[axis] for x in dataSet]
        # 维度下所有可能的不重复值
        valueSet = set(allValue)
        newEntropy = 0.0
        for value in valueSet:
            # 按不重复的值分割成子数据集
            subDataSet = splitDataSet(dataSet, axis, value)
            prob = float(len(subDataSet)) / float(len(dataSet))
            # 新的熵为部分熵按比例求和
            newEntropy += prob * calcShannon(subDataSet)
        # 作差为正说明新熵比旧熵小，混乱程度减小
        # newInfoGain = baseEntropy - newEntropy
        # if newInfoGain > bestInfoGain:
            # bestAxis = axis
            # bestInfoGain = newInfoGain
        if newEntropy < baseEntropy:
            # 上面源码有点绕 简单理解就是熵变小了就选择
            bestAxis = axis
    return bestAxis

5. 生成决策树

def createTree(dataSet, labels):
    labelList = [data[-1] for data in dataSet]
    # 递归出口一：子数据集的标签已经统一只有一种，不需要再进一步分割
    if labelList.count(labelList[0]) == len(labelList):
        return labelList[0]
    # 递归出口二：子数据集已经没有了可分割的维度只剩下了标签
    if len(dataSet[0]) == 1:
        # 统计子数据集中出现次数最多的标签即为决策结果
        return voteMaxLabel(labelList)
    # 选择熵最小的分割维度
    bestAxis = chooseBestSplitAxis(dataSet)
    bestLabel = labels[bestAxis]
    # 建立决策树字典
    myTree = {bestLabel: {}}
    # 删除已用于分割的维度对应的标签
    del(labels[bestAxis])
    allValue = [x[bestAxis] for x in dataSet]
    valueSet = set(allValue)
    for value in valueSet:
        # 复制一遍标签
        subLabel = labels[:]
        # 采用最好的分割方法分割数据集后递归生成子树
        myTree[bestLabel][value] = createTree(splitDataSet(dataSet, bestAxis, value), subLabel)
    return myTree

6. 利用决策树进行决策

• 决策树生成范例

  {'flippers': {0: 'no', 1: {'no surfacing': {0: 'no', 1: 'yes'}}}}

  其中每一次决策需要用到决策树的两层

  以这里的决策树为例

  第一层‘flippers’为进行决策的标签

  第二层的0和1为在该标签下进行决策的不同选择

• 核心代码

def classifyByTree(tree, labels, data):
    # 得到进行决策的标签
    firstLabel = list(tree.keys())[0]
    # 用该标签进行决策的子树
    secondDict = tree[firstLabel]
    # 得到用于决策的标签所属的维度，用于后面取出数据在该维度的值
    firstLabelIndex = labels.index(firstLabel)
    classLabel = 'Error'
    # 对于该标签下进行决策的不同的值
    for value in secondDict.keys():
        # 如果数据在该决策标签维度下的值等于子树的决策值
        if data[firstLabelIndex] == value:
            # 如果子树下还有子树（即还是一个字典类型的数据）则继续进行决策
            if type(secondDict[value]).__name__ == 'dict':
                classLabel = classifyByTree(secondDict[value], labels, data)
            else:
                # 否则子树下的值就是决策的结果
                classLabel = secondDict[value]
    return classLabel

[foresight]

MachineLearning入门初识

• 参考Google developer https://developers.google.cn/machine-learning/crash-course
• 参考《机器学习实战》

什么是（监督式）机器学习？

• 机器学习系统通过学习如何组合输入信息来对从未见过的数据做出有用的预测

标签

• 标签是我们要预测的事物，即简单线性回归中的 y 变量。标签可以是小麦未来的价格、图片中显示的动物品种、音频剪辑的含义或任何事物。

特征

• 特征是输入变量，即简单线性回归中的 x 变量。简单的机器学习项目可能会使用单个特征，而比较复杂的机器学习项目可能会使用数百万个特征

样本

• 样本是指数据的特定实例：
  • 有标签样本
  • 无标签样本
  • • **我们使用有标签样本来训练模型。**在垃圾邮件检测器中，有标签样本是用户明确标记为“垃圾邮件”或“非垃圾邮件”的各个电子邮件。
    • **在使用有标签样本训练模型之后，我们会使用该模型预测无标签样本的标签。**在垃圾邮件检测器示例中，无标签样本是用户尚未添加标签的新电子邮件。
• • labeled examples: {features, label}: (x, y) 有特征和标签
    • 例如房子的大小，房型，房间数；而房价则可称为标签；
  • unlabeled examples: {features, ?}: (x, ?) 有特征而无标签
    • 房子大小房型知道，房价未知
• 个人理解：标签是更为主观的判断

模型

• 模型定义了特征与标签之间的关系。
• 训练是指创建或学习模型。也就是说，向模型展示有标签样本，让模型逐渐学习特征与标签之间的关系。
• 推断是指将训练后的模型应用于无标签样本。也就是说，使用经过训练的模型做出有用的预测 (y')。例如，在推断期间，您可以针对新的无标签样本预测 medianHouseValue.（即由房型，大小，房间数推断价格）

回归与分类

• 回归模型可预测连续值。例如，回归模型做出的预测可回答如下问题：
  • 加利福尼亚州一栋房产的价值是多少？
  • 用户点击此广告的概率是多少？
• 分类模型可预测离散值。例如，分类模型做出的预测可回答如下问题：
  • 某个指定电子邮件是垃圾邮件还是非垃圾邮件？
  • 这是一张狗、猫还是仓鼠图片？

线性回归

• 
• 即可简单的写出模型方程式

训练与损失

平方损失：一种常见的损失函数

= the square of the difference between the label and the prediction
= (observation - prediction(x))2
= (y - y')2

均方误差 (MSE)

• 指的是每个样本的平均平方损失。要计算 MSE，请求出各个样本的所有平方损失之和，然后除以样本数量。

迭代方法

• hot and cold 游戏
• • 初始值
  • 计算损失
  • “计算参数更新”部分，机器学习系统就是在此部分检查损失函数的值，并为和生成新值。
  • 学习过程会持续迭代，直到该算法发现损失可能最低的模型参数
  • 不断迭代，直到总体损失不再变化或至少变化极其缓慢为止。这时候，我们可以说该模型已收敛。

梯度下降法

• 

梯度

• 函数的梯度是偏导数相对于所有自变量的矢量
• • z = f(x,y) 就像一个山谷，最低点为 (2,0,4)：的梯度是一个二维矢量，可让您了 解向哪个 (x,y) 方向移动时高度下降得最快。也就是说，梯度矢量指向山谷。
  • 梯度是矢量：具有大小和方向
  • 在机器学习中，梯度用于梯度下降法。我们的损失函数通常具有很多变量，而我们尝试通过跟随函数梯度的负方向来尽量降低损失函数。

学习速率

• 每个回归问题都存在一个金发姑娘学习速率。“金发姑娘”值与损失函数的平坦程度相关。
• 学习速率过大：如果您知道损失函数的梯度较小，则可以放心地试着采用更大的学习速率，以补偿较小的梯度并获得更大的步长。
• 学习速率过小花费更多时间

优化学习速率

playground>>>https://developers.google.cn/machine-learning/crash-course/fitter/graph

随机梯度下降法

• 通过从我们的数据集中随机选择样本，我们可以通过小得多的数据集估算（尽管过程非常杂乱）出较大的平均值。 随机梯度下降法 (SGD) 将这种想法运用到极致，它每次迭代只使用一个样本（批量大小为 1）。如果进行足够的迭代，SGD 也可以发挥作用，但过程会非常杂乱。
• 批量指的是用于在单次迭代中计算梯度的样本总数
• 批量大小越大，出现冗余的可能性就越高。一些冗余可能有助于消除杂乱的梯度，但超大批量所具备的预测价值往往并不比大型批量高。
• “随机”这一术语表示构成各个批量的一个样本都是随机选择的。

Playground

• playground>>>http://playground.tensorflow.org/

[foresight]

随机森林RandomForest

基本思想

• 随机森林的结果是依赖于多棵决策树的结果，这是一种集成学习的思想
• 随机思想：随机选取一定数量的特征（需调参），再从中选取最优的几组特征（GINI、熵、OOB）
• 票选的思想：最终的结果是多棵决策树票选的结果

基本步骤

• 随机抽样训练决策树（选取最优的几组决策树）
• 随机选取属性做节点分裂属性（选取最优的几组属性）
• 重复步骤2，直到不能再分裂
• 建立大量决策树，形成森林

GINI指数（评估特征的重要性）

• 用随机森林进行特征重要性评估的思想其实很简单，说白了就是看看每个特征在随机森林中的每颗树上做了多大的贡献，然后取个平均值，最后比一比特征之间的贡献大小。

• Gini指数越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高，反之，集合越不纯。

• Gini = 1 – Σ (Pi)2 for i=1 to number of classes(pi is squared probabilities of each class)

  # 计算GINI，gini表示不纯度，越小越纯，越大越不纯
  def calGini(dataSet):
      # 创建字典，统计该数据集中的各个标签的数量
      lables = calculateDiffCount(dataSet)
      # 计算gini
      length = len(dataSet)
      gini = 1.0
      for key in lables.keys():
          gini -= (lables[key]/length)**2
      return gini

实现（基于GINI指数,Pima数据集）

• Pima印第安人数据集
  【1】Pregnancies：怀孕次数
  【2】Glucose：葡萄糖
  【3】BloodPressure：血压 (mm Hg)
  【4】SkinThickness：皮层厚度 (mm)
  【5】Insulin：胰岛素 2小时血清胰岛素（mu U / ml
  【6】BMI：体重指数 （体重/身高）^2
  【7】DiabetesPedigreeFunction：糖尿病谱系功能
  【8】Age：年龄 （岁）
  【9】Outcome：类标变量 （0或1）

6	148	72	35	0	33.6	0.627	50	1
1	85	66	29	0	26.6	0.351	31	0
8	183	64	0	0	23.3	0.672	32	1
1	89	66	23	94	28.1	0.167	21	0
0	137	40	35	168	43.1	2.288	33	1
5	116	74	0	0	25.6	0.201	30	0
3	78	50	32	88	31	0.248	26	1
......

• 导入库

import numpy as np
import random
# 一个是随机选取样本，一个是随机选取特征
# 决策树的个数、特征属性的个数、递归次数（即决策树的深度）

• 构建决策树部分

# 决策树部分

# 计算GINI，gini表示不纯度，越小越纯，越大越不纯
def calGini(dataSet):
    # 创建字典，统计该数据集中的各个标签的数量
    lables = calculateDiffCount(dataSet)
    # 计算gini
    length = len(dataSet)
    gini = 1.0
    for key in lables.keys():
        gini -= (lables[key]/length)**2
    return gini

# 对数据集dataSet，对于第col列特征，根据value划分为两个数据集
def splitData(dataSet,col,value):
    data1 = []
    data2 = []
    for line in dataSet:
        if(line[col] >= value):
            data1.append(line)
        else:
            data2.append(line)
    return data1,data2

# 数标签
def calculateDiffCount(datas):
    results = {}
    for data in datas:
        if data[-1] not in results:
            results[data[-1]] = 1
        else:
            results[data[-1]] += 1
    return results


# 递归调用，选取最佳的特征和最佳特征当中的最佳分割值
def BuildCartDecisionTree(dataSet,features,maxDepth,depth):
    
    if(depth >= maxDepth):
        return calculateDiffCount(dataSet)
    
    depth+=1
    
    # 目前的gini
    currentgini = calGini(dataSet)
    # 列数
    column_length = len(dataSet[0])
    # 行数（样本数）
    rows_length = len(dataSet)
    
    # giniIndex的差
    best_gini_gain = 0.0
    
    best_value = None
    best_set = None
    
    for col in features:
        values = set([x[col] for x in dataSet])
        for value in values:
            data1,data2 = splitData(dataSet,col,value)
            p = len(data1)/rows_length
            gini = p*calGini(data1)+(1-p)*calGini(data2)
            gain = currentgini-gini
            if(gain > best_gini_gain):
                best_gini_gain = gain
                best_value = (col,value)
                best_set = (data1,data2)
                

    if(best_gini_gain > 0.0):
        trueBranch = BuildCartDecisionTree(best_set[0], features,maxDepth,depth)
        falseBranch = BuildCartDecisionTree(best_set[1], features,maxDepth,depth)
        return (best_value[0],
                best_value[1],
                falseBranch,
                trueBranch)
    else:
        return calculateDiffCount(dataSet)

• 随机取特征

def getFeatures(dataSet,n_features):
    return random.sample(range(len(dataSet[0])-1),n_features)

• 导入数据

def loadData():
#     dataMat = []; labelMat = []
    alldataMat = []
    pima = open("../Pima.csv")
    for line in pima:
        lineArr = line.strip().split(',')
        float_map = map(float,lineArr)
        float_list = list(float_map)
#         dataMat.append(float_list[0:-1])
#         labelMat.append(int(lineArr[-1]))
        float_list[-1] = int(lineArr[-1])
        alldataMat.append(float_list)
    return alldataMat

• 切分数据集

# 切分数据集，以便交叉验证
# input(数据集，个数)
def spiltDataSet(dataSet,bag_nums):
    spiltedDataSet = []
    oneBagLength = int(len(dataSet)/bag_nums)
    data = []
    for index in random.sample(range(len(dataSet)),len(dataSet)):
        if(len(data) < oneBagLength):
            data.append(dataSet[index])
        else:
            spiltedDataSet.append(data)
            data = []
    return spiltedDataSet

• 建立森林

# 树的个数，随机选取的特征数，树的最大深度，随机分成的数据集的个数
def buildRandomForest(n_trees,n_features,max_tree_depth,n_dataSets):
    RForest = []
    # 载入数据
    dataMat = loadData()
    # 随机分数据集
    spiltedDataSet = spiltDataSet(dataMat,n_dataSets)
    # 构建n_trees棵树的森林
    for i in range(n_trees):
        features = getFeatures(dataMat,n_features)
        tree = BuildCartDecisionTree(spiltedDataSet[random.randint(0,len(spiltedDataSet)-1)],features,max_tree_depth,1)
        RForest.append(tree)
    return RForest

• 基于决策树分类数据

def classifyByTree(tree,data):
    lengthOfNode = len(tree)
    if(lengthOfNode == 4):
        feature = tree[0]
        value = tree[1]
        data_value = data[feature]
        if(data_value >= value):
            return classifyByTree(tree[3],data)
        else:
            return classifyByTree(tree[2],data)
    else:
        return max(tree,key=tree.get)

• 基于森林分类（票选）

def classifyByForest(forest,data):
    results = {}
    for tree in forest:
        result = classifyByTree(tree,data)
        if result not in results:
            results[result] = 1
        else:
            results[result] += 1
    return max(results,key=results.get)

• 计算准确度

def acc():
    forest = buildRandomForest(200,3,10,5)
    dataMat = loadData()
    count = 0
    for index in random.sample(range(len(dataMat)),len(dataMat)-1):
        result = classifyByForest(forest,dataMat[index])
        if(result == dataMat[index][-1]):
            count += 1
    return float(count/len(dataMat))

• 参考:
  1.通俗易懂图示剖析随机森林 https://blog.csdn.net/cg896406166/article/details/83796557
  2.Gini重要性评估 https://blog.csdn.net/zjuPeco/article/details/77371645
  3.票选带图示 https://www.sohu.com/a/234722514_787107
  4.票选 https://blog.csdn.net/zjuPeco/article/details/77371645
  5.GINI阿里实战：用Python实现随机森林 https://baijiahao.baidu.com/s?id=1621066120041839448&wfr=spider&for=pc
  6.IForesthttps://scikit-learn.org/stable/modules/generated/sklearn.ensemble.IsolationForest.html
  7.RForesthttps://scikit-learn.org/stable/modules/generated/sklearn.ensemble.RandomForestClassifier.html
  8.一文看懂RF https://easyai.tech/ai-definition/random-forest/

[foresight]

孤立森林

概述

• 孤立森林是用于异常检测的机器学习算法。这是一种无监督学习算法，通过隔离数据中的离群值识别异常。

基本思想

• 孤立森林是基于决策树的算法。从给定的特征集合中随机选择特征，然后在特征的最大值和最小值间随机选择一个分割值，来隔离离群值。这种特征的随机划分会使异常数据点在树中生成的路径更短，从而将它们和其他数据分开。

原理

• 孤立森林的原理是：异常值是少量且不同的观测值，因此更易于识别。孤立森林集成了孤立树，在给定的数据点中隔离异常值。
• 孤立森林通过随机选择特征，然后随机选择特征的分割值，递归地生成数据集的分区。和数据集中「正常」的点相比，要隔离的异常值所需的随机分区更少，因此异常值是树中路径更短的点，路径长度是从根节点经过的边数。

优势

• 用孤立森林，不仅可以更快地检测异常，还需要更少的内存。
• 孤立森林隔离数据点中的异常值，而不是分析正常的数据点。和其他正常的数据点相比，异常数据点的树路径更短，因此在孤立森林中的树不需要太大的深度，所以可以用更小的 max_depth 值，从而降低内存需求。

定义与拟合模型

我们要创建一个模型变量，并实例化 IsolationForest（孤立森林）类。将这四个参数的值传递到孤立森林方法中，如下所示。

• 评估器数量：n_estimators 表示集成的基评估器或树的数量，即孤立森林中树的数量。
• 最大样本：max_samples 是训练每个基评估器的样本的数量。如果 max_samples 比样本量更大，那么会用所用样本训练所有树。
• 数据污染问题：算法对这个参数非常敏感，它指的是数据集中离群值的期望比例，根据样本得分拟合定义阈值时使用。
• 最大特征：所有基评估器都不是用数据集中所有特征训练的。这是从所有特征中提出的、用于训练每个基评估器或树的特征数量。

import numpy as np
import pandas as pd
import seaborn as sns
import matplotlib.pyplot as plt
from sklearn.ensemble import IsolationForest

df = pd.read_csv('salary.csv')
df.head(len(df))

model=IsolationForest(n_estimators=100,
                      max_samples='auto', 
                      contamination='auto',# 
                      max_features=1.0)
model.fit(df[['salary']])

df['scores']=model.decision_function(df[['salary']])
df['anomaly']=model.predict(df[['salary']])
df.head(len(df))

anomaly=df.loc[df['anomaly']==-1]
anomaly_index=list(anomaly.index)
print(anomaly)
print(anomaly_index)

outliers_counter = len(df[df['salary'] > 9999999])
outliers_counter

print("Accuracy percentage:", 100*list(df['anomaly']).count(-1)/(outliers_counter))