《K-NN和K-means算法》由会员分享，可在线阅读，更多相关《K-NN和K-means算法（32页珍藏版）》请在金锄头文库上搜索。
1、KNN 和 k-means算法 数据支撑中心 2015年11月16日,全称：k-Nearest Neighbor 简称：K-NN 中文：K-近邻算法,猜猜看：最后一行未知电影属于什么类型的电影?,K-NN算法是怎么来的,想一想：下面图片中只有三种豆，有三个豆是未知的种类，如何判定他们的种类？,未知的豆离哪种豆最近就认为未知豆和该豆是同一种类。,定义：为了判定未知样本的类别，以全部训练样本作为代表点，计算未知样本与所有训练样本的距离，并以最近邻者的类别作为决策未知样本类别的唯一依据。 但是，最近邻算法明显是存在缺陷的，我们来看一个例子。,最近邻算法,K-NN算法是怎么来的,猜猜看：有一个未知形状
2、（绿色圆点），如何判断其是什么形状?,对噪声数据过于敏感。为了解决这个问题，我们可以把位置样本周边的多个最近样本计算在内，扩大参与决策的样本量，以避免个别数据直接决定决策结果。,K-NN算法是怎么来的,K-NN算法,K-近邻算法，即K-Nearest Neighbor algorithm，简称K-NN算法。单从名字来猜想，可以简单粗暴的认为是：K个最近的邻居，当K=1时，算法便成了最近邻算法，即寻找最近的那个邻居。 所谓K-NN算法，即是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例（也就是K个邻居）， 这K个实例的多数属于某个类，就把该输入实例分类到这个类中。
3、,基本概念,有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是待分类的数据。,举例,如果K=3，判定绿色的这个待分类点属于红色的三角形一类。 如果K=5，判定绿色的这个待分类点属于蓝色的正方形一类。,问题：给这个绿色的圆分类？,K-NN算法,K-NN算法本身简单有效，它是一种 lazy-learning 算法，分类器不需要使用训练集进行训练，训练时间复杂度为0。K-NN 分类的计算复杂度和训练集中的样本数目成正比。 近邻法的一个严重问题是需要存储全部训练样本，以及繁重的距离计算量。,特点,K-NN算法,三要素,距离度量 根据欧氏距离定义样本
4、间的距离。,分类决策规则 往往是多数表决，即由输入实例的 K个最临近的训练实例中的多数类决定输入实例的类别。,K 值的选择,对于位置样本Xu，通过K-NN算法，我们显然可以得到X应属于红点，但对于位置样本Y，通过KNN算法我们似乎得到了Y应属于蓝点的结论，而这个结论直观来看并没有说服力。,不足,当样本不平衡时，可能导致当输入一个未知样本时，该样本的K个邻居中大数量类的样本占多数。 但是这类样本并不接近目标样本，而数量小的这类样本很靠近目标样本。 K-NN却不关心这个问题，它只关心哪类样本的数量最多，而不去把距离远近考虑在内。 因此，我们可以采用权值的方法来改进。和该样本距离小的邻居权值大，和该
5、样本距离大的邻居权值则相对较小。由此，将距离远近的因素也考虑在内，避免因一个样本过大导致误判的情况。,不足,全称：k-means 中文：K-均值聚类算法,聚类（Clustering）就是对大量未知标注的数据集，按数据的内在相似性将数据集划分为多个族（Cluster），使族内的数据相似度尽可能大而类别间的数据相似度尽可能小。,聚类中没有任何指导信息，完全按照数据的分布进行类别划分,对相似的文档或超链接进行聚类，由于类别数远小于文档数，能够加快用户寻找相关信息的速度。,为什么要聚类,客户分割（segmentation）是一种发现用户特性的方法。 将一个基于数据的客户信息分组；从而给你一个客户信息的
6、概况，这可以直接转化为针对不同客户的营销策略。,为什么要聚类,经济领域： 帮助市场分析人员从客户数据库中发现不同的客户群 对住宅区进行聚类，确定自动提款机ATM的安放位置 股票市场板块分析，找出最具活力的板块龙头股 企业信用等级分类 生物学领域： 推导植物和动物的分类； 对基因分类，获得对种群的认识 其他： 作为其他数学算法的预处理步骤，获得数据分布状况,应用领域,聚类分析中“类”的特征： 聚类所说的类不是事先给定的，而是根据数据的相似性和距离来划分； 聚类的数目和结构都没有事先假定 聚类方法的目的是寻找数据中： 潜在的自然分组结构 感兴趣的关系,原理,有16张牌 如何将他们分为一组一组的牌呢
7、？,例子,有类别标记和无类别标记; 有监督与无监督;,与分类的区别,给定数据集合V，根据数据对象间的相似程度将数据集合分成组，并满足： 则该过程称为聚类。Ci 称为簇。,一个好的聚类方法要能产生高质量的聚类结果簇，这些簇要具备以下两个特点： 高的簇内相似性 低的簇间相似性,形式化描述,划分方法（partitioning method） 层次的方法（hierarchical method） 基于密度的方法（density-based method） 基于网格的方法（grid-based method） 基于模型的聚类方法（model-based method） 聚类高维数据 基于约束的聚类分析
8、离群点分析,k-means,算法分类,Q1：k是什么？ A1：k是聚类算法当中类的个数。,Q2：means是什么？ A2：means是均值算法。,Summary：k-means是采用均值算法把数据分成K个类的硬聚类算法！,对于连续型属性具有较好的聚类效果，不适合处理离散型属性。,基本思想：通过迭代把数据集划分为不同的类别（或称簇），使得评价聚类性能的准则函数达到最优，使得每个聚类类内紧凑，类间独立。,平方误差和准则函数 即SSE（sum of the squared error） 其中， 为数据对象； 为簇， 的平均值。 这个准则函数使得生成的簇尽可能的紧凑和独立。,影响聚类 效果！,一般采用欧氏距离、曼哈顿距离作为样本间的相似性度量,1. 凭检验直观选择k 2.按密度大小选代表点确定k 3.使距离度量方法值最小的k 4.最大最小距离法确定,1. 随机选点的方法 2.凭借经验选取有代表性的点 3.基于取样的方法确定 4.基于密度的选择方法,初始化4个类别中心 左侧的全体数据仅与第一个类别中心相似,一只遥望大海的小狗。此图为100100像素的JPG图片，每个像素可以表示为三维向量（分别对应红绿蓝三基色）。 要求使用k-means算法，将图片分割为合适的背景区域（三个）和前景区域（小狗）。,分割后,分割前,谢谢！,
