サンキーダイアグラムの紹介とその可読性を上げるための最適化手法

webマーケティングの世界ではユーザのコンテンツ間の遷移パターンが重要な分析対象となる場合が多くあります。例えばHPの動線を改善するためにTOPページからどのようなコンテンツにどれだけ遷移するのかを分析したり、離脱を減らすために離脱するユーザはどのような行動パターンを取るのかを分析します。始点/終点のような2点の場合このような分析はクロス集計や遷移行列のようなもので表現できます。一方コンテンツは一般的に多数あるので始点/2番目/3番目/終点のような複数層パターンでの遷移を考慮する必要があります。このパターンは組み合わせが膨大になり単純なクロス集計のようなものでは情報が繁雑になります。

このような複数層を直観的に可視化できるツールとしてサンキーダイアグラムというものがあります。（以下に図表）

上記例はぺージTOPから1回目のコンテンツ遷移そして2回目のコンテンツ遷移のパターンを可視化したものです。CONTENTS11→CONTENTS32とは最初1回目の遷移先がCONTENTS1で2回目がCONTENTS3に遷移したことを表します（すなわち末尾数字は何回目かを表します）。この例ですとCONTENTSが4つしかないので比較的容易に読み取ることができます。一方でコンテンツが増えると層間の辺はコンテンツ数の2乗となり可読性に問題があることが分かります。それを整数計画法で解決しようというのがこの論文https://ialab.it.monash.edu/~dwyer/papers/optimal-sankey-diagrams.pdf

で解説されています。

本稿ではまずこのサンキーダイアグラムの簡単な紹介と、可読性を上げるために 整数計画法 を用いる方法を当該論文の内容に沿って紹介します。

サンキーダイアグラムを描く

サンキーダイアグラムをググると以下のツールが上位候補として挙がってきます。

• Google Charts Sankey Diagram
• Python
• R
• Tableau

私はPython派なので本稿ではPythonを前提にご説明します。基本的な使い方はこの記事を参照願います。

Anaconda環境からAnacondaプロンプトを呼び出しhttps://github.com/ricklupton/ipysankeywidget このGithubを参考に以下のように打ち込みます。

$ pip install ipysankeywidget
$ jupyter nbextension enable --py --sys-prefix ipysankeywidget

次にpythonコード上で以下のように記述します。

from ipysankeywidget import SankeyWidget
#以下が流入出のデータ
links = [

{'source': 'TOP', 'target': 'CONTENTS11', 'value': 5000, 'color': 'red'},
{'source': 'TOP', 'target': 'CONTENTS21', 'value': 10000},
{'source': 'TOP', 'target': 'CONTENTS31', 'value': 7000, 'color': 'green'},
{'source': 'TOP', 'target': 'CONTENTS41', 'value': 10000, 'color': 'yellow'},

{'source': 'CONTENTS11', 'target': 'CONTENTS12', 'value': 2500, 'color': 'red'},
{'source': 'CONTENTS11', 'target': 'CONTENTS22', 'value': 500},
{'source': 'CONTENTS11', 'target': 'CONTENTS32', 'value': 800, 'color': 'green'},
{'source': 'CONTENTS11', 'target': 'CONTENTS42', 'value': 1200, 'color': 'yellow'},

{'source': 'CONTENTS21', 'target': 'CONTENTS12', 'value': 6000, 'color': 'red'},
{'source': 'CONTENTS21', 'target': 'CONTENTS22', 'value': 2000},
{'source': 'CONTENTS21', 'target': 'CONTENTS32', 'value': 1500, 'color': 'green'},
{'source': 'CONTENTS21', 'target': 'CONTENTS42', 'value': 500, 'color': 'yellow'},

{'source': 'CONTENTS31', 'target': 'CONTENTS12', 'value': 1000, 'color': 'red'},
{'source': 'CONTENTS31', 'target': 'CONTENTS22', 'value': 2500},
{'source': 'CONTENTS31', 'target': 'CONTENTS32', 'value': 2000, 'color': 'green'},
{'source': 'CONTENTS31', 'target': 'CONTENTS42', 'value': 1500, 'color': 'yellow'},

{'source': 'CONTENTS41', 'target': 'CONTENTS12', 'value': 6000, 'color': 'red'},
{'source': 'CONTENTS41', 'target': 'CONTENTS22', 'value': 500},
{'source': 'CONTENTS41', 'target': 'CONTENTS32', 'value': 500, 'color': 'green'},
{'source': 'CONTENTS41', 'target': 'CONTENTS42', 'value': 3000, 'color': 'yellow'},

]

