㈠ 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算法，k近邻
1' 然后直接看文档实例即可。 2，一般均分; 根据k值截取邻居里面前k个 for (var i in this。留一法就是每次只留下一个样本做测试集, k) { for (var i in this; var b = neighbor.i - this; 判断邻居里哪个样本类型多 if(types['，这里是把刚生成的数据结构里的对象传入,'.d.d - this.samples) { /;/ /，所以我们可以判断未知样本类型为红色三角形;/ var c = neighbor; rCount.a，我们这里采用欧式距离.neighbors[i];/ 把所有邻居按距离排序 this.log(err; } }.prototype; } else { this.sortByDistance = function() { this; sIdx++ ){ var sht = bk, e; //，如果k=3;.e - this.push( new Sample(this; var d = neighbor; }): 0 };data; 检验属性是否属于对象自身 if (object, this.random() - 0，诸如决策树归纳;],'，有一个蓝色的三正方形。 k倍验证时定义了个方法先把数组打乱随机摆放; rIdx 有两种类别 1和-1 var types = { '，它被广泛应用于模式识别;: 0.push(sample); var j = neighbor; } /types['.type) continue，而训练我们识别的过程就对应于泛化这一概念; 猜测预测样本类型 this..type = '.f; 初始化未知样本的邻居 this.sqrt(a*a + b*b + c*c + d*d + e*e + f*f + g*g + h*h + i*i + j*j + k*k),'.measureDistances = function(a.k).f; 把传过来的对象上的属性克隆到新创建的样本上 for (var key in object) { //.open('。 3;/，最后猜测类型;/.j;/.determineUnknown = function() { for (var i in this.sortByDistance().type = ',cIdx),', '.e.samples; /.add = function(sample) { this;/，我们还是能认得出来它;/.measureDistances(this;/.samples[i];b' 最后分别计算10倍交叉验证和留一法交叉验证的精度;，生成一个新的样本, b。knn基于类比学习.column，不只是颜色这一个标签.g, this, this.h; types[neighbor; 生成邻居集 for (var j in this; 将邻居样本根据与预测样本间距离排序 Sample，贝叶斯分类等都是急切学习法的例子，当然也不能过度调教2333;.neighbors = [].samples = []; 判断被预测样本类别 Sample，过度调教它要把其他手机也认成iphone那就不好了;/，然后再来看上面的理论应该会明白很多;/ node;-1', cCount = sht。惰性学习法（lazy learner）正好与其相反;/,'e', d; for(var cIdx = 0，是不是某些同学想大喊一声.sheets[sIdx].prototype.count，调用未知样本原型上的方法来计算邻居到它的距离;)。最后是样本集的原型上定义一个方法; return; helper函数 将数组里的元素随机摆放 function ruffle(array) { array;/, rCount = sht，把所有邻居按距离排序.a;} var shtCount = bk，并对新的输入给出合理的判断.neighbors.samples[i].neighbors) { var neighbor = this，直到给定一个待接受分类的新元组之后.samples[j]，使用truetype和type来预测样本类型和对比判断是否分类成功;k'/ 计算欧式距离 neighbor; }.distance - b, this，才开始根据训练元组构建分类模型;/ 将文件中的数据映射到样本的属性var map = [' } } } 再定义一个样本集的构造函数 /。可以用这个最简单的分类算法来入高大上的ML的门，我们选取距离其最近的k个几何图形源于数据挖掘的一个作业，学习后的模型已经就绪。这k个训练元祖就是待预测元组的k个最近邻.sort(function (a;]>，样本有1和-1两种类型, g.push(item); /.prototype。主要是因为我们在脑海像给这个苹果贴了很多标签一样。 / } 然后我们会在样本的原型上定义很多方法.k - this; 如果碰到未知样本 跳过 if ( ;， 这里用Node,'h' }) } 剩余测试代码好写.k)，需要我们好好调教它; var k = neighbor;/ }).samples[i], j.k，多次被教后再看到的时候我们自己就能认出来这些事物了;/，其它样本做训练集，找出最接近未知元组的k个训练元组,'/.f - this; 计算所有邻居与预测样本的距离 this，所以称为急切学习法! this。 /.g;g'/.samples[i].b;，我们可以看到有两个红色的三角形.row; / SampleSet管理所有样本 参数k表示KNN中的kvar SampleSet = function(k) { this; } } 注意到我这里的数据有a-k共11个属性，训练集大的话会很慢; } } }.distance。缺点就是进行分类时要扫描所有训练样本得到距离; Sample表示一个样本 var Sample = function (object) { /，最后的平均测试结果可以衡量模型的性能.cell(rIdx, b) { return a.sort(function (a。本文的knn算法就是一种惰性学习法。 / for(var rIdx = 0.j - this，惰性学习法在分类进行时做更多的工作;，可能还有苹果的形状大小等等, c，包含未知类型样本 SampleSet。这些标签让我们看到苹果的时候不会误认为是橘子;/ for(var sIdx = 0.c;node-xlrd'.b, h; } data;1'.samples) { /，由于红色三角形所占比例高，这里的距离就是我们根据样本的特征所计算出来的数值, function(err。那么求距离其实不同情况适合不同的方法。取一份作为测试样本，在此之前只是存储着训练元组。这个过程重复K次; var a = neighbor, err! this.neighbors.message)，这k个几何图形就是未知类型样本的邻居.count;.slice(0;i'.c - this; shtCount。 K倍交叉验证将所有样本分成K份;a'.prototype,'，剩余K-1份作为训练样本;-1'，这里的k即是knn中的k; cIdx++){ item[map[cIdx]] = sht; sIdx <，搜索模式空间，但蠢计算机就不知道怎么做了; }。 /，但却能在很多关键的地方发挥作用并且效果非常好.h - this，绿色的圆代表未知样本。 k-nearest-neighbor-classifier 还是先严谨的介绍下; var e = neighbor，这样每个样本都可以用这些方法.k = k; 读取文件 xls。所以特征就是提取对象的信息.samples[i];/ var g = neighbor; 如果发现没有类型的样本 if ( ，把数据解析后插入到自己的数据结构里;! 还是来通俗的解释下。综上所述knn分类的关键点就是k的选取和距离的计算.samples[i].b - this。扩展到一般情况时，将未知的新元组与训练元组进行对比; 等文件读取完毕后 执行测试 run().g - this.distance = Math; var h = neighbor.prototype，这里就不贴了. 总结 knn算法非常简单;/.5, this.d, this;d'.neighbors.speak Chinese，即可预测样本类型，并生成他们的邻居集; 然后定义一个构造函数Sample表示一个样本，这个红的是苹果等等。 /.xls', k)) { var neighbor = this; this, this.neighbors[i];1'j'.c; var i = neighbor;/ this; var f = neighbor.hasOwnProperty(key)) { this[key] = object[key].samples[j]) )，这是小鸭子。测试结果为用余弦距离等计算方式可能精度会更高, b) { return Math;c'。其实这些标签就对应于机器学习中的特征这一重要概念.guessType(this。 var data = [];/, i.e,bk){ if(err) {console。 balabala了这么多。小时候妈妈会指着各种各样的东西教我们，这对于我们人来说非常简单，泛化就是学习到隐含在这些特征背后的规律, this;;]){ this; } /.sheet; /。急切学习法（eager learner）是在接受待分类的新元组之前就构造了分类模型; rIdx++){ var item = {};/.name，再找出距离未知类型样本最近的K个样本.a - this.js用来读取xls文件的包 var xls = require('-1'.h; / / 将样本加入样本数组 SampleSet. 实现我的数据是一个xls文件。一台iphone戴了一个壳或者屏幕上有一道划痕，那么我去npm搜了一下选了一个叫node-xlrd的包直接拿来用，该方法可以在整个样本集里寻找未知类型的样本; 计算样本间距离 采用欧式距离 Sample; } } /.type) { / 构建总样本数组.guessType = function(k) { /，其实这就叫过度泛化,'f'，那我们哼哧哼哧的看着应答着,', f，所以称为惰性学习法.trueType] += 1; cIdx <，会有点小小的成就感; cCount。我们可以看上图.js技术来实现一下这个机器学习中最简单的算法之一k-nearest-neighbor算法(k最近邻分类法)，急着对未知的元组进行分类.count.i
㈢ KNN算法，结果报错，帮忙怎么改
knn算法(k-Nearest Neighbor algorithm).是一种经典的分类算法.
注意,不是聚类算法.所以这种分类算法必然包括了训练过程.
然而和一般性的分类算法不同,knn算法是一种 懒惰算法 .它并非
像其他的分类算法先通过训练建立分类模型.,而是一种被动的分类
过程.它是边测试边训练建立分类模型.
算法的一般描述过程如下:
1.首先计算每个测试样本点到其他每个点的距离.
这个距离可以是欧氏距离,余弦距离等.
㈣ C语言，编写程序，计算n的k次方，n和k为整数，从键盘输入。分别用do while和for语句实现
1. int n= int.Parse(Console.ReadLine());
int i=1;
int sum=0;
Console.WriteLine("求前n个自然数之和，请输入n的值：");
for(i=1;i<=n;i++)
{
sum+=i;
}
Console.WriteLine("前n个自然数之和为：{0}",sum);
Console.ReadLine();
2. int sum = 0;
int i = 0;
Console.WriteLine("输入自然数n:");
string s = Console.ReadLine();
int n = int.Parse(s);
while (i < n)
{
sum = sum + i;
i++;
}
Console.WriteLine("前{0}个自然数的和为:{1}", n, sum);
Console.Read();
3.int sum = 0;
int i = 0;
Console.WriteLine("输入自然数n:");
string s = Console.ReadLine();
int n = int.Parse(s);
do { sum = sum + i; i++; }
while (i < n);
Console.WriteLine("前{0}个自然数的和为:{1}", n, sum);
Console.Read();
㈤ 卡尔曼滤波 用C语言实现 急！！.......
#include "rinv.c"
缺少rinv.c文件
㈥ KNN数据填补算法
KNN利用数据在各个维度上的相关性对数据中的缺失值或者异常值进行填补和修正
本文中讨论的数据集是来源于分布于某地各站点测得的空气污染物浓度数值随着时间的变化记录，在某些地点或某些时刻存在数据缺失，而我们已知，在该批数据中，测点浓度值在 距离 和 时间 上呈现出相关性，即，空间距离越接近，时间越接近的测量点测得的数值也会越相关，所以可以使用KNN算法从经度、纬度和时间三个维度入手进行数据的处理
在上图中，我们没有获得某时刻目标点处的测量值 ，但我们可以获得其周围若干测量值情况 , , ..., ，这样我们便可使用已有数据对目标值c_x进行估计：
其中权重 与邻点与目标点的距离成反相关，如：
实际使用时可以自行定义权重与距离的关系
在使用KNN算法对数据进行填补时，需要对每条样本寻找其近邻点，所以我们首先需要计算不同样本之间的距离，这里可以使用sklearn.neighbors中的NearestNeighbors来解决
nbrs = NearestNeighbors(n_neighbors, algorithm = 'ball_tree').fit(X)
distances, indices = nbrs.kneighbors(X)
获得了距离矩阵后我们便可以对每个样本寻找其与其他样本的距离，使用前面的公式便可计算出其对应的估计值 这里需要注意，样本距离是指样本在指定的维度上的欧式距离，样本在指定的维度上均满足距离和测量值上的相关性，比如我们可以把样本的经纬度和测量时间作为计算样本距离的维度 ，这样目标点周围那些空间距离越近、测量时间越接近的邻点测量值对目标点估计值 的影响就越大
㈦ KNN计算复杂度是多少，有好的说明资料或者参考文献吗
解决方案1：M，且与类域边界的沿垂直于该超平面方向的距离最大，其归于cj类的类条件概率是P(X/；T2，具有相对优良的性能指标（1）决策树
决
策树归纳是经典的分类算法，…。另外，M，类别总体的概率分布和各类样本的概率分布函数(或密度函数)常常是不知道的，由此构造出的分类器可以最大化类与
类的间隔，Bayes分类方法在理论上论证得比较充分，因此该方法往往在效果上难以达到理论上的最大值，记为C=｛c1;
ci)P(ci)=Maxj［P(x/，这样的条件在实际文本中一般很难满足，而那些样本容量较小的类域采用这种算法比较容易产生误分：
若
P(x/，因为对每一个待分类的文本都要计算它到全体已知样本的距离。因此：D=D(T1，因此对于类域的交叉或重叠较多的待分样本集来说，由
Salton等人于60年代末提出，待分样本的分类结果取决于各类域中样本的全体；…，VSM法相对其他分类方法而言;P(x)(1)
若
P(ci/，…，其包含的每个特征项对于类别的表达能力越弱，Bayes法要求表达文本的主题词相互独立，采用这种方法可以较好地避免样本的不平衡问题：
如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别。为了获得它们，只与极少量的相邻样本有关，则有
x∈ci(2)
式(2)是最大后验概率判决准则，ci，…，只需要计算待分样本和每一个类别向量的相似度即内积。该方法的思路非常简单直观。当需要对一篇待分样本进行分类的时候，2，是一个理论上比较成熟的方法。
设训练样本集分为M类;x)=P(x/。
KNN方法虽然从原理上也依赖于极限定理，故SVM法亦被称为最大边缘(maximum margin)算法，移去或者减少这些样本对分类结果没有影响，事先去除对分类作用不大的样本，则该样本也属于这个类别。当文本被表示为空间向量模型的时候，则x∈ci
这就是常用到的Bayes分类判决准则，Wn)。另外，就要求样本足够大。可以从生成的决策树中提取规则。
Bayes
方法的薄弱环节在于实际情况下，但在类别决策时;X)=MaxjP(cj/，2，可得到cj类的后验概率P(ci/，i=1，而不是靠判别类域的方法来确
定所属类别的，由于KNN方法主要靠周围有限的邻近的样本。当样本集非常大时，由Vapnik等人于1995年提出;ci)，i=1，能降低KNN算法的
计算复杂度。因此，i=1，…，SVM可以自动寻找出那些对分类有较好区分能力的支持向量，则有，…，提高分类的效率，在应用上也是非常广泛的;总样本
数，KNN方法较其他方法更为适合。待分样本集中的大部分样本不是支持向量。目前常用的解决方法是事先对已知样本点进行剪辑。该方法在定类决策上只依据最
邻近的一个或者几个样本的类别来决定待分样本所属的类别。根据研究发现。经过长期的研究。
该算法比较适用于样本容量比较大的类域的自动分类。该方
法只需要由各类域的边界样本的类别来决定最后的分类结果。通过学习算法。它采用自顶向下递归的各个击破方式构造决策树，而该空间向量的建立又很大程度的依
赖于该类别向量中所包含的特征项，文本的相似度就可以借助特征向量之间的内积来表示。
(4) VSM法
VSM法即向量空间模型(Vector Space Model)法。这是最早也是最出名的信息检索方面的数学模型。
由于VSM法中需要事先计算类别的空间向量，SVM法对小样本情况下的自动分类有着较好的分类结果。
(3) SVM法
SVM法即支持向量机(Support Vector Machine)法。
在实际应用中，j=1，M，j=1。另外还有一种Reverse KNN法；Tn;ci)·P(ci)/，因而有较好的适应能力和较高的分准率，W1：
P(ci/，M，然后选取相似度最大的类别作为该待分样本所对应的类别，VSM法一般事先依据语料库中的训练样本和分类体系建立类别向量空间，则根据Bayes定理。
该方法的不足之处是计算量较大，类别中所包含的非零特征项越多，最初由Cover和Hart于1968年提出的。树的每一个结点上使用信息增益度量选择测试属性;X)。
支
持向量机算法的目的在于寻找一个超平面H(d)，…cM}，2，将式(1)代入式(2)。对于一个待分样本X，然后通过计算文本相似度的方法来确定待分样
本的类别，2，2,该超平面可以将训练集中的数据分开。该方法是建立在统计学习理论基础上的机器学习方法，每类的先验概率为P(ci)，W2，…。
(5) Bayes法
Bayes法是一种在已知先验概率与类条件概率的情况下的模式分类方法;cj)P(cj)］，更适合于专业文献的分类，才能求得它的K个最近邻点。
(2) KNN法(K-Nearest Neighbor)
KNN法即K最近邻法，M;X)，可以认为P(ci)=ci类样本数/。其基本思想是将文档表示为加权的特征向量
㈧ K-means 与KNN 聚类算法
K-means 算法属于聚类算法的一种。聚类算法就是把相似的对象通过静态分类方法分成不同的组别或者更多的子集（subset），这样让在同一个子集中的成员对象都有相似的一些属性。聚类算法的任务是将数据集划分为多个集群。在相同集群中的数据彼此会比不同集群的数据相似。通常来说，聚类算法的目标就是通过相似特征将数据分组并分配进不同的集群中。
K-means 聚类算法是一种非监督学习算法，被用于非标签数据（data without defined categories or groups）。该算法使用迭代细化来产生最终结果。算法输入的是集群的数量 K 和数据集。数据集是每个数据点的一组功能。 算法从 Κ 质心的初始估计开始，其可以随机生成或从数据集中随机选择 。然后算法在下面两个步骤之间迭代：
每个质心定义一个集群。在此步骤中，基于平方欧氏距离将每个数据点分配到其最近的质心。更正式一点， ci 属于质心集合 C ，然后每个数据点 x 基于下面的公式被分配到一个集群中。
在此步骤中，重新计算质心。这是通过获取分配给该质心集群的所有数据点的平均值来完成的。公式如下：
K-means 算法在步骤 1 和步骤 2 之间迭代，直到满足停止条件（即，没有数据点改变集群，距离的总和最小化，或者达到一些最大迭代次数）。
上述算法找到特定预选 K 值和数据集标签。为了找到数据中的集群数，用户需要针对一系列 K 值运行 K-means 聚类算法并比较结果。通常，没有用于确定 K 的精确值的方法，但是可以使用以下技术获得准确的估计。
Elbow point 拐点方法
通常用于比较不同 K 值的结果的度量之一是数据点与其聚类质心之间的平均距离。由于增加集群的数量将总是减少到数据点的距离，因此当 K 与数据点的数量相同时，增加 K 将总是减小该度量，达到零的极值。因此，该指标不能用作唯一目标。相反，绘制了作为 K 到质心的平均距离的函数，并且可以使用减小率急剧变化的“拐点”来粗略地确定 K 。
DBI（Davies-Bouldin Index）
DBI 是一种评估度量的聚类算法的指标，通常用于评估 K-means 算法中 k 的取值。简单的理解就是：DBI 是聚类内的距离与聚类外的距离的比值。所以，DBI 的数值越小，表示分散程度越低，聚类效果越好。
还存在许多用于验证 K 的其他技术，包括交叉验证，信息标准，信息理论跳跃方法，轮廓方法和 G 均值算法等等。
需要提前确定 K 的选值或者需尝试很多 K 的取值
数据必须是数字的，可以通过欧氏距离比较
对特殊数据敏感，很容易受特殊数据影响
对初始选择的质心/中心（centers）敏感
之前介绍了 KNN （K 邻近）算法 ，感觉这两个算法的名字很接近，下面做一个简略对比。
K-means ：
聚类算法
用于非监督学习
使用无标签数据
需要训练过程
K-NN ：
分类算法
用于监督学习
使用标签数据
没有明显的训练过程
邻近算法，或者说K最近邻(kNN，k-NearestNeighbor)分类算法是数据挖掘分类技术中最简单的方法之一。所谓K最近邻，就是k个最近的邻居的意思，说的是每个样本都可以用它最接近的k个邻居来代表。Cover和Hart在1968年提出了最初的邻近算法。KNN是一种分类(classification)算法，它输入基于实例的学习（instance-based learning），属于懒惰学习（lazy learning）即KNN没有显式的学习过程，也就是说没有训练阶段，数据集事先已有了分类和特征值，待收到新样本后直接进行处理。与急切学习（eager learning）相对应。
KNN是通过测量不同特征值之间的距离进行分类。
思路是：如果一个样本在特征空间中的k个最邻近的样本中的大多数属于某一个类别，则该样本也划分为这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。
提到KNN，网上最常见的就是下面这个图，可以帮助大家理解。
我们要确定绿点属于哪个颜色（红色或者蓝色），要做的就是选出距离目标点距离最近的k个点，看这k个点的大多数颜色是什么颜色。当k取3的时候，我们可以看出距离最近的三个，分别是红色、红色、蓝色，因此得到目标点为红色。
算法的描述：
1）计算测试数据与各个训练数据之间的距离；
2）按照距离的递增关系进行排序；
3）选取距离最小的K个点；
4）确定前K个点所在类别的出现频率；
5）返回前K个点中出现频率最高的类别作为测试数据的预测分类
二、关于 K 的取值
K：临近数，即在预测目标点时取几个临近的点来预测。
K值得选取非常重要，因为：
如果当K的取值过小时，一旦有噪声得成分存在们将会对预测产生比较大影响，例如取K值为1时，一旦最近的一个点是噪声，那么就会出现偏差，K值的减小就意味着整体模型变得复杂，容易发生过拟合；
如果K的值取的过大时，就相当于用较大邻域中的训练实例进行预测，学习的近似误差会增大。这时与输入目标点较远实例也会对预测起作用，使预测发生错误。K值的增大就意味着整体的模型变得简单；
如果K==N的时候，那么就是取全部的实例，即为取实例中某分类下最多的点，就对预测没有什么实际的意义了；
K的取值尽量要取奇数，以保证在计算结果最后会产生一个较多的类别，如果取偶数可能会产生相等的情况，不利于预测。
K的取法：
常用的方法是从k=1开始，使用检验集估计分类器的误差率。重复该过程，每次K增值1，允许增加一个近邻。选取产生最小误差率的K。
一般k的取值不超过20，上限是n的开方，随着数据集的增大，K的值也要增大。
三、关于距离的选取
距离就是平面上两个点的直线距离
关于距离的度量方法，常用的有：欧几里得距离、余弦值（cos）, 相关度 （correlation）, 曼哈顿距离 （Manhattan distance）或其他。
Euclidean Distance 定义：
两个点或元组P1=（x1，y1）和P2=（x2，y2）的欧几里得距离是
距离公式为：（多个维度的时候是多个维度各自求差）
四、总结
KNN算法是最简单有效的分类算法，简单且容易实现。当训练数据集很大时，需要大量的存储空间，而且需要计算待测样本和训练数据集中所有样本的距离，所以非常耗时
KNN对于随机分布的数据集分类效果较差，对于类内间距小，类间间距大的数据集分类效果好，而且对于边界不规则的数据效果好于线性分类器。
KNN对于样本不均衡的数据效果不好，需要进行改进。改进的方法时对k个近邻数据赋予权重，比如距离测试样本越近，权重越大。
KNN很耗时，时间复杂度为O(n)，一般适用于样本数较少的数据集，当数据量大时，可以将数据以树的形式呈现，能提高速度，常用的有kd-tree和ball-tree。
㈨ KNN算法常见问题总结
给定测试实例，基于某种距离度量找出训练集中与其最靠近的k个实例点，然后基于这k个最近邻的信息来进行预测。
通常，在分类任务中可使用“投票法”，即选择这k个实例中出现最多的标记类别作为预测结果；在回归任务中可使用“平均法”，即将这k个实例的实值输出标记的平均值作为预测结果；还可基于距离远近进行加权平均或加权投票，距离越近的实例权重越大。
k近邻法不具有显式的学习过程，事实上，它是懒惰学习（lazy learning）的着名代表，此类学习技术在训练阶段仅仅是把样本保存起来，训练时间开销为零，待收到测试样本后再进行处理。
KNN一般采用欧氏距离，也可采用其他距离度量，一般的Lp距离：
KNN中的K值选取对K近邻算法的结果会产生重大影响。如果选择较小的K值，就相当于用较小的领域中的训练实例进行预测，“学习”近似误差（近似误差：可以理解为对现有训练集的训练误差）会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是“学习”的估计误差会增大，换句话说，K值的减小就意味着整体模型变得复杂，容易发生过拟合；
如果选择较大的K值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少学习的估计误差，但缺点是学习的近似误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，且K值的增大就意味着整体的模型变得简单。
在实际应用中，K值一般取一个比较小的数值，例如采用交叉验证法来选择最优的K值。经验规则：k一般低于训练样本数的平方根
1、计算测试对象到训练集中每个对象的距离
2、按照距离的远近排序
3、选取与当前测试对象最近的k的训练对象，作为该测试对象的邻居
4、统计这k个邻居的类别频率
5、k个邻居里频率最高的类别，即为测试对象的类别
输入X可以采用BallTree或KDTree两种数据结构，优化计算效率，可以在实例化KNeighborsClassifier的时候指定。
KDTree
基本思想是，若A点距离B点非常远，B点距离C点非常近， 可知A点与C点很遥远，不需要明确计算它们的距离。 通过这样的方式，近邻搜索的计算成本可以降低为O[DNlog(N)]或更低。 这是对于暴力搜索在大样本数N中表现的显着改善。KD 树的构造非常快，对于低维度 (D<20) 近邻搜索也非常快, 当D增长到很大时，效率变低： 这就是所谓的 “维度灾难” 的一种体现。
KD 树是一个二叉树结构，它沿着数据轴递归地划分参数空间，将其划分为嵌入数据点的嵌套的各向异性区域。 KD 树的构造非常快：因为只需沿数据轴执行分区, 无需计算D-dimensional 距离。 一旦构建完成, 查询点的最近邻距离计算复杂度仅为O[log(N)]。 虽然 KD 树的方法对于低维度 (D<20) 近邻搜索非常快, 当D增长到很大时, 效率变低。
KD树的特性适合使用欧氏距离。
BallTree
BallTree解决了KDTree在高维上效率低下的问题，这种方法构建的树要比 KD 树消耗更多的时间，但是这种数据结构对于高结构化的数据是非常有效的， 即使在高维度上也是一样。
KD树是依次对K维坐标轴，以中值切分构造的树；ball tree 是以质心C和半径r分割样本空间，每一个节点是一个超球体。换句简单的话来说，对于目标空间(q, r)，所有被该超球体截断的子超球体内的所有子空间都将被遍历搜索。
BallTree通过使用三角不等式减少近邻搜索的候选点数:|x+y|<=|x|+|y|通过这种设置, 测试点和质心之间的单一距离计算足以确定距节点内所有点的距离的下限和上限. 由于 ball 树节点的球形几何, 它在高维度上的性能超出 KD-tree, 尽管实际的性能高度依赖于训练数据的结构。
BallTree适用于更一般的距离。
1、优点
非常简单的分类算法没有之一，人性化，易于理解，易于实现
适合处理多分类问题，比如推荐用户
可用于数值型数据和离散型数据，既可以用来做分类也可以用来做回归
对异常值不敏感
2、缺点
属于懒惰算法，时间复杂度较高，因为需要计算未知样本到所有已知样本的距离
样本平衡度依赖高，当出现极端情况样本不平衡时，分类绝对会出现偏差，可以调整样本权值改善
可解释性差，无法给出类似决策树那样的规则
向量的维度越高，欧式距离的区分能力就越弱
样本空间太大不适合，因为计算量太大，预测缓慢
文本分类
用户推荐
回归问题
1）所有的观测实例中随机抽取出k个观测点，作为聚类中心点，然后遍历其余的观测点找到距离各自最近的聚类中心点，将其加入到该聚类中。这样，我们就有了一个初始的聚类结果，这是一次迭代的过程。
2）我们每个聚类中心都至少有一个观测实例，这样，我们可以求出每个聚类的中心点（means），作为新的聚类中心，然后再遍历所有的观测点，找到距离其最近的中心点，加入到该聚类中。然后继续运行2）。
3）如此往复2），直到前后两次迭代得到的聚类中心点一模一样。
本算法的时间复杂度：O(tkmn)，其中，t为迭代次数，k为簇的数目，m为记录数，n为维数；
空间复杂度：O((m+k)n)，其中，k为簇的数目，m为记录数，n为维数。
适用范围：
K-menas算法试图找到使平凡误差准则函数最小的簇。当潜在的簇形状是凸面的，簇与簇之间区别较明显，且簇大小相近时，其聚类结果较理想。前面提到，该算法时间复杂度为O(tkmn)，与样本数量线性相关，所以，对于处理大数据集合，该算法非常高效，且伸缩性较好。但该算法除了要事先确定簇数K和对初始聚类中心敏感外，经常以局部最优结束，同时对“噪声”和孤立点敏感，并且该方法不适于发现非凸面形状的簇或大小差别很大的簇。
1）首先，算法只能找到局部最优的聚类，而不是全局最优的聚类。而且算法的结果非常依赖于初始随机选择的聚类中心的位置。我们通过多次运行算法，使用不同的随机生成的聚类中心点运行算法，然后对各自结果C通过evaluate(C)函数进行评估，选择多次结果中evaluate(C)值最小的那一个。k-means++算法选择初始seeds的基本思想就是：初始的聚类中心之间的相互距离要尽可能的远
2）关于初始k值选择的问题。首先的想法是，从一个起始值开始，到一个最大值，每一个值运行k-means算法聚类，通过一个评价函数计算出最好的一次聚类结果，这个k就是最优的k。我们首先想到了上面用到的evaluate(C)。然而，k越大，聚类中心越多，显然每个观测点距离其中心的距离的平方和会越小，这在实践中也得到了验证。第四节中的实验结果分析中将详细讨论这个问题。
3）关于性能问题。原始的算法，每一次迭代都要计算每一个观测点与所有聚类中心的距离。有没有方法能够提高效率呢？是有的，可以使用k-d tree或者ball tree这种数据结构来提高算法的效率。特定条件下，对于一定区域内的观测点，无需遍历每一个观测点，就可以把这个区域内所有的点放到距离最近的一个聚类中去。这将在第三节中详细地介绍。
相似点：都包含这样的过程，给定一个点，在数据集中找离它最近的点。即二者都用到了NN(Nears Neighbor)算法，一般用KD树来实现NN。
k-d tree 与 ball tree
1）k-d tree[5]
把n维特征的观测实例放到n维空间中，k-d tree每次通过某种算法选择一个特征(坐标轴)，以它的某一个值作为分界做超平面，把当前所有观测点分为两部分，然后对每一个部分使用同样的方法，直到达到某个条件为止。
上面的表述中，有几个地方下面将会详细说明：（1）选择特征（坐标轴）的方法 （2）以该特征的哪一个为界 （3）达到什么条件算法结束。
(1)选择特征的方法
计算当前观测点集合中每个特征的方差，选择方差最大的一个特征，然后画一个垂直于这个特征的超平面将所有观测点分为两个集合。
（2)以该特征的哪一个值为界 即垂直选择坐标轴的超平面的具体位置。
第一种是以各个点的方差的中值（median）为界。这样会使建好的树非常地平衡，会均匀地分开一个集合。这样做的问题是，如果点的分布非常不好地偏斜的，选择中值会造成连续相同方向的分割，形成细长的超矩形(hyperrectangles)。
替代的方法是计算这些点该坐标轴的平均值，选择距离这个平均值最近的点作为超平面与这个坐标轴的交点。这样这个树不会完美地平衡，但区域会倾向于正方地被划分，连续的分割更有可能在不同方向上发生。
（3）达到什么条件算法结束
实际中，不用指导叶子结点只包含两个点时才结束算法。你可以设定一个预先设定的最小值，当这个最小值达到时结束算法。
图6中，星号标注的是目标点，我们在k-d tree中找到这个点所处的区域后，依次计算此区域包含的点的距离，找出最近的一个点（黑色点），如果在其他region中还包含更近的点则一定在以这两个点为半径的圆中。假设这个圆如图中所示包含其他区域。先看这个区域兄弟结点对应区域，与圆不重叠；再看其双亲结点的兄弟结点对应区域。从它的子结点对应区域中寻找（图中确实与这个双亲结点的兄弟结点的子结点对应区域重叠了）。在其中找是否有更近的结点。
k-d tree的优势是可以递增更新。新的观测点可以不断地加入进来。找到新观测点应该在的区域，如果它是空的，就把它添加进去，否则，沿着最长的边分割这个区域来保持接近正方形的性质。这样会破坏树的平衡性，同时让区域不利于找最近邻。我们可以当树的深度到达一定值时重建这棵树。
然而，k-d tree也有问题。矩形并不是用到这里最好的方式。偏斜的数据集会造成我们想要保持树的平衡与保持区域的正方形特性的冲突。另外，矩形甚至是正方形并不是用在这里最完美的形状，由于它的角。如果图6中的圆再大一些，即黑点距离目标点点再远一些，圆就会与左上角的矩形相交，需要多检查一个区域的点，而且那个区域是当前区域双亲结点的兄弟结点的子结点。
为了解决上面的问题，我们引入了ball tree。
2）ball tree[4]
解决上面问题的方案就是使用超球面而不是超矩形划分区域。使用球面可能会造成球面间的重叠，但却没有关系。ball tree就是一个k维超球面来覆盖这些观测点，把它们放到树里面。图7（a)显示了一个2维平面包含16个观测实例的图,图7（b）是其对应的ball tree，其中结点中的数字表示包含的观测点数。
不同层次的圆被用不同的风格画出。树中的每个结点对应一个圆，结点的数字表示该区域保含的观测点数，但不一定就是图中该区域囊括的点数，因为有重叠的情况，并且一个观测点只能属于一个区域。实际的ball tree的结点保存圆心和半径。叶子结点保存它包含的观测点。
使用ball tree时，先自上而下找到包含target的叶子结点，从此结点中找到离它最近的观测点。这个距离就是最近邻的距离的上界。检查它的兄弟结点中是否包含比这个上界更小的观测点。方法是：如果目标点距离兄弟结点的圆心的距离大于这个圆的圆心加上前面的上界的值，则这个兄弟结点不可能包含所要的观测点。（如图8）否则，检查这个兄弟结点是否包含符合条件的观测点。
那么，ball tree的分割算法是什么呢？
选择一个距离当前圆心最远的观测点i1，和距离i1最远的观测点 i2，将圆中所有离这两个点最近的观测点都赋给这两个簇的中心，然后计算每一个簇的中心点和包含所有其所属观测点的最小半径。对包含n个观测点的超圆进行分割，只需要线性的时间。
与k-d tree一样，如果结点包含的观测点到达了预先设定的最小值，这个顶点就可以不再分割了。