2018-05-25 20:23:18 songzhiren5560 阅读数 424
  • 机器学习& 深度学习 基础视频教程(人工智能AI方向)

    机器学习,深度学习基础教程入门视频培训教程,该课程主要包含机器学习基础,包括常用的数据集、训练集、样本、特征、矩阵、Numpy数组、Pandas的使用等;机器学习数学基础,包括线形代数基础、概率基础、信息论基础、最优化基础等;机器学习算法,包括简单线形回归和逻辑回归、决策树、KNN、SVM、层次聚类、密度聚类等。这是一门非常好的AI入门教程。

    660 人正在学习 去看看 Array老师

最近在学习《机器学习实战》

    kNN算法是从训练集中找到和新数据最接近的k条记录(欧氏距离),然后根据他们的主要分类来决定新数据的类别。该算法涉及3个主要因素:训练集、距离或相似的衡量、k的大小。

一、运行kNN算法

    kNN算法可以解决如下问题,样本如下:


span group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])  
labels = ['A','A','B','B']  

然后要判断[1.1,1.2],[0.1,0.2]属于哪一类,首先创建kNN.py文件导入数据


def createDataSet():
    group = numpy.array([[1.0,1.1], [1.1,1.0], [0,0], [0,0.1]])
    labels = ['A','A','B','B']
    return group,labels

然后我们使用kNN算法

对待测样本点执行以下操作

1、计算待测点与样本点的欧氏距离;

2、按距离递增次序排列;

3、选择前k个点,计算其对应的标签,对标签次数按降序排列;

4、选择出现次数最多的标签作为kNN算法的预测结果

代码如下:


# K-近邻算法
def classify0(inX,dataSet,labels,k):
    dataSetSize = dataSet.shape[0]
    # 计算距离(欧氏距离)
    diffMat = numpy.tile(inX, (dataSetSize, 1)) - dataSet
    sqDiffMat = diffMat**2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances**0.5
    # 对距离排序返回排序后的索引
    sortedDistIndicies = distances.argsort()
    # 定义一个空的字典
    classCount = {}
    #选择距离最小的K个点
    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]

然后去当前文件目录下打开控制台启动python,进入Python交互式环境执行以下命令(这是一个简单的分类器)

>>>import kNN  
    >>> group,labels=kNN.createDataSet()  
    >>> kNN.classify0([1.1,1.2],group,labels,3)  
    'A'  
    >>> kNN.classify0([0.1,0.2],group,labels,3)  
    'B'  
    >>>  

二 运用kNN解决网站约会配对效果

数据集存放在文本文件datingTestSet.txt文件中,每个样本占据一行,一共1000行,主要包括了以下3个特征:

1、每年获得的飞行常客里程数

2、玩视频游戏所消耗时间

3、每周消费的冰淇淋公升数

2.1 从文本中解析数据并分析

将上述数据输入到分类器之前,需要将数据的格式处理为分类器可以接受的格式,在kNN.py中创建名为file2matrix函数,来处理输入格式问题,该程序如下:

# 将约会数据文本记录转化为numpy的解析程序
def file2matrix(filename):
    fr = open(filename)
    arrayOLines = fr.readlines()
    # 得到文件的行数
    numberOfLines = len(arrayOLines)
    # 创建返回Numpy的矩阵
    returnMat = numpy.zeros((numberOfLines, 3))
    classLabelVector = []
    index = 0
    # 解析文件数据到列表
    for line in arrayOLines:
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index,:] = listFromLine[0:3]
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
    return returnMat,classLabelVector

重新载入kNN.py(Python2版本是直接reload(kNN),但是Python3.6是 import importlib; importlib.reload(kNN))

再利用Matpoltlib可以创建散点图,观察数据分布:

>>> import kNN  
>>> datingDataMat,datingLabels = kNN.file2matrix('datingTestSet.txt')  
>>> import matplotlib  
>>> import matplotlib.pyplot as plt  
>>> fig=plt.figure()  
>>> ax=fig.add_subplot(111)  
>>> ax.scatter(datingDataMat[:,1],datingDataMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels))   
>>> plt.show()

    这里使用datingDataMat矩阵第二和第三列数据方分别表示“玩游戏所耗时间百分比”和“每周消耗冰激凌公升数”。得到效果图如下:



2.2 归一化数据 

在进行测试之前我们需要对数据进行归一化处理,不然数值大的属性对距离计算的影响十分巨大,所以我们需要将数据值处理到0到1 之间或者-1到1 之间,利用如下公式:

newValue = (oldValue - min) / (max - min)

我们需要在kNN.py文件里添加函数autoNorm(),该函数自动将数值转化到0和1之间:

# 归一化特征值(约会数据)
def autoNorm(dataSet):
    # 取最小值和最大值并计算差值
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    ranges = maxVals - minVals
    # 建立一个1000*3的矩阵 值都是0
    normDataSet = numpy.zeros(numpy.shape(dataSet),dtype=float)
    # 取dataSet的维度 1000
    m = dataSet.shape[0]
    # 利用公式进行归一化( newVal = (oldVal - min)/ranges )
    normDataSet = dataSet - numpy.tile(minVals, (m, 1))
    normDataSet = normDataSet/numpy.tile(ranges,(m, 1))
    return normDataSet,ranges,minVals