w = SankeyWidget(links=links,margins=dict(top=0, bottom=0, left=50, right=200))
w
w.auto_save_png("sankey_example_post.png")

これを打ち込むと冒頭で示したサンキーダイアグラムが表示されます。

可読性を上げるためには

さてこの記事の趣旨はこんな便利なツールがありますではなく、こいつの可読性を上げるにはどうするか？でした。色々議論の余地があると思いますが当該論文では

可読性が高い＝コンテンツ間の太いエッジ同士の交点は少なく、細いエッジ同市の交点が多い

とあり、本記事でもこれを定義として進めていきます。直観的に考えて太いもの同士が交わると見にくいですよね？

整数計画法を適用し問題を解く

整数計画法 とはある制約条件のもとで任意の目的関数を最小化（最大化）するアルゴリズムです。線形計画法との違いは変数がバイナリー（すなわち1/0であるかどうかの違いで整数計画法は1/0の変数のみ用います）したがって太い（細い）エッジ同市の交点ができた時に大きく（小さく）なる関数を定義し、それを制約条件のもとで最小化する整数計画問題を解くことで可読性の高いサンキーダイアグラムの表示方法の解が得られるというのが当該論文の主張です。

本記事ではPythonの線形計画法のパッケージであるpulpを使います。

#必要なパッケージのインポート
import numpy as np
import pandas as pd
from pandas import DataFrame,Series

import pulp
from pulp.pulp import lpSum
from pulp import LpVariable as Var
from pulp import lpSum
from collections import defaultdict
from pulp import *

from collections import defaultdict
import itertools

 変数の設定

一番上のソースコードのlinksで定義されるデータをinputとします。

#改善対象
links = [

{'source': 'CONTENTS11', 'target': 'CONTENTS12', 'value': 2500, 'color': 'red'},
{'source': 'CONTENTS11', 'target': 'CONTENTS22', 'value': 500},
{'source': 'CONTENTS11', 'target': 'CONTENTS32', 'value': 800, 'color': 'green'},
{'source': 'CONTENTS11', 'target': 'CONTENTS42', 'value': 1200, 'color': 'yellow'},

{'source': 'CONTENTS21', 'target': 'CONTENTS12', 'value': 6000, 'color': 'red'},
{'source': 'CONTENTS21', 'target': 'CONTENTS22', 'value': 2000},
{'source': 'CONTENTS21', 'target': 'CONTENTS32', 'value': 1500, 'color': 'green'},
{'source': 'CONTENTS21', 'target': 'CONTENTS42', 'value': 500, 'color': 'yellow'},

{'source': 'CONTENTS31', 'target': 'CONTENTS12', 'value': 1000, 'color': 'red'},
{'source': 'CONTENTS31', 'target': 'CONTENTS22', 'value': 2500},
{'source': 'CONTENTS31', 'target': 'CONTENTS32', 'value': 2000, 'color': 'green'},
{'source': 'CONTENTS31', 'target': 'CONTENTS42', 'value': 1500, 'color': 'yellow'},

{'source': 'CONTENTS41', 'target': 'CONTENTS12', 'value': 6000, 'color': 'red'},
{'source': 'CONTENTS41', 'target': 'CONTENTS22', 'value': 500},
{'source': 'CONTENTS41', 'target': 'CONTENTS32', 'value': 500, 'color': 'green'},
{'source': 'CONTENTS41', 'target': 'CONTENTS42', 'value': 3000, 'color': 'yellow'},
]
#深さ
d=2

頂点集合vを取得する。

#頂点集合を定義
v1=[]
v2=[]
for i in links:
    temp1=i['source']
    temp2=i['target']
    v1.append(i['source'])
    v2.append(i['target'])
    #num.append(i['value'])
    v1 = list(dict.fromkeys(v1))
    v2 = list(dict.fromkeys(v2))
    v=[1]*d
    for j in range(d):
        if j+1!=d:
            v[j]=[i for i in v1 if i[-1]==str(j+1)]
        else:
            v[j]=[i for i in v2 if i[-1]==str(j+1)]

エッジの重み変数wを作成する、ここれは重みはエッジの流入出量とする。

