给定一个图（假设为完全连通图）以及所有点之间的距离列表，是否有可用的方法来计算实现该图所需的维数？
例如，通过构建，我们有一个图G，包含点A、B、C，距离AB=BC=CA=1。从A开始（0维），我们添加B点，距离为1（1维），现在我们发现需要添加第2维来添加C点并满足约束条件。是否有代码可以执行此操作并输出（在这种情况下）dim(G) = 2？
例如，如果这些点是照片，并且它们之间的距离由Gist算法计算（http://people.csail.mit.edu/torralba/code/spatialenvelope/），我期望推导出的维度与Gist考虑的图像参数数量相匹配。
补充：这里是一个基于建议的5维Python演示，看起来非常完美！’similarities’是距离矩阵。
import numpy as npfrom sklearn import manifoldsimilarities = [[0., 1., 1., 1., 1., 1.], [1., 0., 1., 1., 1., 1.], [1., 1., 0., 1., 1., 1.], [1., 1., 1., 0., 1., 1.], [1., 1., 1., 1., 0., 1.], [1., 1., 1., 1., 1., 0]]seed = np.random.RandomState(seed=3)for i in [1, 2, 3, 4, 5]: mds = manifold.MDS(n_components=i, max_iter=3000, eps=1e-9, random_state=seed, dissimilarity="precomputed", n_jobs=1) print("%d %f" % (i, mds.fit(similarities).stress_))输出：
1 3.3333332 1.0717973 0.3431464 0.1515315 0.000000我发现当我将此方法应用于我的数据子集（文件名中包含’11’的329张图片之间的距离，使用两种不同的度量标准）时，压力值并未像我预期的那样线性下降到0 – 在大约5维之后就趋于平稳。（在SURF结果上，我尝试了将max_iter加倍，并将eps调整了一个数量级，但前四位数字的结果没有变化。）
结果显示，大约0.02%的三角形不满足三角不等式，平均违规值大约是平均距离的8%，对于检查的一个度量标准而言。
总的来说，我更喜欢使用排序距离的分形维度，因为它不需要选择一个截止值。我将MDS的回答标记为答案，因为它适用于一致的情况。我对分形维度和MDS情况的结果如下所示。
另一个描述性统计数据是三角形违规情况。结果如下。如果有人能推广到更高维度，那将非常有趣（结果和学习Python :-）。
忽略三角不等式问题的MDS结果：
N_dim stress_ SURF_match GIST_match 1 83859853704.027344 913512153794.477295 2 24402474549.902721 238300303503.782837 3 14335187473.611954 107098797170.304825 4 10714833228.199451 67612051749.697998 5 9451321873.828577 49802989323.714806 6 8984077614.154467 40987031663.725784 7 8748071137.806602 35715876839.391762 8 8623980894.453981 32780605791.135693 9 8580736361.368249 31323719065.684353 10 8558536956.142039 30372127335.209297 100 8544120093.395177 28786825401.1785961000 8544192695.435946 28786840008.666389继续前进，以制定一个比较两个结果维度的度量，一个临时选择是将标准设定为
1.1 * stress_at_dim=100由此提出SURF_match的准维度在5到6之间，而GIST_match的准维度在8到9之间。我很好奇是否有人认为这意味着什么 :-）。另一个问题是，对于这两个度量标准在任何维度上的应力相对大小是否有任何有意义的解释。这里有一些结果来提供一些视角。Frac_d是根据Higuchi方法计算的排序距离的分形维度，使用来自IQM的代码，Dim是如上所述的维度。
Method Frac_d Dim stress(100) stress(1)Lab_CIE94 1.1458 3 2114107376961504.750000 33238672000252052.000000Greyscale 1.0490 8 42238951082.465477 1454262245593.781250 HS_12x12 1.0889 19 33661589105.972816 3616806311396.510254HS_24x24 1.1298 35 16070009781.315575 4349496176228.410645 HS_48x48 1.1854 64 7231079366.861403 4836919775090.241211GIST 1.2312 9 28786830336.332951 997666139720.167114HOG_250_words 1.3114 10 10120761644.659481 150327274044.045624HOG_500_words 1.3543 13 4740814068.779779 70999988871.696045HOG_1k_words 1.3805 15 2364984044.641845 38619752999.224922SIFT_1k_words 1.5706 11 1930289338.112194 18095265606.237080SURFFAST_200w 1.3829 8 2778256463.307569 40011821579.313110SRFFAST_250_w 1.3754 8 2591204993.421285 35829689692.319153SRFFAST_500_w 1.4551 10 1620830296.777577 21609765416.960484SURFFAST_1k_w 1.5023 14 949543059.290031 13039001089.887533SURFFAST_4k_w 1.5690 19 582893432.960562 5016304129.389058查看表格列之间的皮尔逊相关系数：
Pearson correlation 2-tailed p-valueFracDim, Dim: (-0.23333296587402277, 0.40262625206429864)Dim, Stress(100): (-0.24513480360257348, 0.37854224076180676)Dim, Stress(1): (-0.24497740363489209, 0.37885820835053186)Stress(100),S(1): ( 0.99999998200931084, 8.9357374620135412e-50)FracDim, S(100): (-0.27516440489210137, 0.32091019789264791)FracDim, S(1): (-0.27528621200454373, 0.32068731053608879)我天真地想知道为什么除了一个之外的所有相关性都是负的，以及可以得出什么结论。使用此代码：
import sysimport numpy as npfrom scipy.stats.stats import pearsonrfile = sys.argv[1]col1 = int(sys.argv[2])col2 = int(sys.argv[3])arr1 = []arr2 = []with open(file, "r") as ins: for line in ins: words = line.split() arr1.append(float(words[col1])) arr2.append(float(words[col2]))narr1 = np.array(arr1)narr2 = np.array(arr2)# normalizenarr1 -= narr1.mean(0)narr2 -= narr2.mean(0)# standardizenarr1 /= narr1.std(0)narr2 /= narr2.std(0)print pearsonr(narr1, narr2)接下来是各种度量标准对三角不等式的违规次数，所有这些都是针对序列中包含’11’的329张图片的：
(1) n_violations/triangles (2) avg violation(3) avg distance(4) avg violation / avg distance n_vio (1) (2) (3) (4)lab 186402 0.031986 157120.407286 795782.437570 0.197441grey 126902 0.021776 1323.551315 5036.899585 0.262771600px 120566 0.020689 1339.299040 5106.055953 0.262296Gist 69269 0.011886 1252.289855 4240.768117 0.295298RGB12^3 25323 0.004345 791.203886 7305.977862 0.10829524^3 7398 0.001269 525.981752 8538.276549 0.06160332^3 5404 0.000927 446.044597 8827.910112 0.05052748^3 5026 0.000862 640.310784 9095.378790 0.07040064^3 3994 0.000685 614.752879 9270.282684 0.06631498^3 3451 0.000592 576.815995 9409.094095 0.061304128^3 1923 0.000330 531.054082 9549.109033 0.055613RGB/600px12^3 25190 0.004323 790.258158 7313.379003 0.10805724^3 7531 0.001292 526.027221 8560.853557 0.06144632^3 5463 0.000937 449.759107 8847.079639 0.05083748^3 5327 0.000914 645.766473 9106.240103 0.07091564^3 4382 0.000752 634.000685 9272.151040 0.068377128^3 2156 0.000370 544.644712 9515.696642 0.057236HueSat12x12 7882 0.001353 950.321873 7555.464323 0.12577924x24 1740 0.000299 900.577586 8227.559169 0.10945948x48 1137 0.000195 661.389622 8653.085004 0.07643464x64 1134 0.000195 697.298942 8776.086144 0.079454 HueSat/600px12x12 6898 0.001184 943.319078 7564.309456 0.12470724x24 1790 0.000307 908.031844 8237.927256 0.11022648x48 1267 0.000217 693.607735 8647.060308 0.08021364x64 1289 0.000221 682.567106 8761.325172 0.077907hog250 53782 0.009229 675.056004 1968.357004 0.342954500 18680 0.003205 559.354979 1431.803914 0.3906651k 9330 0.001601 771.307074 970.307130 0.7949104k 5587 0.000959 993.062824 650.037429 1.527701sift500 26466 0.004542 1267.833182 1073.692611 1.1808161k 16489 0.002829 1598.830736 824.586293 1.9389494k 10528 0.001807 1918.068294 533.492373 3.595306surffast250 38162 0.006549 630.098999 1006.401837 0.626091500 19853 0.003407 901.724525 830.596690 1.0856351k 10659 0.001829 1310.348063 648.191424 2.0215454k 8988 0.001542 1488.200156 419.794008 3.545072是否有人能够推广到更高维度？这是我的初学者代码：
import sysimport timeimport mathimport numpy as npimport sortedcontainersfrom sortedcontainers import SortedSetfrom sklearn import manifoldseed = np.random.RandomState(seed=3)pairs = sys.argv[1]ss = SortedSet()print time.strftime("%H:%M:%S"), "counting/indexing"sys.stdout.flush()with open(pairs, "r") as ins: for line in ins: words = line.split() ss.add(words[0]) ss.add(words[1])N = len(ss)print time.strftime("%H:%M:%S"), "size ", Nsys.stdout.flush()sim = np.diag(np.zeros(N))dtot = 0.0with open(pairs, "r") as ins: for line in ins: words = line.split() i = ss.index(words[0]) j = ss.index(words[1]) #val = math.log(float(words[2])) #val = math.sqrt(float(words[2])) val = float(words[2]) sim[i][j] = val sim[j][i] = val dtot += valavgd = dtot / (N * (N-1))ntri = 0nvio = 0vio = 0.0for i in xrange(1, N): for j in xrange(i+1, N): d1 = sim[i][j] for k in xrange(j+1, N): ntri += 1 d2 = sim[i][k] d3 = sim[j][k] dd = d1 + d2 diff = d3 - dd if (diff > 0.0): nvio += 1 vio += diffavgvio = 0.0if (nvio > 0): avgvio = vio / nvioprint("tot: %d %f %f %f %f" % (nvio, (float(nvio)/ntri), avgvio, avgd, (avgvio/avgd)))这是我尝试使用sklearn的Isomap的方法：
for i in [1, 2, 3, 4, 5]: # nbrs < points iso = manifold.Isomap(n_neighbors=nbrs, n_components=i, eigen_solver="auto", tol=1e-9, max_iter=3000, path_method="auto", neighbors_algorithm="auto") dis = euclidean_distances(iso.fit(sim).embedding_) stress = ((dis.ravel() - sim.ravel()) ** 2).sum() / 2回答：
给定一个图（假设为完全连通图）以及所有点之间的距离列表，是否有可用的方法来计算实现该图所需的维数？
是的。从图论的角度来看，这个问题属于更广泛的主题，称为“图嵌入”。
例如，通过构建，我们有一个图G，包含点A、B、C，距离AB=BC=CA=1。从A开始（0维），我们添加B点，距离为1（1维），现在我们发现需要添加第2维来添加C点并满足约束条件。是否有代码可以执行此操作并输出（在这种情况下）dim(G) = 2？
这几乎正是多维缩放的工作方式。
多维缩放（MDS）并不会直接回答“我需要多少维度来表示这个点云/图？”这个问题，而是返回足够的信息来近似它。
多维缩放方法会尝试找到一个“良好的映射”来减少维数，例如从原始空间的120维减少到另一个空间的4维。因此，你可以迭代尝试不同维数的嵌入，并查看每个嵌入的“应力”（或误差）。你所寻找的维数是第一个导致误差急剧减小的数字。
由于其工作方式，经典MDS可以返回新映射的特征值向量。通过检查这个特征值向量，你可以确定需要保留多少个条目才能实现（足够好或低误差）对原始数据集的表示。
这里的关键概念是“相似性”矩阵，它是图的距离矩阵（你似乎已经有了）的花哨名称，无论其语义如何。
嵌入算法总体上试图找到一个看起来可能不同的嵌入，但最终，在新空间中的点云将最终具有一个类似的（取决于我们能承受多少误差）距离矩阵。
就代码而言，我相信所有主要的科学计算包中都有一些可用的东西，但我能想到的可以指向你的是Python和MATLAB的代码示例。
例如，如果这些点是照片，并且它们之间的距离由Gist算法计算（http://people.csail.mit.edu/torralba/code/spatialenvelope/），我期望推导出的维度与Gist考虑的图像参数数量相匹配
不完全是。这是一个非常好的用例。在这种情况下，MDS返回的，或者你通过降维探测的，将是检查你的数据集需要多少这些特征来表示。因此，根据场景，或者根据数据集，你可能会发现并不是所有这些特征对于整个数据集的足够好表示都是必要的。（此外，你可能还想看看这个链接）。
希望这对你有帮助。