在Python命令提示符下,重新加载kNN.py模块,执行autoNorm函数,检测执行效果

>>> import importlib
>>> importlib.reload(kNN)
<module 'kNN' from 'E:\\pyCharm\\workspace\\test1\\learning\\kNN.py'>
>>> norMat,ranges,minVals = kNN.autoNorm(datingDataMat)
[[  4.09200000e+04   8.32697600e+00   9.52796000e-01]
 [  1.44880000e+04   7.15346900e+00   1.67274800e+00]
 [  2.60520000e+04   1.44187100e+00   8.03968000e-01]
 ...,
 [  2.65750000e+04   1.06501020e+01   8.65471000e-01]
 [  4.81110000e+04   9.13452800e+00   7.26889000e-01]
 [  4.37570000e+04   7.88260100e+00   1.33129000e+00]]
[[  9.12730000e+04   2.09193490e+01   1.69436100e+00]
 [  9.12730000e+04   2.09193490e+01   1.69436100e+00]
 [  9.12730000e+04   2.09193490e+01   1.69436100e+00]
 ...,
 [  9.12730000e+04   2.09193490e+01   1.69436100e+00]
 [  9.12730000e+04   2.09193490e+01   1.69436100e+00]
 [  9.12730000e+04   2.09193490e+01   1.69436100e+00]]

2.3 测试算法

机器学习的算法最重要的是要保证算发的正确率,这个例子用90%作为训练样本,10%作为测试,因为数据是随机分布的,索引选择前10%的数据用来测试,在文件中创建datingClassTest函数:

# 分类器针对约会网站的测试代码
def datingClassTest():
    # 取10%的数据进行测试
    hoRatio = 0.10
    datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')
    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 classfier 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)))

在Python命令提示符下,重新加载kNN.py模块,执行该函数,检测执行效果:

>>> import importlib
>>> importlib.reload(kNN)
<module 'kNN' from 'E:\\pyCharm\\workspace\\test1\\learning\\kNN.py'>
>>> kNN.datingClassTest()
the classfier came back with: 3,the real answer is : 3
the classfier came back with: 2,the real answer is : 2
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 3,the real answer is : 3
the classfier came back with: 3,the real answer is : 3
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 3,the real answer is : 3
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 2,the real answer is : 2
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 2,the real answer is : 2
the classfier came back with: 3,the real answer is : 3
the classfier came back with: 2,the real answer is : 2
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 3,the real answer is : 2
the classfier came back with: 3,the real answer is : 3
the classfier came back with: 2,the real answer is : 2
the classfier came back with: 3,the real answer is : 3
the classfier came back with: 2,the real answer is : 2
the classfier came back with: 3,the real answer is : 3
the classfier came back with: 2,the real answer is : 2
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 3,the real answer is : 3
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 3,the real answer is : 3
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 2,the real answer is : 2
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 2,the real answer is : 2
the classfier came back with: 3,the real answer is : 3
the classfier came back with: 3,the real answer is : 3
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 2,the real answer is : 2
the classfier came back with: 3,the real answer is : 3
the classfier came back with: 3,the real answer is : 3
the classfier came back with: 3,the real answer is : 3
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 2,the real answer is : 2
the classfier came back with: 2,the real answer is : 2
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 3,the real answer is : 3
the classfier came back with: 2,the real answer is : 2
the classfier came back with: 2,the real answer is : 2
the classfier came back with: 2,the real answer is : 2
the classfier came back with: 2,the real answer is : 2
the classfier came back with: 3,the real answer is : 3
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 2,the real answer is : 2
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 2,the real answer is : 2
the classfier came back with: 2,the real answer is : 2
the classfier came back with: 2,the real answer is : 2
the classfier came back with: 2,the real answer is : 2
the classfier came back with: 2,the real answer is : 2
the classfier came back with: 3,the real answer is : 3
the classfier came back with: 2,the real answer is : 2
the classfier came back with: 3,the real answer is : 3
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 2,the real answer is : 2
the classfier came back with: 3,the real answer is : 3
the classfier came back with: 2,the real answer is : 2
the classfier came back with: 2,the real answer is : 2
the classfier came back with: 3,the real answer is : 1
the classfier came back with: 3,the real answer is : 3
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 3,the real answer is : 3
the classfier came back with: 3,the real answer is : 3
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 2,the real answer is : 2
the classfier came back with: 3,the real answer is : 3
the classfier came back with: 3,the real answer is : 1
the classfier came back with: 3,the real answer is : 3
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 2,the real answer is : 2
the classfier came back with: 2,the real answer is : 2
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 3,the real answer is : 3
the classfier came back with: 2,the real answer is : 3
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 2,the real answer is : 2
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 3,the real answer is : 3
the classfier came back with: 3,the real answer is : 3
the classfier came back with: 2,the real answer is : 2
the classfier came back with: 1,the real answer is : 1
the classfier came back with: 3,the real answer is : 1
the total error rate is: 0.050000

由此可见,错误率为5%,可以改变函数datingClassSet内变量hoRatio和变量k的值,检测错误率是否随着变量值的变化而变化。依赖于分类算法、数据集和程序设置,分类器的输出结果都是不同的。

