当前位置：文档之家 › 采用特征相关性差异优化距离的改进k近邻算法

采用特征相关性差异优化距离的改进k近邻算法

  • 格式：pdf
  • 大小：533.79 KB
  • 文档页数：4

程度；当| | = | |， = 0 时，仅处于一个圆上，表示 对样本归 属 或 完全确定，此时 的相关性与样本的分布无关联。推
广 到 多 类 ，分 析 同 上 。 由 此 可 知
值越小，越能体现 对
分类的强相关性，0 则表示绝对相关。
r4
Round1
r1 r2
Cr O
Round3
Round2 r3
2 FCDKNN
2.1 特 征 相 关 性 差 异优 化 距 离 测 度
(1)特征参数 对分类的相关性
的定义。设 = 1,
2,…,m)是训练样本集，它包含了 n 个不同类别 = 1,2,…,n)，
| |为 特征 在训 练集 中出 现的 次数，| |为 在 类 中出 现的 次
数，p ( ) = | | / m 为 的分布概率， = | |/| |为 在类 中出现的
距离加权平均-KNN 的距离测度定义过于简单，没有考虑 特 征 对 于 样 本 类 别 归 属 的 重 要 影 响 ，极 易 受 样 本 分 布 情 况 影
收稿日期：2010-09-12；修订日期：2010-11-16。 作者简介：周靖 (1980－)，女，广东茂名人，硕士，实验师，研究方向为人工智能、数据挖掘； 刘晋胜 (1979－)，男，广东梅州人，硕士，讲 师，研究方向为人工智能、嵌入式系统及信号系统处理。E-mail：zhoujing_1980@
向 量 ，由 特 征 相 关 性 差 异 值 设 置 方 法 计 算 或 者 判 断 训 练 集 样
本 与 待 分 样 本 各 条 件 属 性 下 对 应 特 征 的 差 异 值 。由 于 在 实 际
应 用 中 ，绝 大 多 数 数 据 集 特 征 在 具 有 很 强 重 复 性 的 同 时 ，对 于
2.2 FCDKNN 的 实现
FCDKNN 的核心思想为：直观上说
说明了 对于样
本归属类 的判断不仅与其在 类中出现的频率有关，还与
其在训练集中出现的频率相关，充分考虑到了 在训练集中关
于样本判别方面的重要性和相关性。基于此 FCDKNN 使用式 (1) 对数据进行规约，构造新的特征向量。然后根据新的特征
Maoming 525000, China)
Abstract：To solve the contradiction of -nearest neighbor between training samples size and classification accuracy effectively, an improved algorithm (feature correlation difference -nearest neighbor, FCDKNN) adopting correlation difference to optimize distance is proposed, the impacted algorithm takes the product between the entropy of feature and distribution probability of feature as the concept of correlation, and a distance measure of samples is defined around feature correlation difference, the important and the correlation of feature on classification are cleared, a lot of useful information about classification is extracted in small samples for employing global optimization ability. The contrast simulation experiment shows that the improved algorithm raised the rate of classification accuracy greatly, meanwhile it also maintains efficiency of classification. Key words： -nearest neighbor; feature; correlation; difference; distance
摘 要：为有效 地 解决 近 邻 算 法 训 练样 本 规 模 及 分 类 精度 间 的 矛 盾 ，提 出 了 一 种 采 用特 征 相 关 性 差 异 优化距离的改 进算 法(FCDKNN)。该算法将特 征熵值与其分 布概率的乘积作 为特征相关性的 概念，在此基础 上定义围绕特征 相关性差异的 样本 距离 测度，明确特征在类别 上的重要性及 相关性，在小样本情况 下提取针对分类 的大量有效信 息，以增 强算法的全局 优化 能力 。对比仿真实验 结果表明，该算 法在保持效率的 情况下分类精 度得到了极大地 提高。 关键词：近邻; 特征; 相关性; 差异; 距离 中图 法分类号：TP301 文献标 识码：A 文章编号：1000-7024 (2011) 09-3178-04
其原理பைடு நூலகம்为简化讨论，图 1 只包含了 2 个类别。圆上的点表示 ，圆心 、 分别代表任意两类 、 类的绝对相关点，处于圆
心期望区内的 均与圆心代表类别绝对相关。半径表示 针对
圆 心 代 表 的 类 别 对 分 类 影 响 程 度 的 强 弱 ，若 半 径 越 小 ，则 作 用
越大。当| |≠| |， ≠0 时，至少处于两个圆上，即是两个不 同圆心的圆存在交点，交点位置表示 对区分 、 类的影响
, =|
|。
(3)样本间的距离测度 , 的定义
, = 1 D_
,
(2)
=1 =1
样本间的距离是各特征类相关性大小差异的总和，以 D_
, 作为优化因子，累加平均得到样本间的距离测度，D_ , 越小，距离就越接近，样本也就越相似。这种距离的
计算方法不仅包括了样本、特征的频数信息，还包括了特征间
的 关 联 性 信 息 ，用 其 衡 量 样 本 间 距 离 精 准 度 是 相 当 高 的 。
概率， 为 的分类熵， 为 对 类的分类熵，则
为
=
ln
=0
=
ln =
(1)
=0
包含了两个计算因子： 用来反映特征的分布情
况； 体现了 判断样本归属的期望值，用来降低在样本分布
中大样本类别相对小样本类别来说在类别归属上不平衡的因
素 ，抑 制 实 际 应 用 中 数 据 分 布 倾 斜 的 弱 点 。 从 几 何 角 度 分 析
1 KNN 算法
KNN 思想比较简单，计算待分样本 x 到所有训练集样本 的距离，找出与 x 最近的 k 个近邻进行投票，得票多的即为样 本所属类 。 [10] 对于离散型数据集，KNN 算法主要采用统计相 同特征个数作为距离，然后加权平均的方法 ；对 [11-13] 于数值型 数 据 集 ，主 要 采 用 欧 氏 距 离 [14-15] 来 确 定 样 本 的 距 离 。
全确定，虽然表面特征显示 、并不相关，但由于具有 、的样
本归属类别一致，因而 、距离测度为 0，无差异；
3)若 ≠ ，且 = 0 ( 对样本归属 类完全确定)， = 0 ( 对样本归属 类完全确定)，表示 与 完全不相关，差异无
限大，定义特征距离距离测度为最大值 1；
4) 除 上 述 极 端 情 况 外 ，D_
Improved algorithm of adopting feature correlation difference to optimize distance
ZHOU Jing, LIU Jin-sheng (College of Computer and Electronic Information, Guangdong University of Petrochemical Technology,
周靖，刘晋胜：采用特征相关性差异优化距离的改进 近邻算法
2011, Vol. 32, No.9 3179
响 ，产 生 由 于 不 同 类 别 的 邻 近 点 个 数 相 同 而 导 致 待 测 样 本 与 各 类 的 平 均 距 离 相 同 ，进 而 无 法 对 测 试 样 本 进 行 判 断 的 情 况 。 而欧式距离-KNN 的距离测度注重的是特征间表面数字特征 的 关 联 ，没 有 体 现 出 针 对 分 类 的 相 关 信 息 ，直 接 影 响 了 分 类 的 有效性和准确性。
3178 2011, Vol.32, No.9 计算计机算工机程工与程设与设计计CoCmopmupteurteErnEgningeinereienrginagnadnDdeDsiegsnign
采用特征相关性差异优化距离的改进 近邻算法
周 靖， 刘晋胜 (广东石油化工学院 计算机与电子信息学院，广东 茂名 525000)
分 类 都 是 绝 对 相 关 或 者 无 关 的 ，因 而 特 征 相 关 性 的 确 定 主 要
集中在类绝对相关的设置上，而 D_Corr 的确定则主要集中在 特 征 无 差 异 或 差 异 无 限 大 的 两 种 极 端 情 况 上 ，所 以 特 征 相 关
性差异值的计算更侧重对数据的检索比较，这也是 FCDKNN 计算量相对较小的原因。上述说明属于 FCDKNN 的预处理部
O'
Cw
Round4
1
图1
几何意义
(2)同一条件属性下特征相关性差异 D_
, 的设置。
设训练集有 v 个条件属性，, = 1,2,…,v，由特征相关性计
算其针对分类作用程度的差异可分为如下几种情况：
1)若 = ，表示特征针对分类的相关性相同，无差异，特征

