《数据挖掘原理与应用 第2版 》课件 6.3分类预测-k-近邻分类

第6章分类预测6.3k-近邻分类K-近邻分类K-近邻（K-NearestNeighbor，KNN）分类算法，最初是由Cover和Hart于1968年提出，是一个理论上比较成熟的方法。算法原理简单直观：未知样本的类别，由特征空间中K个最相似（即特征空间中最邻近）的样本的大多数类别来确定。是一种基于实例的懒惰学习方法。K-近邻分类K-近邻分类算法的处理过程为：对于待预测的未分类样本，计算其与数据集中每个样本之间的相似度；筛选出最近邻的K个数据样本；根据K个最近邻数据样本的类别，采用多数投票机制确定待预测样本的类别。K-近邻分类这里有几个问题需要详细讨论：以何种指标来衡量数据样本之间的相似度；K值如何确定；采用多数投票机制判定样本类别时如何设计具体算法。相似度度量1.距离(1)欧几里得距离（EuclideanDistance）(2)曼哈顿距离（ManhattanDistance）(3)明可夫斯基距离（MinkowskiDistance）(4)马氏距离（Mahalanobisdistance）(5)汉明距离（HammingDistance）2.相似系数(1)余弦相似度(2)相关系数(3)Jaccard相似系数(JaccardSimilarityCoefficient)“距离”度量定义距离函数，基于属性值进行计算非负性对于任意x，y，两者之间的距离d(x，y)≥0，当x

=y时，等号成立。对称性对于任意x，y，两者之间的距离d(x，y)=d(y，x)，即距离是标量而不是向量。三角不等式对于任意x，y，z，有d(x，y)

≤d(x，z)+d(z，y)。即对象x到对象y的距离小于等于途经其他任何对象z的距离之和。也称为相似性“距离”度量欧几里得距离EuclideanDistance对于n维数据

X={x1，x2，…，xn}，Y={y1，y2，…，yn}，其欧几里得距离为在二维空间中的欧几里得距离就是平面中两点之间的实际距离。在三维空间中的欧几里得距离就是立体（三维）空间中两点之间的实际距离。“距离”度量曼哈顿距离对于n维数据

X={x1，x2，…，xn}，Y={y1，y2，…，yn}，其曼哈顿距离为(6,6)(2,2)欧几里得距离=5.66曼哈顿距离=(6-2)+(6-2)=844xy“距离”度量明可夫斯基距离MinkowskiDistance对于n维数据

X={x1，x2，…，xn}，Y={y1，y2，…，yn}，其明可夫斯基距离为相似系数余弦相似度对于n维数据

X={x1，x2，…，xn}，Y={y1，y2，…，yn}，即对于x，y两个向量，有：cos(x,y)=(x·y)/‖x‖·‖y‖

余弦相似度【例如】分析以下两个句子的相似性：

句子A：我喜欢看电视，不喜欢看电影。句子B：我不喜欢看电视，也不喜欢看电影。1)可以将两个句子进行分词：句子A：我/喜欢/看电视/不/喜欢/看/电影句子B：我/不/喜欢/看/电视/也/不/喜欢/看/电影2)对所出现的各个词汇（我

喜欢

看

电视

电影

不

也），计算其词频：句子A：我1，喜欢2，看2，电视1，电影1，不1，也0句子B：我1，喜欢2，看2，电视1，电影1，不2，也1余弦相似度【例如】分析以下两个句子的相似性：

句子A：我喜欢看电视，不喜欢看电影。句子B：我不喜欢看电视，也不喜欢看电影。3)将词频转换为向量：句子A：x=(1221110)句子B：y=(1221121)4)计算其余弦相似度，有：余弦相似度由此，我们就得到了“找出相似文章”的一种算法：使用TF-IDF算法，找出两篇文章的关键词；每篇文章各取出若干个关键词（比如20个），合并成一个集合，计算每篇文章对于这个集合中的词的词频（为了避免文章长度的差异，可以使用相对词频）；生成两篇文章各自的词频向量；计算两个向量的余弦相似度，值越大就表示越相似。相似系数余弦相似度相关系数反映变量之间相关关系密切程度的统计指标相关系数按积差的方法计算，以两变量与各自平均值的离差为基础，通过两个离差相乘来反映两变量之间相关程度。x与y之间的协方差x,y的均方差相似系数余弦相似度相关系数Jaccard相似系数(JaccardSimilarityCoefficient)用于比较有限样本集之间的相似性与差异性A、B的相似性：Jaccard距离：余弦相似度TF-IDF算法TF-IDF通过统计方法，对字词对于语料库中的一份文件或文件集的重要程度进行评估。字词的重要性随其在文件中出现的次数正比增加，随其在语料库中出现的频率成反比下降，即如果某字在一篇文章中出现的频率TF高，而在其他文章中很少出现，则认为该字词具有很好的类别区分能力，适合用于分类。这里TF为词频(TermFrequency)，表示词条在文档d中出现的频率；IDF为逆向文件频率(InverseDocumentFrequency)，表示包含词条的文档的数量，值越大，表明词条具有很好的类别区分能力。TF-IDF加权的各种形式常被搜索引擎应用，作为文件与用户查询之间相关程度的度量或评级。除了TF-IDF以外，因特网上的搜索引擎还会使用基于链接分析的评级方法，以确定文件在搜寻结果中出现的顺序。K-近邻分类这里有几个问题需要详细讨论：以何种指标来衡量数据样本之间的相似度；K值如何确定；采用多数投票机制判定样本类别时如何设计具体算法。K值如何确定K值是K-近邻算法的一个超参数，表示选择多少个最近邻的样本来进行预测。K值的选择对算法的性能有很大影响，需要根据具体的应用问题和数据的特征进行设置和调整。K值如何确定K值如何确定当K值设置偏小时算法会更多地关注局部的细节，精确度较高，同时对训练数据中的噪声和异常值较为敏感，增加了过拟合风险，泛化性降低，导致分类结果不稳定。当K值设置偏大时算法更多地关注整体的趋势，对局部噪声和异常值的敏感度降低，但可能使模型过于平滑，忽略了数据中的某些重要细节，导致分类结果过于笼统。K值的增加通常意味着计算复杂度的提高。在实际应用中通过交叉验证等方法来选择合适的K值除了K值外，还可以考虑调整其他参数（如相似度度量方式、特征权重等）来进一步优化算法的性能。K-近邻分类这里有几个问题需要详细讨论：以何种指标来衡量数据样本之间的相似度；K值如何确定；采用多数投票机制判定样本类别时如何设计具体算法。多数投票机制判定方法：以出现次数最多的样本类别以样本类别的平均值必要时可对类别属性进行编码以邻样本类别加权平均值权重可以选近邻样本距离的倒数或与最大值的差变化：以近邻半径判定变化：K-近邻回归计算待预测样本与K个最近邻样本的距离，取平均值作为预测结果数据点0数据点1变化：K-近邻回归计算待预测样本与Radius半径内的样本的距离，取平均值作为预测结果数据点0数据点1算法特点K-近邻方法算法原理简单，易于理解和实现算法基于实例进行分类判别，直接利用数据集进行预测没有显式的训练过程，能够较为轻松地处理多分类问题算法从原理上依赖于极限定理，但在类别判别时，只与少量的相邻样本有关，因此可以较好地处理非线性数据，也能够避免样本的不平衡问题对于