@hayata-yamamoto です。この記事を書いていたら、小学校の自由研究を思い出しました。当時私は、アリジゴクの採集にハマっていて、研究テーマにしたことがありました。成虫であるウスバカゲロウになるとあっという間に生涯を終えてしまう儚さはなんとも言いがたいものがありますね。
さて、私はEdTech Labという研究開発チームに所属しています。(前回の記事に登場した齋藤と同じです)普段は、Python で機械学習 のモデル開発やデータ分析をしています。以前、分析チームについては書きましたので、よければそちらもみてください。
rarejob-tech-dept.hatenablog.com
rarejob-tech-dept.hatenablog.com
目次
はじめに
多くのプログラミング言語 では、別のクラスをあるクラスに継承させることができます。これにより、共通部分の実装を省きながらユースケース に合わせた追加実装ができるようになります。また、共通部分も上書きすれば、必要な実装に書き換えたりできます。例えば、Django では、以下のようにクラスを継承し必要な実装を加えて使ったりします。
from django.http import HttpResponse
from django.views.generic import ListView
from books.models import Book
class BookListView (ListView):
model = Book
def head (self, *args, **kwargs):
last_book = self.get_queryset().latest('publication_date' )
response = HttpResponse()
response['Last-Modified' ] = last_book.publication_date.strftime('%a, %d %b %Y %H:%M:%S GMT' )
return response
本記事では、この継承に着目します。具体的には、継承を「あるクラス」→「別のクラス」という関係性で捉え、ネットワーク分析の枠組みで分析します。最初にUML で描いたクラス図を定性的に分析します。次にネットワーク分析の指標を用いて定量 的に分析しました。普段何気なく実装しているクラスの継承関係も数学的に捉えなおせば、より客観的で俯瞰的な理解ができると伝われば嬉しいです。
なお、ソースはGitHub に掲載してあります。
github.com
使ったデータ
collections.abc1 というPython の標準モジュールを対象に分析しました。データの選定理由は大きく2つあります。念のためですが、このモジュールを知らなくても問題ないですので安心してください。
よく使われるデータセット はもうすでに良い記事がたくさんあるから
このモジュールを深く理解したかったから
データ作成に当たっては、公式のドキュメントとcpython2 を参考にしています。コレクション抽象基底クラスの継承関係と抽象メソッド、及びMixinについて記載したテーブルが公式には記載されています。このモジュールは、typing3 の説明にもしばしば登場します。mypy4 などを使用するに当たっては、知っておいて損はありません。
また、分析にあたってCSV データを別途作成しました。(気を利かせて?)Gremlin形式5 になっています。もし興味があれば、Gremlin形式でロードできるグラフDBと合わせて使ってみてください。例えば、AWS Neptuneとかでしょうかね。
$ head -n 5 data/vetices.csv
~id,name:String
v0," Container "
v1," Hashable "
v2," Iterable "
v3," Iterator "
$ head -n 5 data/edges.csv
~id,~from,~to,~label
e0,v3,v2,extends
e1,v4,v2,extends
e2,v5,v3,extends
e3,v8,v6,extends
ネットワーク、そしてグラフ
普段、ネットワークという言葉をよく耳にします。SNS やインターネット、VPN 、サブネットとかネットワークACL などなど、身近なものからテクニカルなものまで様々あります。ビジネスの文脈ですと、ネットワークというのは人脈のような人同士の繋がりを意味することもあります。要するに、あるものと、別のあるものがつながっている時に、「ネットワーク」という言葉を使いたくなります。このような構造を数学的に扱うのに、グラフが有効です。
グラフと言っても、棒グラフなどの図を意味するわけではありません。宮崎氏によると、『いくつかの点と、二つの点を繋ぐ線からなるもの』6 と説明されています。この点を頂点(Vertex)や節点(Node)と呼び、繋ぐ線を辺(Edge)や弧(Arc)と呼びます。また、この辺に向きがあるものを有向グラフ(Directed Graph)、向きがないものを無向グラフ(Undirected Graph)と呼びます。実務でよく目にするグラフといえば、木(Tree)や有向非巡回グラフ(DAG)あたりでしょうか。隣接や(最短)経路なども基礎的で重要ですが、今回は省略します。
以下のリンクは、レ・ミゼラブル に登場するキャラク ター相関図をグラフで表現しています。目まぐるしくすぎていくストーリーも、一度立ち止まって、それぞれの登場人物を点と線で結んでみるとより深く理解できるというわけです。まさに、"Connecting the dots"ですね。エモい。
observablehq.com
とはいえ最初からグラフを使おうとすると、難しすぎて心が折れてしまいそうです。ですので、まずはこのモジュールをUML でクラス図にしてみるところから始めます。ちなみに、UML は以下の記事でも紹介されています。
rarejob-tech-dept.hatenablog.com
この分析では、大きく二点を確認しました。
モジュール全体を把握し、クラスを覚える
どのクラスがたくさん継承していそうか、継承されていそうかを直感的に理解する
以下の図を確認すると、直感的には
Collection, Set, MappingViewに向いている矢印が多い
Collectionは出ていく矢印も多い
いくつかエッジを持たないクラスが存在する
とわかるのではないでしょうか。
collections.abc Diagram
いよいよ分析
次に定量 的な分析をしてみます。今回の分析には、NetworkX7 というライブラリを用いました。分析には以下の3つを用います。
次数中心性 (degree centrality)
媒介中心性 (betweenness centrality)
PageRank
中心性とは、「そのノードがネットワークの中でどれくらい重要か」を表す指標と思ってくれれば大丈夫です。人で例えると、次数中心性は「たくさんの人とつながりを持っていること」を評価し、媒介中心性は「その人経由で別の人と繋がることが多いこと」を評価しています。PageRank は、Webページの重要度をはかる指標で被リンクの数を重視します。(一部の例外を除けば)良い記事は、被リンク数が多くなることを期待できます。PageRank はその性質を数値的に表現したものくらいの理解で大丈夫です。色々なページで丁寧に説明されていますので、検索してみると理解が深まるかもしれません。勇気がある人はぜひ、論文8 も読んでみてください。
さて、CSV を読み出して有向グラフを作成し、そのグラフに対して必要な計算を実行します。JupyterNotebookの処理を抜粋してみます。
import networkx as nx
import pandas as pd
from typing import Tuple
def pairing (row: pd.Series) -> Tuple[str , str ]:
return (row['~from' ], row['~to' ])
vertices = pd.read_csv('./data/vertices.csv' , index_col=None )
edges_df = pd.read_csv("./data/edges.csv" , index_col=None )
edges_df['pair' ] = edges_df.apply(pairing, axis=1 )
G = nx.DiGraph()
G.add_nodes_from(vertices['~id' ])
G.add_edges_from(edges_df.pair)
degree = nx.degree_centrality(G)
between = nx.betweenness_centrality(G)
page_rank = nx.algorithms.pagerank_numpy(G)
df = pd.DataFrame.from_records([degree, between, page_rank], index=['degree' , 'betweenness' , 'pagerank' ]).T
df = pd.merge(left=df, right=vertices, left_index=True , right_on='~id' ).drop('~id' , axis=1 ).set_index('name:String' )
このDataFrameをheadすると以下のようなテーブルが取得できます。
name:String
degree
betweenness
pagerank
Container
0.0416667
0
0.0536147
Hashable
0
0
0.019103
Iterable
0.125
0
0.118524
Iterator
0.0833333
0.00181159
0.0353406
Reversible
0.0833333
0.00271739
0.0410238
(よしなに)可視化すると以下のようになります。ノードの大きさは、各指標の値の大きさと比例しています。それぞれの指標によって評価のされ方が異なることがみて取れますね。
最後に、各指標毎にランキングをとって、その合計順位の高い順上位5つを並べると以下のようになります。UML での定性分析通り、CollectionやSet, MappingViewが上位にあると確認できました。めでたしめでたし
name:String
Sum of rank value
Collection
3
Set
8
Sequence
12.5
MappingView
16.5
Mapping
23.5
おわりに
この記事では、継承をテーマに簡単なネットワーク分析を行いました。ところどころ難しい言葉や解釈に苦労する部分もあったかもしれませんが、普段の何気ないテーマも数学的に捉えなおせば、よりよく理解できることが少しわかっていただけたら嬉しいです。実はそんなに頑張ってテーマを探さなくても、意外と身近に分析のテーマは落ちていて、そこまで難しい手法や実装をしなくても解決できたり調査できたりします。
ネットワーク分析は適用範囲が広く、今回取り上げたテーマの他にもSNS や書籍引用、Webページなど手頃なテーマはたくさんあります。ぜひ手頃なテーマを見つけて勉強してみてください。
引用・参考