合集下载

k紧邻分类的距离计算方法

k紧邻分类的距离计算方法

k紧邻分类的距离计算方法k-近邻分类（k-nearest neighbors classification）是一种常用的机器学习算法，它通过计算样本之间的距离来进行分类。

本文将介绍k-近邻分类的距离计算方法，并探讨其在实际应用中的优缺点。

一、距离计算方法在k-近邻分类中，计算样本之间的距离是非常重要的一步。

常用的距离计算方法有欧氏距离、曼哈顿距离、闵可夫斯基距离等。

下面分别介绍这些距离计算方法的原理和特点。

1. 欧氏距离（Euclidean Distance）欧氏距离是最常用的距离计算方法之一，它用于计算两个样本之间的直线距离。

假设有两个样本点A(x1, y1)和B(x2, y2)，则它们之间的欧氏距离可以表示为：d(A, B) = sqrt((x2 - x1)^2 + (y2 - y1)^2)欧氏距离的优点是计算简单，直观易懂。

然而，它对异常值比较敏感，可能会导致错误的分类结果。

2. 曼哈顿距离（Manhattan Distance）曼哈顿距离是另一种常用的距离计算方法，它用于计算两个样本之间的城市街区距离。

假设有两个样本点A(x1, y1)和B(x2, y2)，则它们之间的曼哈顿距离可以表示为：d(A, B) = |x2 - x1| + |y2 - y1|曼哈顿距离的优点是不受异常值的影响，对于离群点具有较好的鲁棒性。

