機器學習

1宝与、低維嵌入

事實上喜滨，在高維情形下出現的數據樣本稀疏捉捅、距離計算困難等問題，是所有機器學習方法共同面臨的嚴重障礙虽风，被稱為“維數災難”棒口。緩解維數災難的一個重要途徑是降維寄月，即通過某種數學變換將原始高維屬性空間轉變?yōu)橐粋€低維的“子空間”，在這個子空間中樣本密度大幅度提高无牵，計算距離也變得更加容易漾肮。

2、多維放縮（MDS-multiple dimensional scaling）

若要求原始空間樣本之間的距離在低維空間中得以保持茎毁，就得到一種典型的降維方法MDS克懊。

假定 $m$ 個樣本在原始空間的距離矩陣為 $D \in \mathbb{R}^{m \times m}$ ,其第 $i$ 行 $j$ 列的元素 $Dist_{ij}$ 為樣本 $\mathbf{x}_i$ 到 $\mathbf{x}_j$ 的距離。我們的目標是獲得樣本在低維 $d^\prime$ 維空間的表示 $\mathbf{Z} \in \mathbb{R}^{d^\prime \times m},d^\prime \le d$ 七蜘，且任意兩個樣本在 $d^\prime$ 維空間的歐氏距離等于原始空間的歐式距離谭溉，即 $||z_i - z_j|| = Dist_{ij}$ 。其中

$\mathbf{Z} = \left[ \begin{matrix} z_{11} & z_{12} & z_{13} & \cdots & z_{1m}\\ z_{21} & z_{22} & z_{23} & \cdots & z_{2m} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ z_{d^\prime1} & z_{d^\prime2} & z_{d^\prime3} & \cdots & z_{d^\prime m} \end{matrix} \right] = \left[ \begin{matrix} \mathbf{z_1} & \mathbf{z_2} & \mathbf{z_3} & \cdots & \mathbf{z_m} \end{matrix} \right] \\$

$\mathbf{z_i} = \left[ \begin{matrix} z_{1i} \\ z_{2i} \\ \vdots \\ z_{d^\prime i} \end{matrix} \right]$
表明第i個樣本在 $d^\prime$ 空間的坐標

令 $\mathbf{B} = \mathbf{Z}^{\mathrm{T}}\mathbf{Z} \in \mathbb{R}^{m \times m}$ ,其中 $\mathbf{B}$ 為降維后樣本的內積矩陣橡卤， $b_{ij} = \mathbf{z}_i^\mathrm{T}\mathbf{z_j}$ ,有

$\mathbf{B} = \left[ \begin{matrix} \mathbf{z_1^{\mathrm{T}}} \\ \mathbf{z_2^{\mathrm{T}}} \\ \vdots \\ \mathbf{z_m^{\mathrm{T}}} \\ \end{matrix} \right] \left[ \begin{matrix} \mathbf{z_1} & \mathbf{z_2} & \mathbf{z_3} & \cdots & \mathbf{z_m} \end{matrix} \right] = \left[ \begin{matrix} \mathbf{z_1}^\mathrm{T}\mathbf{z_1} & \mathbf{z_1}^\mathrm{T}\mathbf{z_2} & \mathbf{z_1}^\mathrm{T}\mathbf{z_3} & \cdots & \mathbf{z_1}^\mathrm{T}\mathbf{z_m} \\ \mathbf{z_2}^\mathrm{T}\mathbf{z_1} & \mathbf{z_2}^\mathrm{T}\mathbf{z_2} & \mathbf{z_2}^\mathrm{T}\mathbf{z_3} & \cdots & \mathbf{z_2}^\mathrm{T}\mathbf{z_m} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ \mathbf{z_m}^\mathrm{T}\mathbf{z_1} & \mathbf{z_m}^\mathrm{T}\mathbf{z_2} & \mathbf{z_m}^\mathrm{T}\mathbf{z_3} & \cdots & \mathbf{z_m}^\mathrm{T}\mathbf{z_m} \end{matrix} \right] = \left[ \begin{matrix} b_{11} & b_{12} & b_{13} & \cdots & b_{1m} \\ b_{21} & b_{22} & b_{23} & \cdots & b_{2m} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ b_{m1} & b_{m2} & b_{m3} & \cdots & b_{mm} \\ \end{matrix} \right] \\ Dist_{ij}^2 = ||\mathbf{z_i} - \mathbf{z_j}||^2 = (\mathbf{z_i} - \mathbf{z_j})^2 = ||\mathbf{z_i}||^2 + ||\mathbf{z_j}||^2 - 2\mathbf{z_i}^\mathrm{T}\mathbf{z_j} = b_{ii} + b_{jj} -2b_{ij}$

