今度考えるのは、自然な例として、発言者間の距離が定義されているようなものを考える。ここで言う"距離"とは、実際の発言者間の物理的な距離だけでなく、それぞれの間の関係性や声の大きさなどの概念を含んだ一般的な意味での距離である。実際には、そのように距離の計算に用いるパラメータが$b$(<$a$)個あるとして、そのパラメータによる元に対して距離を考える。
簡単な例として$b$次元ユークリッド距離を取ることを考える。すなわち$b$個の数の組み合わせによって表される集合$X$があった時、
距離関数$d: X \times X \rightarrow R$が
$$d(x, y) = \sqrt{\sum_{i=1}^{b}(x_{i}-y_{i})^{2}}\ \ ,\ x,y\in X$$と書けることを意味する。
NOTE:実際の場合には、各データ同士の相関を考慮に入れたマハラノビス距離などのほうが適当な場合もあるかもしれないが、まずはイメージしやすいということでユークリッド距離を考えた。
以下では、記述の簡単にするため、発言者$i$と発言者$j$の間の距離を$d_{ij}$と書くことにする。
時刻$k$に$i$が発言を行い、その後時刻$k+1$に$j$が発言$x_{k+1}^{j}$を行う確率$p_{k}(i,j)$は、距離$d_{ij}$の関数として、次のようにできる。
$$p_{k}(i,j) = \frac{g_{k}(d_{ij})}{\sum_{j} g_{k}(d_{ij})}$$この$g$の選び方によって、距離の大きさがどのように確率に重みを持たせるかということが決定される。一般に$g$は時刻$k$によって変化してもいいので、添字$k$をつけて時刻$k$における関数であることを表した。
単純な例として$g_{k}(d) = const.,\ ^{\forall}k, d\in R^{1}$とすると、距離に依らず発言者が選ばれるわけなので、例1の発言者の選び方と同じである。
$g(d)$は$[0, +\infty]$で定義される非負の有界な実関数である。
ex)
$$g(d) = \frac{1}{d+1}$$$$g(d) = e^{-d}$$$$g(d) = \left\{ \begin{array}{ll} c & (0\le d \le 1/c) \\ 1/d & (d>1/c) \\ \end{array}\right., \ \ c>0$$しかし、ここで注意すべき点として、どの発言者が発言するにしても、例1で考えたように、どの発言者も$[0,1]$の一様乱数を取るなら、結局、意見について見た時の試行は同じことをしており、誰が発言したかは本質的な問題にはならないことが分かる。
以下に示すのは上に示すような簡単なことに気付かないまま色々機能をつけてしまったもの。
はじめに人の配置をGUIで設定、その後startを押すと、[-1,1]ほどの領域にスケールし直され、その位置関係でシミュレーションが実行される。Notebook上ではインタラクティブに表示されないが、これを通常のプログラムとして走らせるとちゃんとインタラクティブに繋がれていく様子が分かる。その後は各発言者の発言回数とリンクのつながり方に関して、その重みを反映したグラフを表示する。また、各時刻においての発言に対して張られたリンクの数のグラフとその累積のグラフを生成する。
%matplotlib inline
from Tkinter import *
import matplotlib.pyplot as plt
import numpy as np
import collections
import operator
def accumulate(iterable, func=operator.add):
'Return running totals'
# accumulate([1,2,3,4,5]) --> 1 3 6 10 15
# accumulate([1,2,3,4,5], operator.mul) --> 1 2 6 24 120
it = iter(iterable)
total = next(it)
yield total
for element in it:
total = func(total, element)
yield total
class Person(object):
def __init__(self, ideas_num=10, place=(0., 0.), **kwargs):
# 意見は0~1の間の値を一様に取りうる
self.ideas = list(np.random.random(ideas_num))
# 発言者の実際の位置が2次元の座標として表せる
self.place = place
# その他の特徴量
for (k, v) in kwargs.items():
setattr(self, k, v)
def distance(self, p):
# 人pと自分との間の距離(ユークリッド距離)
d = np.sqrt((self.place[0]-p.place[0])**2 + (self.place[1]-p.place[1])**2)
return d
class meeting(object):
def __init__(self, N):
# 会議の参加人数
self.N = N
# 意見の時系列
self.ideas = []
# 発言者の時系列
self.speaker = []
# 時刻
self.k = 0
self.K = 100
# 張られたリンク(時刻, 時刻)のタプルで表現する
self.links = []
# リンクの数(各時刻)
self.l = [0]
# リンクの数(累計)
self.L = [0]
def g(self, x):
# 発言者の物理的距離に対する関数
return np.exp(-x)
def p(self, i):
# 参加者の中で話せる人のみを対象に
_N = []
for k in range(1, self.N+1):
if len(self.members[k].ideas):
_N.append(k)
# それらの人たちに対し、関数gによる重み付けの確率を付与
w = []
for n in _N:
d = self.members[n].distance(i)
w.append(self.g(d))
w = np.array(w)
sum_ = np.sum(w)
_p = list(w/sum_)
p = list(accumulate(_p))
rn = np.random.rand()
nm = 0
while True:
if p[nm] > rn:
break
else:
nm += 1
# その確率で選ばれた人の名前を返す
j = _N[nm]
return j
def q(self, j):
# 発言者jが選ばれた時、持っている意見から等確率で意見を取り出す
x_j = self.members[j]
return np.random.rand() #x_j.ideas.pop()
def distance(self, x, y):
# 意見の近さを絶対値で表現
d = np.abs(x - y)
if d == 0:
return self.radius + 1
else:
return d
def connect(self):
l = 0
for i, v in enumerate(self.ideas[:-1]):
# k番目の意見と意見が近い時、それらノードの間にリンクを形成する
if self.distance(v, self.ideas[self.k]) < self.radius:
self.links.append((i, self.k))
l += 1
return l
def check_agreement(self):
# 合意チェック 参加人数Nによる関数
def L(N):
return N**2
#if self.l[-1] > L(self.N):
if self.k > self.K:
return True
else:
return False
def check_ideas(self):
for k in range(1, self.N+1):
if len(self.members[k].ideas):
return True
return False
def f_L(self):
# リンクから会議の評価
# 単純に会議終了時に得られたリンクの数を返す
return self.L[-1]
def f_T(self):
# 会議に必要な時間の評価
# 単純に必要な時間kを返す
return self.k
def f(self):
# f_Lとf_Tを使った評価関数f
return self.f_L() - self.f_T()
def end(self):
# 会議の通常終了、各定義量の計算や受け渡しなどはここで
plt.ioff()
plt.show()
# ネットワーク図を描画
link_s = [(a, b) for a, b in zip(self.speaker[:-1], self.speaker[1:])]
counter_links = collections.Counter(link_s)
for link, lw in counter_links.items():
ix = self.members[link[0]].place[0]
iy = self.members[link[0]].place[1]
jx = self.members[link[1]].place[0]
jy = self.members[link[1]].place[1]
_x, _y = ((ix+jx)/2, (iy+jy)/2)
if link[0] == link[1]:
continue
elif link[0] < link[1]:
color = 'black'
va = 'bottom'
else:
color = 'red'
va = 'top'
plt.plot([ix, jx], [iy, jy], color=color, lw=lw*4/self.k+1)
plt.text(_x, _y, '(%d,%d)' % (link[0], link[1]),
color=color, va=va)
counter = collections.Counter(self.speaker)
for key, i in self.members.items():
x = i.place[0]
y = i.place[1]
size = counter[key] * 30
plt.scatter(x, y, s=size)
plt.text(x, y, str(key), color='green')
plt.show()
# 各時刻に追加されたリンク数のグラフ
r = self.radius
k = np.arange(self.k + 1)
y = (-r**2 + 2*r)*k
delta = np.sqrt((-r**4 + 4*r**3 - 5*r**2 + 2*r)*k)
y1 = y + delta
y2 = y - delta
plt.fill_between(k, y1, y2, facecolor='green', alpha=0.2)
plt.plot(k, self.l)
plt.plot(k, y)
plt.xlabel(r"Time: $k$")
plt.ylabel(r"A number of edges for each time: $l$")
plt.show()
# リンク数の累積グラフ
plt.plot(k, self.L)
plt.plot(k, (-self.radius**2 + 2*self.radius)*k**2/2.)
plt.xlabel(r"Time: $k$")
plt.ylabel(r"A number of edges: $L$")
plt.show()
# 時系列で発言者の表示
# print 'self.speaker:', self.speaker
# 評価関数を通した結果
# print 'self.f', self.f()
def end2(self):
# 会議の異常終了(発言者が発言できなくなる)
pass
def init(self):
x = [i.place[0] for i in self.members.values()]
y = [i.place[1] for i in self.members.values()]
plt.scatter(x, y)
plt.ion()
plt.draw()
def callback(self):
# print 'speaker:', self.speaker[-1]
# print 'link:', self.l[-1]
ix = self.members[self.speaker[-2]].place[0]
iy = self.members[self.speaker[-2]].place[1]
jx = self.members[self.speaker[-1]].place[0]
jy = self.members[self.speaker[-1]].place[1]
plt.plot([ix, jx], [iy, jy])
plt.text((ix+jx)/2, (iy+jy)/2, '%d:(%d,%d)'
% (self.k, self.speaker[-2], self.speaker[-1]))
plt.draw()
def progress(self):
self.init()
# はじめに1が発言するとする
self.ideas.append(self.q(1))
self.speaker.append(1)
while True:
j = self.p(self.members[self.speaker[-1]])
self.ideas.append(self.q(j))
self.speaker.append(j)
self.k += 1
self.l.append(self.connect())
self.L.append(len(self.links))
self.callback()
if self.check_agreement():
print "\nnormal end"
self.end()
break
if not self.check_ideas():
print "\nno one can speak"
self.end2()
break
class Main:
def __init__(self, radius=0.3):
N = 6
self.app = meeting(N)
self.app.radius = radius
window = Window(N, main=self.app)
window.display()
class Window(object):
def __init__(self, N, main):
self.root = Tk()
self.main = main
self.width = 640
self.height = 480
self.canvas = Canvas(self.root, width=self.width, height=self.height)
self.var = StringVar()
self.oval(self.canvas, N)
self.canvas.bind('<Motion>', self.pointer)
self.canvas.pack()
label = Label(self.root, textvariable=self.var, font='Ubuntu 9')
label.pack(side='left')
b1 = Button(self.root, text='start', command=self.b1_clicked)
b1.pack(side='right')
b2 = Button(self.root, text='save', command=self.b2_clicked)
b2.pack(side='right')
def oval(self, canvas, N=6):
self.members = dict()
deg = np.linspace(0., 360., N, endpoint=False)
radius = 20
self.r = int((min(self.height, self.width)/2-radius)*0.9)
self.centerx = int(self.width/2)
self.centery = int(self.height/2)
for n in range(1, N+1):
rad = np.radians(deg[n-1])
self.members[n] = Oval(canvas, n,
self.centerx+self.r*np.cos(rad),
self.centery+self.r*np.sin(rad),
radius, self.var)
def pointer(self, event):
self.var.set("(%d,%d)" % (event.x, event.y))
def b1_clicked(self):
self.main.members = dict()
for n in range(1, self.main.N+1):
x = (self.members[n].x-self.centerx)/float(self.r)
y = (self.members[n].y-self.centery)/float(self.r)
self.main.members[n] = Person(place=(x, y))
self.main.progress()
self.root.destroy()
def b2_clicked(self):
import tkFileDialog
import os
fTyp = [('eps file', '*.eps'), ('all files', '*')]
filename = tkFileDialog.asksaveasfilename(filetypes=fTyp,
initialdir=os.getcwd(),
initialfile='figure_1.eps')
if filename is None:
return
try:
self.canvas.postscript(file=filename)
except TclError:
print """
TclError: Cannot save the figure.
Canvas Window must be alive for save."""
return 1
def display(self):
self.root.mainloop()
class Oval:
def __init__(self, canvas, id, x, y, r, var):
self.c = canvas
self.x = x
self.y = y
self.var = var
self.tag = str(id)
self.c.create_oval(x-r, y-r, x+r, y+r, outline='', fill='#069', tags=self.tag)
self.c.tag_bind(self.tag, '<Button-1>', self.pressed)
self.c.tag_bind(self.tag, '<Button1-Motion>', self.dragging)
def pressed(self, event):
self.x = event.x
self.y = event.y
def dragging(self, event):
self.c.move(self.tag, event.x - self.x, event.y - self.y)
self.x = event.x
self.y = event.y
main = Main(radius=1/3.)
normal end
これらのグラフからも確かめられることだが、例1で考えたとおり、意見の近さに関する閾値$r$を定めて、その範囲に既になされた発言が存在するときにリンクを張るようにすると、時刻$k$にある点が選ばれたときに張られるリンクの数は、二項分布$B(k, p)$にしたがっていたので、その期待値は試行回数$k$に比例する($E(X) = kp(x,r)$)(実際には複数回これを実施して平均を取ってやる必要がある←あとでやる?:GUIとか全部切って繰り返す)。
このときの傾きは、$p(x,r)$が
$$p(x,r)= \left\{ \begin{array}{ll}x+r & 0\le x< \min(r,1-r) \\ p(r) = \min(2r, 1) & \min(r, 1-r)\le x \le \max(1-r, r) \\ 1 - x+r & \max(1-r, r) < x \le 1 \end{array}\right.$$のように$x$によって決まる関数として与えられていることから$p(x,r)$の$x$に関する期待値として求められて、
$0<r\le0.5$のとき
$$\begin{align}E(p(x, r)) &= \int^{r}_{0}x+r\mathrm{d}x + \int^{1-r}_{r}2r \mathrm{d}x + \int^{1}_{1-r} 1-x+r \mathrm{d}x\\ &= \left[\frac{x^{2}}{2} + rx \right]^{r}_{0} + \left[ 2rx\right]^{1-r}_{r}+ \left[ x-\frac{x^{2}}{2} + rx\right]^{1}_{1-r}\\ &= -r^{2} + 2r \end{align}$$$0.5<r\le1$のときも同様にして
$$E(p(x,r)) = -r^{2} + 2r$$である。
import matplotlib.pyplot as plt
import numpy as np
r = np.linspace(0., 1., 100)
plt.plot(r, -r**2+2*r)
plt.xlabel(r'$r$')
plt.ylabel(r'$E(p(x,r))$')
plt.show()
上図の場合、$r$に対応する値としてself.radius=1/.3
としているので、傾きの平均値は$-1/3(1/3-2) = 5/9$である(緑の線)。また、累積のリンク数についても、同じように曲線でフィットすることができている。
上までに考えてきたように、実際にはこの例はほとんど例1と同じであることが分かる(沈黙を[0,1]の間の一様乱数の期待値0.5とした場合)。実際にこの場合についてシミュレーションを作成したので、これを元に新たに改良していくことは可能だろう。また、上では議論しなかったが、誰が発言したかという時系列については、ネットワークとしての解析の余地は残されている。次の例では、距離と発言者の間の関係の統計的性質について調べる。また、その結果を踏まえて、人による意見の差異の効果をうまく取り込む方法を探る。
今回考えた意見同士にリンクを張る方法は、閾値モデルの変形と考えることができる。
閾値モデル:
重み$w_{i}$が指数分布
$$f(x) = \left\{\begin{array}{ll} \lambda e^{-\lambda x} & (x \ge 0) \\ 0 & (x< 0) \end{array} \right.,\ \ \lambda > 0$$に従う時、次数分布$p(k)$は
$$p(k)\propto k^{-2}$$になる。
一方で、今回考えたように重みを一様分布とした場合に次数分布を求めてみると
import networkx as nx
import matplotlib.pyplot as plt
from collections import Counter
# グラフの作成
G = nx.Graph()
G.add_edges_from(main.app.links)
# print len(G.neighbors(0))
#nx.draw_circular(G)
#plt.show()
# ランキングプロット ---
#degree_sequence = sorted(nx.degree(G).values(), reverse=True)
print nx.degree(G)
#dmax = max(degree_sequence)
#plt.loglog(degree_sequence, 'b-', marker='o')
#plt.title("Degree reank plot")
#plt.ylabel("degree")
#plt.xlabel("rank")
#plt.show()
# ---
# 次数分布
c = Counter(nx.degree(G).values())
s = sum(c.values())
x = []
y = []
for _x, _y in c.items():
x.append(_x)
y.append(_y)
plt.scatter(x, np.array(y)/float(s))
plt.show()
{0: 58, 1: 75, 2: 76, 3: 41, 4: 58, 5: 70, 6: 58, 7: 67, 8: 62, 9: 33, 10: 71, 11: 73, 12: 35, 13: 65, 14: 61, 15: 32, 16: 77, 17: 33, 18: 65, 19: 76, 20: 58, 21: 36, 22: 72, 23: 75, 24: 38, 25: 58, 26: 42, 27: 69, 28: 71, 29: 37, 30: 36, 31: 66, 32: 58, 33: 73, 34: 71, 35: 63, 36: 75, 37: 37, 38: 77, 39: 34, 40: 39, 41: 34, 42: 58, 43: 31, 44: 70, 45: 65, 46: 71, 47: 58, 48: 59, 49: 65, 50: 71, 51: 65, 52: 58, 53: 38, 54: 75, 55: 73, 56: 66, 57: 58, 58: 59, 59: 77, 60: 60, 61: 74, 62: 75, 63: 42, 64: 67, 65: 41, 66: 67, 67: 58, 68: 61, 69: 26, 70: 61, 71: 71, 72: 62, 73: 58, 74: 75, 75: 70, 76: 59, 77: 39, 78: 31, 79: 76, 80: 75, 81: 58, 82: 61, 83: 67, 84: 62, 85: 61, 86: 58, 87: 58, 88: 58, 89: 61, 90: 69, 91: 35, 92: 26, 93: 34, 94: 37, 95: 69, 96: 40, 97: 58, 98: 67, 99: 70, 100: 71, 101: 58}
???
from IPython.display import HTML
HTML('<iframe src=http://ja.wikipedia.org/wiki/%E5%AF%BE%E4%BA%BA%E8%B7%9D%E9%9B%A2?useformat=mobile width=700 height=350></iframe>')
from IPython.display import HTML
HTML('<iframe src=http://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%8F%E3%83%A9%E3%83%8E%E3%83%93%E3%82%B9%E8%B7%9D%E9%9B%A2?useformat=mobile width=700 height=350></iframe>')