然而，它没有考虑样本之间的斜率差异，可能导致分类结果不准确。

3. 闵可夫斯基距离（Minkowski Distance）闵可夫斯基距离是欧氏距离和曼哈顿距离的一种推广，它通过一个参数p来调节距离的计算方式。

当p=2时，闵可夫斯基距离等同于欧氏距离；当p=1时，闵可夫斯基距离等同于曼哈顿距离。

d(A, B) = (|x2 - x1|^p + |y2 - y1|^p)^(1/p)闵可夫斯基距离的优点是可以根据具体问题选择合适的p值，从而权衡欧氏距离和曼哈顿距离的影响。

然而，它的计算复杂度较高，需要考虑到p的选择和样本特征的归一化问题。

1.简述k最近邻算法的原理、算法流程以及优缺点

1.简述k最近邻算法的原理、算法流程以及优缺点

1.简述k最近邻算法的原理、算法流程以及优缺点一、什么是K近邻算法k近邻算法又称knn算法、最近邻算法，是一种用于分类和回归的非参数统计方法。

在这两种情况下，输入包含特征空间中的k个最接近的训练样本，这个k可以由你自己进行设置。

在knn分类中，输出是一个分类族群。

一个对象的分类是由其邻居的“多数表决”确定的，k个最近邻居（k为正整数，通常较小），所谓的多数表决指的是，在k个最近邻中，取与输入的类别相同最多的类别，作为输入的输出类别。

简而言之，k近邻算法采用测量不同特征值之间的距离方法进行分类。

knn算法还可以运用在回归预测中，这里的运用主要是指分类。

二、k近邻算法的优缺点和运用范围优点：精度高、对异常值不敏感、无数据输入假定。

缺点：计算复杂度高、空间复杂度高。

适用范围：数值型和标称型、如手写数字的分类等。

三、k近邻算法的工作原理假定存在一个样本数据集合，并且样本集中的数据每个都存在标签，也就是说，我们知道每一个样本数据和标签的对应关系。

输入一个需要分类的标签，判断输入的数据属于那个标签，我们提取出输入数据的特征与样本集的特征进行比较，然后通过算法计算出与输入数据最相似的k个样本，取k个样本中，出现次数最多的标签，作为输入数据的标签。

四、k近邻算法的一般流程（1）收集数据：可以使用任何方法，可以去一些数据集的网站进行下载数据。

（2）准备数据：距离计算所需要的数值，最好是结构化的数据格式（3）分析数据：可以使用任何方法（4）训练算法：此步骤不适用于k近邻算法（5）测试算法：计算错误率（6）使用算法：首先需要输入样本数据和结构化的输出结构（统一数据格式），然后运行k近邻算法判定输入数据属于哪一种类别。

五、k近邻算法的实现前言：在使用python实现k近邻算法的时候，需要使用到Numpy科学计算包。

如果想要在python中使用它，可以按照anaconda，这里包含了需要python需要经常使用到的科学计算库，如何安装。

k-nearest neighbors classifier

k-nearest neighbors classifier

k-nearest neighbors classifierK-nearest neighbors classifier（KNN）是一种非常简单且有效的分类算法。

它的基本思想是：在特征空间中，根据待分类样本的k个最近邻居的类别进行多数投票，以确定待分类样本的类别。

具体来说，KNN算法需要选择近邻的数量k和距离度量方法。

在训练阶段，算法会计算每个样本与训练集中其他样本之间的距离，并按照距离的升序进行排序。

然后，选择距离最小的k个样本作为待分类样本的最近邻居。

在分类阶段，算法会根据最近邻居的类别进行多数投票，以确定待分类样本的类别。

KNN算法的优点包括：简单易懂、实现容易、无需训练阶段、对数据分布不敏感等。

但是，KNN算法也存在一些缺点，例如：计算量大、对参数k的选择敏感、容易受到噪声和异常值的影响等。

在使用KNN算法时，需要注意以下几点：1.确定合适的k值：k值的选择对分类结果的影响较大，需要根据实际情况进行调整和选择。

常用的方法是通过交叉验证等技术来选择最优的k值。

2.距离度量的选择：距离度量方法的选择也会影响分类结果。

常用的距离度量方法有欧氏距离、曼哈顿距离等。

需要根据实际情况选择合适的距离度量方法。

3.数据预处理：由于KNN算法是基于距离的度量，因此数据预处理对于KNN算法来说非常重要。

需要将数据进行归一化或标准化处理，以消除不同特征之间的尺度差异。