2.4 使用算法,构建完整系统

将下列代码加入kNN.py中,并重新载入:

# 约会网站预测函数
def calssifyPerson():
    resultList = ['not al all','is small doses','in large doses']
    percentTats = float(input("percentage of time spent playing video games?"))
    ffMiles = float(input("frequent flier miles earned per year?"))
    iceCream = float(input("liters of ice cream consumed per year?"))
    datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')
    normMat, ranges, minVals = autoNorm(datingDataMat)
    inArr = numpy.array([ffMiles,percentTats,iceCream])
    classifierResult = classify0((inArr - minVals)/ranges,normMat,datingLabels,3)
    print("you will probably like this person:",resultList[classifierResult - 1])

    执行上述函数,输入摸个用户三个特征的值,并返回判断结果:

>>> import importlib
>>> importlib.reload(kNN)
<module 'kNN' from 'E:\\pyCharm\\workspace\\test1\\learning\\kNN.py'>
>>> kNN.calssifyPerson()
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: is small doses


2018-07-03 17:28:25 sinat_30353259 阅读数 6562
  • 机器学习& 深度学习 基础视频教程(人工智能AI方向)

    机器学习,深度学习基础教程入门视频培训教程,该课程主要包含机器学习基础,包括常用的数据集、训练集、样本、特征、矩阵、Numpy数组、Pandas的使用等;机器学习数学基础,包括线形代数基础、概率基础、信息论基础、最优化基础等;机器学习算法,包括简单线形回归和逻辑回归、决策树、KNN、SVM、层次聚类、密度聚类等。这是一门非常好的AI入门教程。

    660 人正在学习 去看看 Array老师

1-1 机器学习算法分类

一、基本分类:

①监督学习(Supervised learning)

数据集中的每个样本有相应的“正确答案”, 根据这些样本做出
预测, 分有两类: 回归问题和分类问题。

步骤1: 数据集的创建和分类
步骤2: 训练
步骤3: 验证
步骤4: 使用

( 1) 回归问题举例
例如: 预测房价, 根据样本集拟合出一条连续曲线。
( 2) 分类问题举例
例如: 根据肿瘤特征判断良性还是恶性,得到的是结果是“良性”或者“恶性”, 是离散的。

监督学习:从给定的训练数据集中学习出一个函数(模型参数), 当新的数据到来时,可以根据这个函数预测结果。监督学习的训练集要求包括输入输出,也可以说是特征和目标。训练集中的目标是由人标注的。
PCA和很多deep learning算法都属于无监督学习

②无监督学习

无监督学习:输入数据没有被标记,也没有确定的结果。样本数据类别未知, 需要根据样本间的相似性对样本集进行分类(聚类, clustering)试图使类内差距最小化,类间差距最大化。
实际应用中, 不少情况下无法预先知道样本的标签,也就是说没有训练样本对应的类别,因而只能从原先没有样本标签的样本集开始学习分器设计

有监督学习 无监督学习
样本 必须要有训练集与测试样本。在训练集中找规律,而对测试样本使用这种规律。
目标 方法是识别事物,识别的结果表现在给待识别数据加上了标签。 因此训练样本集必须由带标签的样本组成。

③半监督学习

半监督学习: 即训练集同时包含有标记样本数据和未标记样本数据。

④强化学习

实质是: make decisions问题,即自动进行决策,并且可以做连续决策。
主要包含四个元素: agent, 环境状态, 行动, 奖励;
强化学习的目标就是获得最多的累计奖励。

小结:

监督学习:
In:有标签
Out:有反馈
目的:预测结果
案例:学认字
算法:分类(类别),回归(数字)

无监督学习:
In:无标签
Out:无反馈
目的:发现潜在结构
案例:自动聚类
算法:聚类,降维

半监督学习:
已知:训练样本Data和待分类的类别
未知:训练样本有无标签均可
应用:训练数据量过时,
监督学习效果不能满足需求,因此用来增强效果。

强化学习:
In:决策流程及激励系统
Out:一系列行动
目的:长期利益最大化,回报函数(只会提示你是否在朝着目标方向前进的延迟反映)
案例:学下棋
算法:马尔科夫决策,动态规划

2-1 KNN基本流程

一、概念:

KNN(K Near Neighbor):k个最近的邻居,即每个样本都可以用它最接近的k个邻居来代表。
这里写图片描述
最近邻 (k-Nearest Neighbors, KNN) 算法是一种分类算法, 1968年由 Cover和 Hart 提出, 应用场景有字符识别、 文本分类、 图像识别等领域。
该算法的思想是: 一个样本与数据集中的k个样本最相似, 如果这k个样本中的大多数属于某一个类别, 则该样本也属于这个类别。

二、距离度量

在选择两个实例相似性时,一般使用的欧式距离
Lp距离定义:

Lp(xi,xj)=(l=1n|xi(l)xj(l)|p)1p

其中xiRn,xjRn, 其中L∞定义为:
L(xi,xj)=maxl|xi(l)xj(l)|

