草庐IT

数据挖掘——KNN算法的实现

君临๑ 2023-07-01 原文

👨‍💻作者简介：练习时长两年半的java博主

📖个人主页：君临๑

🎁 ps：点赞是免费的，却可以让写博客的作者开心好几天😎

文章目录

一、k-最近邻分类算法介绍

二、k-NN的特点

三、KNN算法的伪代码

四、KNN算法的python实现

一、k-最近邻分类算法介绍

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

如图1所示，有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是待分类的数据。也就是说，现在， 我们不知道中间那个绿色的数据是从属于哪一类（蓝色小正方形or红色小三角形），下面，我们就要解决这个问题：给这个绿色的圆分类。

 ​

                      图一 

我们常说，物以类聚，人以群分，判别一个人是一个什么样品质特征的人，常常可以从他/她身边的朋友入手，所谓观其友，而识其人。我们不是要判别图1中那个绿色的圆是属于哪一类数据么，好说，从它的邻居下手。但一次性看多少个邻居呢？从图1中，你还能看到：

  • 如果K=3，绿色圆点的最近的3个邻居是2个红色小三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。

  • 如果K=5，绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。

于此我们看到，当无法判定当前待分类点是从属于已知分类中的哪一类时，我们可以依据统计学的理论看它所处的位置特征，衡量它周围邻居的权重，而把它归为(或分配)到权重更大的那一类。这就是K近邻算法的核心思想。

步骤：

1:令k是最近邻数目，D是训练样例的集合

2: for每个测试样例z=(x ',y) do


3:计算z和每个样例(x,y) ∈ D之间的距离d(x ', x)

4:选择离z最近的k个训练样例的集合Dz包含于D

5.

​

 6:end for

  •  距离加权表决

​

  •  其中，v是类标号，yi是一个最近邻的类标号。1()为指示函数，其中参数为真，返回值为1，否则为0


​

二、k-NN的特点
 

（一）是一种基于实例的学习

  • 需要一个邻近性度量来确定实例间的相似性或距离

（二）不需要建立模型，但分类一个测试样例开销很大

  • 需要计算与所有训练实例之间的距离

（三）基于局部信息进行预测，对噪声非常敏感

（四）最近邻分类器可以生成任意形状的决策边界

  • 决策树和基于规则的分类器通常是直线决策边界

（五）需要适当的邻近性度量和数据预处理

  • 防止邻近性度量被某个属性左右

（六）k值的选择:

  • 如果k太小,则对噪声点敏感
  • 如果k太大,邻域可能包含很多其他类的点

（七）定标问题（规范化)

  • 属性可能需要规范化，防止距离度量被具有很大值域的属性所左右

三、KNN算法的伪代码

输入参数:k值、trainingSamples（训练数据集，M*N矩阵，M为样本数，N为属性数)、trainingLabels (训练数据集的分类标签0、1、2...，M*1矩阵） , testingSample（测试数据，1*N矩阵)
输出参数: class（测试数据对应类别标签)

算法流程:
1、得到训练数据集trainingSamples的大小M，N
2、初始化Distance数组(M*1)，用来存储每个训练样本与测试样本的距离。

3、对每一个训练样本trainingSamples(i,:)【 for i in range(M)】，计算其与测试样本testingSample之间的距离，存储在Distance[i]中
4、对Distance数组排升序【argsort函数】
5、取得排序前K个距离对应的序号，将序号对应的训练数据的分类标签得到赋给labs
6、得到labs数组的不重复元素，存储在数组All_labs 【unique函数】