4.处理多分类问题：KNN算法也可以用于多分类问题，但是需要采用一些特殊的方法进行处理。

例如，可以将多分类问题转化为多个二分类问题进行处理，或者使用其他多分类技术如一对多、多对一等。

5.处理连续特征：KNN算法对于连续特征的处理方式可能会影响分类结果。

如果待分类样本的特征是连续的，可以将连续特征离散化或者使用其他技术进行处理。

总之，KNN算法是一种简单且有效的分类算法，但是在实际应用中需要注意以上几点问题，并根据具体情况进行调整和优化。

人工智能实验-k-近邻算法

人工智能实验-k-近邻算法

k-近邻算法一、 实验题目1. kNN 代码实现-AB 分类采用测量不同特征值之间的距离方法进行分类，用所给的函数创建具有两个特征与一个标签类型的数据作 为训练集，编写 classify0 函数对所给的数据进行 AB 分类。

2. k-近邻算法改进约会网站的配对效果k-近邻算法改进约会网站的配对效果通过收集的一些约会网站的数据信息，对匹配对象的归类：不喜欢的人、魅力一般的人、极具魅力的人。

数据中包含了 3 种特征：每年获得的飞行常客里程数、玩视频游戏所耗时间百分比、每周消费的冰淇淋公升数二、 实验代码1. kNN 代码实现-AB 分类kNN from http.client import ImproperConnectionStatefrom numpy import ∗ from collections importCounter import operator def createDataSet():group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])labels = [’A ’, ’A ’, ’B’, ’B’] return group, labelsdef classify0(inX, group, labels, k = 3):res1 = (inX − group)∗∗2 dist =res1[:,0] + res1[:,1] dic = argsort(dist) dic = dic[0:k:1] newdic = [] for i in range (k): newdic.append(labels[dic[i]]) c = Counter(newdic).most_common(1) return c[0][0] tests import kNN group, lables = kNN.createDataSet() print (’分类结果’) print (’[0,0] %c’ %(kNN.classify0([0, 0], group, lables, k = 3))) print (’[0.8,0.7] %c’ %(kNN.classify0([0.8, 0.7], group, lables, k = 3)))2.k-近邻算法改进约会网站的配对效果1 2 3 4 5 67 8 910111213141516171819 1 2 3 4 5import pandas as pdimport kNNfrom sklearn.model_selection import train_test_splitdf = pd.read_table(’datingTestSet2.txt’,sep=’\s+’, names = [’A ’, ’B’, ’C’, ’Y’])# 对特征进行归一化处理df2 = df.iloc[:, :3] df2 =(df2−df2.mean())/df2.std() lable=df.iloc[:,3:4] df2.loc[:, ’Y’] =lable# 对数据集进行测试集和训练集划分，90%作为训练集，10%作为测试集X_train, X_test, Y_train, Y_test = train_test_split(df2.iloc[:, :3], df2.Y, train_size=.90)# 将DataFrame 格式转化为numpy 格式处理 group = X_train.values label =Y_train.values length =len (X_test) X_test.iloc[0:1,:]# res 以储存测试结果res = []# 设置错误正确数count 以计算正确率Tnum = 0 Fnum = 0 for iin range (length):inX = X_test.iloc[i:i+1 , :].values res.append(kNN.classify0(inX,group, label, k = 3)) if (kNN.classify0(inX, group, label, k = 3) ==Y_test.values[i]):Tnum += 1 else :Fnum += 1res1 = pd.DataFrame(data = res, columns=[’TestResult’])Y_test.reset_index(inplace=True,drop=True)res1.loc[:, ’OriginTest’] = Y_testprint (’前20个数据测试结果和原数据比较’) print (’−−−−−−−−−−−−−−−−−−−−−——−−−−’) print (res1.head(20))print (’−−−−−−−−−−−−−−−−−−−−−——−−−−’) print (’正确率%.2f%%’ %(100∗Tnum/(Tnum+Fnum))) 三、 实验结果及分析1. kNN 代码实现-AB 分类分类结果[0, 0] B[0.8, 0.7] A2. k-近邻算法改进约会网站的配对效果1 2 3 45 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2526 27 28 29 3031 32 33 3435363738 1 2 3前20个数据测试结果和原数据比较−−−−−−−−−−−−−−−−−−−−−——−−−TestResult OriginTest0 2 2 1 3 3 2 1 3 3 2 2 4 2 2 5 3 3 6 3 3 7 2 2 8 1 1 9 1 1 10 1 1 11 3 3 12 2 2 13 2 2 14 1 1 15 2 2 16 1 1 17 2 2 18 1 1 19 3 3−−−−−−−−−−−−−−−−−−−−−——−−− 正确率97.00%从实验结果可以看出，通过 k-近邻算法改进后的约会网站的配对效果比较显著，多次随机划分测试集和训练集后发现正确率基本可以达到 90% 以上。