其中p是一个变参数。
当p=1时,就是曼哈顿距离(对应L1范数)
曼哈顿距离对应L1-范数,也就是在欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。例如在平面上,坐标(x1, y1)的点P1与坐标(x2, y2)的点P2的曼哈顿距离为:|x1x2|+|y1y2|,要注意的是,曼哈顿距离依赖座标系统的转度,而非系统在座标轴上的平移或映射。
曼哈顿距离:

L1=k=1n|x1kx2k|

L1范数表示为:
L1|x|=i=1n|xi|x=[x1x2xn]Rn

当p=2时,就是欧氏距离(对应L2范数)
最常见的两点之间或多点之间的距离表示法,又称之为欧几里得度量,它定义于欧几里得空间中。n维空间中两个点x1(x11,x12,…,x1n)与 x2(x21,x22,…,x2n)间的欧氏距离
欧氏距离:

d12=k=1n(x1x2)2

L2范数:

L2|x|=i=1nxi2x=[x1x2xn]Rn

当p→∞时,就是切比雪夫距离
二维平面两点a(x1,y1)与b(x2,y2)间的切比雪夫距离:

d12=max(|x1x2|,|y1y2|)

n维空间点a(x11,x12,…,x1n)与b(x21,x22,…,x2n)的切比雪夫距离:
d12=max(|x1ix2i|)

三、k值选择

如果选择较小的K值,就相当于用较小的邻域中的训练实例进行预测,学习的近似误差会减小,只有与输入实例较近的训练实例才会对预测结果起作用,单缺点是学习的估计误差会增大,预测结果会对近邻的实例点分成敏感。如果邻近的实例点恰巧是噪声,预测就会出错。换句话说,K值减小就意味着整体模型变复杂,分的不清楚,就容易发生过拟合。

如果选择较大K值,就相当于用较大邻域中的训练实例进行预测,其优点是可以减少学习的估计误差,但近似误差会增大,也就是对输入实例预测不准确,K值得增大就意味着整体模型变的简单

近似误差:可以理解为对现有训练集的训练误差。
估计误差:可以理解为对测试集的测试误差。

近似误差关注训练集,如果k值小了会出现过拟合的现象,对现有的训练集能有很好的预测,但是对未知的测试样本将会出现较大偏差的预测。模型本身不是最接近最佳模型。

估计误差关注测试集,估计误差小了说明对未知数据的预测能力好。模型本身最接近最佳模型。

在应用中,K值一般取一个比较小的数值,通常采用交叉验证法来选取最优的K值。

流程:
1) 计算已知类别数据集中的点与当前点之间的距离
2) 按距离递增次序排序
3) 选取与当前点距离最小的k个点
4) 统计前k个点所在的类别出现的频率
5) 返回前k个点出现频率最高的类别作为当前点的预测分类

优点:
1、简单有效
2、重新训练代价低
3、算法复杂度低
4、适合类域交叉样本
5、适用大样本自动分类

缺点:
1、惰性学习
2、类别分类不标准化
3、输出可解释性不强
4、不均衡性
5、计算量较大

例子如下图:
距离越近,就越相似,属于这一类的可能性就越大
这里写图片描述
这里写图片描述

import math

movie_data = {"宝贝当家": [45, 2, 9, "喜剧片"],
              "美人鱼": [21, 17, 5, "喜剧片"],
              "澳门风云3": [54, 9, 11, "喜剧片"],
              "功夫熊猫3": [39, 0, 31, "喜剧片"],
              "谍影重重": [5, 2, 57, "动作片"],
              "叶问3": [3, 2, 65, "动作片"],
              "伦敦陷落": [2, 3, 55, "动作片"],
              "我的特工爷爷": [6, 4, 21, "动作片"],
              "奔爱": [7, 46, 4, "爱情片"],
              "夜孔雀": [9, 39, 8, "爱情片"],
              "代理情人": [9, 38, 2, "爱情片"],
              "新步步惊心": [8, 34, 17, "爱情片"]}

# 测试样本  唐人街探案": [23, 3, 17, "?片"]
#下面为求与数据集中所有数据的距离代码:
x = [23, 3, 17]
KNN = []
for key, v in movie_data.items():
    d = math.sqrt((x[0] - v[0]) ** 2 + (x[1] - v[1]) ** 2 + (x[2] - v[2]) ** 2)
    KNN.append([key, round(d, 2)])

# 输出所用电影到 唐人街探案的距离
print(KNN)

#按照距离大小进行递增排序
KNN.sort(key=lambda dis: dis[1])

#选取距离最小的k个样本,这里取k=5;
KNN=KNN[:5]
print(KNN)

#确定前k个样本所在类别出现的频率,并输出出现频率最高的类别
labels = {"喜剧片":0,"动作片":0,"爱情片":0}
for s in KNN:
    label = movie_data[s[0]]
    labels[label[3]] += 1
labels =sorted(labels.items(),key=lambda l: l[1],reverse=True)
print(labels,labels[0][0],sep='\n')

代码和例子来自:https://blog.csdn.net/saltriver/article/details/52502253

2-2 K值的选择