7、得到不重复元素（数组All_labs )的个数LabNum
8、( for i in range(LabNum)）对每一个不重复的分类标签All_labs[i]，查找最近的k个类别标签labs中，等于All_labs[i]的有几个，将该数目作为第i类的投票数Vote[i]

9、求投票数Vote[i]的最大值所在的索引ind
10、All_labs[ind]是最大投票数对应的类别标签，即为算法输出结果class


四、KNN算法的python实现

KNN_Classify_E:

import numpy as np
import math
def KNN_Classify_E(trainingSamples,trainingLabels,testingSample,k):
    M=trainingSamples.shape[0]
    N=trainingSamples.shape[1]
    Distance=np.zeros((M,1))
    for i in range(M):
        training = trainingSamples[i,:]
        Distance[i] = dist_E(training, testingSample)
    ind=np.argsort(Distance,axis=0)#axis=0 指明在列的方向排序
    labs = trainingLabels[ind[:k]]
    labs = np.array(labs)
    All_labs = np.unique(labs) # labs 要从mat转为array,否则unique返回结果有问题
    LabNum = All_labs.size;
    Vote = np.zeros((LabNum, 1))
    for i in range(LabNum):
        vect = labs[labs == All_labs[i]]
        Vote[i] = vect.size
    ind = Vote.argmax(0) #默认
    c = All_labs[ind]
    return c

def dist_E(vect1,vect2):
    dist = -1
    if (vect1.size != vect2.size):
        print('length of input vectors must agree')
    else:
        t = np.multiply((vect1 - vect2), (vect1 - vect2))
        dist = math.sqrt(t.sum())
    return dist

TestE:

import numpy as np
from KNN_Classify_E import *


def classify_data(Tr_file_path, Tst_file_path):
    Tr = np.loadtxt(Tr_file_path, delimiter=",", dtype="double")
    Tst = np.loadtxt(Tst_file_path, delimiter=",", dtype="double")

    Tr = np.mat(Tr)
    Tst = np.mat(Tst)

    trAttr = Tr[:, :-1]
    trLabels = Tr[:, -1]
    tstAttr = Tst[:, :-1]
    tstLabels = Tst[:, -1]

    trAttr=normalize(trAttr)
    tstAttr=normalize(tstAttr)

    k = 3
    
    predictlabel = np.zeros((tstLabels.size, 1))
    for i in range(tstLabels.size):
        predictlabel[i, 0] = KNN_Classify_E(trAttr, trLabels, tstAttr[i, :], k)

    predict_right = predictlabel[predictlabel == tstLabels]
    acc = predict_right.size / predictlabel.size
    return acc


def normalize2(Samples):
    meanValue = np.mean(Samples, axis=0)
    stdValue = np.std(Samples, axis=0)
    Samples2 = (Samples - meanValue)/stdValue
    return  Samples2

def normalize(Samples):
    Samples = np.mat(Samples)
    M = Samples.shape[0]
    N = Samples.shape[1]
    Samples2 = np.mat(np.zeros((M, N)))
    for i in range(N):
        allAtr = Samples[:, i]
        STD = allAtr.std()
        MEAN = allAtr.mean()
        x = (allAtr - MEAN) / STD;
        Samples2[:, i] = x
    return Samples2


if __name__ == "__main__":
    Tr_file_path = '0data/diabets_Tr.csv'
    Tst_file_path = '0data/diabets_Tst.csv'
    acc = classify_data(Tr_file_path, Tst_file_path)
    print(acc)

diabets_Tr:(训练数据)

​

 diabets_Tst:(测试数据)

 ​

mdash挖掘xffxff0cxff0算法数据挖掘机器学习python

有关数据挖掘——KNN算法的实现的更多相关文章

  1. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  2. ruby - 如何根据特征实现 FactoryGirl 的条件行为 - 2

    我有一个用户工厂。我希望默认情况下确认用户。但是鉴于unconfirmed特征，我不希望它们被确认。虽然我有一个基于实现细节而不是抽象的工作实现，但我想知道如何正确地做到这一点。factory:userdoafter(:create)do|user,evaluator|#unwantedimplementationdetailshereunlessFactoryGirl.factories[:user].defined_traits.map(&:name).include?(:unconfirmed)user.confirm!endendtrait:unconfirmeddoenden

  3. ruby - Ruby 有 `Pair` 数据类型吗？ - 2

    有时我需要处理键/值数据。我不喜欢使用数组，因为它们在大小上没有限制(很容易不小心添加超过2个项目，而且您最终需要稍后验证大小)。此外，0和1的索引变成了魔数(MagicNumber)，并且在传达含义方面做得很差(“当我说0时，我的意思是head...”)。散列也不合适，因为可能会不小心添加额外的条目。我写了下面的类来解决这个问题:classPairattr_accessor:head,:taildefinitialize(h,t)@head,@tail=h,tendend它工作得很好并且解决了问题，但我很想知道:Ruby标准库是否已经带有这样一个类？ 最佳

  4. ruby - 我如何添加二进制数据来遏制 POST - 2

    我正在尝试使用Curbgem执行以下POST以解析云curl-XPOST\-H"X-Parse-Application-Id:PARSE_APP_ID"\-H"X-Parse-REST-API-Key:PARSE_API_KEY"\-H"Content-Type:image/jpeg"\--data-binary'@myPicture.jpg'\https://api.parse.com/1/files/pic.jpg用这个:curl=Curl::Easy.new("https://api.parse.com/1/files/lion.jpg")curl.multipart_form_

  5. 世界前沿3D开发引擎HOOPS全面讲解——集3D数据读取、3D图形渲染、3D数据发布于一体的全新3D应用开发工具 - 2

    无论您是想搭建桌面端、WEB端或者移动端APP应用，HOOPSPlatform组件都可以为您提供弹性的3D集成架构，同时，由工业领域3D技术专家组成的HOOPS技术团队也能为您提供技术支持服务。如果您的客户期望有一种在多个平台（桌面/WEB/APP，而且某些客户端是“瘦”客户端）快速、方便地将数据接入到3D应用系统的解决方案，并且当访问数据时，在各个平台上的性能和用户体验保持一致，HOOPSPlatform将帮助您完成。利用HOOPSPlatform，您可以开发在任何环境下的3D基础应用架构。HOOPSPlatform可以帮您打造3D创新型产品，HOOPSSDK包含的技术有：快速且准确的CAD

  6. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  7. 华为OD机试用Python实现 -【明明的随机数】 2023Q1A - 2

    华为OD机试题本篇题目：明明的随机数题目输入描述输出描述：示例1输入输出说明代码编写思路最近更新的博客华为od2023|什么是华为od，od薪资待遇，od机试题清单华为OD机试真题大全，用Python解华为机试题|机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为o

  8. FOHEART H1数据手套驱动Optitrack光学动捕双手运动(Unity3D) - 2

    本教程将在Unity3D中混合Optitrack与数据手套的数据流，在人体运动的基础上，添加双手手指部分的运动。双手手背的角度仍由Optitrack提供，数据手套提供双手手指的角度。 01  客户端软件分别安装MotiveBody与MotionVenus并校准人体与数据手套。MotiveBodyMotionVenus数据手套使用、校准流程参照：https://gitee.com/foheart_1/foheart-h1-data-summary.git02  数据转发打开MotiveBody软件的Streaming，开始向Unity3D广播数据；MotionVenus中设置->选项选择Unit

  9. 使用canal同步MySQL数据到ES - 2

    文章目录一、概述简介原理模块二、配置Mysql使用版本环境要求1.操作系统2.mysql要求三、配置canal-server离线下载在线下载上传解压修改配置单机配置集群配置分库分表配置1.修改全局配置2.实例配置垂直分库水平分库3.修改group-instance.xml4.启动监听四、配置canal-adapter1修改启动配置2配置映射文件3启动ES数据同步查询所有订阅同步数据同步开关启动4.验证五、配置canal-admin一、概述简介canal是Alibaba旗下的一款开源项目，Java开发。基于数据库增量日志解析，提供增量数据订阅&消费。Git地址：https://github.co

  10. 基于C#实现简易绘图工具【100010177】 - 2

    C#实现简易绘图工具一.引言实验目的:通过制作窗体应用程序(C#画图软件),熟悉基本的窗体设计过程以及控件设计,事件处理等,熟悉使用C#的winform窗体进行绘图的基本步骤,对于面向对象编程有更加深刻的体会.Tutorial任务设计一个具有基本功能的画图软件**·包括简单的新建文件,保存,重新绘图等功能**·实现一些基本图形的绘制,包括铅笔和基本形状等,学习橡皮工具的创建**·设计一个合理舒适的UI界面**注明:你可能需要先了解一些关于winform窗体应用程序绘图的基本知识,以及关于GDI+类和结构的知识二.实验环境Windows系统下的visualstudio2017C#窗体应用程序三.

随机推荐