平成 25 年度創成シミュレーション工学専攻修士論文梗概集計算応用科学分野 0-1 マトリックスからの階層構造の再構築学籍番号 1 序論人間関係は，近年の SNS の発達により，複雑で多様化している．このように，複雑で多様な構造をもつものや関係は実世界に多く存在する．例えば，工業製品の部品構成，生物の細胞構造，生態系などである．本論では，このような繋がり関係からは一目では見えない隠れている階層構造を再構築することを目的としている． 2 最下層節点と他の節点との関係が 0-1 マトリックスで与えられた時のアルゴリズム階層構造の最下層節点と，その他の節点の間の繋がり関係が分かる場合のアルゴリズム (本論ではアルゴリズム-1 と呼ぶ) を独自のアイディアとして学士卒業論文で提案したが，本論でも再度掲載し，その応用例について述べた．応用例として，(1) 人間関係 (2) ある製品をの不良原因と不良現象の相関表の 2 つについて階層構造を立ち上げた． 3 連結無向グラフとしての 0-1 マトリックスから再構築するためのアルゴリズム V 3 v0 v1 v2 V2 v5 v6 列番号はそれぞれ vi の i に対応する 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 3 4 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 6 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 7 8 9 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 10 11 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 12 13 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 アルゴリズム-2 は次のようである．V を節点集合， di (j) を節点 i から節点 j までの最短距離 (i，j ∈ V )， Vi (k) を節点 i から最短距離 k で繋がる節点数とすると，各節点について，ki∗ = maxj∈V di (j) として ∗ v3 ki∗ v7 ki ∑ ∗ v8 v9 v10 ∗ ki ki ∑ ∑ jVi (j) − j Vi (j) j=1 j=1 ki∗ j=1 ∗ ki (∑ )2 ∑ ki∗ j2 − j j=1 V1 中根雅斗大鑄史男表 1: 図 1 から生成される 0 − 1 マトリックス C ．行， ai = v4 氏名指導教員 24413558 j=1 から，頂点節点集合を W = {i|ai = max0≦j≦n−1 aj } v11 と定める．dstar(j)，j ∈ V を i ∈ W ，dstar(i) = 0 V 0 v12 v13 v14 v15 v16 図 1: 階層構造の例 V を節点集合，E を節点対の集合，V の要素を行，列要素とする隣接行列 C を { 1， (vi ， vj ) ∈ E cvi ，vj = 0，その他 j ∈ V \W ，dstar(j) = min di (j) i∈W とし，dstar(j) から l = max (dstar(j)) j∈V \W W0 = W W k = {j | dstar(j) = k } , k = 0, · · · , l を定め，行列 C から W 0 ，W 1 ，· · · ，W l を各層とするできる．図 1 から作成された行列 C が表 1 である．こ階層構造 G を、辺集合を次のように定めて定義する． E 0 = {(α， β) |cαβ = 1 かつ dstar(β) − dstar(α) = 1} の逆問題を考え，一目では階層構造グラフの隣接行列アルゴリズム-2 を表 1 に適用すると，図 2 になる．と定義すると，行列 C は背景階層構造から容易に作成であるとは容易に想像することが困難であるような 0-1 アルゴリズム-2 は，いくつかの階層構造の例から，階マトリックスから，背景に存在するであろう階層構造層構造は一般的に頂点節点から階層が下がるにつれ節を再現することを目的としている．点数が増加していくことに気づき，頂点節点は，距離平成 25 年度創成シミュレーション工学専攻修士論文梗概集計算応用科学分野とその距離に存在する節点の個数で回帰直線を引いた際に他の節点よりも傾きが大きくなるのではないかという考えから思いついた次第である．本章では，木の高さ 5 の完全 2 分木，左右非対称の木，頂点から深さ k まで１分木でそれ以下が n 分木の木に対してアルゴリズム-2 を適用した際の理論解析も行い，その頑健性が強いことも示した． v12 図 4: 図 3 からの再現階層構造．頂点節点は v21 v9 し，それらの例での特徴をつかむ必要がある．一般に，再現階層構造は肩書きや組織図などの階層構造と違い， v5 真に及ぼしあっている影響の関係性による階層構造で v7 あると言える． v6 v8 v10 v3 v11 v2 v4 v6 v13 v14 v15 v16 5 アルゴリズム-2 の改良アルゴリズム-2 では，頂点節点からすべて 1 ステップで繋がるような場合は，階層数 2 の再現階層構造となり，頂点以下の節点同士の関係を見出すことが出来ない．以上の事から，アルゴリズム-2 の改良では，階層毎に節点を決め，頂点以下の節点同士の関係を見出 v1 図 2: 表 1 からの再現階層構造すことにした．アルバイト先の人間関係に適用したところ，アルゴリズム-2 では階層数 2 の再現階層構造だったのに対し，アルゴリズム-2 の改良では，アルバイト先に大きな影響を及ぼしている人は，人間関係にも大 4 アルゴリズム-2 のシミュレーションによる検証アルゴリズム-2 の特徴を調べるために，6 種類の場きな影響力を持っていて，そのような人は，人と人を合に対してシミュレーションを行った．は，スペース上詳細に書けなので，詳しくは本論を参完全 n 分木，左右非対称の木，上下非対称の木，横連結している木については完全に背景階層構造を再現できた．横連結とは，階層構造の同層内に存在する節点同士を枝で繋げることである．つなぐパイプ役になっていることも分かった．ここで照していただきたい． 6 まとめアルゴリズム-1 では，最下層を特定することが難しいが，節点間同士の順序関係から階層構造を立ち上げることが出来た．アルゴリズム-2 では，背景階層構造を完全に再現できる場合が分かり，できなくても再現階層構造は実際の影響力の強さによる階層構造を立ち上げることが出来た．アルゴリズム-2 の改良では，アルゴリズム-2 ではできない頂点以外の節点の関係性を示す階層構造を立ち上げることが出来た．今後，多様な木にアルゴリズム-2，アルゴリズム-2 の改良を適用し，アルゴリズム-2，アルゴリズム-2 の改良が持つ特図 3: 背景階層構造が隠れて見えない例．頂点 v0 ，第 4 層左から v1 ，v2 ，第 3 層左から v3 ，v4 ，· · · ，v6 ，第 2 層左から v7 ，· · · ，v14 ，第 1 層左から v15 ，· · · ，v30 ，第 0 層左から v31 ，· · · ，v62 背景階層構造が大分隠れていて見えない場合 (図 3 参照) は，背景階層構造を完全に再現できない．しかし，一概に悪いこととは言い切れず，実際の応用例に適用徴を掴む必要がある．今後の課題として，アルゴリズム-1 の具体的応用例の模索，アルゴリズム-2 を適用する階層構造を広げ，同時にアルゴリズム-2 の改良も適用し，その特徴を掴む，などである．参考文献 [1] 中根雅斗，” 階層構造の再構築”，学士卒業論文，2012． [2] 茨木俊秀，”C によるアルゴリズムとデータ構造”，昭晃堂，初版 1999 第 16 刷． [3] 松坂和夫，” 集合・位相”，岩波書店，初版 1968 第 8 刷．