一、近似误差与估计误差:
近似误差:对现有训练集的训练误差,关注训练集,如果近似误差过小可能会出现过拟合的现象,对现有的训练集能有很好的预测,但是对未知的测试样本将会出现较大偏差的预测。模型本身不是最接近最佳模型。
估计误差:可以理解为对测试集的测试误差,关注测试集,估计误差小说明对未知数据的预测能力好,模型本身最接近最佳模型。
二、K值确定标准:
K值过小:k值小,特征空间被划分为更多子空间(模型的项越多),整体模型变复杂,容易发生过拟合,k值越小,选择的范围就比较小,训练的时候命中率较高,近似误差小,而用test的时候就容易出错,估计误差大,容易过拟合。
K值=N:无论输入实例是什么,都将简单的预测他属于训练实例中最多的类。

2-3 kd树

一、原理:

kd树(K-dimension tree)是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。 kd树是是一种二叉树,表示对k维空间的一个划分,构造kd树相当于不断地用垂直于坐标轴的超平面将K维空间切分,构成一系列的K维超矩形区域。kd树的每个结点对应于一个k维超矩形区域。 利用kd树可以省去对大部分数据点的搜索, 从而减少搜索的计算量。

一个三维k-d树。 第一次划分(红色)把根节点(白色)划分成两个节点,然后它们分别再次被划分(绿色) 为两个子节点。最后这四个子节点的每一个都被划分(蓝色) 为两个子节点。 因为没有更进一步的划分, 最后得到的八个节点称为叶子节点
这里写图片描述
类比“二分查找”: 给出一组数据: [9 1 4 7 2 5 0 3 8], 要查找8。如果挨个查找(线性扫描),那么将会把数据集都遍历一遍。而如果排一下序那数据集就变成了: [0 1 2 3 4 5 6 7 8 9], 按前一种方式我们进行了很多没有必要的查找, 现在如果我们以5为分界点, 那么数据集就被划分为了左右两个“簇” [0 1 2 3 4]和[6 7 8 9]。

因此, 根本久没有必要进入第一个簇,可以直接进入第二个簇进行查找。==把二分查找中的数据点换成k维数据点, 这样的划分就变成了用超平面对k维空间的划分==。空间划分就是对数据点进行分类, “挨得近”的数据点就在一个空间里面。

二、构造方法:

第一个问题简单的解决方法可以是选择随机选择某一维或按顺序选择,但是更好的方法应该是在数据比较分散的那一维进行划分(分散的程度可以根据方差来衡量)。好的划分方法可以使构建的树比较平衡, 可以每次选择中位数来进行划分, 这样问题2也得到了解决。
这里写图片描述
代码实现:

# -*- coding: utf-8 -*-

#from operator import itemgetter
import sys
reload(sys)
sys.setdefaultencoding('utf8')


# kd-tree每个结点中主要包含的数据结构如下 
class KdNode(object):
    def __init__(self, dom_elt, split, left, right):
        self.dom_elt = dom_elt  # k维向量节点(k维空间中的一个样本点)
        self.split = split      # 整数(进行分割维度的序号)
        self.left = left        # 该结点分割超平面左子空间构成的kd-tree
        self.right = right      # 该结点分割超平面右子空间构成的kd-tree


class KdTree(object):
    def __init__(self, data):
        k = len(data[0])  # 数据维度

        def CreateNode(split, data_set): # 按第split维划分数据集exset创建KdNode
            if not data_set:    # 数据集为空
                return None
            # key参数的值为一个函数,此函数只有一个参数且返回一个值用来进行比较
            # operator模块提供的itemgetter函数用于获取对象的哪些维的数据,参数为需要获取的数据在对象中的序号
            #data_set.sort(key=itemgetter(split)) # 按要进行分割的那一维数据排序
            data_set.sort(key=lambda x: x[split])
            split_pos = len(data_set) // 2      # //为Python中的整数除法
            median = data_set[split_pos]        # 中位数分割点             
            split_next = (split + 1) % k        # cycle coordinates

            # 递归的创建kd树
            return KdNode(median, split, 
                          CreateNode(split_next, data_set[:split_pos]),     # 创建左子树
                          CreateNode(split_next, data_set[split_pos + 1:])) # 创建右子树

        self.root = CreateNode(0, data)         # 从第0维分量开始构建kd树,返回根节点


# KDTree的前序遍历
def preorder(root):  
    print root.dom_elt  
    if root.left:      # 节点不为空
        preorder(root.left)  
    if root.right:  
        preorder(root.right)  


if __name__ == "__main__":
    data = [[2,3],[5,4],[9,6],[4,7],[8,1],[7,2]]
    kd = KdTree(data)
    preorder(kd.root)
2018-10-15 16:05:11 hliyang 阅读数 105
  • 机器学习& 深度学习 基础视频教程(人工智能AI方向)

    机器学习,深度学习基础教程入门视频培训教程,该课程主要包含机器学习基础,包括常用的数据集、训练集、样本、特征、矩阵、Numpy数组、Pandas的使用等;机器学习数学基础,包括线形代数基础、概率基础、信息论基础、最优化基础等;机器学习算法,包括简单线形回归和逻辑回归、决策树、KNN、SVM、层次聚类、密度聚类等。这是一门非常好的AI入门教程。

    660 人正在学习 去看看 Array老师
k-近邻算法:

