大型數據集（R 或 Python）上的 MDS
我有一個大的 400000 $ \times $ 400000 個數據集（相異矩陣），我想對其進行多維縮放。但是，在查看 R 中的通用 cmdscale() 函數後，它最多只需要 46340 $ \times $ 46340 矩陣作為輸入。有什麼辦法可以解決這個問題嗎？另外，Python 是否有同樣的限制（在 sklearn 包中）？
我應該補充一點，這裡的內存不是問題。
僅使用雙精度浮點數來存儲該大小的密集距離矩陣就需要超過 TB。使用標準的 MDS 算法正面攻擊如此大規模的問題可能是不可行的。運行時縮放為，您甚至可能無法在單台機器上將距離矩陣放入內存中。根據您的情況，您可能可以解決它。如何做到這一點取決於您的具體數據和問題，但這裡有幾個例子：
PCA 等效於使用歐幾里得距離度量的經典 MDS。因此，如果這是您要執行的 MDS 類型，您可以改用 PCA。另一個要求是您可以訪問作為向量的原始數據點，而不僅僅是距離矩陣。有許多算法可以在龐大的數據集上有效地運行 PCA。
使用 MDS 的近似形式。如果您想執行經典的 MDS，這種方法可能會起作用。它不需要歐幾里得距離度量或數據的向量空間表示（只需要訪問距離）。Landmark MDS 就是一個很好的例子。第一步是選擇一組較小的“地標點”來代表完整的數據集。這些可以簡單地通過從數據中隨機抽樣來獲得，或者使用快速、貪婪的算法來進一步優化它們。原則上也可以使用聚類，但它的計算成本很高且沒有必要。對地標點執行經典 MDS 以將它們嵌入向量空間中。然後使用地標點的經典 MDS 結果將完整數據集映射到嵌入空間。雖然最初並未如此表述，
3）如果你想執行非經典的MDS，像Landmark MDS這樣的方法是行不通的。這是因為 MDS 的非經典變體是使用優化算法迭代求解的，而不是通過求解特徵值問題。採用以下方法可能會起作用： a) 選擇數據的代表性子樣本。b) 使用您選擇的 MDS 風格將這些點嵌入向量空間。c) 使用二次採樣數據點作為示例，使用非線性回歸方法學習到嵌入空間的映射。需要適當注意學習良好的映射，而不是過度擬合等。 d) 使用學習的映射來獲得整個數據集的嵌入。我記得看過幾篇論文將這種方法描述為一種對非線性降維算法進行樣本外泛化的方法。但是，在我看來，它也可以用作一種有效地逼近非經典 MDS 的方法。可能存在更專業的解決方案；如果是這樣，我會很高興聽到他們的消息。
4）如果絕對必要，可以使用並行化來解決全部問題。例如，對於經典 MDS，您可以在機器之間分配距離矩陣的塊，然後使用並行/分佈式矩陣運算和特徵求解器來執行 MDS。對於非經典 MDS，可能會想出一些方案。但是，這可能是一項艱鉅的任務，而且近似 MDS 很可能會運行得很好。所以，這是一個更好的起點。
參考：
德席爾瓦和特南鮑姆（2004 年）。使用地標點的稀疏多維縮放。
普拉特（2005 年）。FastMap、MetricMap 和 Landmark MDS 都是 Nystrom 算法。