巨視的構造 最適化 基
4.4 実験
4.4.2 実験環境
全 実験 ，Intel Core i3 2.93 GHz 4 GB 構成 単一 Linux
上 行 ．提案 C++言語 実装 ．最適化問題
IPOPT [42] 3.8.3 利用 ． 大規模非線形最適化
，limited-memory quasi-Newton (L-BFGS)手法[26]
実装 ．提案手法 GN MCL 比較 ．GN
実装 igraph [6] 利用 ，MCL 実装
公式 配布 利用 ．全 GCC 4.5.2
．
Algorithm 1 生成
Input: n,k,pin,pout
Output: graphG V ← {v1,v2, . . . ,vn}
C←divide_into_clusters(V,k){Fig. 4.3a}
E ← ∅ fori=1tokdo
forj=itokdo ifi= jthen
E←E∪generate_edge_random_between(pin,Ci,Cj){Fig. 4.3b}
else
E←E∪generate_edge_random_between(pout,Ci,Cj){Fig. 4.3c}
end if end for end for return (V,E)
20 40 60 80
20 40 60 80
(a)頂点集合 k 個
分割 ．
20 40 60 80
20 40 60 80
(b)同一 内 頂点間
確率pin 辺 張 ．
20 40 60 80
20 40 60 80
(c) 異 頂点間
確率pout 辺 張 ．
図4.3: 人工 生成過程．n個 頂点 k 個 生成
過程 示 ．生成過程 各 ， 隣接行列 状態
示 ，横軸 縦軸 行列 行 列 対応 ． ，(i,j) 位置 ，頂点i 頂点 j 辺 場合 限 ，白色 塗 潰 ．
4.4.3 実験 1: 多様 量 持 対 網羅的調査
人工
量 調整 生成 ， 1 開発
． 4 頂点数 n， 数 k， 内
間 辺 張 確率pin pout ．図 4.3 生成過程 例 示
．
5 10 15 20 25
5 10 15 20 25
(a) 5 孤立
5 10 15 20 25
5 10 15 20 25
(b)弱 繋 5
多
図4.4: 生成 人工 例． 1 生成 人工 例
2 示 (図(a) 図(b))．各 図形的表現(上) 隣接行列
表現 (下) 2通 方法 示 ． 表現 ，横軸 縦軸 隣接行列 行 列 対応 ． ，(i,j) 位置 ，頂点i 頂 点 j 辺 場合 限 ，白色 塗 潰 ．図(a) 同一 内 頂点
間 辺 最大限張 ，図(b) 追加 ( 内 辺
削除 ， 間 辺 追加) ．
pin
pout
0.0 0.2 0.4 0.6 0.8
0.2 0.4 0.6 0.8 1.0 value
0.0 0.2 0.4 0.6 0.8 1.0
(a) NMI
pin
pout
0.0 0.2 0.4 0.6 0.8
0.2 0.4 0.6 0.8 1.0 value
0 5000 10000 15000
(b)最適化計算 反復数
pin
pout
0.0 0.2 0.4 0.6 0.8
0.2 0.4 0.6 0.8 1.0 value
0 200 400 600 800 1000 1200
(c)計算時間
図4.5: 提案手法 結果．1000個 頂点 均等 5 構成 様々 生成 下 生成 ，提案手法 適用 ．各生成 組(pin,pout)
，対応 NMI 計算時間 基 色付 ．
図4.4 生成 人工 例 示 ．図 隣接行
列 表示 ，横軸 縦軸 行列 行 列 添字
対応 ．(i,j) 位置 目 頂点i j 辺 存在 場合 白色
塗 潰 ．
提案手法 性能
本節 程度大 対 提案手法 性能 示 ．先 述 1 対 ，pin,pout ∈ {0,0.1,0.2,. . . ,1} pin > pout 満 55個 (pin,pout) = (0.1,0),(0.2,0),(0.2,0.1),. . . ,(1,0.9) ▽与 ．
10個 1000個 頂点 均等 5 分
生成 ． ，各 200個 頂点 含 ．提案手法 生成 全 適用 結果 NMI 評価 ．最終的 各生成
NMI 評価値 平均値 求 ．
図4.5 実験 結果 示 ．図4.5a 4.5c ，(pin,pout) 各値 対 応 55個 目 色 付 示 ．色 色相 NMI 計算時間 表現 ，青(最低値) 赤(最大値) 変化 ．図 4.5a 提案手法 55
種類 内 場合 高 評価値 得 分 ． ，評価値
計算時間 2 生成 差(pin −pout) 依存 読
取 ． 観察 ，提案 入力 絶対的 量 影
響 受 結論 ． ，提案 同一 内 辺 密度 異
pin
pout
0.0 0.2 0.4 0.6 0.8
0.2 0.4 0.6 0.8 1.0
value
0.0 0.2 0.4 0.6 0.8 1.0
(a)提案手法
pin
pout
0.0 0.2 0.4 0.6 0.8
0.2 0.4 0.6 0.8 1.0
value
0.0 0.2 0.4 0.6 0.8 1.0
(b) GNmod
pin
pout
0.0 0.2 0.4 0.6 0.8
0.2 0.4 0.6 0.8 1.0
value
0.0 0.2 0.4 0.6 0.8 1.0
(c) GNnum
pin
pout
0.0 0.2 0.4 0.6 0.8
0.2 0.4 0.6 0.8 1.0
value
0.0 0.2 0.4 0.6 0.8 1.0
(d) MCL (inflation=4.0)
図4.6: 各 性能 比較．提案手法，GNmod，GNnum
MCL 結果 示 ．128個 頂点 均等 4 構成
様々 生成 下 生成 ，各手法 適用 ．各生成 組(pin,pout)
，対応 NMI 基 色付 ．
間 辺 密度 差 検出 言 ． 性質 自
然 ，提案 抽出 多 扱
向 示唆 ．
先行研究 比較
本節 ，提案 ，GN [16] MCL [41]
比較 行 ．実験 手順 基本的 前 実験 同 ，生成 頂点数
128個 ， 均等 4 分 生成 点 異
．
GN 階層的 ，実際
結果 得 特定 階層 選択 必要 ． 2 異
方法 用 ．1 modularity尺度 [29] 最大化 階層 選択 方法
(GN 手法 組 合 GNmod 呼 )． 1
数 人工 生成時 指定 数 同 階層 選択 方法
(同様 手法 組 合 GNnum 呼 )．MCL
‘inflation” 呼 ， 粒度 対応 ，出力
結果 数 間接的 制御 ．MCL 著者 推奨 4
値 試 ，最 良 結果 示 inflation=4.0 場合 図4.6 示 ．
図4.6a 提案手法 結果，図4.6b，4.6c 4.6d GNmod，GNnum MCL 結果 示 ．既存手法 ，三角形状
内上部 上手 ，下部 値 上手
分 ． 結果 先行研究 異 間 辺 絶対的 疎
依存 ， 既存 同 内 異
間 辺 密度 小 差 検出 示唆 ．
4.4.4 実験 2: 応用
最後 ， 「 」 応用 場合 各 精度 比較
． ， 距離 間 関係
抽出 ， 入力 ． 人工的 生成
，良 知 Fisher Iris [12] 利用 ．
20 40 60 80 100 120
20 4060 80100120
−6 −4 −2 0 2 4 6
−6−20246
X
Y
20 40 60 80 100 120
20 4060 80100120 20 40 60 80 100 120
20 4060 80100120
α = 0.5 α = 0.125 α = 0.03125
Vector Dataset
Graph Representation
(a) 変換例．
変換 α 値 変 ，生成
量 様々 変化
．
pin
pout
0.0 0.2 0.4 0.6 0.8
0.2 0.4 0.6 0.8 1.0
value
0.0 0.2 0.4 0.6 0.8
large r α
1.0sm aller
α
(b)変換 生成 性質．変換
α 値 変化 ，生成
性質 図中 矢印 曲線 沿 変 化 ．α 値 小 場合(右上)
多 生成 ，α 値 大 場合(左
下) 少 生成 ．
図4.7: 変換．
人工 ，nk 個 d 次元 k- 問題向
次 生成 ．
1. 中心 [0,1]d 一様 k 個選択 ，
2. 各 ，n個 d 次元多変量正規分布
．分布 平均 前 選択 中心 ，共分散行列
d次元単位行列 ．
空間 2 関係 強度 ， 上 2 頂点間
辺 張 確率 表現 ，生成 変換 ．
， 同士 関係 強 距離 近 定義 ．
alpha
score
0.0 0.2 0.4 0.6 0.8 1.0
2−4 2−2 20 22 24
method
Ours
GN (# of clusters) GN (modularity) MCL (inflation = 14) MCL (inflation = 20) MCL (inflation = 40) MCL (inflation = 60)
(a) 2次元
alpha
score
0.0 0.2 0.4 0.6 0.8 1.0
2−6 2−5 2−4 2−3 2−2 2−1 20 21
method
Ours
GN (# of clusters) GN (modularity) MCL (inflation = 14) MCL (inflation = 20) MCL (inflation = 40) MCL (inflation = 60)
(b) 10次元
図4.8: 人工 対 結果．変換 α 各
値 ，10個 平均 NMI ．
D= {vk} 対 ，隣接行列 A=[ai j] 次 構築 ． ai j =
1 if rand() < exp(−αvi −vj)
0 otherwise (4.2)
，vi,vj D 要素 ，rand() [0,1] 含 実数値
返 乱数生成器 呼 出 ．α∈ (0,∞) 生成 辺 数 制御
，∥·∥ 距離 表 ．
生成 例， 異
α 値 用 抽出 例 図4.7a 示 ．生成 性質 ，
図4.7b 示 曲線 沿 変化 α 値 従 変化 ．
alpha
score
0.0 0.2 0.4 0.6 0.8 1.0
2−6 2−4 2−2 20 22
method
Ours
GN (# of clusters) GN (modularity) MCL (inflation = 14) MCL (inflation = 20) MCL (inflation = 40) MCL (inflation = 60)
図4.9: Iris 対 結果．2 問題 実験
行 ．変換 α 各値 ， 変換 実験 3回 行 ，
NMI 平均値 ．
図 4.8 人工 対 実験 結果 示 ．生成
n = 32,k = 4 設定 ，2次元 10次元 作成
実験 行 ． 生成 影響 小 ，10
個 生成 ， NMI 平均 ．図中左側，
α 値 小 生成 多 辺 (非常 多 )場合
見 ，提案手法 高 評価値 得 ，他方既存手法 上手
分 ． 提案手法 ， 多 優位性
示唆 ．一方 ，図 右側 既存手法 上手 対
，提案手法 失敗 ． 原因 ，図4.7b ，同一 内 辺密度
異 間 辺密度 差 提案手法 検出 小 説明
．
図4.9 Iris 対 実験結果 示 ．Iris
3 種 150 標本 構成 ， 内2
区別 難 ． ，本実験 k =2，
2-問題 扱 ，提案手法 GNnum 与 数
2 ．既存 結果 前 実験 似 ， 少
比較的 生成 α 狭 領域 上手
． 対照的 ，提案 α 広 範囲，特 既存
評価値 著 低 α 領域 上手 ．