(kNN —— k-Nearest Neighbors)
测量不同特征值之间的距离方法进行分类。
有一个样本数据集(每个样本都存在标签),输入没有标签的新数据后,将新数据的每个特征与样本集中数据对应的特征进行比较,提取样本集中特征最相似数据(最近邻)的分类标签。一般,只选择样本数据中前k个最相似的数据(k通常不大于20),选择其中分类出现次数最多的作为新数据的分类。

欧式距离公式:

计算两个向量点xA和xB之间的距离:
在这里插入图片描述
举例:如果数据集存在4个特征值,则(1,0,0,1)与(7,6,9,4)之间的距离为:
在这里插入图片描述

测试分类器的效果:

在这里插入图片描述

算法使用:

对要约会的人进行分类(不喜欢的人、魅力一般的人、极具魅力的人),
提取数据中的4个样本:
在这里插入图片描述
计算样本3和4的距离:
在这里插入图片描述
可以看出数字差值最大的属性对计算结果影响最大,而这种原因是“每年获得的飞行常客里程数”远大于其他特征值。但是这3中特征值是同等重要的,所以“每年获得的飞行常客里程数”不该如此严重影响计算结果。
解决方法:将不同取值范围的特征值进行归一化,处理到0到1/-1到1
在这里插入图片描述
min和max为数据集中对应特征的最小和最大值。

通常使用数据的90%作为训练样本来训练分类器,其余的10%来测试分类器,这是最原始的做法,还有其他一些高级方法。注意:10%的数据是随机选择的。

算法特点:

k-近邻算法是基于实例的学习,使用算法时必须有接近实际数据的训练样本数据,同时又必须对数据集中的每个数据计算距离值,所以十分耗时。

代码案例:

kNN算法应用实例(1、2)

2017-08-17 14:30:19 u012736685 阅读数 383
  • 机器学习& 深度学习 基础视频教程(人工智能AI方向)

    机器学习,深度学习基础教程入门视频培训教程,该课程主要包含机器学习基础,包括常用的数据集、训练集、样本、特征、矩阵、Numpy数组、Pandas的使用等;机器学习数学基础,包括线形代数基础、概率基础、信息论基础、最优化基础等;机器学习算法,包括简单线形回归和逻辑回归、决策树、KNN、SVM、层次聚类、密度聚类等。这是一门非常好的AI入门教程。

    660 人正在学习 去看看 Array老师

一、KNN(K近邻)概述

KNN一种基于距离的计算的分类和回归的方法。

其主要过程为:

  1. 计算训练样本和测试样本中每个样本点的距离(常见的距离度量有欧式距离,马氏距离等);
  2. 对上面所有的距离值进行排序(升序);
  3. 选前k个最小距离的样本;
  4. 根据这k个样本的标签进行投票,得到最后的分类类别;

优点:

  1. 理论成熟,思想简单,既可以用来做分类也可以用来做回归;
  2. 可用于非线性分类;
  3. 训练时间复杂度为O(n);
  4. 对数据没有假设,准确度高,对异常值不敏感;

缺点:

  1. 计算量大(体现在距离计算上);
  2. 样本不平衡问题(即有些类别的样本数量很多,而其它样本的数量很少)效果差;
  3. 需要大量内存;

二、实现——sklearn

1、sklearn.neighbors

与近邻法这一大类相关的类库都在sklearn.neighbors包之中。

KNN分类树的类是KNeighborsClassifier,KNN回归树的类是KNeighborsRegressor。

除此之外,还有KNN的扩展,即限定半径最近邻分类树的类RadiusNeighborsClassifier和限定半径最近邻回归树的类RadiusNeighborsRegressor, 以及最近质心分类算法NearestCentroid。

2、KNN分类的实现

(1)数据的随机生成

import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
from sklearn.datasets.samples_generator import make_classification
# X为样本特征,Y为样本类别输出, 共1000个样本,每个样本2个特征,输出有3个类别,没有冗余特征,每个类别一个簇
X, Y = make_classification(n_samples=1000, n_features=2, n_redundant=0,
                             n_clusters_per_class=1, n_classes=3)
plt.scatter(X[:, 0], X[:, 1], marker='o', c=Y)
plt.show()

结果如下图所示:
这里写图片描述

make_classification 函数

from sklearn.datasets.samples_generator import make_classification
sklearn.datasets.make_classification(n_samples=100, n_features=20, n_informative=2, n_redundant=2, n_repeated=0, n_classes=2, n_clusters_per_class=2, weights=None, flip_y=0.01, class_sep=1.0, hypercube=True,shift=0.0, scale=1.0, shuffle=True, random_state=None)  

通常用于分类算法。
n_features :特征个数= n_informative() + n_redundant + n_repeated
n_informative:多信息特征的个数
n_redundant:冗余信息,informative特征的随机线性组合
n_repeated :重复信息,随机提取n_informative和n_redundant 特征
n_classes:分类类别
n_clusters_per_class :某一个类别是由几个cluster构成的

(2)模型的拟合

用KNN来拟合模型,我们选择K=15,权重为距离远近。代码如下:

from sklearn import neighbors
clf = neighbors.KNeighborsClassifier(n_neighbors = 15 , weights='distance')
clf.fit(X, Y)

(3)模型的预测

