k-近邻(kNN, k-NearestNeighbor)算法是一种基本分类与回归方法,这里只讨论分类问题中的 k-近邻算法。
作为一种有监督分类算法,是最简单的机器学习算法之一,顾名思义,其算法主体思想就是根据距离相近的邻居类别,来判定自己的所属类别。算法的前提是需要有一个已被标记类别的训练数据集,通俗理解其计算过程:
给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例最邻近的 k 个实例,这 k 个实例的多数属于某个类,就把该输入实例分为这个类。
一句话总结:近朱者赤近墨者黑!
K近邻算法的输入为实例的特征向量,对应于特征空间的点;输出为实例的类别,可以取多类。k 近邻算法假设给定一个训练数据集,其中的实例类别已定。分类时,对新的实例,根据其 k 个最近邻的训练实例的类别,通过多数表决等方式进行预测。因此,k近邻算法不具有显式的学习过程。
K近邻算法实际上利用训练数据集对特征向量空间进行划分,并作为其分类的“模型”。 k值的选择、距离度量以及分类决策规则是k近邻算法的三个基本要素。
电影可以按照题材分类,那么如何区分 动作片 和 爱情片 呢?
动作片:打斗次数更多爱情片:亲吻次数更多基于电影中的亲吻、打斗出现的次数,使用 k-近邻算法构造程序,就可以自动划分电影的题材类型。
现在根据上面我们得到的样本集中所有电影与未知电影的距离,按照距离递增排序,可以找到 k 个距离最近的电影。 假定 k=3,则三个最靠近的电影依次是, He's Not Really into Dudes 、 Beautiful Woman 和 California Man。 knn 算法按照距离最近的三部电影的类型,决定未知电影的类型,而这三部电影全是爱情片,因此我们判定未知电影是爱情片。
K值的设定
K值设置过小会降低分类精度;若设置过大,且测试样本属于训练集中包含数据较少的类,则会增加噪声,降低分类效果。
通常,K值的设定采用交叉检验的方式(以K=1为基准)
经验规则:K一般低于训练样本数的平方根。
优化问题
压缩训练样本;
确定最终的类别时,不是简单的采用投票法,而是进行加权投票,距离越近权重越高。
海伦使用约会网站寻找约会对象。经过一段时间之后,她发现曾交往过三种类型的人:
不喜欢的人魅力一般的人极具魅力的人她希望:
工作日与魅力一般的人约会周末与极具魅力的人约会不喜欢的人则直接排除掉现在她收集到了一些约会网站未曾记录的数据信息,这更有助于匹配对象的归类。
开发流程 收集数据:提供文本文件准备数据:使用 Python 解析文本文件分析数据:使用 Matplotlib 画二维散点图训练算法:此步骤不适用于 k-近邻算法测试算法:使用海伦提供的部分数据作为测试样本。 测试样本和非测试样本的区别在于: 测试样本是已经完成分类的数据,如果预测分类与实际类别不同,则标记为一个错误。使用算法:产生简单的命令行程序,然后海伦可以输入一些特征数据以判断对方是否为自己喜欢的类型。1.收集数据
海伦将其约会的对象特征提取出来标记分类,存放在了文本中,主要包含以下 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
...
2.准备数据:使用 Python 解析文本文件
将文本记录转换为 NumPy 的解析程序
def file2matrix(filename):
"""
Desc:
导入训练数据
parameters:
filename: 数据文件路径
return:
数据矩阵 returnMat 和对应的类别 classLabelVector
"""
with open(filename) as f:
lines = f.readlines()
row_num = len(lines)
matrix = zeros((row_num, 3))
index = 0
class_label = []
for line in lines:
features = line.strip().split("/t")
matrix[index, :] = features[0:3]
class_label.append(features[-1])
index += 1
return matrix, class_label
3.分析数据
import matplotlib
import matplotlib.pyplot as plt
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDataMat[:, 0], datingDataMat[:, 1], 15.0*array(datingLabels), 15.0*array(datingLabels))
plt.show()
下图中采用矩阵的第一和第二列属性得到很好的展示效果,清晰地标识了三个不同的样本分类区域,具有不同爱好的人其类别区域也不同。
归一化数据
归一化是一个让权重变为统一的过程,更多细节请参考: https://www.zhihu.com/question/19951858
样本3和样本4的距离:
(0−67)2+(20000−32000)2+(1.1−0.1)2" role="presentation">(0−67)2+(20000−32000)2+(1.1−0.1)2
归一化特征值,消除特征之间量级不同导致的影响
归一化定义: 我是这样认为的,归一化就是要把你需要处理的数据经过处理后(通过某种算法)限制在你需要的一定范围内。首先归一化是为了后面数据处理的方便,其次是保正程序运行时收敛加快。 方法有如下:
1) 线性函数转换,表达式如下:
y=(x-MinValue)/(MaxValue-MinValue)
说明:x、y分别为转换前、后的值,MaxValue、MinValue分别为样本的最大值和最小值。
2) 对数函数转换,表达式如下:
y=log10(x)
说明:以10为底的对数函数转换。
如图:

3) 反余切函数转换,表达式如下:
y=arctan(x)*2/PI
如图:

在统计学中,归一化的具体作用是归纳统一样本的统计分布性。归一化在0-1之间是统计的概率分布,归一化在-1--+1之间是统计的坐标分布。
def normalize(matrix):
"""
Desc:
归一化特征值,消除特征之间量级不同导致的影响
parameter:
dataSet: 数据集
return:
归一化后的数据集 normDataSet. ranges和minVals即最小值与范围,并没有用到
归一化公式:
Y = (X-Xmin)/(Xmax-Xmin)
其中的 min 和 max 分别是数据集中的最小特征值和最大特征值。该函数可以自动将数字特征值转化为0到1的区间。
"""
min_val = matrix.min()
max_val = matrix.max()
ranges = max_val - min_val
m = matrix.shape[0]
norm_matrix = matrix - tile(min_val, (m, 1))
norm_matrix = norm_matrix / tile(ranges, (m, 1))
return norm_matrix, ranges, min_val
4.训练算法:此步骤不适用于 k-近邻算法
因为测试数据每一次都要与全量的训练数据进行比较,所以这个过程是没有必要的
kNN 算法伪代码:
对于每一个在数据集中的数据点:
计算目标的数据点(需要分类的数据点)与该数据点的距离
将距离排序:从小到大
选取前K个最短距离
选取这K个中最多的分类类别
返回该类别来作为目标数据点的预测值
def classify(input_data, dataset, labels, k):
"""
knn分类算法
:param input_data: 输入待分类的目标数据,即某人的特征一维向量(一行列表)
:param dataset: 分类数据集
:param labels: dataset对应的分类标签
:param k: k个最下距离
:return:
"""
msize = dataset.shape[0]
diff_mat = tile(input_data, (msize, 1)) - dataset
sq_diff_mat = diff_mat ** 2
sq_distances = sq_diff_mat.sum(axis=1)
distances = sq_distances ** 0.5
sorted_index = distances.argsort()
class_count = {}
for i in range(k):
label = labels[sorted_index[i]]
class_count[label] = class_count.get(label, 0) + 1
sorted_class = sorted(class_count.items(), key=operator.itemgetter(1), reverse=True)
return sorted_class[0][0]
5.测试算法
使用海伦提供的部分数据作为测试样本。如果预测分类与实际类别不同,则标记为一个错误。
def dating_class_test():
"""
Desc:
对约会网站的测试方法
parameters:
none
return:
错误数
"""
ratio = 0.1
feature_matrix, labels = txt2matrix("data/datingTestSet.txt")
norm_mat, ranges, min_val = normalize(feature_matrix)
m = norm_mat.shape[0]
test_num = int(m * ratio)
error_count = 0
for i in range(test_num):
classifier_result = classify(norm_mat[i, :], norm_mat[test_num:m, :, labels[test_num:m, :, 3]])
print("the classifier came back with: %d, the real answer is: %d" % (classifier_result, labels[i]))
if (classifier_result != labels[i]):
error_count += 1
print("the total error rate is: %f" % (error_count / test_num))
print(error_count)
6.使用算法
产生简单的命令行程序,然后海伦可以输入一些特征数据以判断对方是否为自己喜欢的类型。
约会网站预测函数伪代码
def classifyPerson():
resultList = ['not at all', 'in small doses', 'in large doses']
percentTats = float(raw_input("percentage of time spent playing video games ?"))
ffMiles = float(raw_input("frequent filer miles earned per year?"))
iceCream = float(raw_input("liters of ice cream consumed per year?"))
datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')
normMat, ranges, minVals = autoNorm(datingDataMat)
inArr = array([ffMiles, percentTats, iceCream])
classifierResult = classify0((inArr-minVals)/ranges,normMat,datingLabels, 3)
print "You will probably like this person: ", resultList[classifierResult - 1]
相关知识
【机器学习】6:K
python机器学习
【机器学习】鸢尾花分类:机器学习领域经典入门项目实战
【机器学习】鸢尾花分类
【机器学习】任务七:聚类算法 (K
机器学习算法
Python机器学习基础教程
机器学习笔记(通俗易懂)
【机器学习】KNN算法实现鸢尾花分类
机器学习案例:鸢尾花分类——基于Scikit
网址: 【机器学习】k https://m.huajiangbk.com/newsview854487.html
上一篇: 科学理性看待转基因技术 |
下一篇: 可视化=面子工程?浅谈企业可能走 |