HITSアルゴリズム

HITSアルゴリズム(Hyperlink-Induced Topic Search)という手法がありますので紹介します。
NetworkXのドキュメントにおいて、PageRankと一緒に Link Analysis のページにあることから存在を知りました。
参考: NetworkXのドキュメントの Link Analysis
論文: A Survey of Eigenvector Methods for Web Information Retrieval (Amy N. Langville, Carl D. Meyer)
Wikipedia: HITS algorithm

まずおさらいですが、PageRankの発想は、「重要なページからリンクされているページは重要」というものでした。
そして、各ページはそれぞれ一つのスコア(PageRank)を持ちます。
PageRankの特徴として、リンクが増えると、リンクされている側のページのスコアは上がりますが、
リンク元のページにはなんら恩恵がありません。

しかし実際、優良なページに多くのリンクを貼っているのであれば、そのページも便利なページではあります。いわゆるリンク集やナビサイトです。
この、優良なページにたどり着くことを容易にするページも評価しようとしているのが、HITSアルゴリズムです。
HITSアルゴリズムは、それぞれのページに Hub(ハブ値) と Authority(権威値) という二つのスコアを付与します。
Authority の方が、PageRankに近い概念で、Hubの方は、優良なページにリンクを飛ばすと高くなる値になります。

実際の計算式に近い形でまとめて説明すると、HITSアルゴリズムは次の二つの要素からなります。
– Hubが高いページからリンクされるほど、Authorityが高くなる。
– Authorityが高いページへリンクするほど、Hubが高くなる。

ここ最近の固有ベクトル中心性PageRankの記事を読んでいただけていたら予想がつくと思うのですが、
これらの計算も行列の掛け算の繰り返しが収束することによって求まります。
そして、行列の固有ベクトルとして算出することもできます。

