數(shù)據(jù)降維方法介紹：
第一種方法：多維尺度分析算法（二）
姓名：何源? 學(xué)號(hào)：21011210073? 學(xué)院：通信工程學(xué)院
【嵌牛導(dǎo)讀】多維尺度分析算法發(fā)展
【嵌牛鼻子】多維尺度分析算法
【嵌牛提問】多維尺度算法有哪些弧可？
【嵌牛正文】
經(jīng)典多維尺度分析算法[1]提鸟，要求已知所有網(wǎng)絡(luò)節(jié)點(diǎn)或者參考數(shù)據(jù)之間的相關(guān)值信息，即每個(gè)點(diǎn)之間的度量信息必須是已知的矾屯。在這種情況下，網(wǎng)絡(luò)中節(jié)點(diǎn)的個(gè)數(shù)為N聋涨，則構(gòu)建的矩陣為NN拓颓，為一個(gè)方陣。對(duì)矩陣進(jìn)行特征值分解孕惜，得到網(wǎng)絡(luò)中各點(diǎn)之間的相互關(guān)系，但是該算法隨著N的大小冪次上升晨炕，算法復(fù)雜度更大衫画。
因此，提出了一種部分連通瓮栗，即部分點(diǎn)之間的距離信息已知的多維尺度分析算法MDS-MAP[2]削罩。由于部分節(jié)點(diǎn)直接的距離信息缺失，但是需要得到該信息構(gòu)建矩陣费奸。所以弥激，引入圖論中的相關(guān)理論，采用Floyd最短路徑估計(jì)距離算法愿阐，估計(jì)節(jié)點(diǎn)之間的距離信息微服，利用估計(jì)的距離信息代替計(jì)算的歐氏距離信息，完成矩陣元素的填充缨历。但是以蕴，可以想到糙麦，估計(jì)距離的偏差導(dǎo)致計(jì)算結(jié)果的誤差以及引入Floyd算法增加了算法復(fù)雜度，改進(jìn)的方法效果并不是很理想丛肮。
因此喳资，在此基礎(chǔ)上提出了一種新的MDS方法，為MDS-MAP（P）算法[3]腾供，其中P表示分塊的意思。將網(wǎng)絡(luò)中的點(diǎn)進(jìn)行分簇處理鲜滩，在每一簇內(nèi)伴鳖，所有點(diǎn)的距離是已知的即精確值，在分簇內(nèi)采用經(jīng)典MDS算法徙硅，將每一個(gè)分簇進(jìn)行縫合榜聂，從而恢復(fù)網(wǎng)絡(luò)中所有點(diǎn)的相對(duì)關(guān)系。每一簇內(nèi)嗓蘑，矩陣維數(shù)降低须肆，降低算法的復(fù)雜度，在縫合的過程中桩皿，存在一定的精度偏差豌汇，但是仍可以接受。
參考文獻(xiàn)
[1] Torgerson W S. Multidimensional scaling: I. Theory and method[J]. Psychometrika, 1952,17(4):401-419. [Online]. Available: https://doi.org/10.1007/BF02288916.
[2]?Shang Y, Ruml W, Zhang Y, et al. Localization from mere connectivity[C]// ACM International Symposium on Mobile Ad Hoc Networking and Computing, ACM, 2003.
[3]?Shang Y, Ruml W. Improved MDS-based localization[C]// IEEE International Conference on Computer Communications, IEEE, 2004.