為了便于討論扮念，令降維后的樣本 $\mathbf{Z}$ 被中心化，那么就可以得到 $\mathbf{B}$ 的行于列之和均為零碧库，即 $\sum^{m}_{i=1}b_{ij} = \sum_{j=1}^{m}b_{ij} = 0$ 柜与。易知道：
$Dist_{\cdot j}^2 = \sum_{i=1}^m Dist_{ij}^2 = \sum_{i=1}^m b_{ii} + b_{jj} -2b_{ij} = \sum_{i=1}^m b_{ii} + b_{jj} -2 \sum_{i=1}^mb_{ij} = tr(\mathbf{B}) + mb_{jj} \\$
$Dist_{i\cdot}^2 =\sum_{j=1}^m Dist_{ij}^2 = \sum_{j=1}^m b_{ii} + b_{jj} -2b_{ij} = \sum_{j=1}^m b_{ii} + b_{jj} -2 \sum_{j=1}^mb_{ij} = tr(\mathbf{B}) + mb_{ii} \\$
$Dist_{\cdot \cdot}^2 =\sum_{i=1}^{m}\sum_{j=1}^{m}Dist_{ij}^2 = \sum_{i=1}^{m} tr(\mathbf{B})+mb_{ii} = m\times tr(\mathbf{B}) + m \times tr(\mathbf{B}) = 2m\times tr(\mathbf{B})$
其中 $tr(\cdot)$ 表示矩陣的跡， $tr(\mathbf{B}) = \sum_{i=1}^{m} b_{ii}$ .則
$b_{ij} = - \frac{1}{2} ( \frac{Dist_{\cdot \cdot}^2}{m^2} - \frac{Dist_{i\cdot}^2}{m} - \frac{Dist_{\cdot j}^2}{m} + Dist_{ij}^2 ) = - \frac{1}{2} [\frac{2}{m}tr(\mathbf{B})-\frac{1}{m}tr(\mathbf{B})-b_{ii} -\frac{1}{m}tr(\mathbf{B})-b_{jj} + b_{ii} + b_{jj} -2b_{ij} ]$
因為所有的 $Dist_{ij}$ 都是已知的嵌灰，那么 $Dist_{\cdot\cdot}^2,Dist_{i\cdot}^2,Dist_{\cdot j}^2$ 都可以算出來弄匕，那么就可以根據原空間的距離矩陣 $\mathbf{D}$ 求取 $d^\prime$ 維空間的內積矩陣 $\mathbf{B}$ 。

接下來對 $\mathbf{B}$ 做特征分解就可以啦伞鲫， $\mathbf{B} = \mathbf{V\Lambda V^{\mathrm{T}}}$ ,其中 $\Lambda = diag(\lambda_1,\lambda_2,\cdots,\lambda_d)$ 為特征值構成的對角矩陣粘茄， $\lambda_1 \ge \lambda_2 \ge \cdots \lambda_d$ , $\mathbf{V}$ 為特征向量矩陣，假定其中有 $d^\star$ 個非零特征值秕脓，它們構成對角矩陣 $\Lambda_\star = diag(\lambda_1,\lambda_2,\cdots,\lambda_{d^\star})$ 柒瓣，令 $\mathbf{V_\star}$ 表示相應的特征向量矩陣，則 $\mathbf{Z}$ 可表示為
$\mathbf{Z} = \Lambda_{\star}^{\frac{1}{2}}\mathbf{V_\star^{\mathrm{T}}} \in \mathbb{R}^{d^\star \times m}$
在現實應用中為了有效的降維吠架，往往不需要降維后的空間距離與原空間相同芙贫，大致相近即可，此時可取 $d^{\prime}(d^{\prime} \ll d)$ 個最大特征值構成的對角矩陣 $\widetilde{\Lambda} = diag(\lambda_1,\lambda_2,\cdots,\lambda_{d^{\prime}})$ ,令 $\widetilde{\mathbf{V}}$ 表示相應的特征向量矩陣傍药，則 $\mathbf{B}$ 可以表示為
$\mathbf{Z} = \widetilde{\Lambda}^{\frac{1}{2}}\widetilde{\mathbf{V}}^{\mathrm{T}} \in \mathbb{R}^{d^\prime \times m}$