#weight定数行列作成
#w[i][j][k][l]:=エッジijとエッジklが交差したときの重み
w=dict(zip(range(d-1),[[] for i in range(d-1)]))
for h in range(d-1):
    l_=[]
    for i in v[h]:
        for j in v[h+1]:
            for k in v[h]:
                for l in v[h+1]:
                    #print (i,j,k,l)
                    #print ([ii['value'] for ii in links if ii['source']==i and ii['target']==j][0])
                    #print ([ii1['value'] for ii1 in links if ii1['source']==k and ii1['target']==l][0])
                    x=[ii['value'] for ii in links if ii['source']==i and ii['target']==j][0]
                    y=[ii1['value'] for ii1 in links if ii1['source']==k and ii1['target']==l][0]
                    print (h,i,j,k,l,x,y,x*y)
                    l_.append([ii['value'] for ii in links if ii['source']==i and ii['target']==j][0] * [ii1['value'] for ii1 in links if ii1['source']==k and ii1['target']==l][0])
                    w[h]=l_

交差変数cの作成を行う。エッジが交差したた1それ以外は0となるように定義する。

#交差変数作成
#c[i][j][k][l]エッジijがklと交差したとき1そうでないとき0
c=dict(zip(range(d-1),[[] for i in range(d-1)]))
for i in range(d-1):
    n1=range(len(v[i]))
    n2=range(len(v[i+1]))
    c_ = defaultdict(dict)
    c_=LpVariable.dicts("c"+str(i),(n1,n2,n1,n2),0,1,cat='Binary')
    c[i]=c_

ある頂点がほかの頂点より同層ないで上にあれば1それ以外は0となるような 頂点の順序変数xを作成する。

#頂点の順序変数作成
#x[i][j][k] i層の頂点jが頂点kより上の場合1 other 0
x=dict(zip(range(d),[{} for i in range(d)]))
for h in range(d): 
    #print (h)
    x_=defaultdict(dict)
    for i,s in enumerate(v[h]):
        for j,t in enumerate(v[h]):
            if i!=j:
                x_[i][j] = Var(name='{}_{}'.format(s, t), cat='Binary')
                x[h]=x_

目的関数の設定

最小化したい目的関数を設定します。

目的関数:=Σ(エッジu1v1の数×エッジu2v2)×cu1v1u2v2

u1,u2は1層目の頂点、v1,v2は2層目の頂点エッジu1v1はu1とv1を結ぶ辺cu1v1u2v2は辺が交差していれば1それ以外0となる変数でΣは全ての頂点の組み合わせを走るとします。

#object 目的関数
m = LpProblem()
m += lpSum([c[h][i][j][k][l]*np.array(w[h]).reshape(len(v[h]),len(v[h+1]),len(v[h]),len(v[h+1]))[i][j][k][l]
for h in range(d-1) for i in range(len(v[h])) 
for j in range(len(v[h+1])) 
for k in range(len(v[h])) for l in range(len(v[h+1])) if (i!=k) or (j!=l) ] )

制約条件の作成

同じ層に属する頂点の2つの組は必ずどちらかが上であればかならず他方が下であるという制約を定式化します。具体的に述べるとxij=1 頂点iがjより上と定義すると必ず xij+xji=1となるように制約を設けるということです。

またiがjより上でkがiより上の場合kは必ずjより上にあるという推移率も定式化します。

#(1) 頂点iがjより上かそれ以外かが排他的である
for h in range(d):
    for i in range(len(x[h])):
        for j in range(len(x[h])):
            if i!=j:
                m += x[h][i][j]+x[h][j][i] == 1
#(2) 順序の推移律:頂点iがjより上で頂点kがiより上ならばkはjより上でなくてはならない
for h in range(d): 
    for i in list(itertools.permutations(range(len(x[h])), 3)):
        m += x[h][i[0]][i[2]]-x[h][i[0]][i[1]]-x[h][i[1]][i[2]] >= -1

頂点の位置関係と交差関係に矛盾がないように制約式を立てる。また交差の対称性も定式化する。

