K-NN和K-means算法.ppt

谢谢！！！！！ KNN 和 k-means算法 数据支撑中心 2015年11月16日 全称：k-Nearest Neighbor 简称：K-NN 中文：K-近邻算法 K-NN算法是怎么来的 猜猜看：最后一行未知电影属于什么类型的电影? 电影名称 打斗次数 接吻次数 电影类型 California Man? 3 104 Romance He’s Not Really into Dudes 2 100 Romance Beautiful Woman? 1 81 Romance Kevin Longblade? 101 10 Action Robo Slayer 3000? 99 5 Action Amped II? 98 2 Action 未知 18 90 Unknown 点 X坐标 Y坐标 点类型 A点? 3 104 Romance B点? 2 100 Romance C点? 1 81 Romance D点? 101 10 Action E点? 99 5 Action F点 98 2 Action G点 18 90 Unknown K-NN算法是怎么来的 想一想：下面图片中只有三种豆，有三个豆是未知的种类，如何判定他们的种类？ 未知的豆离哪种豆最近就认为未知豆和该豆是同一种类。 定义：为了判定未知样本的类别，以全部训练样本作为代表点，计算未知样本与所有训练样本的距离，并以最近邻者的类别作为决策未知样本类别的唯一依据。 但是，最近邻算法明显是存在缺陷的，我们来看一个例子。 最近邻算法 K-NN算法是怎么来的 猜猜看：有一个未知形状（绿色圆点），如何判断其是什么形状? 对噪声数据过于敏感。为了解决这个问题，我们可以把位置样本周边的多个最近样本计算在内，扩大参与决策的样本量，以避免个别数据直接决定决策结果。 K-NN算法是怎么来的 K-NN算法 K-近邻算法，即K-Nearest Neighbor algorithm，简称K-NN算法。单从名字来猜想，可以简单粗暴的认为是：K个最近的邻居，当K=1时，算法便成了最近邻算法，即寻找最近的那个邻居。 所谓K-NN算法，即是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例（也就是K个邻居）， 这K个实例的多数属于某个类，就把该输入实例分类到这个类中。 基本概念 K-NN算法 有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是待分类的数据。 举例 如果K=3，判定绿色的这个待分类点属于红色的三角形一类。 如果K=5，判定绿色的这个待分类点属于蓝色的正方形一类。 问题：给这个绿色的圆分类？ K-NN算法 K-NN算法本身简单有效，它是一种 lazy-learning 算法，分类器不需要使用训练集进行训练，训练时间复杂度为0。K-NN 分类的计算复杂度和训练集中的样本数目成正比。 近邻法的一个严重问题是需要存储全部训练样本，以及繁重的距离计算量。 特点 K-NN算法 三要素 距离度量 根据欧氏距离定义样本间的距离。 分类决策规则 往往是多数表决，即由输入实例的 K个最临近的训练实例中的多数类决定输入实例的类别。 K 值的选择 K-NN算法 对于位置样本Xu，通过K-NN算法，我们显然可以得到X应属于红点，但对于位置样本Y，通过KNN算法我们似乎得到了Y应属于蓝点的结论，而这个结论直观来看并没有说服力。 不足 当样本不平衡时，可能导致当输入一个未知样本时，该样本的K个邻居中大数量类的样本占多数。 但是这类样本并不接近目标样本，而数量小的这类样本很靠近目标样本。 K-NN却不关心这个问题，它只关心哪类样本的数量最多，而不去把距离远近考虑在内。 因此，我们可以采用权值的方法来改进。和该样本距离小的邻居权值大，和该样本距离大的邻居权值则相对较小。由此，将距离远近的因素也考虑在内，避免因一个样本过大导致误判的情况。 K-NN算法 不足 全称：k-means 中文：K-均值聚类算法 聚类 聚类（Clustering）就是对大量未知标注的数据集，按数据的内在相似性将数据集划分为多个族（Cluster），使族内的数据相似度尽可能大而类别间的数据相似度尽可能小。 聚类中没有任何指导信息，完全按照数据的分布进行类别划分 聚类 对相似的文档或超链接进行聚类，由于类别数远小于文档数，能够加快用户寻找相关信息的速度。 为什么要聚类 客户分割（segmentation）是一种发现用户特性的方法。 将一个基于数据的客户信息分组；从而给你一个客户信息的概况，这可以直接转化为针对不同客户的营销策略。 聚类 为什么要聚类 经济领域： 帮助市场分析人员从客户数据库中发现不同的客户群 对住宅区进行聚类，确定自动提款机ATM的安放