算法1：k近邻法

复杂度：O(n)

算法2：构造平衡kd树

算法3：搜索kd树

复杂度:O(log(n))

当空间维数接近训练实例数时，他的效率会迅速下降，几乎接近线性扫描

 

python代码实现k近邻法：

# # k近邻算法
步骤：
1.导入数据
2.分割数据(用于交叉验证)
3.k近邻算法
4.模型评估


# ### 一、导入数据
# 从sklearn.datasets 导入 iris数据加载器。
from sklearn.datasets import load_iris
# 使用加载器读取数据并且存入变量iris。
iris = load_iris()
# 查验数据规模。
iris.data.shape
# 查看数据说明。对于一名机器学习的实践者来讲，这是一个好习惯。
print (iris.DESCR)


### 二、分割数据
# 从sklearn.model_selection里选择导入train_test_split用于数据分割。
from sklearn.model_selection import train_test_split
# 从使用train_test_split，利用随机种子random_state采样25%的数据作为测试集。
X_train, X_test, y_train, y_test = train_test_split(iris.data, iris.target, test_size=0.25, random_state=33)
X_train.shape


### 三、k近邻算法
# 从sklearn.preprocessing里选择导入数据标准化模块。
from sklearn.preprocessing import StandardScaler
# 从sklearn.neighbors里选择导入KNeighborsClassifier，即K近邻分类器。
from sklearn.neighbors import KNeighborsClassifier

# 对训练和测试的特征数据进行标准化。
ss = StandardScaler()
X_train = ss.fit_transform(X_train) 
X_test = ss.transform(X_test)#没有.fit 说明用的还是训练集的均值与标准差

# 使用K近邻分类器对测试数据进行类别预测，预测结果储存在变量y_predict中。
knc = KNeighborsClassifier()
knc.fit(X_train, y_train)
y_predict = knc.predict(X_test)


# ### 四、模型评估
# 使用模型自带的评估函数进行正确性测评。
print ('The accuracy of K-Nearest Neighbor Classifier is', knc.score(X_test, y_test) )
# 依然使用sklearn.metrics里面的classification_report模块对预测结果做更加详细的分析。
from sklearn.metrics import classification_report
print (classification_report(y_test, y_predict, target_names=iris.target_names))