身近なデータ分析〜クラスの継承関係を題材に〜

@hayata-yamamotoです。この記事を書いていたら、小学校の自由研究を思い出しました。当時私は、アリジゴクの採集にハマっていて、研究テーマにしたことがありました。成虫であるウスバカゲロウになるとあっという間に生涯を終えてしまう儚さはなんとも言いがたいものがありますね。

さて、私はEdTech Labという研究開発チームに所属しています。（前回の記事に登場した齋藤と同じです）普段は、Pythonで機械学習のモデル開発やデータ分析をしています。以前、分析チームについては書きましたので、よければそちらもみてください。

rarejob-tech-dept.hatenablog.com rarejob-tech-dept.hatenablog.com

はじめに

多くのプログラミング言語では、別のクラスをあるクラスに継承させることができます。これにより、共通部分の実装を省きながらユースケースに合わせた追加実装ができるようになります。また、共通部分も上書きすれば、必要な実装に書き換えたりできます。例えば、Djangoでは、以下のようにクラスを継承し必要な実装を加えて使ったりします。

# 引用元: https://docs.djangoproject.com/en/3.0/topics/class-based-views/

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()
        # RFC 1123 date format
        response['Last-Modified'] = last_book.publication_date.strftime('%a, %d %b %Y %H:%M:%S GMT')
        return response

本記事では、この継承に着目します。具体的には、継承を「あるクラス」→「別のクラス」という関係性で捉え、ネットワーク分析の枠組みで分析します。最初にUMLで描いたクラス図を定性的に分析します。次にネットワーク分析の指標を用いて定量的に分析しました。普段何気なく実装しているクラスの継承関係も数学的に捉えなおせば、より客観的で俯瞰的な理解ができると伝われば嬉しいです。

なお、ソースはGitHubに掲載してあります。

github.com

使ったデータ

collections.abc¹というPythonの標準モジュールを対象に分析しました。データの選定理由は大きく２つあります。念のためですが、このモジュールを知らなくても問題ないですので安心してください。

よく使われるデータセットはもうすでに良い記事がたくさんあるから
このモジュールを深く理解したかったから

データ作成に当たっては、公式のドキュメントとcpython²を参考にしています。コレクション抽象基底クラスの継承関係と抽象メソッド、及びMixinについて記載したテーブルが公式には記載されています。このモジュールは、typing³の説明にもしばしば登場します。mypy⁴などを使用するに当たっては、知っておいて損はありません。

また、分析にあたってCSVデータを別途作成しました。（気を利かせて？）Gremlin形式⁵になっています。もし興味があれば、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などなど、身近なものからテクニカルなものまで様々あります。ビジネスの文脈ですと、ネットワークというのは人脈のような人同士の繋がりを意味することもあります。要するに、あるものと、別のあるものがつながっている時に、「ネットワーク」という言葉を使いたくなります。このような構造を数学的に扱うのに、グラフが有効です。

グラフと言っても、棒グラフなどの図を意味するわけではありません。宮崎氏によると、『いくつかの点と、二つの点を繋ぐ線からなるもの』⁶と説明されています。この点を頂点（Vertex）や節点（Node）と呼び、繋ぐ線を辺（Edge）や弧（Arc）と呼びます。また、この辺に向きがあるものを有向グラフ（Directed Graph）、向きがないものを無向グラフ（Undirected Graph）と呼びます。実務でよく目にするグラフといえば、木（Tree）や有向非巡回グラフ（DAG）あたりでしょうか。隣接や（最短）経路なども基礎的で重要ですが、今回は省略します。

以下のリンクは、レ・ミゼラブルに登場するキャラクター相関図をグラフで表現しています。目まぐるしくすぎていくストーリーも、一度立ち止まって、それぞれの登場人物を点と線で結んでみるとより深く理解できるというわけです。まさに、"Connecting the dots"ですね。エモい。

observablehq.com

まずはUMLで

とはいえ最初からグラフを使おうとすると、難しすぎて心が折れてしまいそうです。ですので、まずはこのモジュールをUMLでクラス図にしてみるところから始めます。ちなみに、UMLは以下の記事でも紹介されています。

rarejob-tech-dept.hatenablog.com

この分析では、大きく二点を確認しました。

モジュール全体を把握し、クラスを覚える
どのクラスがたくさん継承していそうか、継承されていそうかを直感的に理解する

以下の図を確認すると、直感的には

Collection, Set, MappingViewに向いている矢印が多い
Collectionは出ていく矢印も多い
いくつかエッジを持たないクラスが存在する

とわかるのではないでしょうか。

f:id:hayata-yamamoto:20200525220140p:plain — collections.abc Diagram

いよいよ分析

次に定量的な分析をしてみます。今回の分析には、NetworkX⁷というライブラリを用いました。分析には以下の3つを用います。

次数中心性 (degree centrality)
媒介中心性 (betweenness centrality)
PageRank

中心性とは、「そのノードがネットワークの中でどれくらい重要か」を表す指標と思ってくれれば大丈夫です。人で例えると、次数中心性は「たくさんの人とつながりを持っていること」を評価し、媒介中心性は「その人経由で別の人と繋がることが多いこと」を評価しています。PageRankは、Webページの重要度をはかる指標で被リンクの数を重視します。（一部の例外を除けば）良い記事は、被リンク数が多くなることを期待できます。PageRankはその性質を数値的に表現したものくらいの理解で大丈夫です。色々なページで丁寧に説明されていますので、検索してみると理解が深まるかもしれません。勇気がある人はぜひ、論文⁸も読んでみてください。

さて、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

（よしなに）可視化すると以下のようになります。ノードの大きさは、各指標の値の大きさと比例しています。それぞれの指標によって評価のされ方が異なることがみて取れますね。 f:id:hayata-yamamoto:20200528233423j:plain

最後に、各指標毎にランキングをとって、その合計順位の高い順上位５つを並べると以下のようになります。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ページなど手頃なテーマはたくさんあります。ぜひ手頃なテーマを見つけて勉強してみてください。