python机器学习_监督学习算法之KNN分类算法

KNN的英文全称叫K-Nearest Neighbor，中文名称为K最近邻算法，它是由Cover和Hart在1968年提出来的。

相似性的度量：

相似性一般用空间内两个点的距离来度量。距离越大，表示两个越不相似。

KNN算法原理：

1. 计算已知类别数据集中的点与当前点之间的距离；

2. 按照距离递增次序排序；

3. 选择与当前距离最小的k个点；

4. 确定前k个点所在类别的出现概率；

5. 返回前k个点出现频率最高的类别作为当前点的预测分类。

电影分类：

KNN算法归纳：

（1）KNN属于惰性学习（lazy-learning）

（2）KNN的计算复杂度较高

（3）k取不同值时，分类结果可能会有显著不同

KNN算法应用说明：

按距离加权的k-近邻算法是一种非常有效的归纳推理方法。它对训练数据中的噪声有很好的鲁棒性，而 且当给定足够大的训练集合时它也非常有效。注意通过取k个近邻的加权平均，可以消除孤立的噪声样例的影

响。

问题一：近邻间的距离会被大量的不相关属性所支配。

解决方法：当计算两个实例间的距离时对每个属性加权。 

问题二：应用k-近邻算法的另外一个实践问题是如何建立高效的索引。因为这个算法推迟所有的处理，直

到接收到一个新的查询，所以处理每个新查询可能需要大量的计算。 

解决方法：目前已经开发了很多方法用来对存储的训练样例进行索引，以便在增加一定存储开销情况下 更高效地确定最近邻。一种索引方法是kd-tree（Bentley 1975；Friedman et al. 1977），它把实例存 储在树的叶结点内，邻近的实例存储在同一个或附近的结点内。通过测试新查询xq的选定属性，树的内 部结点把查询xq排列到相关的叶结点。

KNN算法归纳：

(1)  在各分类样本数量不平衡时误差较大；

(2)  由于其每次比较都要遍历整个训练样本集来计算相似度，所以分类的效率较低，时间和空间的复杂度较高；

(3)  k值的选择不合理，可能导致结果的误差较大；

示例1：KNN算法实现电影分类

import  pandas as pd
import  numpy as np

from sklearn.neighbors import KNeighborsClassifier

def build_data():
    # 加载数据
    data = pd.read_excel("./电影分类数据.xlsx")
    # print("data:\n",data)
    # print("data的列名称：\n",data.columns)
    # print("data的形状：\n",data.shape)

    # 获取训练集的特征与目标值
    train_data = data.iloc[:,1:6]

    # print("train_data:\n",train_data)

    #获取测试集数据
    test_data = data.columns[-4:]
    # print("test_data:\n",test_data)

    return  train_data,test_data

# def distance(v1,v2):
#     """
#     计算距离
#     :param v1:点1
#     :param v2: 点2
#     :return: 距离
#     """
#     dist = np.sqrt(np.sum(np.power((v1-v2),2)))
#
#     return dist
#
#
# def knn_owns(train_data, test_data,k):
#     """
#     自实现knn算法
#     :param train_data: 训练集
#     :param test_data: 测试集
#     :param k: 邻居个数
#     :return: 属于类别
#     """
#     # 训练集的行数
#     index_num = train_data.shape[0]
#
#     # 训练集特征值
#     train_x = train_data.iloc[:,1:-1]
#
#     # print(train_x)
#     # 训练集目标值
#     train_y = train_data.iloc[:,-1]
#
#     # 获取测试集的特征值
#     test_x = test_data[1:]
#     # 1、循环计算测试集与每一个训练样本的距离
#     for i in range(index_num):
#         # pass
#         # 计算距离
#         train_data.loc[i,'dist'] = distance(train_x.iloc[i,:],test_x)
#
#     # print(train_data)
#
#     # 接下来按照dist 进行从小到大排序
#     res_data = train_data.sort_values(by='dist')['电影类型'][:k]
#
#     res = res_data.mode()
#
#     # print(res)
#
#     return  res.values




