文本分类算法knn

① R语言-KNN算法

1、K最近邻(k-NearestNeighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。

2、KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。

3、KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。

简言之，就是将未标记的案例归类为与它们最近相似的、带有标记的案例所在的类 。

原理及举例

工作原理：我们知道样本集中每一个数据与所属分类的对应关系，输入没有标签的新数据后，将新数据与训练集的数据对应特征进行比较，找出“距离”最近的k（通常k<20）数据，选择这k个数据中出现最多的分类作为新数据的分类。

算法描述

1、计算已知数据集中的点与当前点的距离

2、按距离递增次序排序

3、选取与当前数据点距离最近的K个点

4、确定前K个点所在类别出现的频率

5、返回频率最高的类别作为当前类别的预测

距离计算方法有"euclidean"（欧氏距离）,”minkowski”（明科夫斯基距离）, "maximum"（切比雪夫距离）, "manhattan"（绝对值距离）,"canberra"（兰式距离）, 或 "minkowski"（马氏距离）等

Usage

knn(train, test, cl, k = 1, l = 0, prob =FALSE, use.all = TRUE)

Arguments

train

matrix or data frame of training set cases.

test

matrix or data frame of test set cases. A vector will  be interpreted as a row vector for a single case.

cl

factor of true classifications of training set

k

number of neighbours considered.

l

minimum vote for definite decision, otherwisedoubt. (More precisely, less thank-ldissenting votes are allowed, even

ifkis  increased by ties.)

prob

If this is true, the proportion of the votes for the

winning class are returned as attributeprob.

use.all

controls handling of ties. If true, all distances equal

to thekth largest are

included. If false, a random selection of distances equal to thekth is chosen to use exactlykneighbours.

kknn(formula = formula(train), train, test, na.action = na.omit(), k = 7, distance = 2, kernel = "optimal", ykernel = NULL, scale=TRUE, contrasts = c('unordered' = "contr.mmy", ordered = "contr.ordinal"))

参数：

formula                            A formula object.

train                                 Matrix or data frame of training set cases.

test                                   Matrix or data frame of test set cases.

na.action                         A function which indicates what should happen when the data contain ’NA’s.

k                                       Number of neighbors considered.

distance                          Parameter of Minkowski distance.

kernel                              Kernel to use. Possible choices are "rectangular" (which is standard unweighted knn), "triangular", "epanechnikov" (or beta(2,2)), "biweight" (or beta(3,3)), "triweight" (or beta(4,4)), "cos", "inv", "gaussian", "rank" and "optimal".

ykernel                            Window width of an y-kernel, especially for prediction of ordinal classes.

scale                                Logical, scale variable to have equal sd.

contrasts                         A vector containing the ’unordered’ and ’ordered’ contrasts to use

kknn的返回值如下：

fitted.values              Vector of predictions.

CL                              Matrix of classes of the k nearest neighbors.

W                                Matrix of weights of the k nearest neighbors.

D                                 Matrix of distances of the k nearest neighbors.

C                                 Matrix of indices of the k nearest neighbors.

prob                            Matrix of predicted class probabilities.

response                   Type of response variable, one of continuous, nominal or ordinal.

distance                     Parameter of Minkowski distance.

call                              The matched call.

terms                          The ’terms’ object used.

iris%>%ggvis(~Length,~Sepal.Width,fill=~Species)

library（kknn）
data（iris）

dim(iris)

m<-(dim(iris))[1]
val<-sample(1:m,size=round(m/3）,replace=FALSE,prob=rep(1/m,m))

建立训练数据集

data.train<-iris[-val,]

建立测试数据集

data.test<-iris[val,]

调用kknn  之前首先定义公式

formula ： Species ~ Sepal.Length + Sepal.Width + Petal.Length + Petal.Width

iris.kknn<-kknn(Species~.,iris.train,iris.test,distance=1,kernel="triangular")

summary(iris.kknn)

# 获取fitted.values

fit <- fitted(iris.kknn)

# 建立表格检验判类准确性

table(iris.valid$Species, fit)
# 绘画散点图，k-nearest neighbor用红色高亮显示

pcol <- as.character(as.numeric(iris.valid$Species))

pairs(iris.valid[1:4], pch = pcol, col = c("green3", "red")[(iris.valid$Species != fit)+1]

二、R语言knn算法

install.packages("class")

library(class)

对于新的测试样例基于距离相似度的法则，确定其K个最近的邻居，在K个邻居中少数服从多数

确定新测试样例的类别

1、获得数据

2、理解数据

对数据进行探索性分析，散点图

如上例

3、确定问题类型，分类数据分析

4、机器学习算法knn

5、数据处理，归一化数据处理

normalize <- function(x){

num <- x - min(x)

denom <- max(x) - min(x)

return(num/denom)

}

iris_norm <-as.data.frame(lapply(iris[,1:4], normalize))

summary(iris_norm)

6、训练集与测试集选取

一般按照3:1的比例选取

方法一、set.seed(1234)

ind <- sample(2,nrow(iris), replace=TRUE, prob=c(0.67, 0.33))

iris_train <-iris[ind==1, 1:4]

iris_test <-iris[ind==2, 1:4]

train_label <-iris[ind==1, 5]

test_label <-iris[ind==2, 5]

方法二、

ind<-sample(1:150,50)

iris_train<-iris[-ind,]

iris_test<-iris[ind,1:4]

iris_train<-iris[-ind,1:4]

train_label<-iris[-ind,5]

test_label<-iris[ind,5]

7、构建KNN模型

iris_pred<-knn(train=iris_train,test=iris_test,cl=train_label,k=3)

8、模型评价

交叉列联表法

table（test_label,iris_pred)

实例二

数据集

http://archive.ics.uci.e/ml/machine-learning-databases/breast-cancer-wisconsin/wdbc.data

导入数据

dir <-'http://archive.ics.uci.e/ml/machine-learning-databases/breast-cancer-wisconsin/wdbc.data'wdbc.data <-read.csv(dir,header = F)

names(wdbc.data) <- c('ID','Diagnosis','radius_mean','texture_mean','perimeter_mean','area_mean','smoothness_mean','compactness_mean','concavity_mean','concave points_mean','symmetry_mean','fractal dimension_mean','radius_sd','texture_sd','perimeter_sd','area_sd','smoothness_sd','compactness_sd','concavity_sd','concave points_sd','symmetry_sd','fractal dimension_sd','radius_max_mean','texture_max_mean','perimeter_max_mean','area_max_mean','smoothness_max_mean','compactness_max_mean','concavity_max_mean','concave points_max_mean','symmetry_max_mean','fractal dimension_max_mean')

table(wdbc.data$Diagnosis)## M = malignant, B = benign

wdbc.data$Diagnosis <- factor(wdbc.data$Diagnosis,levels =c('B','M'),labels = c(B ='benign',M ='malignant'))

② KNN库简介

机器学习经典库scikit-learn中的sklearn.neighbors包集成了近邻法相关的算法，KNN分类树算法使用KNeighborsClassifier，回归树使用KNeighborsRegressor。除此之外，还有KNN的扩展，即限定半径最近邻分类树RadiusNeighborsClassifier和限定半径最近邻回归树RadiusNeighborsRegressor，以及最近质心分类算法NearestCentroid。

在这些算法中，KNN分类和回归的类参数完全一样。限定半径最近邻法分类和回归的类的主要参数也和KNN基本一样。比较特别是的最近质心分类算法，由于它是直接选择最近质心来分类，所以仅有两个参数，距离度量和特征选择距离阈值。

限定半径最近邻算法，即样本中某系类别的样本非常的少，甚至少于K，这导致稀有类别样本在找K个最近邻的时候，会把距离其实较远的其他样本考虑进来，而导致预测不准确。为了解决这个问题，我们限定最近邻的一个最大距离，也就是说，我们只在一个距离范围内搜索所有的最近邻，这避免了上述问题。这个距离我们一般称为限定半径。

最近质心算法首先把样本按输出类别归类。对于第 L类的Cl个样本。它会对这Cl个样本的n维特征中每一维特征求平均值，最终该类别所有维度的n个平均值形成所谓的质心点。对于样本中的所有出现的类别，每个类别会最终得到一个质心点。当我们做预测时，仅仅需要比较预测样本和这些质心的距离，最小的距离对于的质心类别即为预测的类别。这个算法通常用在文本分类处理上。

KNN的主要优点有：

1） 理论成熟，思想简单，既可以用来做分类也可以用来做回归

2） 可用于非线性分类

3） 训练时间复杂度比支持向量机之类的算法低，仅为O(n)

4） 和朴素贝叶斯之类的算法比，对数据没有假设，准确度高，对异常点不敏感

5） 由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合

6）该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分

KNN的主要缺点有：

1）计算量大，尤其是特征数非常多的时候

2）样本不平衡的时候，对稀有类别的预测准确率低

3）KD树，球树之类的模型建立需要大量的内存

4）使用懒散学习方法，基本上不学习，导致预测时速度比起逻辑回归之类的算法慢

5）相比决策树模型，KNN模型可解释性不强

③ KNN 算法-理论篇-如何给电影进行分类

KNN 算法 的全称是 K-Nearest Neighbor ，中文为 K 近邻 算法，它是基于 距离 的一种算法，简单有效。

KNN 算法 即可用于分类问题，也可用于回归问题。

假如我们统计了一些 电影数据，包括电影名称，打斗次数，接吻次数，电影类型 ，如下：

可以看到，电影分成了两类，分别是动作片和爱情片。

如果现在有一部新的电影A，它的打斗和接吻次数分别是80 和7，那如何用KNN 算法对齐进行分类呢？

我们可以将打斗次数作为 X 轴 ，接吻次数作为 Y 轴 ，将上述电影数据画在一个坐标系中，如下：

通过上图可以直观的看出，动作电影与爱情电影的分布范围是不同的。

KNN 算法 基于距离，它的原理是： 选择与待分类数据最近的K 个点，这K 个点属于哪个分类最多，那么待分类数据就属于哪个分类 。

所以，要判断电影A 属于哪一类电影，就要从已知的电影样本中，选出距离电影A 最近的K 个点：

比如，我们从样本中选出三个点（即 K 为 3），那么距离电影A 最近的三个点是《功夫》，《黑客帝国》和《战狼》，而这三部电影都是动作电影。因此，可以判断电影A 也是动作电影。

另外，我们还要处理两个问题：

关于点之间的距离判断，可以参考文章 《计算机如何理解事物的相关性》 。

至于K 值的选择，K 值较大或者较小都会对模型的训练造成负面影响，K 值较小会造成 过拟合 ，K 值较大 欠拟合 。

因此，K 值的选择，一般采用 交叉验证 的方式。

交叉验证的思路是，把样本集中的大部分样本作为训练集，剩余部分用于预测，来验证分类模型的准确度。一般会把 K 值选取在较小范围内，逐一尝试K 的值，当模型准确度最高时，就是最合适的K 值。

可以总结出， KNN 算法 用于分类问题时，一般的步骤是：

如果，我们现在有一部电影B，知道该电影属于动作电影，并且知道该电影的接吻次数是 7 ，现在想预测该电影的打斗次数是多少？

这个问题就属于 回归问题 。

首先看下，根据已知数据，如何判断出距离电影B 最近的K 个点。

我们依然设置K 为3，已知数据为：

根据已知数据可以画出下图：

图中我画出了一条水平线，这条线代表所有接吻次数是7 的电影，接下来就是要找到距离 这条线 最近的三部（K 为 3）动作电影。

可以看到，距离这条水平线最近的三部动作电影是《功夫》，《黑客帝国》和《战狼》，那么这三部电影的打斗次数的平均值，就是我们预测的电影B 的打斗次数。

所以，电影B 的打斗次数是：

本篇文章主要介绍了 KNN 算法 的基本原理，它简单易懂，即可处理分类问题，又可处理回归问题。

KNN 算法 是基于 距离 的一种机器学习算法，需要计算测试点与样本点之间的距离。因此，当数据量大的时候，计算量就会非常庞大，需要大量的存储空间和计算时间。

另外，如果样本数据分类不均衡，比如有些分类的样本非常少，那么该类别的分类准确率就会很低。因此，在实际应用中，要特别注意这一点。

（本节完。）

推荐阅读：

决策树算法-理论篇-如何计算信息纯度

决策树算法-实战篇-鸢尾花及波士顿房价预测

朴素贝叶斯分类-理论篇-如何通过概率解决分类问题

朴素贝叶斯分类-实战篇-如何进行文本分类

计算机如何理解事物的相关性-文档的相似度判断

④ 文本分类方法有哪些

文本分类问题： 给定文档p（可能含有标题t），将文档分类为n个类别中的一个或多个
文本分类应用： 常见的有垃圾邮件识别，情感分析
文本分类方向： 主要有二分类，多分类，多标签分类
文本分类方法： 传统机器学习方法（贝叶斯，svm等），深度学习方法（fastText，TextCNN等）
本文的思路： 本文主要介绍文本分类的处理过程，主要哪些方法。致力让读者明白在处理文本分类问题时应该从什么方向入手，重点关注什么问题，对于不同的场景应该采用什么方法。
文本分类的处理大致分为 文本预处理 、文本 特征提取 、 分类模型构建 等。和英文文本处理分类相比，中文文本的预处理是关键技术。

针对中文文本分类时，很关键的一个技术就是中文分词。特征粒度为词粒度远远好于字粒度，其大部分分类算法不考虑词序信息，基于字粒度的损失了过多的n-gram信息。下面简单总结一下中文分词技术:基于字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法 [1]。

1，基于字符串匹配的分词方法：
过程：这是 一种基于词典的中文分词 ，核心是首先建立统一的词典表，当需要对一个句子进行分词时，首先将句子拆分成多个部分，将每一个部分与字典一一对应，如果该词语在词典中，分词成功，否则继续拆分匹配直到成功。
核心： 字典，切分规则和匹配顺序是核心。
分析：优点是速度快，时间复杂度可以保持在O（n）,实现简单，效果尚可；但对歧义和未登录词处理效果不佳。

2， 基于理解的分词方法：基于理解的分词方法是通过让计算机模拟人对句子的理解 ，达到识别词的效果。其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现象。它通常包括三个部分：分词子系统、句法语义子系统、总控部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。这种分词方法需要使用大量的语言知识和信息。由于汉语语言知识的笼统、复杂性，难以将各种语言信息组织成机器可直接读取的形式，因此目前基于理解的分词系统 还处在试验阶段 。

3，基于统计的分词方法:
过程：统计学认为分词是一个 概率最大化问题 ，即拆分句子，基于语料库，统计 相邻的字组成的词语出现的概率 ，相邻的词出现的次数多，就出现的概率大， 按照概率值进行分词 ，所以一个完整的语料库很重要。
主要的统计模型有： N元文法模型（N-gram），隐马尔可夫模型（Hidden Markov Model ，HMM），最大熵模型（ME），条件随机场模型（Conditional Random Fields，CRF）等。

1， 分词 ： 中文任务分词必不可少，一般使用jieba分词，工业界的翘楚。
2， 去停用词：建立停用词字典 ，目前停用词字典有2000个左右，停用词主要包括一些副词、形容词及其一些连接词。通过维护一个停用词表，实际上是一个特征提取的过程，本质 上是特征选择的一部分。
3， 词性标注 ： 在分词后判断词性（动词、名词、形容词、副词…），在使用jieba分词的时候设置参数就能获取。

文本分类的核心都是如何从文本中抽取出能够体现文本特点的关键特征，抓取特征到类别之间的映射。 所以特征工程很重要，可以由四部分组成：

1，基于词袋模型的特征表示：以词为单位（Unigram）构建的词袋可能就达到几万维，如果考虑二元词组（Bigram）、三元词组（Trigram）的话词袋大小可能会有几十万之多，因此基于词袋模型的特征表示通常是极其稀疏的。

（1）词袋特征的方法有三种：

（2）优缺点：

2，基于embedding的特征表示： 通过词向量计算文本的特征。（主要针对短文本）

4，基于任务本身抽取的特征：主要是针对具体任务而设计的，通过我们对数据的观察和感知，也许能够发现一些可能有用的特征。有时候，这些手工特征对最后的分类效果提升很大。举个例子，比如对于正负面评论分类任务，对于负面评论，包含负面词的数量就是一维很强的特征。

5，特征融合：对于特征维数较高、数据模式复杂的情况，建议用非线性模型（如比较流行的GDBT, XGBoost）；对于特征维数较低、数据模式简单的情况，建议用简单的线性模型即可（如LR）。

6，主题特征：
LDA（文档的话题）： 可以假设文档集有T个话题，一篇文档可能属于一个或多个话题，通过LDA模型可以计算出文档属于某个话题的概率，这样可以计算出一个DxT的矩阵。LDA特征在文档打标签等任务上表现很好。
LSI（文档的潜在语义）： 通过分解文档-词频矩阵来计算文档的潜在语义，和LDA有一点相似，都是文档的潜在特征。

这部分不是重点，传统机器学习算法中能用来分类的模型都可以用，常见的有：NB模型，随机森林模型（RF），SVM分类模型，KNN分类模型，神经网络分类模型。
这里重点提一下贝叶斯模型，因为工业用这个模型用来识别垃圾邮件[2]。

1，fastText模型： fastText 是word2vec 作者 Mikolov 转战 Facebook 后16年7月刚发表的一篇论文： Bag of Tricks for Efficient Text Classification [3]。

模型结构：

改进：注意力（Attention）机制是自然语言处理领域一个常用的建模长时间记忆机制，能够很直观的给出每个词对结果的贡献，基本成了Seq2Seq模型的标配了。实际上文本分类从某种意义上也可以理解为一种特殊的Seq2Seq，所以考虑把Attention机制引入近来。

过程：
利用前向和后向RNN得到每个词的前向和后向上下文的表示：

词的表示变成词向量和前向后向上下文向量连接起来的形式：

模型显然并不是最重要的： 好的模型设计对拿到好结果的至关重要，也更是学术关注热点。但实际使用中，模型的工作量占的时间其实相对比较少。虽然再第二部分介绍了5种CNN/RNN及其变体的模型，实际中文本分类任务单纯用CNN已经足以取得很不错的结果了，我们的实验测试RCNN对准确率提升大约1%，并不是十分的显着。最佳实践是先用TextCNN模型把整体任务效果调试到最好，再尝试改进模型。

理解你的数据： 虽然应用深度学习有一个很大的优势是不再需要繁琐低效的人工特征工程，然而如果你只是把他当做一个黑盒，难免会经常怀疑人生。一定要理解你的数据，记住无论传统方法还是深度学习方法，数据 sense 始终非常重要。要重视 badcase 分析，明白你的数据是否适合，为什么对为什么错。

超参调节： 可以参考 深度学习网络调参技巧 - 知乎专栏

一定要用 dropout： 有两种情况可以不用：数据量特别小，或者你用了更好的正则方法，比如bn。实际中我们尝试了不同参数的dropout，最好的还是0.5，所以如果你的计算资源很有限，默认0.5是一个很好的选择。

未必一定要 softmax loss： 这取决与你的数据，如果你的任务是多个类别间非互斥，可以试试着训练多个二分类器，也就是把问题定义为multi lable 而非 multi class，我们调整后准确率还是增加了>1%。

类目不均衡问题： 基本是一个在很多场景都验证过的结论：如果你的loss被一部分类别dominate，对总体而言大多是负向的。建议可以尝试类似 booststrap 方法调整 loss 中样本权重方式解决。

避免训练震荡： 默认一定要增加随机采样因素尽可能使得数据分布iid，默认shuffle机制能使得训练结果更稳定。如果训练模型仍然很震荡，可以考虑调整学习率或 mini_batch_size。

知乎的文本多标签分类比赛，给出第一第二名的介绍网址：
NLP大赛冠军总结：300万知乎多标签文本分类任务(附深度学习源码)
2017知乎看山杯 从入门到第二

⑤ knn和kmeans的区别

knn属于监督学习,类别是已知的,通过对已知分类的数据进行训练和学习,找到这些不同类的特征,再对未分类的数据进行分类。kmeans属于非监督学习,事先不知道数据会分为几类,通过聚类分析将数据聚合成几个群体。

knn和kmeans的区别

1.KNN算法是分类算法，分类算法肯定是需要有学习语料，然后通过学习语料的学习之后的模板来匹配我们的测试语料集，将测试语料集合进行按照预先学习的语料模板来分类

2Kmeans算法是聚类算法，聚类算法与分类算法最大的区别是聚类算法没有学习语料集合。

K-means算法是聚类分析中使用最广泛的算法之一。它把n个对象根据他们的属性分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。

Kmeans算法的缺陷

聚类中心的个数K 需要事先给定，但在实际中这个 K 值的选定是非常难以估计的，很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适

Kmeans需要人为地确定初始聚类中心，不同的初始聚类中心可能导致完全不同的聚类结果。(可以使用Kmeans++算法来解决)

针对上述第2个缺陷，可以使用Kmeans++算法来解决

K-Means ++ 算法

k-means++算法选择初始seeds的基本思想就是：初始的聚类中心之间的相互距离要尽可能的远。

从输入的数据点集合中随机选择一个点作为第一个聚类中心

对于数据集中的每一个点x，计算它与最近聚类中心(指已选择的聚类中心)的距离D(x)

选择一个新的数据点作为新的聚类中心，选择的原则是：D(x)较大的点，被选取作为聚类中心的概率较大

重复2和3直到k个聚类中心被选出来

利用这k个初始的聚类中心来运行标准的k-means算法

从上面的算法描述上可以看到，算法的关键是第3步，如何将D(x)反映到点被选择的概率上，一种算法如下：

先从我们的数据库随机挑个随机点当“种子点”

对于每个点，我们都计算其和最近的一个“种子点”的距离D(x)并保存在一个数组里，然后把这些距离加起来得到Sum(D(x))。

然后，再取一个随机值，用权重的方式来取计算下一个“种子点”。这个算法的实现是，先取一个能落在Sum(D(x))中的随机值Random，然后用Random -= D(x)，直到其<=0，此时的点就是下一个“种子点”。

重复2和3直到k个聚类中心被选出来

利用这k个初始的聚类中心来运行标准的k-means算法

⑥ 文本分类器（基于KNN算法），语言最好是Matlab的，有测试数据集。。。。

function [ccr,pgroupt]=knnt(x,group,K,dist,xt,groupt)
%#
%# AIM: to classify test set objects or unknown objects with the
%# K Nearest Neighbour method
%#
%# PRINCIPLE: KNN is a supervised, deterministic, non-parametric
%# classification method. It uses the majority rule to
%# assign new objects to a class.
%# It is assumed that the number of objects in each class
%# is similar.
%# There are no assumptions about the data distribution and
%# the variance-covariance matrices of each class.
%# There is no limitation of the number of variables when
%# the Euclidean distance is used.
%# However, when the correlation coefficient is used, the
%# number of variables must be larger than 1.
%# Ref: Massart D. L., Vandeginste B. G. M., Deming S. N.,
%# Michotte Y. and Kaufman L., Chemometrics: a textbook,
%# Chapter 23, 395-397, Elsevier Science Publishers B. V.,
%# Amsterdam 1988.
%#
%# INPUT: x: (mxn) data matrix with m objects and n variables,
%# containing samples of several classes (training set)
%# group: (mx1) column vector labelling the m objects from the
%# training set
%# K: integer, number of nearest neighbours
%# dist: integer,
%# = 1, Euclidean distance
%# = 2, Correlation coefficient, (No. of variables >1)
%# xt: (mtxn) data matrix with mt objects and n variables
%# (test set or unknowns)
%# groupt: (mtx1) column vector labelling the mt objects from
%# the test set
%# --> if the new objects are unknown, input [].
%#
%# OUTPUT: ccr: scalar, correct classification rate
%# pgroupt:row vector, predicted class label for the test set
%# 0 means that the object is not classified to any
%# class
%#
%# SUBROUTINES: sortlab.m: sorts the group label vector into classes
%#
%# AUTHOR: Wen Wu
%# Copyright(c) 1997 for ChemoAc
%# FABI, Vrije Universiteit Brussel
%# Laarbeeklaan 103 1090 Jette
%#
%# VERSION: 1.1 (28/02/1998)
%#
%# TEST: Andrea Candolfi
%#

function [ccr,pgroupt]=knnt(x,group,K,dist,xt,groupt);

if nargin==5, groupt=[]; end % for unknown objects
distance=dist; clear dist % change variable
if size(group,1)>1,
group=group'; % change column vector into row vector
groupt=groupt'; % change column vector into row vector
end;
[m,n]=size(x); % size of the training set

if distance==2 & n<2, error('Number of variables must > 1'),end % to check the number of variables when using correlation coefficient

[mt,n]=size(xt); % size of the test set
dis=zeros(mt,m); % initial values for the distance (matrix of zeros)

% Calculation of the distance for each test set object
for i=1:mt
for j=1:m % between each training set object and each test set object
if distance==1
dis(i,j)=(xt(i,:)-x(j,:))*(xt(i,:)-x(j,:))'; % Euclidian distance
else
r=corrcoef(xt(i,:)',x(j,:)'); % Correlation coefficient matrix
r=r(1,2); % Correlation coefficient
dis(i,j)=1-r*r; % 1 - the power of correlation coefficient
end
end
end

% Finding of the nearest neighbours
lab=zeros(1,mt); % initial values of lab
for i=1:mt % for each test object
[a,b]=sort(dis(i,:)); % sort distances
b=b(find(a<=a(K))); % to find the nearest neighbours indices
b=group(b); % the nearest neighbours objects
[ng,lgroup]=sortlab(b); % calculate the number of objects from each class in the nearest neighbours
a=find(ng==max(ng)); % find the class with the maximum number of objects

if length(a)==1 % only one class
lab(i)=lgroup(a); % class label
else
lab(i)=0; % more than one class
end
end

% Calculation of the success rate
if ~isempty(groupt)
dif=groupt-lab; % difference between predicted class label and known class label
ccr=sum(dif==0)/mt; % success rate
end

pgroupt=lab; % the output vector

⑦ 什么叫做knn算法

在模式识别领域中，最近邻居法（KNN算法，又译K-近邻算法）是一种用于分类和回归的非参数统计方法。

在这两种情况下，输入包含特征空间（Feature Space）中的k个最接近的训练样本。

1、在k-NN分类中，输出是一个分类族群。一个对象的分类是由其邻居的“多数表决”确定的，k个最近邻居（k为正整数，通常较小）中最常见的分类决定了赋予该对象的类别。若k=1，则该对象的类别直接由最近的一个节点赋予。

2、在k-NN回归中，输出是该对象的属性值。该值是其k个最近邻居的值的平均值。

最近邻居法采用向量空间模型来分类，概念为相同类别的案例，彼此的相似度高，而可以借由计算与已知类别案例之相似度，来评估未知类别案例可能的分类。

K-NN是一种基于实例的学习，或者是局部近似和将所有计算推迟到分类之后的惰性学习。k-近邻算法是所有的机器学习算法中最简单的之一。

无论是分类还是回归，衡量邻居的权重都非常有用，使较近邻居的权重比较远邻居的权重大。例如，一种常见的加权方案是给每个邻居权重赋值为1/ d，其中d是到邻居的距离。

邻居都取自一组已经正确分类（在回归的情况下，指属性值正确）的对象。虽然没要求明确的训练步骤，但这也可以当作是此算法的一个训练样本集。

k-近邻算法的缺点是对数据的局部结构非常敏感。

K-均值算法也是流行的机器学习技术，其名称和k-近邻算法相近，但两者没有关系。数据标准化可以大大提高该算法的准确性。

参数选择

如何选择一个最佳的K值取决于数据。一般情况下，在分类时较大的K值能够减小噪声的影响，但会使类别之间的界限变得模糊。一个较好的K值能通过各种启发式技术（见超参数优化）来获取。

噪声和非相关性特征的存在，或特征尺度与它们的重要性不一致会使K近邻算法的准确性严重降低。对于选取和缩放特征来改善分类已经作了很多研究。一个普遍的做法是利用进化算法优化功能扩展，还有一种较普遍的方法是利用训练样本的互信息进行选择特征。

在二元（两类）分类问题中，选取k为奇数有助于避免两个分类平票的情形。在此问题下，选取最佳经验k值的方法是自助法。

⑧ 用KNN算法判断知识掌握程度高低

KNN算法既可以解决分类问题，也可以解决预测问题。
基础思想：通过计算每个训练样例到待分类样品的距离，取和待分类样品距离最近的K个训练样例，K个样品中哪个类别的训练样例占多数，则待分类样品就属于哪个类别。

对于离散型因变量，从k个最近的已知类别样本中挑选出频率最高的类别用于未知样本的判断；对于连续型因变量，将k个最近的已知样本均值用作未知样本的预测。

k值过小，模型过拟合，例如k=1，未知样本的类别将由最近的1个已知样本点来决定，对于训练数据来说，训练误差几乎为0，对于测试数据来说，训练误差可能会很大，因为距离最近的1个已知样本点可以是异常观测值，也可以是正常观测值。

k值过大，模型欠拟合，例如k=N，未知样本的类别将由所有已知样本中频数最高的类别决定，不管是训练集还是测试集被判为一种类别，易欠拟合。

一般利用多重交叉验证得到平均误差最小的k值。还有一种方法是设置k近邻样本的投票权重，对已知样本距离较远的设置权重低一些，较近的设置权重高一些，通常将权重设置为距离的倒数。

点与点之间的距离即相似性，一般用欧氏距离，即L2范数
或者曼哈顿距离，即L1范数
或者余弦相似度cosα
或者杰卡德相似系数，即J=|A∩B|/|A∪B|

在使用距离方法来度量相似性时，要使所有变量数值化（通过哑变量或者重编码为0,1,2），而且采用标准化方法进行归一化，防止数值变量的量纲影响

近邻搜寻方法包括：暴力搜寻法（全表扫描），kd树（k为训练集中包含的变量个数，而非KNN中的k个邻近样本，先用所有已知类别的样本点构造一棵树，再将未知类别应用在树上），球树搜寻（将kd树中的超矩形体换成了超球体）。

优点：
精度高，对异常值不敏感，无数据输入假定；
KNN 是一种在线技术，新数据可以直接加入数据集而不必进行重新训练；
KNN 理论简单，容易实现。

缺点：
对于样本容量大的数据集计算量比较大，即计算复杂度高；
必须保存全部数据集，即空间复杂度高；
KNN 每一次分类都会重新进行一次全局运算；
样本不平衡时，预测偏差比较大。如：某一类的样本比较少，而其它类样本比较多；
K 值大小的选择；
KNN 无法给出基础结构信息，无法知晓平均实例样本与典型实例样本具有什么特征，即无法给出数据的内在含义。

应用领域：
文本分类；模式识别；聚类分析；多分类领域。

行表示每一个被观测的学生，
STG：在目标学科上的学习时长，
SCG：重复次数
STR：相关科目的学习时长
LPR：相关科目的考试成绩
PEG：目标科目的考试成绩
（以上指标均已标准化）
UNG：对知识的掌握程度高低

利用多重交叉验证获取符合数据的理想k值

经过10重交叉验证，最佳的近邻个数为6

weights=uniform，表示投票权重一样
=distance，表示投票权重与距离成反比

从主对角线看，绝大多数样本被正确分类

通过热力图可视化混淆矩阵

行代表真实地，列代表预测的，主对角线上的颜色比较深，说明绝大多数样本是被正确分类的。

下面得到模型在测试集上的预测准确率：

整体预测准确率为91.09%，要得到每个类别的准确率：

第一列为预测精度，即”预测正确的类别个数/该类别预测的所有个数"
第二列为预测覆盖率，即”预测正确的类别个数/该类别实际的所有个数"
第三列为前两列的加权结果
第四列为类别实际的样本个数

对于预测问题的解决同决策树中一样，用MSE衡量

⑨ knn算法是什么

KNN（K- Nearest Neighbor）法即K最邻近法，最初由Cover和Hart于1968年提出，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。

作为一种非参数的分类算法，K-近邻（KNN）算法是非常有效和容易实现的。它已经广泛应用于分类、回归和模式识别等。

介绍

KNN算法本身简单有效，它是一种lazy-learning算法，分类器不需要使用训练集进行训练，训练时间复杂度为0。KNN分类的计算复杂度和训练集中的文档数目成正比，也就是说，如果训练集中文档总数为n，那么KNN的分类时间复杂度为O(n)。

KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。