from matplotlib.colors import ListedColormap
cmap_light = ListedColormap(['#FFAAAA', '#AAFFAA', '#AAAAFF'])
cmap_bold = ListedColormap(['#FF0000', '#00FF00', '#0000FF'])

#确认训练集的边界
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
#生成随机数据来做测试集,然后作预测
xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.02),
                         np.arange(y_min, y_max, 0.02))
Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])

# 画出测试集数据
Z = Z.reshape(xx.shape)
plt.figure()
plt.pcolormesh(xx, yy, Z, cmap=cmap_light)

# 也画出所有的训练集数据
plt.scatter(X[:, 0], X[:, 1], c=Y, cmap=cmap_bold)
plt.xlim(xx.min(), xx.max())
plt.ylim(yy.min(), yy.max())
plt.title("3-Class classification (k = 15, weights = 'distance')" )

结果如下图所示:
这里写图片描述

三、KNN源码

def classify0(inX, dataSet, labels, k):   
    dataSetSize = dataSet.shape[0] # the number of samples   

    # tile function is the same as "replicate" function of MATLAB  
    # 这个技巧就避免了循环语句  
    diffMat = tile(inX, (dataSetSize, 1)) - dataSet # replicate inX into dataSetSize * 1  
    sqDiffMat = diffMat**2  # 对应元素平方  
    sqDistances = sqDiffMat.sum(axis = 1)  # 按行求和  
    distances = sqDistances**0.5  # 开方求距离  

    sortedDistIndicies = distances.argsort()  # argsort函数返回的是数组值从小到大的索引值  
    classCount = {}   
    # 投票  
    for i in range(k):   
        voteIlabel = labels[sortedDistIndicies[i]] #排名第i近的样本的label  
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1  #get字典的元素,如果不存在key,则为0  
    # operator.itemgetter(1)按照value排序;也可以用 key = lambda asd:asd[1]  
    # 排序完,原classCount不变  
    sortedClassCount = sorted(classCount.iteritems(),  # 键值对  
                              key = operator.itemgetter(1), reverse = True)  #逆序排列   

    return sortedClassCount[0][0]  #输出第一个,也就是最近邻  
2018-11-08 19:59:56 qq_35868994 阅读数 247
  • 机器学习& 深度学习 基础视频教程(人工智能AI方向)

    机器学习,深度学习基础教程入门视频培训教程,该课程主要包含机器学习基础,包括常用的数据集、训练集、样本、特征、矩阵、Numpy数组、Pandas的使用等;机器学习数学基础,包括线形代数基础、概率基础、信息论基础、最优化基础等;机器学习算法,包括简单线形回归和逻辑回归、决策树、KNN、SVM、层次聚类、密度聚类等。这是一门非常好的AI入门教程。

    660 人正在学习 去看看 Array老师

KNN
数据集:第一个数据是此次数据集,第三个是实验说明
参考资料:《统计学习方法》、《机器学习实战》、大佬网站:[一个东北大学的大佬]
(https://cuijiahua.com/blog/2017/11/ml_1_knn.html)
个人原创,未经允许,禁止转载
个人邮箱1274351138@qq.com

  1. 数据预处理
    1.1首先第4列数据并不影响分类结果,所以将其剔除
    1.2数据集太过于奇葩,所以做了归一化处理
    1.3因为做的是分类,所以我想把值控制在0-1,所以采用的归一化方法是:(dataSet - min)/(max-min)
    1.4打乱数据集,因为本来的数据集是排序好的,而且有些数据太奇葩,所以事先将其打乱;一般会选取10%的数据作为测试集,但是显然我的数据太少了,所以我选择了打乱之后的前5行数据作为测试集,剩下的作为训练集(真心觉得数据是老师自己编写的)

  2. 算法
    2.1KNN算法网上百度一大推,这里我看的是李航老师的《统计学习方法》,推导写的很不错,推荐大家可以看一下,我就不写了(反正也是截图******滑稽******)
    2.2数据之间的距离,欧式距离,很好做的。
    2.3算法步骤(在这之前数据要先归一化):
    1)计算已知类别数据集中的点与当前点之间的距离
    2)按距离递增次序排序
    3)选取与当前点距离最小的k个点
    4)统计前k个点所在的类别出现的频率
    5)返回前k个点出现频率最高的类别作为当前点的预测分类

  3. 调试
    3.1hash 发现list不能hash,matrix也不能hash,调试了我好久,我太菜了
    3.2dict 我发现 还是"numpy ndarry"的格式好使,能迭代,能items()

import numpy as np
import matplotlib.pyplot as plt
import operator
import pandas as pd
from math import  sqrt
from matplotlib.font_manager import FontProperties
#################读取文件(数据预处理)#########################
def filematrix(filename):
    array0Lines = np.matrix(pd.read_csv(filename)) 			  ##读取文件
    returnMat = array0Lines[:, 1:3]  ##训练集
    number0Lines = array0Lines.shape[0]                       ##读取文件行数
    classLabelVector = []                                     ##训练集分类标签向量
    for line in array0Lines:                                  #遍历数据集,获取分类标签信息
        if line[:,0]==0:
            classLabelVector.append(0)
        elif line[:,0]==1:
            classLabelVector.append(1)
        elif line[:,0]==2:
            classLabelVector.append(2)
    return returnMat,np.matrix(classLabelVector).T            ##返回训练集和标签向量


