考虑节点彼此距离的算法 [英] Algorithm for placing nodes on a circle considering their distance to eachother
问题描述
我有以下问题。我有大脑区域和它们之间的相关性。我知道大脑的距离。现在，我们期望相关性与大脑区域之间的距离呈负相关。因此，当我们增加距离时，相关性下降到零。期望这是1 / D ^ 2。
我想可视化关联矩阵以检查异常。我已经有了其他一些实现，例如
导入pylab为px
导入numpy为nx
导入numpy.random为rand
rand。 seed（1）
rt2 = nx.sqrt（2）
N = 10＃脑区域数量
＃使脑区域位置r = 1
区域= []
s =2。
而len（regions）
（如果为nx）。 sqrt（px.dot（p，p））< s：
区域.append（p）
区域= nx.array（区域）
＃px.figure（ ）
px.subplot（2,2,1）
for i in range（len（regions））：
px.text（regions [i，0]，regions [i，1 ]，`i`，fontsize = 15）
px.xlim（-1.1 * s，1.1 * s）
px.ylim（-1.1 * s，1.1 * s）
px。 title（初始位置）
＃未来比较的计算距离矩阵
dm = nx.zeros（（N，N），dty pe = nx.float）
for i in range（N）：
for j in range（N）：
dm [i，j] = nx.sqrt（nx.sum（（ region [i，：]-regions [j，：]）** 2））
def randomize_on_circle（n）：
n个随机角度的返回数组
return 2 * nx.pi * rand.rand（n）
def cost_fcn（d_target，d_actual）：＃距离不匹配的成本
return abs（d_target-d_actual）
def calc_cost（angles）：
给定排列的计算成本
c =0。
对于范围（N-1）中的i： j在范围（i，N）中的
：
＃sqrt（...）是圆上两个点之间的距离（我认为）
c + = cost_fcn（dm [j，i ]，rt2 * nx.sqrt（1-nx.cos（angles [i] -angles [j]）））
return c
defoptimize_step（a，shift = 2 * nx .pi / 360）：
尝试将所有点换一点cw和ccw，然后返回最有益的 b $ b max_benefit，ref_cost =无，无
best_i，best_shift =无，无
对于imove在range（N）中：＃循环通过区域并尝试将每个
cost0 = calc_cost（a）
换成in（shift，-shift）：
a_temp = nx.array（a）
a_temp [imove ] + = da
成本= calc_cost（a_temp）
收益= cost0-成本＃如果max_benefit为None或收益>移动降低成本
的收益。 max_benefit：
max_benefit，best_i，best_shift，ref_cost =收益，imove，da，成本
返回max_benefit，best_i，best_shift，ref_cost
最低成本，best_angles =无，无
cost_initials，cost_plateaus = []，[]
对于范围（30）中的i：＃循环通过圆上的20个随机位置
角度= randomize_on_circle（N）
费用= []
的收益= []
＃通过逐步移动展示位置来逐步优化每个原始安排
count_benefits_neg = 0
count_total，max_total = 0，2000
而count_benefits_neg< 10：＃最好做一个可变步长
b，i，s，c = optimize_step（angles）
angles [i] + = s
cost.append（c）
如果b<附加（b）
。 0：
count_benefits_neg + = 1
count_total + = 1
如果count_total> max_total：
打印count_total，b，成本[-20：]，收益[-20]如果最低成本为None或c< c，则
提高未找到平衡
。 minimum_cost：
best_cost = c
best_angles = nx.array（angles）
cost_graph =成本[：]
Benefit_graph = nx.array（好处）
cost_plateaus.append （c）
cost_initials.append（costs [0]）
px.subplot（2，2，2）
px.plot（cost_graph，'o'）＃make确保成本稳定在
px.title（最佳成本演化）
px.subplot（2，2，3）
px.plot（cost_initials，'o'）
px.plot（cost_plateaus，'d'）
px.title（初始成本和最终成本）
px.subplot（2，2，4）
对于范围内的我（len（best_angles））：
px.text（nx.cos（best_angles [i]），nx.sin（best_angles [i]），`i`，fontsize = 15）
px.xlim（-1.2，1.2）
px.ylim（-1.2，1.2）
px.title（放置在圆圈上）
px.show（）
有趣的是，这似乎导致远处的事物变得遥远，近处的事物变得近乎- ，但随着中端订单混乱，所以也许这会做你想要的吗？ （这也说明了从2D到1D的基本问题。例如，圆圈上的4想要离9更远，但是如果不接近其他数字就无法做到这一点，而在2D中可以做到
您可能需要修改 cost_fnc ，以指定具有圆上点的距离与2D排列的距离不匹配。更改此方法的方式会增加大错误的成本（例如四边形），或者强调正确的大距离的成本，例如 d_target *（abs（d_actual-d_target））等可能会有所帮助。
此外，相对于2D数据，更改圆的大小也会改变外观。 ，并且您可能希望使圆弧比数据小一些，就像我在这里所做的那样，因为这将使圆点分布得更多。 （此处圆具有R = 1，因此只需适当地缩放数据即可。）还要注意，这将对成本进行定量评估不是很有意义，因为最好的安排永远不会变得成本很低，因为某些地区无法
运行多个随机起点的要点是，不断发展的安排可能会卡在局部最小值中。这项技术似乎很有用：沉降有助于使距离正确并降低成本（图3，蓝点=初始随机数，菱形=局部最小值），并且它对某些初始布置的帮助远大于其他布置，因此尝试尝试是一件好事多个初始安排。而且，由于其中一些似乎稳定在15点左右，因此可以肯定这种安排可能具有代表性。
I have the following problem. I have brain regions and correlations between them. The brain regions I know the distances of. Now, we expect the correlations to be negatively correlated to the distance between the brain regions. So when we increase distance correlation goes down to zero. The expectation is that this is by 1/D^2.
I want to visualize my correlation matrix to check for abnormalities. I have already some other implementations like Taiyun's correlation matrix visualization and a simple 2D scatterplot with the 1/D^2 curve as a blue line.
Next I want to have something based on correlation circles.
The brain regions I have created a Node class for. So my brain regions are nodes. I mimic correlation with Edges. My Edges have a sourceNode and a destinationNode and also a correlation and distance so I can couple them to the correct Node. The distance and correlation are needed for table lookup (backcoupling to regionID and regionName etc).
Now what I want is to place all nodes on a circle so that the nodes which have a small distance to eachother are placed close together, and nodes far away from eachother are placed further away. This way the strong edges (which are thick) are close to eachother. And when you have a very strong edge crossing the circle it is awkward and the eye spots it easily. Of course I seek an optimum, as pointed out below a single real answer does not excist.
I have been searching google but since I do not have a clue what to search for I have found no results. I suspect there is a name for a standard algorithm for this but i do not know it. A link to such an algorithm is okay too.
The thing I came up with so far is to arrange the nodes on the circle in such a way that the SUM of all distances is smallest. But for this I need to make a sort of point system so regions which are close to each other and placed close to each other get for instance some +points and points close to each other but placed further away from each other get some downpoints. Now optimize the point algorithm and get highest outcome.
Any tips on this matter? My math is not that great ;). I'm currently googling on circles, nodes, weights..
Note
If you have any other bright ideas to visualize the matrix be sure to PM me about it, or comment here :).
The general problem that you describe doesn't have a solution because you're trying to make a map from a 2D surface to a 1D line that preserves all distances, and this isn't possible. If there was a particular region that you wanted to compare to all others, you could then put all the others around a circle so their distance match the distance to this region (but then the distance between these other regions will be distorted).
But you can certainly do better than just random in approximating the distance. Here's an approach: The first step would be to do multiple random arrangements and then pick the best of these. The next improvement would be to optimize each of these arrangements against some cost function by moving the regions around in small steps until they settle into a local minimum, and then pick the best of these local minima. The results of this is shown in the plots below, and the Python code is further down.
import pylab as px
import numpy as nx
import numpy.random as rand
rand.seed(1)
rt2 = nx.sqrt(2)
N = 10 # number of brain regions
# make brain region locations r=1
regions = []
s = 2.
while len(regions)<N:
p = 2*s*rand.rand(2)-s
if nx.sqrt(px.dot(p,p))<s:
regions.append(p)
regions = nx.array(regions)
#px.figure()
px.subplot(2,2,1)
for i in range(len(regions)):
px.text(regions[i,0], regions[i,1], `i`, fontsize=15)
px.xlim(-1.1*s, 1.1*s)
px.ylim(-1.1*s, 1.1*s)
px.title("inital positions")
# precalc distance matrix for future comparisons
dm = nx.zeros((N,N), dtype=nx.float)
for i in range(N):
for j in range(N):
dm[i,j] = nx.sqrt(nx.sum((regions[i,:]-regions[j,:])**2))
def randomize_on_circle(n):
"""return array of n random angles"""
return 2*nx.pi*rand.rand(n)
def cost_fcn(d_target, d_actual): # cost for distances not matching
return abs(d_target-d_actual)
def calc_cost(angles):
"""calc cost for the given arrangement """
c = 0.
for i in range(N-1):
for j in range(i, N):
# sqrt(...) is distance between two pts on a circle (I think)
c += cost_fcn(dm[j, i], rt2*nx.sqrt(1-nx.cos(angles[i]-angles[j])))
return c
def optimize_step(a, shift=2*nx.pi/360):
"""try shifting all points a bit cw and ccw, and return the most beneficial"""
max_benefit, ref_cost = None, None
best_i, best_shift = None, None
for imove in range(N): # loop through the regions and try moving each one
cost0 = calc_cost(a)
for da in (shift, -shift):
a_temp = nx.array(a)
a_temp[imove] += da
cost = calc_cost(a_temp)
benefit = cost0 - cost # benefit if moving lowers the cost
if max_benefit is None or benefit > max_benefit:
max_benefit, best_i, best_shift, ref_cost = benefit, imove, da, cost
return max_benefit, best_i, best_shift, ref_cost
lowest_cost, best_angles = None, None
cost_initials, cost_plateaus = [], []
for i in range(30): # loop though 20 randomized placements on the circle
angles = randomize_on_circle(N)
costs = []
benefits = []
# optimize each original arrangement by shifting placements one-by-one in small steps
count_benefits_neg = 0
count_total, max_total = 0, 2000
while count_benefits_neg < 10: # better to do a variable step size
b, i, s, c = optimize_step(angles)
angles[i] += s
costs.append(c)
benefits.append(b)
if b < 0:
count_benefits_neg += 1
count_total += 1
if count_total > max_total:
print count_total, b, costs[-20:], benefits[-20]
raise "not finding an equilibrium"
if lowest_cost is None or c < lowest_cost:
lowest_cost = c
best_angles = nx.array(angles)
cost_graph = costs[:]
benefit_graph = nx.array(benefits)
cost_plateaus.append(c)
cost_initials.append(costs[0])
px.subplot(2, 2, 2)
px.plot(cost_graph, 'o') # make sure the cost is leveling off
px.title("cost evoloution of best")
px.subplot(2, 2, 3)
px.plot(cost_initials, 'o')
px.plot(cost_plateaus, 'd')
px.title("initial and final costs")
px.subplot(2, 2, 4)
for i in range(len(best_angles)):
px.text(nx.cos(best_angles[i]), nx.sin(best_angles[i]), `i`, fontsize=15)
px.xlim(-1.2, 1.2)
px.ylim(-1.2, 1.2)
px.title("positioned on circle")
px.show()
Interestingly, this seems to have resulted in far things being far-ish, and near things being near-ish, but with the mid-range orders messed up, so maybe this will do what you want? (This also illustrates the fundamental problem in going from 2D to 1D. For example, on the circle the 4 wants to be further from the 9, but it can't do that without getting closer to the other numbers, whereas in 2D it could just go out to the side.)
You'll probably want to modify cost_fnc which specifies the penalty for having the distances of points on the circle not match the distance from the 2D arrangement. Changing this in a way to increase the costs for large errors (say a quadradic), or to emphasise a cost for the large distance being right, say d_target*(abs(d_actual-d_target)), etc, might help.
Also, changing the size of the circle relative to the size of the 2D data will change the look of this quite a lot, and you probably will want to circle somewhat smaller than the data, as I've done here, as this will spread the points around the circle more. (Here the circle has R=1, so just scale the data appropriately.) Also note that this will make a quantitative assessment of the cost to be not very meaningful as the best arrangements never get very to very low cost since some regions can never be as far apart as in the 2D data.
The point of running multiple random starts is that the evolving arrangement can get stuck in local minima. This technique seems to be useful: settling helps in getting the distance right and the costs down (plot #3, blue dots=initial random, diamonds=local minimum) and it helps some initial arrangements much more than others, so it's good to try multiple initial arrangements. Also, since a number of these seem to settle to around 15 it gives some confidence that this arrangement might be representative.
这篇关于考虑节点彼此距离的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
