给定图形（例如完全连接），以及所有点之间的距离列表，是否有一种可用的方法来计算实例化图形所需的尺寸数量？
例如。通过构造，说我们的图G具有A，B，C和距离AB = BC = CA = 1。从A（0维）开始，我们在距离1（1维）中添加B，现在我们发现需要第二维以添加C并满足约束。是否存在代码来执行此操作并吐出（在这种情况下）dim（g）= 2？
例如。如果点是照片，以及由GIST算法计算的距离（http://people.csail.mit.mit.edu/torralba/torralba/code/spatialenvelope/），我希望派生的维度可以匹配。由要点。
添加：这是一个基于建议的5 -D Python演示 - 看似完美！"相似性"是距离矩阵。
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个维度后取消。（在冲浪结果上，我尝试将MAX_ITER加倍，并通过每种方式变化的EPS，而不会更改前四个数字的结果。）
事实证明，对于一个指标，一个指标的距离不满足三角形的三角形不等式，平均违规大约等于平均距离的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
查看表的列之间的皮尔逊相关性：
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)
涉及各种指标对三角形不等式的违规数量，所有这些都适用于其顺序的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
给定图形（例如完全连接），以及所有点之间的距离列表，是否有一种可用的方法来计算实例化图形所需的尺寸数量？
是。就图理论而言，这个问题更通用的话题将是"图形嵌入"的一部分。
例如。通过构造，说我们的图G具有A，B，C和距离AB = BC = CA = 1。从A（0维）开始，我们在距离1（1维）中添加B，现在我们发现需要第二维以添加C并满足约束。是否存在代码来执行此操作并吐出（在这种情况下）dim（g）= 2？
这几乎完全是多维缩放的工作方式。
多维缩放（MDS）不是确切地回答"我需要多少维度来表示这个点云/图形？"有一个数字，但它返回足够的信息以近似。
多维缩放方法将尝试找到一个"良好的映射"来减少尺寸的数量，例如从120（在原始空间中）降低到4（在另一个空间中）。因此，在某种程度上，您可以迭代地尝试不同的嵌入，以增加尺寸的数量，并查看每个嵌入的"压力"（或错误）。您所追求的尺寸的数量是错误最小化的第一个数字。
由于它的工作方式，经典的MD可以返回新映射的特征值向量。通过检查本特征值的此矢量，您可以确定要保留多少条条目，以实现原始数据集的（足够好或低错误）表示。
这里的关键概念是"相似性"矩阵，它是图形距离矩阵（您似乎已经拥有的）的奇特名称，无论其语义如何。
嵌入算法通常正在尝试找到一种看起来不同的嵌入，但归根结底，新空间中的点云最终会产生相似（取决于我们能负担得起的错误）距离矩阵。
在代码方面，我相信所有主要的科学计算套件中都有一些可用的东西，但是我可以将您指向Python和Matlab代码示例。
例如。如果点是照片，以及由GIST算法计算的距离（http://people.csail.mit.mit.edu/torralba/torralba/code/spatialenvelope/），我希望派生的维度可以匹配。由要点
不完全是。这是一个很好的用例。在这种情况下，MD会返回什么，或者您将通过降低维度降低的内容是检查代表您的数据集需要多少这些功能。因此，根据场景的不同，或者根据数据集的不同，您可能会意识到，对于整个数据集的足够代表，并不是所有这些功能都是必需的。（此外，您可能还需要查看此链接）。
希望这会有所帮助。
首先，您可以假设任何数据集最多具有4或5的维度。要获得更相关的维度，您需要一百万个元素（或类似的元素）。显然，您已经计算了一个距离。您确定它实际上是一个Relavnt指标吗？对于非常遥远的图像是否有效？也许您可以尝试ISOMAP（Geodesic距离，仅以亲密的邻居开始），看看您的嵌入式空间是否实际上不是欧几里得。