假設我有一系列數千個節點。對於每對節點，我都有一個距離度量。這個距離度量可以是一個物理距離（比如每個節點的x，y座標）或者其他使節點相似的東西。使用距離度量製作完全連接的圖形
每個節點可以連接至多達N個其它節點，其中N是小 - 說6.
如何可以構造完全連接的曲線圖（例如，I可以按照圖中的邊的任意兩個節點之間行進）同時最小化所有圖形節點之間的總距離。
這就是我不想找任何穿越的總距離最小化的曲線圖，但其中對於任何一個節點從該節點的所有環節的總距離最小化。
我不需要在絕對最低 - 因爲我認爲這是可能的NP完全問題 - 但得到的曲線圖接近真正的絕對最低的一個相對有效的方法。
，你選擇的邊緣，直到所有頂點具有6個鄰居我建議貪心試探法。例如，從最小生成樹開始。然後，對於一些隨機的頂點對，找到它們之間的最短路徑，使用至多一個未選中的邊（在圖的兩個副本上使用Dijkstra算法與選定的邊，由未選中的邊連接）。然後選擇總共產生最大距離減少的邊緣。
您可以使用一個內核只爲在一定截止距離節點創建邊緣。
如果你想非加權邊緣你可以簡單地用一個基本的截止開始。如果d（v1，v2）< R
您可以在2點之間添加邊緣您可以調整截斷值R以獲得節點之間正確的平均邊數。
如果希望加權圖，優選的內核往往是高斯之一，
K（X，Y）= E ^（ - d（X，Y）^ 2/D_0）
與截止到防範節點過低值。 d_0是調整參數以獲得最適合您的權重。
在查找引用，我發現，我沒有這個博客文章，但似乎很說明，有許多詳細資料：http://charlesmartin14.wordpress.com/2012/10/09/spectral-clustering/
這種方法在使用基於圖的半監督機器學習任務，例如在圖像識別中，您可以在其中標記對象的一小部分，並具有有效的標籤傳播來識別整個對象。
你可以在谷歌搜索：半監督與圖形
我不知道學習，但對於修改的MST？我認爲這個錯誤是可以容忍的。 – Fallen