####################数据可视化#########################
def showdatas(datingDataMat,datingLabels):

    """
    函数说明:可视化数据
    Parameters:
        datingDataMat - 特征矩阵
        datingLabels - 分类Label
    Returns:
        无
    """
    #不同类型数据的颜色
    LabelsColors = []                                          ##存放数据颜色的数组
    for i in datingLabels:
        if i == 0:
            LabelsColors.append('black')
        elif i == 1:
            LabelsColors.append('orange')
        elif i == 2:
            LabelsColors.append('red')
    fig,ax = plt.subplots(figsize=(10,6))
    #画图时要注意把matrix格式换成list格式,否则不能画图
    ax.scatter(datingDataMat[:,0].tolist(),datingDataMat[:,1].tolist(),color=LabelsColors,s=15,alpha=.5)
    """
    ###设置图列legend
    '0' = mlines.Line2D([], [], color='black', marker='.',markersize=6, label='0')
    '1' = mlines.Line2D([], [], color='orange', marker='.',markersize=6, label='1')
    '2' = mlines.Line2D([], [], color='red', marker='.',markersize=6, label='2')
    plt.legend(handles=[0,1,2])
    """
    plt.show()

###########归一化处理############
def autoNorm(dataSet):
    """
    函数说明:对数据进行归一化

    Parameters:
        dataSet - 特征矩阵
    Returns:
        normDataSet - 归一化后的特征矩阵
        ranges - 数据范围
        minVals - 数据最小值
    """
    #meanVals = dataSet.mean(0)                                    #数据平均值
    #stdVals = dataSet.std(0)
    minVals = dataSet.min(0)                                      #数据最小值
    maxVals = dataSet.max(0)                                      #数据最大值
    ranges = maxVals - minVals                                    #最大值和最小值的差距
    normDataSet = np.zeros(np.shape(dataSet))                     #用于存放归一化后的数据集
    m= dataSet.shape[0]                                           #返回数据集的行数
    ###归一化过程
    #normDataSet = dataSet-meanVals
    #normDataSet = normDataSet/stdVals
    normDataSet = dataSet - np.tile(minVals,(m,1))                #原始数据减去最小数据
    normDataSet = normDataSet/np.tile(ranges,(m,1))               #所得之差除以最大值最小值得差,得到归一化数据
    return normDataSet,ranges,minVals                             #返回归一化数据结果,数据范围,最小值

def classify(inX,dataSet,labels,k):
    dataSetSize = dataSet.shape[0]                                #返回dataSet的行数
    diffMat = np.tile(inX,(dataSetSize,1)) - dataSet              #测试矩阵-数据集
    sqDiffMat = np.multiply(diffMat,diffMat)
    sqDistances = sqDiffMat.sum(axis=1)                           #沿着列的方向相加
    distances = np.ravel(np.sqrt(sqDistances) )                   #欧式距离
    sortedDisIndices = distances.argsort()                        #返回distances中元素从小到大排序后的索引值
    classCount = {}                                               #空字典,用来记录类别次数
    for i in range(k):                                            #遍历
        voteIlabel = labels[sortedDisIndices[i]]                  #取出最近的K个点
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1 #存放出现的类别次数
        #根据字典的值进行降序排序
        sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
        return  sortedClassCount[0][0]                            #返回次数最多的类别

def datingClassTest():
    filename = "G:/shiyan1/shiyan1/Ex1.1_Challenger.csv"
    datingDataMat, datingLabels = filematrix(filename)            #训练集,标签,测试集
    normMat,ranges,minVals = autoNorm(datingDataMat)
    ###打乱数据集,并取前20个作为训练集
    index = np.arange(23)
    np.random.shuffle(index)
    dataSet = normMat[index]
    test = normMat[0:6,:]                                         #测试集
    numTestVecs = len(test)                                       #测试集个数
    m = np.shape(normMat)[0]                                      ##获得normMat的行数
    errorCount =0.0                                               ##分类错误计数
    for i in range (numTestVecs-1):
        classifierResult = classify(test[i,:],normMat[numTestVecs:m,:],np.ravel(datingLabels)[numTestVecs:m],5)     ##前numTestVecs 作为测试集,后m-numTestVecs作为训练集,这边注意要是list格式,否则不能迭代的
        print("分类结果:%d\t真实类别:%d"%(classifierResult,datingLabels[i]))
        if classifierResult!=datingLabels[i]:
            errorCount+=1.0
    print("错误率:%f%%"%(errorCount/float(numTestVecs)*100))

if __name__=='__main__':
    datingClassTest()
分类结果:0	真实类别:0
分类结果:0	真实类别:1
分类结果:0	真实类别:0
分类结果:0	真实类别:0
分类结果:0	真实类别:0
错误率:16.666667%

有一个数据错了,就是那个特别奇葩的数据。。。。。。。。。。。。。。。。。。。
果然数据处理才是烦的,还有python的一大堆格式问题。
希望有大佬能教教我,怎么画legend。

机器学习笔记-KNN

阅读数 75

没有更多推荐了,返回首页