機器學(xué)習(xí)與數(shù)據(jù)挖掘課件

機器學(xué)習(xí)與數(shù)據(jù)挖掘回歸12/5/20231MultimediaSearchEngine分類與回歸分類：通過樣本預(yù)測離散變量的值回歸：通過樣本預(yù)測連續(xù)變量的值二者本質(zhì)上類似可以使用相同的算法，局部優(yōu)化如：SVR但仍然存在很大差異具有獨特的算法12/5/20232MultimediaSearchEngine回歸算法參數(shù)式方法假設(shè)數(shù)據(jù)由一組特定模型產(chǎn)生優(yōu)化目標(biāo)：找到最優(yōu)模型參數(shù)/tutorials/introreg.html12/5/20233MultimediaSearchEngine回歸算法非參數(shù)方法參數(shù)式方法的問題如果數(shù)據(jù)分布與所假設(shè)的模型差異很大，則參數(shù)式方法性能極差不假設(shè)模型直接使用訓(xùn)練數(shù)據(jù)來描述理論上：可以描述任意分布/tutorials/mbl.html12/5/20234MultimediaSearchEngine回歸算法非參數(shù)方法距離/相似度度量kNN算法依賴于好的距離或相似度度量特征空間內(nèi)的距離/相似度應(yīng)與目標(biāo)函數(shù)的距離/相似度高度相關(guān)且關(guān)系簡單，最好成正比現(xiàn)實：找到合適的距離/相似度度量非常困難12/5/20235MultimediaSearchEngine距離/相似度度量常用距離歐氏距離平方距離，L2等距子空間：(超)球面好處：符合直觀壞處：計算量大，噪聲敏感12/5/20236MultimediaSearchEngine距離/相似度度量常用距離絕對值距離街區(qū)距離，Manhattan/boxcar/taxicab距離，L1等距子空間：(超)多面體好處：計算量小，噪聲敏感度較低壞處：不一定符合直觀但符合某些應(yīng)用的特性12/5/20237MultimediaSearchEngine距離/相似度度量常用距離最大絕對值距離，Chebyshev距離等距子空間：(超)立方體好處：計算量小壞處：不一定符合直觀但易于實現(xiàn)快速索引12/5/20238MultimediaSearchEngine距離/相似度度量常用距離Minkowski距離

以上距離均是Minkowski距離取特定m的特殊情況很少使用較大的m：m越大，噪聲越敏感12/5/20239MultimediaSearchEngine距離/相似度度量常用距離歸一化L1距離值域范圍小的特征維不會被完全掩蓋12/5/202310MultimediaSearchEngine距離/相似度度量常用距離加權(quán)歸一化L1距離特征維重要性與預(yù)測能力成比例權(quán)重IG(信息增益)idf其它特征選擇指標(biāo)12/5/202311MultimediaSearchEngine距離/相似度度量直方圖的特殊距離直方圖是概率密度函數(shù)可以用評價概率分布差異性的量來計算距離

2統(tǒng)計上常用的分布相似性測度12/5/202312MultimediaSearchEngine距離/相似度度量直方圖的特殊距離KL距離“互信息量”12/5/202313MultimediaSearchEngine距離/相似度度量直方圖的特殊距離Jeffrey距離據(jù)說比KL距離數(shù)值穩(wěn)定性好12/5/202314MultimediaSearchEngine距離/相似度度量直方圖的特殊距離直方圖的交一定程度上支持部分匹配12/5/202315MultimediaSearchEngine距離/相似度度量直方圖的特殊距離EarthMover’sDistance(土方工程距離？)支持部分匹配復(fù)雜度高/~efros/courses/AP06/presentations/06-07-presentation.ppt12/5/202316MultimediaSearchEngine回歸算法非參數(shù)方法相似性索引kNN在每次應(yīng)用（分類/預(yù)測）的時候都需要處理所有訓(xùn)練樣本找到最近的k個樣本/某個距離范圍的所有樣本如果訓(xùn)練集大，則計算量極大相似性索引實現(xiàn)快速kNN查詢或范圍查詢12/5/202317MultimediaSearchEngine相似性索引支持范圍查詢和/或最近鄰查詢的索引最近鄰查詢范圍查詢距離閾值等距子空間如何實現(xiàn)？12/5/202318MultimediaSearchEngine相似性索引一維范圍查詢索引：B-樹查詢：[15,50]12/5/202319MultimediaSearchEngine相似性索引多維范圍查詢距離函數(shù)的影響一維：L1=L2=……=多維：均不相等使用哪個距離函數(shù)？最容易實現(xiàn)：效率最高其它距離函數(shù)仍然可以實現(xiàn)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-樹使用超球形節(jié)點真的有效嗎？K-d(-b-),R-,SR-樹的問題性能與插入順序有關(guān)大量插入、輸出等操作后性能可能下降數(shù)據(jù)分割算法的通病不使用數(shù)據(jù)分割，使用空間分割12/5/202324MultimediaSearchEngine相似性索引多維范圍查詢空間分割空間等分成等大小的格子量化只保留有數(shù)據(jù)的格子高維空間：稀疏用簡單索引結(jié)構(gòu)索引格子12/5/202325MultimediaSearchEngine相似性索引多維范圍查詢空間分割格量化(LatticeQuantization)致密格：更接近球形，用較少格即可填滿空間Z2格A2格12/5/202326MultimediaSearchEngine相似性索引多維范圍查詢空間分割格索引Hash:查詢時需要把鄰接格全部查一遍，無論該格是否有數(shù)據(jù)鄰接格數(shù)量越少效率越高維數(shù)123456789致密格Z1A2A3D4D5E6E7E89Z鄰接數(shù)(3^d-1)2826802427282186656019682致密格鄰接數(shù)261224407212624027212/5/202327MultimediaSearchEngine相似性索引多維范圍查詢空間分割格索引Trie：把每維當(dāng)作一個符號，則可用Trie索引Trie索引可以在每維上支持范圍查詢，所以無需遍歷所有鄰接格可以處理任意高維數(shù)12/5/202328MultimediaSearchEngine相似性索引多維范圍查詢數(shù)據(jù)分割可構(gòu)造平衡數(shù)，層數(shù)淺，自適應(yīng)數(shù)據(jù)分布插入順序影響性能，修改操作會顯著降低性能維數(shù)越高影響越大空間分割結(jié)構(gòu)僅與所索引的數(shù)據(jù)有關(guān)維數(shù)無關(guān)不平衡，層數(shù)可能較大，量化步長難把握12/5/202329MultimediaSearchEngine相似性索引多維范圍查詢各種結(jié)構(gòu)可高效處理的維數(shù)R-樹、SR-樹：10-15維K-d(-b-)樹：<25維空間分割：<100維更高的維數(shù)？線性掃描可能更快12/5/