def main():
    """
    主函数
    :return:
    """
    # 1、构建数据
    train_data, test_data = build_data()

    print("train_data:\n", train_data)
    print("test_data:\n", test_data)


    train_data.loc[train_data.loc[:,'电影类型'] == '喜剧片','电影类型'] = 0
    train_data.loc[train_data.loc[:,'电影类型'] == '动作片','电影类型'] = 1
    train_data.loc[train_data.loc[:,'电影类型'] == '爱情片','电影类型'] = 2


    # print(train_data.dtypes)

    train_data['电影类型'] = train_data['电影类型'].astype('float')

    # 2、# 自实现knn算法
    # 需要按照最近的几个邻居进行预测
    k = 5

    # res = knn_owns(train_data, test_data,k)

    # print("唐人街探案属于",res,"类型")




    # 使用sklearn默认的模块实现电影分类

    # # 创建实例
    # knn = KNeighborsClassifier(n_neighbors=k)
    #
    # # 训练数据--- 训练集里面的x,y
    # # y 也是0  1 2 3 之类的标号
    # # 获取训练集的特征值 与目标值
    # train_x = train_data.iloc[:,1:-1]
    # train_y = train_data.iloc[:,-1]
    #
    # print(type(train_y))
    # knn.fit(train_x.values,train_y.values)
    #
    # # 用测试集的特征值来进行预测 (3,)
    # y_predict = knn.predict([test_data[1:]])
    #
    # print(y_predict)






if __name__ == '__main__':
    main()



           

示例2：KNN算法手写字识别案例

import  pandas as pd
import  numpy as np
import  os
import  matplotlib.pyplot as plt

from  sklearn.neighbors import  KNeighborsClassifier


# 循环读取每一个 文件里面的内容
# print(os.listdir("./trainingDigits"))

def build_data(file_path):
    """
    实现数据转化
    :param file_path: 文件路径
    :return: 数据
    """
    # 1、得到要读取的文件名称
    file_name_list = os.listdir(file_path)

    # print(file_name_list)

    # 定义一个大的二维数组
    arr =np.zeros(shape=(len(file_name_list),1025))

    # 2、拼接路径+ 名称

    for i,tmp in enumerate(file_name_list):

        file_name = file_path + "/" + tmp

        # print(file_name)

        # 加载文件内容---默认是float，需要将这一个元素拆分成32个元素
        file_data = np.loadtxt(file_name,dtype=np.str)

        arr_file_content =[]

        for file_num,file_content  in enumerate(file_data):

            # print(file_num,file_content)

            # 将 file_content 转化为  数值类型
            # 法1
            list_file_content =[int(i) for i in file_content]

            # 法2
            # a = [j for j in map(int,file_content)]

            # print(a)

            # print(file_data)
            #
            # print(file_data.dtype)

            # 加进去
            arr_file_content.append(list_file_content)

        arr_file_content = np.array(arr_file_content)

        # print(arr_file_content)
        # print(arr_file_content.shape)

        # 将arr_file_content 进行展开成一行
        arr_file_content_ravel = arr_file_content.ravel()

        # print(arr_file_content_ravel)

        # print(arr_file_content_ravel.shape)
        # 找目标值
        x = tmp[0]

        # print(x)

        arr[i,:-1] = arr_file_content_ravel

        arr[i,-1] = x

        # print("*"*80)
    # print(arr)

    return arr

#
def  save_data(file_data,file_name):
    """
    保存文件
    :param file_name: 文件路径+ 名称
    :return: None
    """
    if not os.path.exists("./data/"):
        os.makedirs("./data/")

    # print(file_name)
    np.save("./data/"+ file_name ,file_data)

def distance(v1,v2):
    """
    距离计算
    :param v1:点1
    :param v2: 点2
    :return: 距离
    """
    dist = np.sqrt(np.sum(np.power((v1-v2),2)))

    return  dist