まず、$i$番目のノードから$j$番目のノードにリンクがある時に$(i, j)$成分が$1$に、そうでない時に$0$になる隣接行列を$L$とおきます。
数式で書くと以下の通りです。
$$
\mathbf{L} = \{a_{i, j}\} =
\left\{ \begin{align}1 (iからjにリンク有り)\\0 (iからjにリンク無し)\end{align}\right.
$$
(文献によって、定義が転置していたり、値が正規化されていたりするのでご注意ください。)

そして、それぞれのノードのハブ値のベクトル$\mathbf{h}^{(k)}$と、権威値のベクトル$\mathbf{a}^{(k)}$を次のように初期化します。
$\mathbf{1}$は全ての要素が1のベクトル、$N$はノード数です。
$$
\mathbf{h}^{(0)} = \mathbf{a}^{(0)} = \mathbf{1}/N.
$$

定義に沿って、ハブ値と、権威値を再帰的に計算するには、次の操作を繰り返すことになります。($\cdot$は行列積です)
$$
\begin{align}
&\mathbf{a}^{(k)} = \mathbf{h}^{(k-1)} \cdot L,\\
&\mathbf{h}^{(k)} = \mathbf{a}^{(k-1)} \cdot L^{\top},\\
&\mathbf{a}^{(k)}と、\mathbf{h}^{(k)}を正規化する.
\end{align}
$$

さて、numpyでこの通り実装し、ループを回して計算すると$\mathbf{h}^{(k)}$も$\mathbf{a}^{(k)}$も一定値に収束することは容易に観測されます。
一応、ランダムに生成したグラフに対して、上の数式の通りに計算して確認しておきましょう。


import numpy as np
import networkx as nx

# ランダムに有向グラフ生成
G = nx.random_graphs.fast_gnp_random_graph(n=10, p=0.2, directed=True)

# 隣接行列取得
L = nx.to_numpy_array(G)
print(L)
"""
[[0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 1. 1. 0. 1. 0. 0. 0. 0.]
 [0. 0. 0. 1. 0. 0. 0. 1. 1. 0.]
 [0. 0. 0. 0. 1. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0. 0. 1. 0. 0.]
 [1. 0. 1. 0. 0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 1. 1. 0. 1. 0. 0.]
 [1. 0. 0. 0. 0. 1. 0. 0. 1. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 1.]
 [0. 0. 0. 0. 1. 0. 1. 0. 0. 0.]]
"""
# ハブ値と権威値を初期化
hubs = np.ones(shape=nx.number_of_nodes(G))/nx.number_of_nodes(G)
authorities = np.ones(shape=nx.number_of_nodes(G))/nx.number_of_nodes(G)

# 再帰的に計算する。
for _ in range(40):
    # ハブ値から権威値を計算する。
    authorities = hubs @ L
    # 権威値からハブ値を計算する。
    hubs = authorities @ L.T

    # 標準化
    hubs /= sum(hubs)
    authorities /= sum(authorities)
    print("authorities: ", authorities.round(3))
    print("hubs:", hubs.round(3))
"""
authorities:  [0.105 0.    0.105 0.105 0.158 0.158 0.053 0.158 0.105 0.053]
hubs: [0.    0.156 0.156 0.067 0.067 0.089 0.2   0.156 0.022 0.089]
authorities:  [0.097 0.    0.097 0.124 0.142 0.204 0.035 0.168 0.124 0.009]
hubs: [0.    0.172 0.168 0.057 0.068 0.079 0.208 0.172 0.004 0.072]
authorities:  [0.097 0.    0.097 0.131 0.13  0.213 0.028 0.172 0.131 0.001]
hubs: [0.    0.178 0.175 0.052 0.069 0.078 0.207 0.178 0.001 0.063]

-- (中略) --

authorities:  [0.1   0.    0.1   0.138 0.116 0.216 0.021 0.172 0.138 0.   ]
hubs: [0.    0.183 0.18  0.047 0.069 0.081 0.203 0.183 0.    0.055]
authorities:  [0.1   0.    0.1   0.138 0.116 0.216 0.021 0.172 0.138 0.   ]
hubs: [0.    0.183 0.18  0.047 0.069 0.081 0.203 0.183 0.    0.055]
"""

この、最後の方で収束している値が、この記事のテーマのハブ値と権威値です。
Networkxで計算することもできるので見ておきましょう。
PageRank同様に複数の実装がありますが、 numpyで実装された、hits_numpyを使えば十分でしょう。


h, a = nx.hits_numpy(G)
print(h)
"""
{0: 0.0,
 1: 0.1828404557137138,
 2: 0.18031994425802442,
 3: 0.04654212497804568,
 4: 0.06918950852466288,
 5: 0.08062191959815146,
 6: 0.20269591155066588,
 7: 0.1828404557137138,
 8: 0.0,
 9: 0.054949679663021944}
"""
print(a)
"""
{0: 0.1000629943543116,
 1: -0.0,
 2: 0.10006299435431144,
 3: 0.13792829814529123,
 4: 0.11553047637984128,
 5: 0.21586948330461359,
 6: 0.020869885042915804,
 7: 0.17174757027342366,
 8: 0.1379282981452913,
 9: -0.0}
"""

さて、例によって、再帰的に計算して、収束を待つというのは非常にコストの高い計算なので、もう少し効率化を考えます。
先ほどの計算式をよく見ると、$\mathbf{h}^{(k)}$と$\mathbf{a}^{(k)}$は相互に計算するのではなく、
自分自身の前の状態から計算できることがわかります。少し変形するとこうですね。

$$
\begin{align}
&\mathbf{a}^{(k)} = \mathbf{a}^{(k-2)} \cdot L^{\top} \cdot L,\\
&\mathbf{h}^{(k)} = \mathbf{h}^{(k-2)} \cdot L \cdot L^{\top},\\
&\mathbf{a}^{(k)}と、\mathbf{h}^{(k)}を正規化する.
\end{align}
$$

$k=0$から計算が始まるので、この式からは偶数番目の項しか出てきませんが、収束先は同じですので無視してしまって、次の漸化式の収束先を考えましょう。
$$
\begin{align}
&\mathbf{a}^{(k)} = \mathbf{a}^{(k-1)} \cdot L^{\top} \cdot L,\\
&\mathbf{h}^{(k)} = \mathbf{h}^{(k-1)} \cdot L \cdot L^{\top},\\
&\mathbf{a}^{(k)}と、\mathbf{h}^{(k)}を正規化する.
\end{align}
$$

すると、固有ベクトル中心性やPageRank時と同じように、$\mathbf{h}^{(k)}$も$\mathbf{a}^{(k)}$も、その収束先を、
行列の最大固有値に対する固有ベクトルとして算出できます。
具体的には、
ハブ値$\mathbf{h}^{(k)}$のほうは、 $(L \cdot L^{\top})^{\top} = L \cdot L^{\top}$ の固有ベクトル、
権威値$\mathbf{a}^{(k)}$のほうは、 $(L^{\top} \cdot L)^{\top} = L^{\top} \cdot L$ の固有ベクトル、
として、求まります。


hub_eig = np.linalg.eig(L@L.T)[1][:, 0]
hub_eig /= sum(hub_eig)
print(hub_eig.round(3))
# [0.    0.183 0.18  0.047 0.069 0.081 0.203 0.183 0.    0.055]

authority_eig = np.linalg.eig(L.T@L)[1][:, 0]
authority_eig /= sum(authority_eig)
print(authority_eig.round(3))
# [ 0.1   -0.     0.1    0.138  0.116  0.216  0.021  0.172  0.138 -0.   ]

バッチリ算出できました。固有ベクトル本当に便利ですね。

最後に、ノードのサイズとして両指標を可視化しておきましょう。
比較用にPageRankと媒介中心性も入れました。


import matplotlib.pyplot as plt

# ハブ値と権威値算出
h_dict, a_dict = nx.hits_numpy(G)
h_list = np.array([h_dict[n] for n in G.nodes])
a_list = np.array([a_dict[n] for n in G.nodes])

# PageRankと媒介中心性も算出
pr_dict = nx.pagerank_numpy(G)
pr_list = np.array([pr_dict[n] for n in G.nodes])
bc_dict = nx.betweenness_centrality(G)
bc_list = np.array([bc_dict[n] for n in G.nodes])

# 可視化
fig = plt.figure(figsize=(12, 12), facecolor="w")
ax = fig.add_subplot(221, title="HITS: hubs")
nx.draw_networkx(G, pos=pos, node_size=3000*h_list, ax=ax, node_color="c")
ax = fig.add_subplot(222, title="HITS: authorities")
nx.draw_networkx(G, pos=pos, node_size=3000*a_list, ax=ax, node_color="c")
ax = fig.add_subplot(223, title="PageRank")
nx.draw_networkx(G, pos=pos, node_size=3000*pr_list, ax=ax, node_color="c")
ax = fig.add_subplot(224, title="betweenness centrality")
nx.draw_networkx(G, pos=pos, node_size=3000*bc_list, ax=ax, node_color="c")

PageRankではほとんど評価されていない1番のノードが、Hubとしてきちんと評価されていること、
それによって1番からリンクを得ている、2,3,5が、PageRankに比べて、権威値が高くなっていることなど確認できますね。

実験する前は PageRank と 権威値 はもっと似てる結果になると思っていたのですが、
(確かに似てはいるけど) 予想よりも指標の特徴がいろいろ出ていますね。

ページランク(PageRank)

今回は、ページランク(PageRank)という指標について紹介します。
これは、Webページの重要度を決定するために作られた指標で、Googleの創業者のラリー・ペイジとセルゲイ・ブリンによって発明されました。
参考: Brin, S. and Page, L. (1998) The Anatomy of a Large-Scale Hypertextual Web Search Engine.

基本的に、次の条件を満たすページが重要である、という考えを元にしています。
1. 多くのページからリンクされている。
2. 重要なページからリンクされている。
3. リンク先を厳選したページからリンクされている。

これの、1.と2.が、前の記事で紹介した、固有ベクトル中心性に似ています。
そして、PageRankのアルゴリズム自体は固有ベクトル中心性を改善して作られています。
その際に、3.を実装しただけでなく、元の固有ベクトル中心性を有向グラフに適用した時に発生する
入力エッジがないノードに対する対応や、出力エッジがない行き止まりのノードに対する対応などが改善されています。

具体的には、グラフの隣接行列を次のように改良した Google行列を使って、固有ベクトル中心性と同じ操作を行います。

以下の説明ですが、紹介しているサイトによって、行と列が逆なので実験の際はご注意ください。
このページでは networkxで得られる隣接行列を使うので、
ノードiからノードjにエッジが伸びている時に(i, j)成分が1になる隣接行列を使います。

(1) 隣接行列の各行の値を合計値で割り、各行の値の合計を1にする。
(2) どこにも遷移先がないノードからは、任意のノードに等確率で遷移するものとする。
つまり、隣接行列の行ベクトルのうち、全ての値が0の行は、$1/(ノード数)$で埋める。
(3) ある一定確率$1-\alpha$、(通常は15%)で、隣接行列に関わらず、グラフ中のどれかのノードにランダムに移動する。
つまり、元の隣接行列に(1)(2)を施したものを$\mathbf{A}$、全ての成分が$1$の同サイズの行列を$\mathbf{I}$、
グラフのノード数を$N$とすると、$\alpha \mathbf{A} + (1-\alpha)\mathbf{I}/N$ を考える。
これをGoogle行列と言うそうです。
Wikipedia – Google matrix
(行と列が逆なので注意。)

(1)により、 3. のリンク先を厳選したページからのリンクが重要視される性質が実装されます。
(どちらかというと、リンクを乱発しているページからのリンクが軽視される、と考えた方がわかりやすいです。)
そして、(2)により行き止まりの問題が解消され、(3)によって、グラフが連結でなくても相互に行き来できるようになります。
また、(2)、(3)のそれぞれにより、入力エッジがないノードも無視されずに済みます。

さて、固有ベクトル中心性を再帰的に計算した時、値がどんどん大きくなってしまうので毎回l2ノルムで正規化していたのを覚えているでしょうか。
非常に都合のいいことに、Google行列で同じ操作をしても、値が大きくなり続ける現象は発生せず、
値の合計値がそのまま一定に保たれます。
そのため、この後のサンプルコードでは、ポイントの合計値を$1/(ノード数)$で開始します。

さて、それでは実装です。
まずはランダムにグラフを生成し、隣接行列からGoogle行列の算出まで行いました。


import networkx as nx
import numpy as np

# ランダムにグラフを生成する
G = nx.random_graphs.fast_gnp_random_graph(
    n=7,
    p=0.3,
    directed=True
)

# 隣接行列 (i番目からj番目のノードにパスがある時、(i, j)成分が1)
adj_matrix = nx.to_numpy_array(G)
print(adj_matrix)
"""
[[0. 1. 0. 0. 1. 0. 1.]
 [0. 0. 1. 1. 1. 0. 1.]
 [0. 1. 0. 0. 1. 0. 0.]
 [0. 0. 0. 0. 1. 1. 0.]
 [0. 1. 0. 1. 0. 0. 1.]
 [0. 0. 1. 0. 0. 0. 0.]
 [0. 0. 1. 0. 1. 1. 0.]]
"""

for i in range(adj_matrix.shape[0]):
    if sum(adj_matrix[i]) != 0:
        # 行の値の合計値を1に正規化する。
        adj_matrix[i] /= sum(adj_matrix[i])
    elif sum(adj_matrix[i]) == 0:
        # 行の値が全て0の行は、1/Nで埋める。
        adj_matrix[i] = 1/nx.number_of_nodes(G)

print(adj_matrix.round(2))
"""
[[0.   0.33 0.   0.   0.33 0.   0.33]
 [0.   0.   0.25 0.25 0.25 0.   0.25]
 [0.   0.5  0.   0.   0.5  0.   0.  ]
 [0.   0.   0.   0.   0.5  0.5  0.  ]
 [0.   0.33 0.   0.33 0.   0.   0.33]
 [0.   0.   1.   0.   0.   0.   0.  ]
 [0.   0.   0.33 0.   0.33 0.33 0.  ]]
"""
# Google行列の計算
N = nx.number_of_nodes(G)
alpha = 0.85
g_matrix = alpha*adj_matrix+(1-alpha)*np.ones(shape=adj_matrix.shape)/N
print(g_matrix)
"""
[[0.021 0.305 0.021 0.021 0.305 0.021 0.305]
 [0.021 0.021 0.234 0.234 0.234 0.021 0.234]
 [0.021 0.446 0.021 0.021 0.446 0.021 0.021]
 [0.021 0.021 0.021 0.021 0.446 0.446 0.021]
 [0.021 0.305 0.021 0.305 0.021 0.021 0.305]
 [0.021 0.021 0.871 0.021 0.021 0.021 0.021]
 [0.021 0.021 0.305 0.021 0.305 0.305 0.021]]
"""

Google 行列が求まったので、固有ベクトル中心性の時と同様に、
定数のベクトルに繰り返しかけて見ます。


# ページランクを1/Nで初期化する
page_rank = np.ones(shape=N)/N
print(page_rank.round(3))

# Google行列を繰り返し掛ける
for _ in range(30):
    page_rank = page_rank@g_matrix
    print(page_rank.round(3))

"""
[0.143 0.143 0.143 0.143 0.143 0.143 0.143]
[0.021 0.163 0.214 0.092 0.254 0.123 0.133]
[0.021 0.19  0.198 0.128 0.23  0.098 0.134]
-- (中略) --
[0.021 0.177 0.192 0.126 0.238 0.113 0.132]
[0.021 0.177 0.192 0.126 0.238 0.113 0.132]
[0.021 0.177 0.192 0.126 0.238 0.113 0.132]
"""

一定の値に収束していますね。これこそが掲題のPageRankです。

もちろんですが、networkxを使って計算することもできます。普段はこれを使いましょう。
numpyを使った実装と、scipyを使った実装、どちらも使っていないものの、3種類用意されています。
ドキュメントはこちら


print(nx.pagerank_numpy(G))
"""
{0: 0.021428571428571422,
 1: 0.17666594642678057,
 2: 0.19229348384918474,
 3: 0.12641130083513927,
 4: 0.23802782043838958,
 5: 0.11269014761536654,
 6: 0.1324827294065679}
"""

また、最初のコード例の中で定義に沿ってGoogle行列を計算しましたが、グラフからGoogle行列を計算する関数も用意してくれています。
google_matrix

一応動かして結果が同じであることを見ておきましょう。


print(nx.google_matrix(G).round(3))
"""
[[0.021 0.305 0.021 0.021 0.305 0.021 0.305]
 [0.021 0.021 0.234 0.234 0.234 0.021 0.234]
 [0.021 0.446 0.021 0.021 0.446 0.021 0.021]
 [0.021 0.021 0.021 0.021 0.446 0.446 0.021]
 [0.021 0.305 0.021 0.305 0.021 0.021 0.305]
 [0.021 0.021 0.871 0.021 0.021 0.021 0.021]
 [0.021 0.021 0.305 0.021 0.305 0.305 0.021]]
"""

値は揃っていますね。 ただ、データ型が numpy.matrix なのでそこだけ注意しましょう。
(と言っても、numpy.arrayとの違いで困ることはほぼないのですが。)

最後に、このページランクですが、固有ベクトル中心性と同じように、
Google行列の固有ベクトルとしても計算できます。
固有ベクトルを求める前に、この記事の定義だと転置する必要があることと、
numpyの固有ベクトルはl2ノルムが1に正則化されているので、
l1ノルムが1になるようにスカラー倍してやる必要があることに注意が必要です。
実際にやってみます。


eigen_vector = np.abs(np.linalg.eig(g_matrix.T)[1][:, 0])
eigen_vector /= sum(eigen_vector)
print(eigen_vector.round(3))
# [0.021 0.177 0.192 0.126 0.238 0.113 0.132]

ご覧の通り、再帰的に求めたPageRank,ライブラリで求めたPageRankと一致しました。

もともと、Webページの重要度を測るために考案されたものですが、
世の中には有向グラフの構造を持つデータは意外に多く、
その各ノードの重要度を測りたい場面というのは頻繁にあるので、活用の場面はたくさんあります。

固有ベクトル中心性

前回の記事に引き続き、グラフのノードの中心性の話です。
参考: ネットワークグラフの中心性
前回紹介した3種類の中心性はノード間のつながり方によってのみ算出されましたが、
それぞれのノードは対等に扱っていました。

例えば、次数中心性では、何個のノードとつながっているかのみを気にしており、つながっているノードの性質は気にしていません。
しかし、ノードの重要度を図る上で、同じ数のノードに繋がっているとしても、
より重要なノードと繋がっている方が需要と考えることは自然なことです。

この、重要なノードとつながっているものの方が重要であると言う概念を取り入れた中心性が、
固有ベクトル中心性(eigenvector centrality)です。

これを説明したいのですが、ちょっと複雑なので、
最初に次のようなゲームを考えてみましょう。

1. 初期の状態(t=0)において、各ノードはそれぞれ等しいポイントを持っている。
2. 次の状態(tが1増える)において、各ノードは、自分のポイントを繋がっている全てのノードに渡す。
(有向グラフの場合は、矢印の向きにのみ渡します。)
各ノードは、受け取ったポイントの合計を自分のポイントとする。
3. 2を繰り返す。

これなら、たくさんのノードとつながっていると、どんどんポイントをもらえます。
また、たくさんポイントを持っているノードとつながっていると有利です。

具体的にこれを計算してみるのですが、その前に隣接行列(adjacency matrix)という概念を導入しておきます。
これは、グラフGに対して定まる$n\times n$($n$はグラフのノード数)行列で、
$i$番目のノードから$j$番目のノードに向かって辺が伸びていたら、$(i, j)$成分が$1$、そうでなければ$0$になるものです。
(無向グラフの場合は、対称行列になります)
networkxには、隣接行列を取り出す関数がたくさん用意されています。(結果のデータ型が少しずつ違います。)
自分がよく使うのを二つだけ紹介します。この記事では、to_numpy_arrayの方を使います。

nx.to_numpy_array() # numpyのarray型で返す。グラフが小さい時はこれがオススメ.
nx.adjacency_matrix(G) # これは scipyの疎行列の型で返します。グラフが大きい時はこちら。


import networkx as nx
import numpy as np
while True:
    # ランダムにグラフを生成する
    G = nx.random_graphs.fast_gnp_random_graph(
        n=7,
        p=0.3,
        directed=False
    )
    # 連結なグラフが生成できたらループを抜ける
    if nx.is_connected(G):
        break


# 隣接行列 (i番目からj番目のノードにパスがある時、(i, j)成分が1)
adj_matrix = nx.to_numpy_array(G)
print(adj_matrix)

"""
[[0. 0. 0. 1. 1. 0. 0.]
 [0. 0. 1. 1. 0. 0. 0.]
 [0. 1. 0. 1. 0. 1. 0.]
 [1. 1. 1. 0. 0. 0. 1.]
 [1. 0. 0. 0. 0. 0. 0.]
 [0. 0. 1. 0. 0. 0. 0.]
 [0. 0. 0. 1. 0. 0. 0.]]
"""

さて、隣接行列を何に使うかというと、先ほど定義したゲームの手順2のポイントの受け渡しです。
これは、for文を回して愚直に計算すると結構面倒なのですが、なんと、ポイントのベクトルにこの連結行列をかけるだけで実装できてしまします。

全てのノードのポイントが1から初めて、$t=3$までやってみましょう。


import matplotlib.pyplot as plt

# 配置を固定しておく
pos = nx.spring_layout(G)

# 各ノードに等しい点を与える。
points_list = []

points_list = [np.ones(shape=G.number_of_nodes())]
for i in range(3):
    # ポイントベクトルに隣接行列を掛けたものが次の状態のポイントベクトル
    points_list.append(points_list[i]@adj_matrix)

# グラフを可視化
fig = plt.figure(figsize=(14, 14), facecolor="w")

for i in range(0, 4):
    ax = fig.add_subplot(2, 2, i+1, title=f"t={i}")
    nx.draw_networkx(
        G,
        ax=ax,
        node_color="c",
        pos=pos,
        node_size=700 * points_list[i] / np.mean(points_list[i]),
        labels=dict(zip(G.nodes, points_list[i])),
    )
plt.show()

出力がこちら。

このゲームのルールが、ポイントベクトルと隣接行列の積で再現できてることが確認できます。

さて、ご覧の通り、これを延々と続けていくと、各ノードのポイントがどこまでも大きくなってしまいます。
これを防ぐために、ポイントはl2ノルムで正規化することにしましょう。(要するにポイントベクトルの長さが1になるように縮めます。)

すると、面白いことに、この操作を繰り返すとポイントが一定の値に収束します。


# 各ノードに等しい点を与える。
points = np.ones(shape=G.number_of_nodes())
# l2正規化
points /= np.linalg.norm(points)

for _ in range(30):
    # 隣接行列をかける
    points = points@adj_matrix
    # l2正規化
    points /= np.linalg.norm(points)
    print(points.round(3))

"""
[0.333 0.333 0.5   0.667 0.167 0.167 0.167]
[0.34  0.476 0.476 0.544 0.136 0.204 0.272]
[0.276 0.413 0.496 0.634 0.138 0.193 0.221]
-- 中略 --
[0.288 0.444 0.502 0.596 0.116 0.203 0.241]
[0.288 0.444 0.502 0.596 0.116 0.203 0.241]
[0.288 0.444 0.502 0.596 0.116 0.203 0.241]
"""

この値こそが、記事タイトルにあげた、固有ベクトル中心性です。

何故このような名前になっているかというと、この値は隣接行列(の、転置行列の)の最大固有値に対する固有ベクトルとして算出できるからです。
無限ループさせて収束を観測するのは、大きなグラフでは大変なので、とてもありがたい性質ですね。
今回は無向グラフを使っているので、 .Tして、転置を取らなくても結果は同じですが、
有向グラフでは転置を取る必要があるのでサンプルコードにも入れておきました。

実際に、numpyで固有ベクトルを計算してみて見比べてみましょう。


eigen_vector = np.abs(np.linalg.eig(adj_matrix.T)[1][:, 0])
print(eigen_vector.round(3))
# [0.288 0.444 0.502 0.596 0.116 0.203 0.241]

確かに同じ値になっています。(符号が逆のベクトルが戻ってくることがあるので、np.absで絶対値取っています。)
(この記事の本題ではないですが、np.linalg.eig は使い方になかなかクセがありますね。
そのうち個別にまとめたいです。)

networkxにも、固有ベクトル中心性を求める関数は準備されています。しかも二つ。
eigenvector_centrality
eigenvector_centrality_numpy

それぞれ、numpyを使わない実装と使う実装のようです。
eigenvector_centrality_numpy の方がメリットが多いようなので、numpyも入っている環境ならこちらを使いましょう。

どちらも結果がdict型なので、使う時はその点だけ注意です。


print(nx.eigenvector_centrality_numpy(G))
"""
{
    0: 0.2878634949610299,
    1: 0.4438129053071405,
    2: 0.5022278145024875,
    3: 0.5959832042188999,
    4: 0.1163324095757721, 
    5: 0.20296207348193807,
    6: 0.24085083182520173
}
"""

この固有ベクトル中心性は、重要なものの近くが重要という再帰的な定義がきっちり計算できる点で数学的にも面白いです。
ただ、いくつか欠点があります。
今回の例は連結な無向グラフを扱いましたが、そうでない場合、つまり有向グラフや孤立したノードがある場合に問題が発生します。
例えば、どの点からも流入がないノードはすぐポイントが0になってしまい、
さらにそのような点からしかパスが通ってないところは連鎖的に0点になってしまいます。
行き止まりの存在も課題です。

次の記事ではこのあたりの問題への対応を紹介する予定です。

ネットワークグラフの中心性

前の記事でサンプルとして(折れ線グラフや棒グラフではなく、グラフ理論で言うところの)グラフを扱ったのでもう少し紹介します。
参考: Matplotlibの配色を別の処理でも流用したい

グラフについて分析するとき「どの点が重要なのか」という問いは非常に自然なものです。
そして、「中心にある点が重要なんじゃないか」と考えることもそこそこ自然な発想になります。
ただ、扱う対象が普通の幾何学的な図形ではなく、点とそれらの間にあるつながりという抽象的な概念で構成されたグラフの場合、
どの点が中心なのかというのは非自明な問題になります。
可視化してみれば確かにどれかの点が真ん中らへんにあるように見えるのですが、それは単に可視化の際にたままたそこにプロットされたというだけで、
グラフ理論で言うところの中心ではないからです。

この問題に対応するために、複数の中心が定義され、中心らしさを表す指標がいくつか提案されています。
networkxにも色々定義されているので、その中でも定義が単純でわかりやすいものを紹介します。
networkxのドキュメントではこちらに該当します。
Centrality

今回の記事では次のグラフをサンプルに使います。
何か特別な名前がついてるやつではなく、僕が今適当に構成したものです。


import matplotlib.pyplot as plt
import networkx as nx

G = nx.Graph()
G.add_edges_from([
    (0, 1),
    (1, 2),
    (2, 3),
    (3, 0),
    (1, 3),
    (0, 4),
    (4, 5),
    (5, 0),
    (5, 6),
])

# 可視化
fig = plt.figure(facecolor="w")
ax=fig.add_subplot(1, 1, 1, title="Sample Graph")
nx.draw_networkx(
    G,
    node_color="c"
)

さて、サンプルが用意できたので、次数中心性/近接中心性/媒介中心性の3種類の中心性の定義を紹介します。

次数中心性
一番単純でわかりやすいのが次数中心性(degree centrality)です。
これは、各ノードの次数(そのノードにつながっている、辺の本数)を指標とするものです。
正確には、各ノードの次数は最大でも「ノード数-1」までの値しか取れないので、「ノード数-1」で割って正規化したものを使います。
networkxではdegree_centralityで計算できます。


print("ノード番号, 次数中心性")
for k, v in nx.degree_centrality(G).items():
    print(k, ",", v)
"""
ノード番号, 次数中心性
0 , 0.6666666666666666
1 , 0.5
2 , 0.3333333333333333
3 , 0.5
4 , 0.3333333333333333
5 , 0.5
6 , 0.16666666666666666
"""

計算してみた各値を6(=7-1)倍すると、全部整数になり、各ノードから伸びてる辺の数に一致することがわかります。

近接中心性
距離がベースになっていて、円の中心などとイメージが近いのが近接中心性(closeness centrality)です。
これは、ある点から、そのほかの全ての点へのそれぞれの距離の平均値を元に決まります。
ただ、ほかの全ての点に近い(つまり距離が小さい)ほど、中心と見なしたいので、
距離の平均の逆数を取ります。
今回のグラフでは各辺に重み付けなどしていない(つまり全部重さ1とみなす)ので、ここで言う距離というのは最短経路を通った時に通過する辺の数です。
networkxではcloseness_centralityで計算できます。


print("ノード番号, 次数中心性")
for k, v in nx.degree_centrality(G).items():
    print(k, ",", v)
"""
ノード番号, 次数中心性
0 0.75
1 0.6
2 0.42857142857142855
3 0.6
4 0.5454545454545454
5 0.6
6 0.4
"""

試しに一つ具体的に計算しておきましょう。
0番のノードに着目します。
このノードの1~6番目までのノードの距離はそれぞれ、$1,2,1,1,1,2$ で、合計は$8$です。なので平均は$4/3$になります。
これの逆数をとったものが$3/4=0.75$なので、ライブラリの結果と一致しました。

媒介中心性
最後が媒介中心性(betweenness centrality)です。
個人的には、この記事で紹介した3種類の中では一番よく使います。
(主観的な感想です。媒介中心性がほかの二種に比べて理論的に優れているということを主張するものではありません。)
これは、着目している点以外の2点を結ぶ最短経路のうち、その点を通過するものの割合です。
networkxではbetweenness_centralityで計算できます。


print("ノード番号, 媒介中心性")
for k, v in nx.betweenness_centrality(G).items():
    print(k, v)
"""
ノード番号, 媒介中心性
0 0.6
1 0.13333333333333333
2 0.0
3 0.13333333333333333
4 0.0
5 0.3333333333333333
6 0.0
"""

さて、これは個別に解説したいと思います。
まず、2, 4, 6 の媒介中心性は0になっています。
これは、可視化した図を見るとわかるのですが、それぞれの点について、ほかの2点をどう選んでも、対象の点を通ると遠回りになるからです。

次にわかりやすいのは
5番です。まず、5番以外の6点から2点を選ぶ方法は全部で$6*5/2=15$通りあります。
その中で、5番を経由すると最短になるのは、6番の点と、そのほかの5点のどれかを結ぶ5通りです。
そのため、5版のノードの媒介中心性は$5/15=1/3$になります。
0番も同様に数えると、4,5,6のどれかと、1,2,3のどれかを結ぶ$3*3=9$通りの最短経路が0番を通過し、
媒介中心性は$9/15=3/5=0.6$になります。

さて、のこるは同じ値になっている1番と3番です。
まずは1番の方ですが、最短経路で1番のノードを通るのは2番のノードと、0,4,5,6のどれかを結ぶ4本になります。
となると、媒介中心性は$4/15=2.666…$になっても良さそうなのですが、実際にはこの$1/2$の値になっています。
実はこれは2番のノードと、0,4,5,6のどれかを結ぶ最短経路がそれぞれ複数あるのが原因です。
1番のノードの代わりに3番のノードを通っても良いわけです。
ということで、1番を通る最短経路を数える時に$0.5$倍して数えるので上の計算例の値になります。
3番も同様です。

辺の媒介中心性
さて、ノードの中心性を3つ紹介しましたが、最後の媒介中心性はノードだけではなく、辺についても定義できます。
ノードの場合は自分以外の2点でしたが、辺の場合はグラフ中の全てのノードから2点選び、
それらの最短経路のうち何本が自身を通過するかで定義されます。
networkxではedge_betweenness_centralityで計算できます。

計算結果が少数が複雑で、ぱっと見わかりにくかったので、
ノードの組みの場合の数、つまり$7*6/2=21$通りを掛けて、整数化したものを表示してみました。


print("辺, 辺の媒介中心性*21")
for k, v in nx.edge_betweenness_centrality(G).items():
    print(k, v*21)
"""
辺, 辺の媒介中心性*21
(0, 1) 6.0
(0, 3) 6.0
(0, 4) 4.0
(0, 5) 8.0
(1, 2) 3.0
(1, 3) 1.0
(2, 3) 3.0
(4, 5) 2.0
(5, 6) 6.0
"""

(1, 3) が 1 なのは、まさにその1と3をつなぐ時以外は通らないからですね。
一方で(5, 6)は、6とほかの点をつなぐ時は必ず通らないといけないので、中心性が高くなっています。

可視化した図では(5, 6)のエッジはかなり端っこにあるように見えるのですが、
媒介中心性は2位タイの高さということで、
可視化した時に真ん中にあるかどうかと、グラフ理論で言うところの中心は違うと言うことの雰囲気が伝わればと思います。

最後に、もう少し大きめのグラフで、それぞの中心性を算出して比較してみましょう。
計算した中心性はノードのサイズで示しました。


# ランダムにグラフデータ生成
while True:
    G=nx.random_graphs.fast_gnp_random_graph(25, 0.1)
    if nx.is_connected(G):
        # 連結なグラフができたら抜ける
        break


# 3種類の中心性をそれぞれ計算
dc_dict = nx.degree_centrality(G)
dc_list = np.array([dc_dict[n] for n in G.nodes])

cc_dict = nx.closeness_centrality(G)
cc_list = np.array([cc_dict[n] for n in G.nodes])

bc_dict = nx.betweenness_centrality(G)
bc_list = np.array([bc_dict[n] for n in G.nodes])

# 中心性をノードのサイズで表して可視化
pos = nx.spring_layout(G, iterations=300)
fig = plt.figure(facecolor="w", figsize=(8, 24))

ax=fig.add_subplot(3, 1, 1, title="Degree centrality ")
nx.draw_networkx(
    G,
    pos=pos,
    ax=ax,
    node_color="c",
    node_size=dc_list*300/np.mean(dc_list),
)
ax=fig.add_subplot(3, 1, 2, title="Closeness centrality")
nx.draw_networkx(
    G,
    pos=pos,
    ax=ax,
    node_color="c",
    node_size=cc_list*300/np.mean(cc_list),
)
ax=fig.add_subplot(3, 1, 3, title="Betweenness centrality")
nx.draw_networkx(
    G,
    pos=pos,
    ax=ax,
    node_color="c",
    node_size=bc_list*300/np.mean(bc_list),
)
plt.show()

出力された結果がこちら。

Matplotlibの配色を別の処理でも流用したい

Python(と jupyter notebook)でデータを可視化する場合、色を16進数のRGBで指定できるライブラリは多くあります。
Matplotlibがベースになっているものは、そのカラーマップを指定できることも多いのですし、
「rは赤」、「bは青」など一部の色はアルファベットや色名で指定できるのですが、
もっと多くの色を使いたかったり、値によってグラデーションをつけたい場合で逐一RGBを構築するのは結構な手間です。

そこで、Matplotlibの配色をそのまま流用できないかと思って調べてみました。
結論から言うと、結構簡単に使えそうです。

まず、配色そのもののデータは、
matplotlib.cm と言うモジュールに含まれています。
配色はその名前で指定しますが、名前と実際の色の対応はこちらのリファレンスをみると良いでしょう。
Colormap reference

使いたいカラーマップが決まったら、cm.get_cmap() か、 cmの属性として、使うことができます。
要するに次の2行は同じものです。


cm.get_cmap("Greens")
cm.Greens

さて、どちらもカラーマップのオブジェクトを返してくれますが、
そのカラーマップのオブジェクトにに数値を渡すと、RGBのタプルを返してくれます。


import matplotlib.cm as cm

print(cm.get_cmap("Greens")(0.7, alpha=0.5))
# (0.18246828143021915, 0.5933256439830834, 0.3067589388696655, 0.5)
print(cm.get_cmap("Paired")(3))
# (0.2, 0.6274509803921569, 0.17254901960784313, 1.0)

渡す数値ですが、連続的に色が変化するものには、 0〜1の値を渡します。
色の値が不連続な(要はリファレンスで、Qualitativeのカテゴリにあるもの)は、0〜1の値で渡しても大丈夫ですが、
整数値で0,1,2,3などを指定しても大丈夫です。
これらは、1と1.0や2と2.0など、同じ値でも整数型と浮動小数型で結果が変わるので注意してください。
ちなみに、値はリスト形式で複数同時に渡しても大丈夫です。

さて、最初の話に戻りますが、このRGB値のタプルを他のライブラリ等で使うには、16進数の文字列に変換する必要があります。
255倍して16進数の文字列に変化して、シャープをつけて結合するコードを自分で書いてもいいのですが、
なんと Matplotlibにその関数が用意されていました。

matplotlib.colors.rgb2hex です。
これはなぜか、色のリストは受け取ってくれないので、順番に適用していかないといけないのですが、
RGBのタプルを16進数文字列に手軽に変換してくれます。
(keep_alpha=Trueを指定すると透明度も含めてくれます。デフォルトはFalseです。)

試しにカラーマップから10色取り出してみましょう。


import matplotlib.colors as mcolors
import matplotlib.cm as cm
import numpy as np

cmap = cm.get_cmap("BuGn")
for rgb in cmap(np.arange(0, 1, 0.1)):
    print(mcolors.rgb2hex(rgb))

"""
#f7fcfd
#e9f7fa
#d6f0ee
#b8e4db
#8fd4c2
#65c2a3
#48b27f
#2f9858
#157f3b
#006428
"""

10個の色が取り出せましたね。

最後に何か例を出しておきたいので、networkx で作成したグラフに中心性で色をつけてみました。
(グラフの中心性には複数の種類がありますが、今回は媒介中心性を使いました。)


import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.cm as cm
import matplotlib.colors as mcolors


while True:
    # ランダムにグラフを生成する
    G = nx.random_graphs.fast_gnp_random_graph(15, 0.2)
    # 連結なグラフが生成できたらループを抜ける
    if nx.is_connected(G):
        break

# 媒介中心性の計算
centrality = nx.betweenness_centrality(G)
# 辞書形式なので、ノードの順番と揃えてリスト化する。
centrality_list = np.array([centrality[node] for node in G.nodes])
# 媒介中心性を0〜1に正規化する
color_level = centrality_list - min(centrality_list)
color_level/=max(color_level)
# ノードの色の生成
rgb_list = cm.get_cmap("Oranges")(color_level, alpha=0.8)
node_color=[mcolors.rgb2hex(rgb, keep_alpha=True) for rgb in rgb_list]

# グラフの可視化
fig = plt.figure(figsize=(8, 8), facecolor="w")
ax = fig.add_subplot(1,1,1)
nx.draw_networkx(
                G,
                node_color=node_color,
                node_size=500,
                edge_color="#aaaaaa",
                node_shape="s"
            )

出力がこちら。

媒介中心性が高いところが色が濃くなっているのがわかります。

WordPressにお問い合わせフォームを作る

このブログに問い合わせフォームをつけることにしたのでその手順のメモです。
複数のプラグインがあるようですが、比較的情報が多かった Contact Form 7 を使うことにしました。

まずはプラグインをインストールします。
– ダッシュボードの左ペインのプラグインをクリック
– Contact Form 7 を検索
– 今すぐインストールボタンからインストール
– インストールしたら有効化ボタンをクリック
– 左ペインに お問い合わせ メニューができたことを確認

新しくできた お問い合わせメニューを選択すると、最初からコンタクトフォーム1というフォームができていました。
設定項目がたくさんあるのですが、ざっと見た限りではそのまま使って問題なさそうなのでデフォルトで使います。

このショートコードをコピーして、投稿、固定ページ、またはテキストウィジェットの内容にペーストしてください:
というコメントの下に貼り付け用のコードがあるのでそれをコピーします。

これをブログ内のどこかに貼れば完成するのですが、サイドバーに置くことにしました。
ウィジェットの一覧から「テキスト」を選択し、ブログサイドバーに追加します。
そして、テキストの本文部分に先ほどの貼り付け用のコードを挿入して完成です。

あとは各ページに表示されたので送信テストを行いました。

DataFrameの日付の欠損行を埋める方法

日付に限らず連番等でも使える方法ですが、自分が日単位の時系列データで行うことが多いのでそれで説明します。

DBなどからデータを日単位で集計してpandasのDataFrameを作った時、集計対象のデータがなかった日は行ごと欠損してしまった状態になります。

例えば次のような感じです。


print(df.head(5))
"""
         date  value
0  2020-01-02      9
1  2020-01-06      3
2  2020-01-07      4
3  2020-01-09      9
4  2020-01-11      2
"""
print(df.tail(5))
"""
          date  value
15  2020-02-01      3
16  2020-02-02      2
17  2020-02-09      3
18  2020-02-11      2
19  2020-02-18      2
"""

このままで困らないこともあるのですが、累積和をとるときや、matplotlibで可視化するときなど、
欠損してる日付を補完しておきたいことがあります。

これまで、補完対象のDataFrameを別途構成してappendすることが多かったのですが、
必要な日付の一覧を持ったDataFrameと結合(SQLでいうJoin,pandasの関数ではMerge)すると手軽に補完できることに気づきました。

具体的には次のようなコードになります。


# dates に必要な期間の日付の一覧が入ってるとします。
date_df = pd.DataFrame({"date": dates})

# date_df と 結合する
df = pd.merge(date_df, df, on="date", how="left")
# NaNを 0で埋める
df[["value"]] = df[["value"]].fillna(0)

この例だと単純なので、不足している分のデータFrameを作ってたすのと比べて、あまりメリットを感じないのですが、
これが、例えば複数のキーに対してそれぞれ日付データを全部揃えたいケースになると、かなり楽になります。

例えば、元のデータフレームが次だったとします。


print(df2)
"""
    key        date  value
0  key1  2020-01-03      5
1  key1  2020-01-04      3
2  key1  2020-01-10      5
3  key2  2020-01-02      4
4  key2  2020-01-03      1
5  key2  2020-01-04      9
6  key3  2020-01-04      2
7  key3  2020-01-06      5
8  key3  2020-01-09      8
"""

このDataFrameの key1,key2,key3 に対して、 2020-01-01〜2020-01-10の行を全て揃えたいとします。
このようなときは、次鵜のようにして、keyの値と日付の値のペア全てのDataFrameを作ってそれと結合すると簡単に保管できます。


# key と 日付のペアを網羅したDataFrameを作る
keys, dates = np.meshgrid(
        ["key1", "key2", "key3"],
        [(datetime(2020, 1, 1) + timedelta(days=i)).strftime("%Y-%m-%d") for i in range(10)]
    )

key_date_df = pd.DataFrame(
        {
            "key": keys.ravel(),
            "date": dates.ravel(),
        }
    )

# 結合してソート
df2 = pd.merge(key_date_df, df2, how="left").sort_values(["key", "date"])
# NaNを 0で埋める
df2[["value"]] = df2[["value"]].fillna(0)
# インデックのリセット
df2.reset_index(inplace=True, drop=True)

途中で meshgridを使いましたが、meshgridに慣れてない場合は別の方法でも大丈夫です。

Pythonで連続した日付のリストを作る

日付の連番を文字列で必要になったので、Pythonで生成する方法を二つメモしておきます。

一つ目は、 標準ライブラリである datetime を使うものです。
開始日を生成して、必要な日数だけtimedeltaで差分を加算したものをリスト化したら得られます。
生成したリストはdatetime.datetime型なので、strftimeで文字列に変換して完成です。


from datetime import datetime, timedelta

# 日付のリスト生成()
date_list = [datetime(2020, 1, 25) + timedelta(days=i) for i in range(10)]
# 文字列に変換
date_str_list = [d.strftime("%Y-%m-%d") for d in date_list]
print(date_str_list)
"""
['2020-01-25', '2020-01-26', '2020-01-27', '2020-01-28',
'2020-01-29', '2020-01-30', '2020-01-31',
'2020-02-01', '2020-02-02', '2020-02-03']
"""

もう一つはpandasのdate_range関数を使います。
いくつかみて回った限りではこちらの方が人気のようです。
生成されるのが、DatetimeIndex なので、DataFrameのIndexで使いたい場合はこちらの方が便利なのだと思います。
また、生成するデータの頻度を指定するオプションが異常なほど充実しています。
参考: Time series / date functionality

とりあえず、同じデータを生成してみます。


import pandas as pd 

date_index = pd.date_range("2020-01-25", periods=10, freq="D")
print(date_index)
"""
DatetimeIndex(['2020-01-25', '2020-01-26', '2020-01-27', '2020-01-28',
               '2020-01-29', '2020-01-30', '2020-01-31', '2020-02-01',
               '2020-02-02', '2020-02-03'],
              dtype='datetime64[ns]', freq='D')
"""

# 配列に変換して必要な文字列に加工
date_ary = date_index.to_series().dt.strftime("%Y-%m-%d")
print(date_ary.values)
"""
['2020-01-25' '2020-01-26' '2020-01-27' '2020-01-28' '2020-01-29'
 '2020-01-30' '2020-01-31' '2020-02-01' '2020-02-02' '2020-02-03']
"""

これだけだと、ちょっと手間が余計にかかっていて、2つ目の方法にメリットがないように見えますが、
date_rangeは指定できる引数の種類が多く、場合によってはかなり柔軟に対応できます。

たとえば、開始日時と件数の代わりに、開始日時と終了日時で指定したり、終了日時とデータ件数で指定できます。
次の3行は全て同じ結果を返します。


pd.date_range("2020-01-25", periods=10, freq="D")
pd.date_range(start="2020-01-25", end="2020-02-03", freq="D")
pd.date_range(end="2020-02-03", periods=10,  freq="D")

また、時間単位や月単位、月単位といった頻度もfreqで指定できますが、
平日のみとか、毎月の15日と月末日など、datetimeで実装するには少し面倒なものも手軽に作れます。
再掲ですが、こちらのリファレンスを見ると色々あって面白いです。
Time series / date functionality

PyPIのパッケージをcondaでインストールする方法

前回の記事で、condaの公式リポジトリとconda-forgeを探して、それでも見つからなかったパッケージは環境を分けてpipで入れるという話を書きましたが、
一応、PyPIのパッケージをcondaで入れる方法は存在します。

それが、自分でcondaバッケージをビルドする方法で、(スムーズに進めば)具体的には次の手順でできます。
(前回の記事の反省を踏まえてさっさとコマンドを載せておきます。)


conda skeleton pypi [パッケージ名]
conda build [パッケージ名]
conda install --use-local [パッケージ名]

ドキュメントはこちら:Conda-build documentation

試しにこのブログを書くのに欠かせない pycodestyle_magic を入れてみます。これはcondaの公式リポジトリにもconda-forgeにも今日時点では存在しません。
準備として、必要なパッケージである、次の3つをcondaで入れておきます。
これがconda install の場合との大きな違いで、依存するライブラリは事前自分で入れておかないとエラーになります。
flit はこれが何かよく理解していないのですが、入れておかないとビルドする時に、 No module named ‘flit’ というエラーが出ました。


conda install pycodestyle
conda install flake8
conda install flit

さて、準備できたら次のコマンドを順番に実行します。


conda skeleton pypi pycodestyle_magic
conda build pycodestyle_magic
conda install --use-local pycodestyle_magic

conda skelton を実行した段階で、カレントディレクトリ直下に、meta.yamlファイルを含むディレクトリが出来上がります。


$ ls
pycodestyle_magic
$ ls pycodestyle_magic/
meta.yaml

次のconda build も成功するはずだったのですが、結局エラーが出たので対応します。
(3行目の conda installはまだ実行できず。)

出たエラーはこれ。


ModuleNotFoundError: No module named 'flit'

事前にインストールしているのに見つけられていないようです。
meta.yamlファイルを開いて、追記してみます。
(numpyで似たようなことをして解決している人がいたので真似しました。結果的に成功したようです。)


vim pycodestyle_magic/meta.yaml

#requirements の host: と run: に - flit を追記して保存。

requirements:
  host:
    - pip
    - python
    - flit
  run:
    - python
    - flit

さて、もう一回、conda build pycodestyle_magicすると成功しました。


####################################################################################
Resource usage summary:

Total time: 0:00:23.6
CPU usage: sys=0:00:00.3, user=0:00:00.6
Maximum memory usage observed: 75.1M
Total disk usage observed (not including envs): 264B


####################################################################################
Source and build intermediates have been left in /Users/[ユーザー名]/.pyenv/versions/[インストールしたAnacondaのディレクトリ]/conda-bld.
There are currently 1 accumulated.
To remove them, you can run the ```conda build purge``` command

メッセージにある通り、Anacondaのインストールフォルダ配下にビルドのアウトプットは移動しており、
さっきのmeta.yamlファイルがあった所の中身はそのままです。

conda-bld/ の下には、 pycodestyle_magic_1582538942427 というディレクトリができていて、よくわからないファイルがあります。

さて、buildが成功したので最後にインストールです。
(紛らわしい書き方して済みませんが、Anacondaのディレクトリではなく、skeletonやbuildしたのと同じディレクトリでそのまま)


# 今度は成功する。
conda install --use-local pycodestyle_magic

# インストール結果の確認
$ conda list | grep pycodestyle
pycodestyle               2.5.0                    py37_0
pycodestyle_magic         0.5                      py37_0    local

結果確認は、わかりやすいように普通にcondaで入れたpycodestyleも表示しましたが、
このskeletonを使う方法で入れたパッケージは local マークがつきます。

最後に後片付けです。
カレントディfレクトリに、skeletonでできた meta.yamlファイルが入ったディレクトリがあると思いますが、
インストールが終わったら不要なので消してよいと思います。
また、
conda build purge コマンドで、
[Anacondaのインストールディレクトリ]/conda-bld
にできていた一次ファイルたちを消せます。


rm -r [パッケージ名]
conda build purge

あとは入れたパッケージを使うだけです。
今回はjupyterのmagicコマンドだったので、
%load_ext pycodestyle_magic

%%pycodestyle
をそれぞれ試しました。

これで、conda-forgeにもないパッケージもPyPIからインストールできました。