机器学习算法原理解析 - 分类

常见分类模型与算法

距离判别法,即最近邻算法KNN;

贝叶斯分类器;

线性判别法,即逻辑回归算法;

决策树;

支持向量机;

神经网络;

1. KNN分类算法原理及应用 1.1 KNN概述

K最近邻(k-Nearest Neighbor,KNN)分类算法是最简单的机器学习算法。

KNN算法的指导思想是“近朱者赤,近墨者黑”,由你的邻居来推断你的类型。

本质上,KNN算法就是用距离来衡量样本之间的相似度。

1.2 算法图示

从训练集中找到和新数据最接近的k条记录,然后根据多数类来决定新数据类别

算法涉及3个主要因素

1) 训练数据集

2) 距离或相似度的计算衡量

3) k的大小

机器学习算法原理解析 - 分类

算法描述

1) 已知两类“先验”数据,分别是蓝方块和红三角,他们分布在一个二维空间中;

2) 有一个未知类别的数据(绿点),需要判断它是属于“蓝方块”还是“红三角”类;

3) 考察离绿点最近的3个(或k个)数据点的类别,占多数的类别即为绿点判定类别;

1.3 算法要点 1.3.1 计算步骤

计算步骤如下:

1) 算距离:给定测试对象,计算它与训练集中的每个对象的距离;

2) 找邻居:圈定距离最近的k个训练对象,作为测试对象的近邻;

3) 做分类:根据这k个近邻归属的主要类别,来对测试对象分类;

1.3.2 相似度的衡量

距离越近应该意味着这两个点属于一个分类的可能性越大,但,距离不能代表一切,有些数据的相似度衡量并不适合用距离;

相似度衡量方法:包括欧式距离、夹角余弦等。

(简单应用中,一般使用欧式距离,但对于文本分类来说,使用余弦来计算相似度就比欧式距离更合适)

1.3.3 类别的判定

简单投票法:少数服从多数,近邻中哪个类别的点最多就分为该类

加权投票法:根据距离的远近,对近邻的投票进行加权,距离越近则权重越大(权重为距离平方的倒数)

1.4 算法不足之处

1. 样本不平衡容易导致结果错误

如一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个新样本时,该样本的K个邻居中大容量类的样本占多数。

改善方法:对此可以采用权值的方法(和该样本距离小的邻居权值大)来改进。

2. 计算量较大

因为对每一个待分类的文本都要计算它到全体已知样本的距离,才能求得它的K个最近邻点。

改善方法:实现对已知样本点进行剪辑,事先去除对分类作用不大的样本。

:该方法比较适用于样本容量比较大的类域的类域的分类,而那些样本容量较小的类域采用这种算法比较容易产生误分。

1.5 KNN分类算法Python实战——KNN简单数据分类实践 1.5.1 需求

计算地理位置的相似度

有以下先验数据,使用KNN算法对未知类别数据分类

属性1

 

属性2

 

类别

 

1.0

 

0.9

 

A

 

1.0

 

1.0

 

A

 

0.1

 

0.2

 

B

 

0.0

 

0.1

 

B

 

未知类别数据

属性1

 

属性2

 

类别

 

1.2

 

1.0

 

?

 

0.1

 

0.3

 

?

 
1.5.2 Python实现

首先,我们新建一个KNN.py脚本文件,文件里面包含两个函数,一个用来生成小数据集,一个实现KNN分类算法。代码如下:

########################## # KNN: k Nearest Neighbors #输入:newInput: (1xN)的待分类向量 # dataSet: (NxM)的训练数据集 # labels: 训练数据集的类别标签向量 # k: 近邻数 # 输出:可能性最大的分类标签 ########################## from numpy import import operator #创建一个数据集,包含2个类别共4个样本 def createDataSet(): # 生成一个矩阵,每行表示一个样本 group = array([[1.0,0.9],[1.0,1.0],[0.1,0.2],[0.0,0.1]]) # 4个样本分别所属的类别 labels = [\'A\', \'A\', \'B\', \'B\'] return group, labels # KNN分类算法函数定义 def KNNClassify(newInput, dataSet, labels, k): numSamples = dataSet.shape[0] #shape[0]表示行数 ## step1:计算距离 # tile(A, reps):构造一个矩阵,通过A重复reps次得到 # the following copy numSamples rows for dataSet diff = tile(newInput, (numSamples, 1)) -dataSet #按元素求差值 squareDiff = diff ** 2 #将差值平方 squareDist = sum(squaredDiff, axis = 1) # 按行累加 ##step2:对距离排序 # argsort() 返回排序后的索引值 sortedDistIndices = argsort(distance) classCount = {} # define a dictionary (can be append element) for i in xrange(k): ##step 3: 选择k个最近邻 voteLabel = labels[sortedDistIndices[i]] ## step 4:计算k个最近邻中各类别出现的次数 # when the key voteLabel is not in dictionary classCount,get() # will return 0 classCount[voteLabel] = classCount.get(voteLabel, 0) + 1 ##step 5:返回出现次数最多的类别标签 maxCount = 0 for key, value in classCount.items(): if value > maxCount: maxCount = value maxIndex = key return maxIndex

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zwyzpw.html