def knn_owns(train_data,test_data,k):
    """
    自实现knn模型实现手写字预测
    :param train_data: 训练集数据
    :param test_data: 测试集数据
    :param k: 邻居个数
    :return: 模型的准确率
    """
    # 获取训练集的特征值 、测试集的特征值
    x_train = train_data[:,:-1]



    x_test = test_data[:,:-1]

    # 定义一个记录正确预测的数量
    true_num = 0

    # 计算每一个测试集与每一个训练集的距离
    # 外面是测试集、里面是训练集
    for i in range(x_test.shape[0]):# 每一个测试集的样本的行索引

        # 定义一个临时数组
        arr = np.zeros(shape=(x_train.shape[0],1))
        for j in range(x_train.shape[0]):# 每一个训练集的样本的行索引

            #计算每一个测试样本与训练集的距离
            dist = distance(x_test[i,:],x_train[j,:])

            arr[j,0] = dist

        # 将距离与train_data 拼成一个完整的数组
        arr_mutile = np.concatenate((train_data,arr),axis=1)

        # 第一列数据 个第二列数据对不上的，不能使用数组排序
        # 先转化为df
        df_arr_mutile = pd.DataFrame(arr_mutile[:,-2:],columns=['目标','距离'])


        # 进行按照距离排序,获取前k个邻居的众数 就是我们预测的类别
        mo = df_arr_mutile.sort_values(by='距离')['目标'][:k].mode()[0]

        # print(mo)

        # 拿测试集里面 每一个样本的真实的目标值
        y_true = test_data[i,-1]
        # print(y_true)

        if mo == y_true :
            true_num += 1


        # print("*"*80)

    # 计算准确率

    score = true_num /test_data.shape[0]

    # print(score)
    return  score




def show_res(k_arr,score_list):
    """
    结果展示
    :param k_arr: 不同K值
    :param score_list: 不同的score
    :return: None
    """
    # 创建画布
    plt.figure()

    # 默认不支持中文，需要配置RC参数
    plt.rcParams['font.sans-serif'] = 'SimHei'
    # 默认不支持负号，需要配置RC参数
    plt.rcParams['axes.unicode_minus'] = False

    # 绘图
    plt.plot(k_arr,score_list,markersize=12,marker="*")

    #增加标题
    plt.title("准确率与K值关系走势图")

    # 增加轴名称
    plt.xlabel("K")
    plt.ylabel("score")

    # 保存
    plt.savefig("./准确率与K值关系.png")

    # 图形展示
    plt.show()







def main():
    """
    主函数
    :return:
    """
    # 构建数据
    # arr_train = build_data("./trainingDigits")
    # arr_test = build_data("./testDigits")

    # print(arr_train)
    # print(arr_train.shape)
    # print("*"*80)
    # print(arr_test)
    # print(arr_test.shape)
    #
    #
    # # 保存文件
    # save_data(arr_train,"arr_train")
    # save_data(arr_test,"arr_test")

    # 加载数据

    train_data = np.load("./data/arr_train.npy")
    test_data = np.load("./data/arr_test.npy")

    print("train_data:\n",train_data)
    print("*"*80)
    print("test_data:\n",test_data)

    # 定义knn算法模型进行预测

    # 确定邻居个数
    k_arr = np.arange(5,11)
    # score_list = []
    # for k in k_arr:
    #     score = knn_owns(train_data,test_data,k)
    #     score_list.append(score)
    #
    # print(score_list)


    # s使用sklearn自带模块实现

    y_predict_list = []

    score_list =[]
    for k in k_arr:
        # 创建实例
        knn = KNeighborsClassifier(n_neighbors=k)
        # 训练数据
        knn.fit(train_data[:,:-1],train_data[:,-1])

        # 预测数据
        y_predict = knn.predict(test_data[:,:-1])

        y_predict_list.append(y_predict)
        # 获取准确率
        score = knn.score(test_data[:,:-1],test_data[:,-1])

        score_list.append(score)

    # 按照k  - score 的关系，绘制走势图
    show_res(k_arr,score_list)

    #转化为数组
    y_predict_arr = np.array(y_predict_list)
    score_arr = np.array(score_list)


    print("y_predict_arr：\n",y_predict_arr)

    print("score_arr:\n",score_arr)




if __name__ == '__main__':
    main()