计算图形的空间维度
calculate the spatial dimension of a graph
给定一个图（比如全连接图）和所有点之间的距离列表，是否有可用的方法来计算实例化图所需的维数？
例如通过构造，假设我们有图 G，其中点 A、B、C 和距离 AB=BC=CA=1。从 A（0 维）开始，我们在距离 1（1 维）处添加 B，现在我们发现需要第二维来添加 C 并满足约束。是否存在执行此操作的代码并吐出（在本例中）dim(G) = 2？
例如如果这些点是照片，并且它们之间的距离是通过 Gist 算法计算的 (http://people.csail.mit.edu/torralba/code/spatialenvelope/)，我希望导出的维度与 Gist 考虑的图像参数数量相匹配。
补充：这是一个基于建议的 5-d python 演示 - 看似完美！
'similarities'是距离矩阵。
import numpy as np
from sklearn import manifold
similarities = [[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.333333
2 1.071797
3 0.343146
4 0.151531
5 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.178596
1000 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.000000
Greyscale 1.0490 8 42238951082.465477 1454262245593.781250
HS_12x12 1.0889 19 33661589105.972816 3616806311396.510254
HS_24x24 1.1298 35 16070009781.315575 4349496176228.410645
HS_48x48 1.1854 64 7231079366.861403 4836919775090.241211
GIST 1.2312 9 28786830336.332951 997666139720.167114
HOG_250_words 1.3114 10 10120761644.659481 150327274044.045624
HOG_500_words 1.3543 13 4740814068.779779 70999988871.696045
HOG_1k_words 1.3805 15 2364984044.641845 38619752999.224922
SIFT_1k_words 1.5706 11 1930289338.112194 18095265606.237080
SURFFAST_200w 1.3829 8 2778256463.307569 40011821579.313110
SRFFAST_250_w 1.3754 8 2591204993.421285 35829689692.319153
SRFFAST_500_w 1.4551 10 1620830296.777577 21609765416.960484
SURFFAST_1k_w 1.5023 14 949543059.290031 13039001089.887533
SURFFAST_4k_w 1.5690 19 582893432.960562 5016304129.389058
查看 table 的列之间的 Pearson 相关性：
Pearson correlation 2-tailed p-value
FracDim, 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 sys
import numpy as np
from scipy.stats.stats import pearsonr
file = 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)
# normalize
narr1 -= narr1.mean(0)
narr2 -= narr2.mean(0)
# standardize
narr1 /= 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.197441
grey 126902 0.021776 1323.551315 5036.899585 0.262771
600px 120566 0.020689 1339.299040 5106.055953 0.262296
Gist 69269 0.011886 1252.289855 4240.768117 0.295298
RGB
12^3 25323 0.004345 791.203886 7305.977862 0.108295
24^3 7398 0.001269 525.981752 8538.276549 0.061603
32^3 5404 0.000927 446.044597 8827.910112 0.050527
48^3 5026 0.000862 640.310784 9095.378790 0.070400
64^3 3994 0.000685 614.752879 9270.282684 0.066314
98^3 3451 0.000592 576.815995 9409.094095 0.061304
128^3 1923 0.000330 531.054082 9549.109033 0.055613
RGB/600px
12^3 25190 0.004323 790.258158 7313.379003 0.108057
24^3 7531 0.001292 526.027221 8560.853557 0.061446
32^3 5463 0.000937 449.759107 8847.079639 0.050837
48^3 5327 0.000914 645.766473 9106.240103 0.070915
64^3 4382 0.000752 634.000685 9272.151040 0.068377
128^3 2156 0.000370 544.644712 9515.696642 0.057236
HueSat
12x12 7882 0.001353 950.321873 7555.464323 0.125779
24x24 1740 0.000299 900.577586 8227.559169 0.109459
48x48 1137 0.000195 661.389622 8653.085004 0.076434
64x64 1134 0.000195 697.298942 8776.086144 0.079454
HueSat/600px
12x12 6898 0.001184 943.319078 7564.309456 0.124707
24x24 1790 0.000307 908.031844 8237.927256 0.110226
48x48 1267 0.000217 693.607735 8647.060308 0.080213
64x64 1289 0.000221 682.567106 8761.325172 0.077907
hog
250 53782 0.009229 675.056004 1968.357004 0.342954
500 18680 0.003205 559.354979 1431.803914 0.390665
1k 9330 0.001601 771.307074 970.307130 0.794910
4k 5587 0.000959 993.062824 650.037429 1.527701
sift
500 26466 0.004542 1267.833182 1073.692611 1.180816
1k 16489 0.002829 1598.830736 824.586293 1.938949
4k 10528 0.001807 1918.068294 533.492373 3.595306
surffast
250 38162 0.006549 630.098999 1006.401837 0.626091
500 19853 0.003407 901.724525 830.596690 1.085635
1k 10659 0.001829 1310.348063 648.191424 2.021545
4k 8988 0.001542 1488.200156 419.794008 3.545072
有人能概括到更高的维度吗？这是我的初学者代码：
import sys
import time
import math
import numpy as np
import sortedcontainers
from sortedcontainers import SortedSet
from sklearn import manifold
seed = 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 ", N
sys.stdout.flush()
sim = np.diag(np.zeros(N))
dtot = 0.0
with 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 += val
avgd = dtot / (N * (N-1))
ntri = 0
nvio = 0
vio = 0.0
for 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 += diff
avgvio = 0.0
if (nvio > 0):
avgvio = vio / nvio
print("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
Given a graph (say fully-connected), and a list of distances between all the points, is there an available way to calculate the number of dimensions required to instantiate the graph?
是的。就图论而言，这个问题属于更一般的主题，称为 "Graph Embedding".
E.g. by construction, say we have graph G with points A, B, C and distances AB=BC=CA=1. Starting from A (0 dimensions) we add B at distance 1 (1 dimension), now we find that a 2nd dimension is needed to add C and satisfy the constraints. Does code exist to do this and spit out (in this case) dim(G) = 2?
这几乎就是 Multidimensional Scaling 的工作方式。
多维缩放 (MDS) 不能准确回答 "How many dimensions would I need to represent this point cloud / graph?" 的问题，但它 return 有足够的信息来近似它。
Multidimensional Scaling methods 将尝试找到一个 "good mapping" 来减少维数，比如从 120（在原来的 space 中）减少到 4（在另一个 space 中） .因此，在某种程度上，您可以迭代地尝试不同的嵌入来增加维数，并查看每个嵌入的 "stress"（或错误）。您所追求的维数是误差突然最小化的第一个数。
由于其工作方式，Classical MDS 可以 return 新映射的特征值向量。通过检查这个特征值向量，您可以确定需要保留多少条目才能实现原始数据集的（足够好或低错误）表示。
这里的关键概念是 "similarity" 矩阵，它是图形距离矩阵（您似乎已经有了）的奇特名称，与它的语义无关。
嵌入算法，一般来说，试图找到一个可能看起来不同的嵌入，但在一天结束时，新 space 中的点云最终将具有相似的（取决于如何我们可以承受的误差）距离矩阵。
就代码而言，我确信所有主要的科学计算包中都有一些可用的东西，但我可以立即向您指出 Python and MATLAB 代码示例。
E.g. if the points are photos, and the distances between them calculated by the Gist algorithm (http://people.csail.mit.edu/torralba/code/spatialenvelope/), I would expect the derived dimension to match the number image parameters considered by Gist
不完全是。这是一个非常好的用例。在这种情况下，什么 MDS return，或者你将用 dimensionality reduction in general would be to check how many of these features seem to be required to represent your dataset. Therefore, depending on the scenes, or, depending on the dataset, you might realise that not all of these features are necessary for a good enough representation of the whole dataset. (In addition, you might want to have a look at this link 探测什么）。
希望这对您有所帮助。
首先，您可以假设任何数据集的维度最多为 4 或 5。要获得更多相关维度，您需要一百万个元素（或类似数量）。
显然，您已经计算了距离。您确定它实际上是一个相关指标吗？对于距离很远的图像是否有效？也许您可以尝试 Isomap（测地线距离，仅从近邻开始）并查看您嵌入的 space 是否实际上不是欧几里得。
给定一个图（比如全连接图）和所有点之间的距离列表，是否有可用的方法来计算实例化图所需的维数？
例如通过构造，假设我们有图 G，其中点 A、B、C 和距离 AB=BC=CA=1。从 A（0 维）开始，我们在距离 1（1 维）处添加 B，现在我们发现需要第二维来添加 C 并满足约束。是否存在执行此操作的代码并吐出（在本例中）dim(G) = 2？
例如如果这些点是照片，并且它们之间的距离是通过 Gist 算法计算的 (http://people.csail.mit.edu/torralba/code/spatialenvelope/)，我希望导出的维度与 Gist 考虑的图像参数数量相匹配。
补充：这是一个基于建议的 5-d python 演示 - 看似完美！ 'similarities'是距离矩阵。
import numpy as np
from sklearn import manifold
similarities = [[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.333333
2 1.071797
3 0.343146
4 0.151531
5 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.178596
1000 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.000000
Greyscale 1.0490 8 42238951082.465477 1454262245593.781250
HS_12x12 1.0889 19 33661589105.972816 3616806311396.510254
HS_24x24 1.1298 35 16070009781.315575 4349496176228.410645
HS_48x48 1.1854 64 7231079366.861403 4836919775090.241211
GIST 1.2312 9 28786830336.332951 997666139720.167114
HOG_250_words 1.3114 10 10120761644.659481 150327274044.045624
HOG_500_words 1.3543 13 4740814068.779779 70999988871.696045
HOG_1k_words 1.3805 15 2364984044.641845 38619752999.224922
SIFT_1k_words 1.5706 11 1930289338.112194 18095265606.237080
SURFFAST_200w 1.3829 8 2778256463.307569 40011821579.313110
SRFFAST_250_w 1.3754 8 2591204993.421285 35829689692.319153
SRFFAST_500_w 1.4551 10 1620830296.777577 21609765416.960484
SURFFAST_1k_w 1.5023 14 949543059.290031 13039001089.887533
SURFFAST_4k_w 1.5690 19 582893432.960562 5016304129.389058
查看 table 的列之间的 Pearson 相关性：
Pearson correlation 2-tailed p-value
FracDim, 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 sys
import numpy as np
from scipy.stats.stats import pearsonr
file = 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)
# normalize
narr1 -= narr1.mean(0)
narr2 -= narr2.mean(0)
# standardize
narr1 /= 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.197441
grey 126902 0.021776 1323.551315 5036.899585 0.262771
600px 120566 0.020689 1339.299040 5106.055953 0.262296
Gist 69269 0.011886 1252.289855 4240.768117 0.295298
RGB
12^3 25323 0.004345 791.203886 7305.977862 0.108295
24^3 7398 0.001269 525.981752 8538.276549 0.061603
32^3 5404 0.000927 446.044597 8827.910112 0.050527
48^3 5026 0.000862 640.310784 9095.378790 0.070400
64^3 3994 0.000685 614.752879 9270.282684 0.066314
98^3 3451 0.000592 576.815995 9409.094095 0.061304
128^3 1923 0.000330 531.054082 9549.109033 0.055613
RGB/600px
12^3 25190 0.004323 790.258158 7313.379003 0.108057
24^3 7531 0.001292 526.027221 8560.853557 0.061446
32^3 5463 0.000937 449.759107 8847.079639 0.050837
48^3 5327 0.000914 645.766473 9106.240103 0.070915
64^3 4382 0.000752 634.000685 9272.151040 0.068377
128^3 2156 0.000370 544.644712 9515.696642 0.057236
HueSat
12x12 7882 0.001353 950.321873 7555.464323 0.125779
24x24 1740 0.000299 900.577586 8227.559169 0.109459
48x48 1137 0.000195 661.389622 8653.085004 0.076434
64x64 1134 0.000195 697.298942 8776.086144 0.079454
HueSat/600px
12x12 6898 0.001184 943.319078 7564.309456 0.124707
24x24 1790 0.000307 908.031844 8237.927256 0.110226
48x48 1267 0.000217 693.607735 8647.060308 0.080213
64x64 1289 0.000221 682.567106 8761.325172 0.077907
hog
250 53782 0.009229 675.056004 1968.357004 0.342954
500 18680 0.003205 559.354979 1431.803914 0.390665
1k 9330 0.001601 771.307074 970.307130 0.794910
4k 5587 0.000959 993.062824 650.037429 1.527701
sift
500 26466 0.004542 1267.833182 1073.692611 1.180816
1k 16489 0.002829 1598.830736 824.586293 1.938949
4k 10528 0.001807 1918.068294 533.492373 3.595306
surffast
250 38162 0.006549 630.098999 1006.401837 0.626091
500 19853 0.003407 901.724525 830.596690 1.085635
1k 10659 0.001829 1310.348063 648.191424 2.021545
4k 8988 0.001542 1488.200156 419.794008 3.545072
有人能概括到更高的维度吗？这是我的初学者代码：
import sys
import time
import math
import numpy as np
import sortedcontainers
from sortedcontainers import SortedSet
from sklearn import manifold
seed = 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 ", N
sys.stdout.flush()
sim = np.diag(np.zeros(N))
dtot = 0.0
with 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 += val
avgd = dtot / (N * (N-1))
ntri = 0
nvio = 0
vio = 0.0
for 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 += diff
avgvio = 0.0
if (nvio > 0):
avgvio = vio / nvio
print("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
Given a graph (say fully-connected), and a list of distances between all the points, is there an available way to calculate the number of dimensions required to instantiate the graph?
是的。就图论而言，这个问题属于更一般的主题，称为 "Graph Embedding".
E.g. by construction, say we have graph G with points A, B, C and distances AB=BC=CA=1. Starting from A (0 dimensions) we add B at distance 1 (1 dimension), now we find that a 2nd dimension is needed to add C and satisfy the constraints. Does code exist to do this and spit out (in this case) dim(G) = 2?
这几乎就是 Multidimensional Scaling 的工作方式。
多维缩放 (MDS) 不能准确回答 "How many dimensions would I need to represent this point cloud / graph?" 的问题，但它 return 有足够的信息来近似它。
Multidimensional Scaling methods 将尝试找到一个 "good mapping" 来减少维数，比如从 120（在原来的 space 中）减少到 4（在另一个 space 中） .因此，在某种程度上，您可以迭代地尝试不同的嵌入来增加维数，并查看每个嵌入的 "stress"（或错误）。您所追求的维数是误差突然最小化的第一个数。
由于其工作方式，Classical MDS 可以 return 新映射的特征值向量。通过检查这个特征值向量，您可以确定需要保留多少条目才能实现原始数据集的（足够好或低错误）表示。
这里的关键概念是 "similarity" 矩阵，它是图形距离矩阵（您似乎已经有了）的奇特名称，与它的语义无关。
嵌入算法，一般来说，试图找到一个可能看起来不同的嵌入，但在一天结束时，新 space 中的点云最终将具有相似的（取决于如何我们可以承受的误差）距离矩阵。
就代码而言，我确信所有主要的科学计算包中都有一些可用的东西，但我可以立即向您指出 Python and MATLAB 代码示例。
E.g. if the points are photos, and the distances between them calculated by the Gist algorithm (http://people.csail.mit.edu/torralba/code/spatialenvelope/), I would expect the derived dimension to match the number image parameters considered by Gist
不完全是。这是一个非常好的用例。在这种情况下，什么 MDS return，或者你将用 dimensionality reduction in general would be to check how many of these features seem to be required to represent your dataset. Therefore, depending on the scenes, or, depending on the dataset, you might realise that not all of these features are necessary for a good enough representation of the whole dataset. (In addition, you might want to have a look at this link 探测什么）。
希望这对您有所帮助。
首先，您可以假设任何数据集的维度最多为 4 或 5。要获得更多相关维度，您需要一百万个元素（或类似数量）。 显然，您已经计算了距离。您确定它实际上是一个相关指标吗？对于距离很远的图像是否有效？也许您可以尝试 Isomap（测地线距离，仅从近邻开始）并查看您嵌入的 space 是否实际上不是欧几里得。