最后編輯于：2019.11.03 00:26:56

?著作權歸作者所有,轉載或內容合作請聯(lián)系作者

人面猴
序言：七十年代末磺平，一起剝皮案震驚了整個濱河市，隨后出現的幾起案子拐辽，更是在濱河造成了極大的恐慌拣挪，老刑警劉巖，帶你破解...
沈念sama閱讀 216,544評論 6贊 501
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件俱诸，死亡現場離奇詭異菠劝，居然都是意外死亡，警方通過查閱死者的電腦和手機睁搭，發(fā)現死者居然都...
沈念sama閱讀 92,430評論 3贊 392
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門赶诊，熙熙樓的掌柜王于貴愁眉苦臉地迎上來笼平，“玉大人，你說我怎么就攤上這事舔痪≡⒌鳎” “怎么了？”我有些...
開封第一講書人閱讀 162,764評論 0贊 353
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵锄码，是天一觀的道長夺英。經常有香客問我，道長巍耗，這世上最難降的妖魔是什么秋麸？我笑而不...
開封第一講書人閱讀 58,193評論 1贊 292
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮炬太，結果婚禮上灸蟆，老公的妹妹穿的比我還像新娘。我一直安慰自己亲族，他們只是感情好炒考，可當我...
茶點故事閱讀 67,216評論 6贊 388
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著霎迫，像睡著了一般斋枢。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上知给，一...
開封第一講書人閱讀 51,182評論 1贊 299
城市分裂傳說
那天瓤帚，我揣著相機與錄音，去河邊找鬼涩赢。笑死戈次，一個胖子當著我的面吹牛，可吹牛的內容都是我干的筒扒。我是一名探鬼主播怯邪，決...
沈念sama閱讀 40,063評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼花墩！你這毒婦竟也來了悬秉？” 一聲冷哼從身側響起，我...
開封第一講書人閱讀 38,917評論 0贊 274
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤冰蘑，失蹤者是張志新（化名）和其女友劉穎和泌，沒想到半個月后，有當地人在樹林里發(fā)現了一具尸體祠肥，經...
沈念sama閱讀 45,329評論 1贊 310
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡允跑，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內容為張勛視角年9月15日...
茶點故事閱讀 37,543評論 2贊 332
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時候發(fā)現自己被綠了。大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片聋丝。...
茶點故事閱讀 39,722評論 1贊 348
活死人
序言：一個原本活蹦亂跳的男人離奇死亡，死狀恐怖工碾，靈堂內的尸體忽然破棺而出弱睦，到底是詐尸還是另有隱情，我是刑警寧澤渊额，帶...
沈念sama閱讀 35,425評論 5贊 343
?日本核電站爆炸內幕
正文年R本政府宣布况木，位于F島的核電站，受9級特大地震影響旬迹，放射性物質發(fā)生泄漏火惊。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點故事閱讀 41,019評論 3贊 326
男人毒藥：我在死后第九天來索命
文/蒙蒙一奔垦、第九天我趴在偏房一處隱蔽的房頂上張望屹耐。院中可真熱鬧，春花似錦椿猎、人聲如沸惶岭。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,671評論 0贊 22
一樁弒父案犯眠，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽按灶。三九已至，卻和暖如春筐咧，著一層夾襖步出監(jiān)牢的瞬間鸯旁，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 32,825評論 1贊 269
情欲美人皮
我被黑心中介騙來泰國打工量蕊，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留铺罢，地道東北人。一個月前我還...
沈念sama閱讀 47,729評論 2贊 368
代替公主和親
正文我出身青樓危融，卻偏偏與公主長得像畏铆，于是被迫代替她去往敵國和親。傳聞我的和親對象是個殘疾皇子吉殃，可洞房花燭夜當晚...
茶點故事閱讀 44,614評論 2贊 353

機器學習

1宝与、低維嵌入

2、多維放縮（MDS-multiple dimensional scaling）

推薦閱讀更多精彩內容