机器学习与数据挖掘(精)

机器学习与数据挖掘回归2020年2月15日MachineLearning2分类与回归分类：通过样本预测离散变量的值回归：通过样本预测连续变量的值二者本质上类似可以使用相同的算法，局部优化如：SVR但仍然存在很大差异具有独特的算法2020年2月15日MachineLearning3回归算法参数式方法假设数据由一组特定模型产生优化目标：找到最优模型参数年2月15日MachineLearning4回归算法非参数方法参数式方法的问题如果数据分布与所假设的模型差异很大，则参数式方法性能极差不假设模型直接使用训练数据来描述理论上：可以描述任意分布年2月15日MachineLearning5回归算法非参数方法距离/相似度度量kNN算法依赖于好的距离或相似度度量特征空间内的距离/相似度应与目标函数的距离/相似度高度相关且关系简单，最好成正比现实：找到合适的距离/相似度度量非常困难2020年2月15日MachineLearning6距离/相似度度量常用距离欧氏距离平方距离，L2等距子空间：(超)球面好处：符合直观坏处：计算量大，噪声敏感iiiyxYXd2,2020年2月15日MachineLearning7距离/相似度度量常用距离绝对值距离街区距离，Manhattan/boxcar/taxicab距离，L1等距子空间：(超)多面体好处：计算量小，噪声敏感度较低坏处：不一定符合直观但符合某些应用的特性iiiyxYXd,2020年2月15日MachineLearning8距离/相似度度量常用距离最大绝对值距离，Chebyshev距离等距子空间：(超)立方体好处：计算量小坏处：不一定符合直观但易于实现快速索引LiiiyxYXdmax,2020年2月15日MachineLearning9距离/相似度度量常用距离Minkowski距离以上距离均是Minkowski距离取特定m的特殊情况很少使用较大的m：m越大，噪声越敏感mLmimiimyxYXd,2020年2月15日MachineLearning10距离/相似度度量常用距离归一化L1距离值域范围小的特征维不会被完全掩盖iiiiiiiiiiiiiyxyxyxyxyxYXd10minmax,,,数值特征2020年2月15日MachineLearning11距离/相似度度量常用距离加权归一化L1距离特征维重要性与预测能力成比例权重IG(信息增益)idf其它特征选择指标iiviiiiiidfwVCHvPCHwyxwYXd|,,2020年2月15日MachineLearning12距离/相似度度量直方图的特殊距离直方图是概率密度函数可以用评价概率分布差异性的量来计算距离2统计上常用的分布相似性测度2/;;ˆ,ˆˆ;,2JifIififififIifJIDi2020年2月15日MachineLearning13距离/相似度度量直方图的特殊距离KL距离“互信息量”iJifIifIifJID;;;,2020年2月15日MachineLearning14距离/相似度度量直方图的特殊距离Jeffrey距离据说比KL距离数值稳定性好iifJifJififIifIifJIDˆ;;ˆ;;,2020年2月15日MachineLearning15距离/相似度度量直方图的特殊距离直方图的交一定程度上支持部分匹配iJifIifJID;;min1,2020年2月15日MachineLearning16距离/相似度度量直方图的特殊距离EarthMover’sDistance(土方工程距离？)支持部分匹配复杂度高~efros/courses/AP06/presentations/06-07-presentation.ppt2020年2月15日MachineLearning17回归算法非参数方法相似性索引kNN在每次应用（分类/预测）的时候都需要处理所有训练样本找到最近的k个样本/某个距离范围的所有样本如果训练集大，则计算量极大相似性索引实现快速kNN查询或范围查询2020年2月15日MachineLearning18相似性索引支持范围查询和/或最近邻查询的索引最近邻查询范围查询距离阈值等距子空间如何实现？2020年2月15日MachineLearning19相似性索引一维范围查询索引：B-树查询：[15,50]2020年2月15日MachineLearning20相似性索引多维范围查询距离函数的影响一维：L1=L2=……=多维：均不相等使用哪个距离函数？最容易实现：效率最高其它距离函数仍然可以实现LL2020年2月15日MachineLearning21相似性索引多维范围查询K-d树,k-d-b树2020年2月15日MachineLearning22相似性索引多维范围查询K-d树,k-d-b树年2月15日MachineLearning23相似性索引多维范围查询R-树及其变种2020年2月15日MachineLearning24相似性索引多维范围查询更近似欧氏距离：SR-树使用超球形节点真的有效吗？K-d(-b-),R-,SR-树的问题性能与插入顺序有关大量插入、输出等操作后性能可能下降数据分割算法的通病不使用数据分割，使用空间分割2020年2月15日MachineLearning25相似性索引多维范围查询空间分割空间等分成等大小的格子量化只保留有数据的格子高维空间：稀疏用简单索引结构索引格子2020年2月15日MachineLearning26相似性索引多维范围查询空间分割格量化(LatticeQuantization)致密格：更接近球形，用较少格即可填满空间Z2格A2格2020年2月15日MachineLearning27相似性索引多维范围查询空间分割格索引Hash:查询时需要把邻接格全部查一遍，无论该格是否有数据邻接格数量越少效率越高维数123456789致密格Z1A2A3D4D5E6E7E89Z邻接数(3^d-1)2826802427282186656019682致密格邻接数26122440721262402722020年2月15日MachineLearning28相似性索引多维范围查询空间分割格索引Trie：把每维当作一个符号，则可用Trie索引Trie索引可以在每维上支持范围查询，所以无需遍历所有邻接格可以处理任意高维数2020年2月15日MachineLearning29相似性索引多维范围查询数据分割可构造平衡数，层数浅，自适应数据分布插入顺序影响性能，修改操作会显著降低性能维数越高影响越大空间分割结构仅与所索引的数据有关维数无关不平衡，层数可能较大，量化步长难把握2020年2月15日MachineLearning30相似性索引多维范围查询各种结构可高效处理的维数R-树、SR-树：10-15维K-d(-b-)树：25维空间分割：100维更高的维数？线性扫描可能更快2020年2月15日MachineLearning31相似性索引最近邻查询先用范围查询获得候选数据，然后线性扫描候选数据利用范围查询的索引结构，配以优先级队列计算节点和查询矢量的最小和最大距离，据此对节点进行排序处理线性扫描维数较高时的唯一选择