#(3)頂点の位置と交差しているかの制約
#(4)交差の対称性:辺ijと辺klが交差しているのならば、辺klと辺ijも交差している
for h in range(d-1): 
    for i in range(len(v[h])):
        for j in range(len(v[h+1])):
            for k in range(len(v[h])):
                for l in range(len(v[h+1])):
                    if i!=k and j!=l:
                        #print (h,i,j,k,l)
                        m +=c[h][i][j][k][l]+x[h][k][i]+x[h+1][j][l] >=1
                        m +=c[h][i][j][k][l]+x[h][i][k]+x[h+1][l][j] >=1
                        m += c[h][i][j][k][l] == c[h][k][l][i][j]
                        m += c[h][i][j][k][l] + c[h][i][l][k][j] == 1

ソルバーを実行して問題を解く

## ソルバー実行
result_status = m.solve()
#print (pulp.LpStatus[result_status])


# In[14]:

#解を確認
for i in range(len(v[0])):
    for j in range(len(v[0])):
        if i!=j:
            print (value(x[0][i][j]),i,j)

実際の解を見てみる

for h in range(d):
    sol_x=[[value(x[h][i][j]),k,m] for i,k in enumerate(v[h]) for j,m in enumerate(v[h]) if i!=j]
    #print (sol_x)
    print (list(DataFrame(sol_x).groupby([1]).mean().sort_values(by=[0],ascending=False).index))

上のコードを走らせると

[‘CONTENTS31’, ‘CONTENTS21’, ‘CONTENTS11’, ‘CONTENTS41’]
[‘CONTENTS22’, ‘CONTENTS32’, ‘CONTENTS12’, ‘CONTENTS42’]

という出力が得られるのでこれを最初のソースコード中に以下のように記述します。

from ipysankeywidget import SankeyWidget
#以下が流入出のデータ
links = [
{'source': 'TOP', 'target': 'CONTENTS11', 'value': 5000, 'color': 'red'},
{'source': 'TOP', 'target': 'CONTENTS21', 'value': 10000},
{'source': 'TOP', 'target': 'CONTENTS31', 'value': 7000, 'color': 'green'},
{'source': 'TOP', 'target': 'CONTENTS41', 'value': 10000, 'color': 'yellow'},

{'source': 'CONTENTS11', 'target': 'CONTENTS12', 'value': 2500, 'color': 'red'},
{'source': 'CONTENTS11', 'target': 'CONTENTS22', 'value': 500},
{'source': 'CONTENTS11', 'target': 'CONTENTS32', 'value': 800, 'color': 'green'},
{'source': 'CONTENTS11', 'target': 'CONTENTS42', 'value': 1200, 'color': 'yellow'},

{'source': 'CONTENTS21', 'target': 'CONTENTS12', 'value': 6000, 'color': 'red'},
{'source': 'CONTENTS21', 'target': 'CONTENTS22', 'value': 2000},
{'source': 'CONTENTS21', 'target': 'CONTENTS32', 'value': 1500, 'color': 'green'},
{'source': 'CONTENTS21', 'target': 'CONTENTS42', 'value': 500, 'color': 'yellow'},
    
{'source': 'CONTENTS31', 'target': 'CONTENTS12', 'value': 1000, 'color': 'red'},
{'source': 'CONTENTS31', 'target': 'CONTENTS22', 'value': 2500},
{'source': 'CONTENTS31', 'target': 'CONTENTS32', 'value': 2000, 'color': 'green'},
{'source': 'CONTENTS31', 'target': 'CONTENTS42', 'value': 1500, 'color': 'yellow'},

{'source': 'CONTENTS41', 'target': 'CONTENTS12', 'value': 6000, 'color': 'red'},
{'source': 'CONTENTS41', 'target': 'CONTENTS22', 'value': 500},
{'source': 'CONTENTS41', 'target': 'CONTENTS32', 'value': 500, 'color': 'green'},
{'source': 'CONTENTS41', 'target': 'CONTENTS42', 'value': 3000, 'color': 'yellow'},

]
#得られた解を以下のように記述
order =[
['TOP'],
['CONTENTS31', 'CONTENTS21', 'CONTENTS11', 'CONTENTS41'],
['CONTENTS22', 'CONTENTS32', 'CONTENTS12', 'CONTENTS42'],
]

w = SankeyWidget(links=links,
                 #orderを以下のように追加
                 order=order, margins=dict(top=0, bottom=0, left=50, right=200))
w
w.auto_save_png("sankey_example_post1.png")

事前事後を比べると（左図が事前右図が事後）

こころなしか事後の方が見やすくなっています。