机器学习与数据挖掘

1、机器学习与数据挖掘,回归,2020年6月29日,Machine Learning,2,分类与回归,分类：通过样本预测离散变量的值 回归：通过样本预测连续变量的值 二者本质上类似 可以使用相同的算法，局部优化 如：SVR 但仍然存在很大差异 具有独特的算法,2020年6月29日,Machine Learning,3,回归算法,参数式方法 假设数据由一组特定模型产生 优化目标：找到最优模型参数 /tutorials/introreg.html,2020年6月29日,Machine Learning,4,回归算法,非参数方法 参数式方法的问题 如果数据分布

2、与所假设的模型差异很大，则参数式方法性能极差 不假设模型 直接使用训练数据来描述 理论上：可以描述任意分布 /tutorials/mbl.html,2020年6月29日,Machine Learning,5,回归算法,非参数方法 距离/相似度度量 kNN算法依赖于好的距离或相似度度量 特征空间内的距离/相似度应与目标函数的距离/相似度高度相关 且关系简单，最好成正比 现实：找到合适的距离/相似度度量非常困难,2020年6月29日,Machine Learning,6,距离/相似度度量,常用距离 欧氏距离 平方距离，L2 等距子空间：(超)球面 好处：

3、符合直观 坏处：计算量大，噪声敏感,2020年6月29日,Machine Learning,7,距离/相似度度量,常用距离 绝对值距离 街区距离，Manhattan/boxcar/taxicab距离，L1 等距子空间：(超)多面体 好处：计算量小，噪声敏感度较低 坏处：不一定符合直观 但符合某些应用的特性,2020年6月29日,Machine Learning,8,距离/相似度度量,常用距离 最大绝对值距离 ，Chebyshev距离 等距子空间：(超)立方体 好处：计算量小 坏处：不一定符合直观 但易于实现快速索引,2020年6月29日,Machine Learning,9,距离/相似度度量,

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

5、性的量来计算距离 2 统计上常用的分布相似性测度,2020年6月29日,Machine Learning,13,距离/相似度度量,直方图的特殊距离 KL距离 “互信息量”,2020年6月29日,Machine Learning,14,距离/相似度度量,直方图的特殊距离 Jeffrey距离 据说比KL距离数值稳定性好,2020年6月29日,Machine Learning,15,距离/相似度度量,直方图的特殊距离 直方图的交 一定程度上支持部分匹配,2020年6月29日,Machine Learning,16,距离/相似度度量,直方图的特殊距离 Earth Movers Distance(土方工

6、程距离？) 支持部分匹配 复杂度高,/efros/courses/AP06/presentations/06-07-presentation.ppt,2020年6月29日,Machine Learning,17,回归算法,非参数方法 相似性索引 kNN在每次应用（分类/预测）的时候都需要处理所有训练样本 找到最近的k个样本/某个距离范围的所有样本 如果训练集大，则计算量极大 相似性索引 实现快速kNN查询或范围查询,2020年6月29日,Machine Learning,18,相似性索引,支持范围查询和/或最近邻查询的索引,如何实现？,2020年6月

7、29日,Machine Learning,19,相似性索引,一维范围查询索引：B-树,查询：15,50,2020年6月29日,Machine Learning,20,相似性索引,多维范围查询 距离函数的影响 一维：L1=L2= 多维：均不相等 使用哪个距离函数？ 最容易实现： 效率最高 其它距离函数仍然可以实现,2020年6月29日,Machine Learning,21,相似性索引,多维范围查询 K-d树, k-d-b树,2020年6月29日,Machine Learning,22,相似性索引,多维范围查询 K-d树, k-d-b树,/qu

8、adtree/index.html,2020年6月29日,Machine Learning,23,相似性索引,多维范围查询 R-树及其变种,2020年6月29日,Machine Learning,24,相似性索引,多维范围查询 更近似欧氏距离：SR-树 使用超球形节点 真的有效吗？ K-d(-b-), R-, SR-树的问题 性能与插入顺序有关 大量插入、输出等操作后性能可能下降 数据分割算法的通病 不使用数据分割，使用空间分割,2020年6月29日,Machine Learning,25,相似性索引,多维范围查询 空间分割 空间等分成等大小的格子 量化 只保留有数据的格子 高维空间：稀疏 用

9、简单索引结构索引格子,2020年6月29日,Machine Learning,26,相似性索引,多维范围查询 空间分割 格量化(Lattice Quantization) 致密格：更接近球形，用较少格即可填满空间,Z2格,A2格,2020年6月29日,Machine Learning,27,相似性索引,多维范围查询 空间分割 格索引 Hash: 查询时需要把邻接格全部查一遍，无论该格是否有数据 邻接格数量越少效率越高,2020年6月29日,Machine Learning,28,相似性索引,多维范围查询 空间分割 格索引 Trie：把每维当作一个符号，则可用Trie索引 Trie索引可以在每维上支持范围查询，所以无需遍历所有邻接格 可以处理任意高维数,2020年6月29日,Machine Learning,29,相似性索引,多维范围查询 数据分割 可构造平衡数，层数浅，自适应数据分布 插入顺序影响性能，修改操作会显著降低性能 维数越高影响越大 空间分割 结构仅与所索引的数据有关 维数无关 不平衡，层数可能较大，量化步长难把握,2020年6月29日,Machine Learning,30,相似性索引,多维范围查询 各种结构可高效处理的维数 R-树、SR-树：10-15维 K-d(-b-)树：25维 空间分割