机器学习与数据挖掘课件

机器学习与数据挖掘回归12/5/20231MultimediaSearchEngine分类与回归分类：通过样本预测离散变量的值回归：通过样本预测连续变量的值二者本质上类似可以使用相同的算法，局部优化如：SVR但仍然存在很大差异具有独特的算法12/5/20232MultimediaSearchEngine回归算法参数式方法假设数据由一组特定模型产生优化目标：找到最优模型参数/tutorials/introreg.html12/5/20233MultimediaSearchEngine回归算法非参数方法参数式方法的问题如果数据分布与所假设的模型差异很大，则参数式方法性能极差不假设模型直接使用训练数据来描述理论上：可以描述任意分布/tutorials/mbl.html12/5/20234MultimediaSearchEngine回归算法非参数方法距离/相似度度量kNN算法依赖于好的距离或相似度度量特征空间内的距离/相似度应与目标函数的距离/相似度高度相关且关系简单，最好成正比现实：找到合适的距离/相似度度量非常困难12/5/20235MultimediaSearchEngine距离/相似度度量常用距离欧氏距离平方距离，L2等距子空间：(超)球面好处：符合直观坏处：计算量大，噪声敏感12/5/20236MultimediaSearchEngine距离/相似度度量常用距离绝对值距离街区距离，Manhattan/boxcar/taxicab距离，L1等距子空间：(超)多面体好处：计算量小，噪声敏感度较低坏处：不一定符合直观但符合某些应用的特性12/5/20237MultimediaSearchEngine距离/相似度度量常用距离最大绝对值距离，Chebyshev距离等距子空间：(超)立方体好处：计算量小坏处：不一定符合直观但易于实现快速索引12/5/20238MultimediaSearchEngine距离/相似度度量常用距离Minkowski距离

以上距离均是Minkowski距离取特定m的特殊情况很少使用较大的m：m越大，噪声越敏感12/5/20239MultimediaSearchEngine距离/相似度度量常用距离归一化L1距离值域范围小的特征维不会被完全掩盖12/5/202310MultimediaSearchEngine距离/相似度度量常用距离加权归一化L1距离特征维重要性与预测能力成比例权重IG(信息增益)idf其它特征选择指标12/5/202311MultimediaSearchEngine距离/相似度度量直方图的特殊距离直方图是概率密度函数可以用评价概率分布差异性的量来计算距离

2统计上常用的分布相似性测度12/5/202312MultimediaSearchEngine距离/相似度度量直方图的特殊距离KL距离“互信息量”12/5/202313MultimediaSearchEngine距离/相似度度量直方图的特殊距离Jeffrey距离据说比KL距离数值稳定性好12/5/202314MultimediaSearchEngine距离/相似度度量直方图的特殊距离直方图的交一定程度上支持部分匹配12/5/202315MultimediaSearchEngine距离/相似度度量直方图的特殊距离EarthMover’sDistance(土方工程距离？)支持部分匹配复杂度高/~efros/courses/AP06/presentations/06-07-presentation.ppt12/5/202316MultimediaSearchEngine回归算法非参数方法相似性索引kNN在每次应用（分类/预测）的时候都需要处理所有训练样本找到最近的k个样本/某个距离范围的所有样本如果训练集大，则计算量极大相似性索引实现快速kNN查询或范围查询12/5/202317MultimediaSearchEngine相似性索引支持范围查询和/或最近邻查询的索引最近邻查询范围查询距离阈值等距子空间如何实现？12/5/202318MultimediaSearchEngine相似性索引一维范围查询索引：B-树查询：[15,50]12/5/202319MultimediaSearchEngine相似性索引多维范围查询距离函数的影响一维：L1=L2=……=多维：均不相等使用哪个距离函数？最容易实现：效率最高其它距离函数仍然可以实现12/5/202320MultimediaSearchEngine相似性索引多维范围查询K-d树,k-d-b树12/5/202321MultimediaSearchEngine相似性索引多维范围查询K-d树,k-d-b树/quadtree/index.html12/5/202322MultimediaSearchEngine相似性索引多维范围查询R-树及其变种12/5/202323MultimediaSearchEngine相似性索引多维范围查询更近似欧氏距离：SR-树使用超球形节点真的有效吗？K-d(-b-),R-,SR-树的问题性能与插入顺序有关大量插入、输出等操作后性能可能下降数据分割算法的通病不使用数据分割，使用空间分割12/5/202324MultimediaSearchEngine相似性索引多维范围查询空间分割空间等分成等大小的格子量化只保留有数据的格子高维空间：稀疏用简单索引结构索引格子12/5/202325MultimediaSearchEngine相似性索引多维范围查询空间分割格量化(LatticeQuantization)致密格：更接近球形，用较少格即可填满空间Z2格A2格12/5/202326MultimediaSearchEngine相似性索引多维范围查询空间分割格索引Hash:查询时需要把邻接格全部查一遍，无论该格是否有数据邻接格数量越少效率越高维数123456789致密格Z1A2A3D4D5E6E7E89Z邻接数(3^d-1)2826802427282186656019682致密格邻接数261224407212624027212/5/202327MultimediaSearchEngine相似性索引多维范围查询空间分割格索引Trie：把每维当作一个符号，则可用Trie索引Trie索引可以在每维上支持范围查询，所以无需遍历所有邻接格可以处理任意高维数12/5/202328MultimediaSearchEngine相似性索引多维范围查询数据分割可构造平衡数，层数浅，自适应数据分布插入顺序影响性能，修改操作会显著降低性能维数越高影响越大空间分割结构仅与所索引的数据有关维数无关不平衡，层数可能较大，量化步长难把握12/5/202329MultimediaSearchEngine相似性索引多维范围查询各种结构可高效处理的维数R-树、SR-树：10-15维K-d(-b-)树：<25维空间分割：<100维更高的维数？线性扫描可能更快12/5/