1、机器学习与数据挖掘回归11/11/20221分类与回归n分类：通过样本预测离散变量的值n回归：通过样本预测连续变量的值n二者本质上类似可以使用相同的算法，局部优化n如：SVR但仍然存在很大差异n具有独特的算法11/11/20222Multimedia Search Engine回归算法n参数式方法假设数据由一组特定模型产生n优化目标：找到最优模型参数nhttp:/www.autonlab.org/tutorials/introreg.html11/11/20223Multimedia Search Engine回归算法n非参数方法参数式方法的问题n如果数据分布与所假设的模型差异很大，则参数式方
2、法性能极差不假设模型n直接使用训练数据来描述理论上：可以描述任意分布nhttp:/www.autonlab.org/tutorials/mbl.html11/11/20224Multimedia Search Engine回归算法n非参数方法距离/相似度度量nkNN算法依赖于好的距离或相似度度量特征空间内的距离/相似度应与目标函数的距离/相似度高度相关n且关系简单，最好成正比n现实：找到合适的距离/相似度度量非常困难11/11/20225Multimedia Search Engine距离/相似度度量n常用距离欧氏距离n平方距离，L2n等距子空间：(超)球面n好处：符合直观n坏处：计算量大，噪
3、声敏感iiiyxYXd2,11/11/20226Multimedia Search Engine距离/相似度度量n常用距离绝对值距离n街区距离，Manhattan/boxcar/taxicab距离，L1n等距子空间：(超)多面体n好处：计算量小，噪声敏感度较低n坏处：不一定符合直观但符合某些应用的特性iiiyxYXd,11/11/20227Multimedia Search Engine距离/相似度度量n常用距离最大绝对值距离n ，Chebyshev距离n等距子空间：(超)立方体n好处：计算量小n坏处：不一定符合直观但易于实现快速索引LiiiyxYXd max,11/11/20228Multi
4、media Search Engine距离/相似度度量n常用距离Minkowski距离n n以上距离均是Minkowski距离取特定m的特殊情况很少使用较大的m：m越大，噪声越敏感mLmimiimyxYXd,11/11/20229Multimedia Search Engine距离/相似度度量n常用距离归一化L1距离n值域范围小的特征维不会被完全掩盖iiiiiiiiiiiiiyxyxyxyxyxYXd10minmax,数值特征11/11/202210Multimedia Search Engine距离/相似度度量n常用距离加权归一化L1距离n特征维重要性与预测能力成比例n权重IG(信息增益)i
5、df其它特征选择指标 iiviiiiiidfwVCHvPCHwyxwYXd|,11/11/202211Multimedia Search Engine距离/相似度度量n直方图的特殊距离直方图是概率密度函数n可以用评价概率分布差异性的量来计算距离2n统计上常用的分布相似性测度 2/;,;,2JifIififififIifJIDi11/11/202212Multimedia Search Engine距离/相似度度量n直方图的特殊距离KL距离n“互信息量”iJifIifIifJID;,11/11/202213Multimedia Search Engine距离/相似度度量n直方图的特殊距离Jeff
6、rey距离n据说比KL距离数值稳定性好 iifJifJififIifIifJID;,11/11/202214Multimedia Search Engine距离/相似度度量n直方图的特殊距离直方图的交n一定程度上支持部分匹配 iJifIifJID;min1,11/11/202215Multimedia Search Engine距离/相似度度量n直方图的特殊距离Earth Movers Distance(土方工程距离？)n支持部分匹配n复杂度高http:/www-2.cs.cmu.edu/efros/courses/AP06/presentations/06-07-presentation.p
7、pt11/11/202216Multimedia Search Engine回归算法n非参数方法相似性索引nkNN在每次应用（分类/预测）的时候都需要处理所有训练样本找到最近的k个样本/某个距离范围的所有样本如果训练集大，则计算量极大相似性索引n实现快速kNN查询或范围查询11/11/202217Multimedia Search Engine相似性索引n支持范围查询和/或最近邻查询的索引最近邻查询范围查询距离阈值等距子空间如何实现？11/11/202218Multimedia Search Engine相似性索引n一维范围查询索引：B-树查询：15,5011/11/202219Multime
8、dia Search Engine相似性索引n多维范围查询距离函数的影响n一维：L1=L2=n多维：均不相等n使用哪个距离函数？最容易实现：n效率最高其它距离函数仍然可以实现LL11/11/202220Multimedia Search Engine相似性索引n多维范围查询K-d树,k-d-b树11/11/202221Multimedia Search Engine相似性索引n多维范围查询K-d树,k-d-b树http:/donar.umiacs.umd.edu/quadtree/index.html11/11/202222Multimedia Search Engine相似性索引n多维范围查
9、询R-树及其变种11/11/202223Multimedia Search Engine相似性索引n多维范围查询更近似欧氏距离：SR-树n使用超球形节点真的有效吗？K-d(-b-),R-,SR-树的问题n性能与插入顺序有关n大量插入、输出等操作后性能可能下降n数据分割算法的通病n不使用数据分割，使用空间分割11/11/202224Multimedia Search Engine相似性索引n多维范围查询空间分割n空间等分成等大小的格子量化n只保留有数据的格子高维空间：稀疏n用简单索引结构索引格子11/11/202225Multimedia Search Engine相似性索引n多维范围查询空间分
10、割n格量化(Lattice Quantization)致密格：更接近球形，用较少格即可填满空间Z2格A2格11/11/202226Multimedia Search Engine相似性索引n多维范围查询空间分割n格索引Hash:查询时需要把邻接格全部查一遍，无论该格是否有数据n邻接格数量越少效率越高维数123456789致密格Z1A2A3D4D5E6E7E89Z邻接数(3d-1)2826802427282186656019682致密格邻接数261224407212624027211/11/202227Multimedia Search Engine相似性索引n多维范围查询空间分割n格索引Tri
11、e：把每维当作一个符号，则可用Trie索引Trie索引可以在每维上支持范围查询，所以无需遍历所有邻接格可以处理任意高维数11/11/202228Multimedia Search Engine相似性索引n多维范围查询数据分割n可构造平衡数，层数浅，自适应数据分布n插入顺序影响性能，修改操作会显著降低性能维数越高影响越大空间分割n结构仅与所索引的数据有关维数无关n不平衡，层数可能较大，量化步长难把握11/11/202229Multimedia Search Engine相似性索引n多维范围查询各种结构可高效处理的维数nR-树、SR-树：10-15维nK-d(-b-)树：25维n空间分割：100维更高的维数？n线性扫描可能更快11/11/202230Multimedia Search Engine相似性索引n最近邻查询先用范围查询获得候选数据，然后线性扫描候选数据利用范围查询的索引结构，配以优先级队列n计算节点和查询矢量的最小和最大距离，据此对节点进行排序处理线性扫描n维数较高时的唯一选择11/11/202231Multimedia Search Engine
