KNN和Kmeans算法讲解.pptx

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