[pandas/matplotlib]時系列データをプロットするときはデータ型に注意

[pandas/matplotlib] 時系列データをプロットするときはデータ型に注意

pandasで時系列データを作って、matplotlibでプロットするときにエラーが出たけど、調べてみたらデータ型(dtype)を間違えていたせいだった。
時系列データのデータ型には気をつけましょう。
という話のメモ。

準備

import datetime
import pandas as pd
import matplotlib.pyplot as plt
pd.options.display.notebook_repr_html = False  # jupyter notebook上での出力形式を制御するために書いています。無くても動きます。
# 動作環境の確認
print(pd.__version__)
import matplotlib
print(matplotlib.__version__)

# --------------------

1.1.2
3.3.1

失敗例 axvspanを実行するとエラーになった

まず適当な時系列データを作ります。

# 2021年の祝日を適当に抜き出して並べただけで、データに意味はありません
date_str_list = ['2021-01-11', '2021-02-11', '2021-03-20', '2021-04-29', '2021-05-05']
val_list = [10, 30, 20, 50, 40]
df_date_str = pd.DataFrame({
    'date'    : date_str_list,
    'val' : val_list
})
df_date_str

# --------------------

         date  val
0  2021-01-11   10
1  2021-02-11   30
2  2021-03-20   20
3  2021-04-29   50
4  2021-05-05   40
df_date_str.dtypes

# --------------------

date    object
val      int64
dtype: object

さて、matplotlibを使ってこのデータをグラフにする。 そして、axvspan関数を使って、一部の背景に色を付ける……と、何やらエラーが出てきた。
axvspan関数は横軸の範囲を指定して(今回の例では、3月1日〜4月1日)、その範囲に色を付けるmatplotlibの関数である。 下記のページを参考にした。
matplotlibで一定区間に背景色をつける方法 – 分析小箱

fig, ax = plt.subplots(figsize=(12,4))
ax.plot(df_date_str['date'], df_date_str['val'])
# 参考:https://bunsekikobako.com/axvspan-and-axhspan/
start_datetime = datetime.datetime(2021, 3,1)
end_datetime = datetime.datetime(2021, 4,1)
ax.axvspan(start_datetime, end_datetime, color="gray", alpha=0.3)

# --------------------

---------------------------------------------------------------------------
    TypeError                                 Traceback (most recent call last)
    /usr/local/lib/python3.8/site-packages/matplotlib/axis.py in convert_units(self, x)
       1519         try:
    -> 1520             ret = self.converter.convert(x, self.units, self)
       1521         except Exception as e:
    /usr/local/lib/python3.8/site-packages/matplotlib/category.py in convert(value, unit, axis)
         60         # force an update so it also does type checking
    ---> 61         unit.update(values)
         62         return np.vectorize(unit._mapping.__getitem__, otypes=[float])(values)
    /usr/local/lib/python3.8/site-packages/matplotlib/category.py in update(self, data)
        210             # OrderedDict just iterates over unique values in data.
    --> 211             cbook._check_isinstance((str, bytes), value=val)
        212             if convertible:
    /usr/local/lib/python3.8/site-packages/matplotlib/cbook/__init__.py in _check_isinstance(_types, **kwargs)
       2234         if not isinstance(v, types):
    -> 2235             raise TypeError(
       2236                 "{!r} must be an instance of {}, not a {}".format(
    TypeError: 'value' must be an instance of str or bytes, not a datetime.datetime
    
    The above exception was the direct cause of the following exception:
    ConversionError                           Traceback (most recent call last)
    <ipython-input-8-40d5c36b235b> in <module>
          7 end_datetime = datetime.datetime(2021, 4,1)
          8 
    ----> 9 ax.axvspan(start_datetime, end_datetime, color="gray", alpha=0.3)
    
    /usr/local/lib/python3.8/site-packages/matplotlib/axes/_axes.py in axvspan(self, xmin, xmax, ymin, ymax, **kwargs)
       1105 
       1106         # first we need to strip away the units
    -> 1107         xmin, xmax = self.convert_xunits([xmin, xmax])
       1108         ymin, ymax = self.convert_yunits([ymin, ymax])
       1109 
    /usr/local/lib/python3.8/site-packages/matplotlib/artist.py in convert_xunits(self, x)
        173         if ax is None or ax.xaxis is None:
        174             return x
    --> 175         return ax.xaxis.convert_units(x)
        176 
        177     def convert_yunits(self, y):
    /usr/local/lib/python3.8/site-packages/matplotlib/axis.py in convert_units(self, x)
       1520             ret = self.converter.convert(x, self.units, self)
       1521         except Exception as e:
    -> 1522             raise munits.ConversionError('Failed to convert value(s) to axis '
       1523                                          f'units: {x!r}') from e
       1524         return ret
    ConversionError: Failed to convert value(s) to axis units: [datetime.datetime(2021, 3, 1, 0, 0), datetime.datetime(2021, 4, 1, 0, 0)]

f:id:soratokimitonoaidani:20210718124022p:plain

結果には2つの問題点がある。原因は共通で、データ型が不適切だった。

結果の問題点は2つある。

  • グラフの横軸が等間隔になっている(日付の間隔が違うことが考慮されていない)
  • axvspanのところでエラーが出た

この2つの原因は共通である。データを作るときのデータ型(dtype)がおかしかったのだ。

上でdf_date_str.dtypesを実行すると、date型はobjectと書いてある。 これは(やや乱暴にいえば)文字列を入れるための型である。したがって、pandasやmatplotlibはdate列を日付(時刻)とは解釈せず、文字列として扱っている
'2021-01-11'というただの文字で、'AAA', 'BBB' みたいな文字列と全く同じと考えれば良い。

type(df_date_str.loc[0, 'date'])

# --------------------

str

これによって、2つの問題点はいずれも説明がつく。

  • グラフの横軸が等間隔になっている(日付の間隔が違うことが考慮されていない)
    →ただの文字列として扱っているので、matplotlibは「それぞれの日付の間隔が違う」ことを理解できない。したがって等間隔でグラフを書く。
    →今回は元のデータが等間隔でないから気づいたが、元のデータが等間隔(毎日、毎週、毎月……)だと一見して気づかない。

  • axvspanのところでエラーが出た
    →ただの文字列として扱っているので、matplotlibは「2021年3月1日がグラフ中のどこか?」を理解できない。したがってエラーを出す。

対処法:日付を扱うためのデータ型に変換する

原因は分かったので、対処法について述べる。
日付を文字列ではなく日付として扱うようにデータを作る必要がある。そのために、datetimeモジュールを使う。

datetime_list = [
    datetime.datetime(2021, 1, 11),
    datetime.datetime(2021, 2, 11),
    datetime.datetime(2021, 3, 20),
    datetime.datetime(2021, 4, 29),
    datetime.datetime(2021, 5, 5),
]
df_datetime = pd.DataFrame({
    'date'    : datetime_list,
    'val' : val_list
})
df_datetime

# --------------------

        date  val
0 2021-01-11   10
1 2021-02-11   30
2 2021-03-20   20
3 2021-04-29   50
4 2021-05-05   40

普通にdataframeを表示しただけでは、「文字列の2021-01-11」と「日付の2021-01-11」は見分けがつかない。
データ型dtypeを確認するのが重要である。

df_datetime.dtypes

# --------------------

date    datetime64[ns]
val              int64
dtype: object
type(df_datetime.loc[0, 'date'])

# --------------------

pandas._libs.tslibs.timestamps.Timestamp

date列がdatetime64[ns]となっている。
これは日付や時刻を扱うためのデータ型(dtype)である。

また、最初のDataFrame(df_date_str)から正しいデータを作り直す場合には、文字列のカラムをto_datetimeで日付型に変換する。

df_datetime2 = df_date_str.copy()
df_datetime2['date'] = pd.to_datetime(df_datetime2['date'])
df_datetime2.dtypes

# --------------------

date    datetime64[ns]
val              int64
dtype: object

df_datetimedf_datetime2は同じデータである。そしてdf_datetimedf_date_strはデータ型が違うので、見た目は一緒でも違うデータである。 df.equals を使ってDataFrameが同一のものか確認しよう。

df_datetime.equals(df_datetime2)

# --------------------

True
df_datetime.equals(df_date_str)

# --------------------

False

時系列データをのグラフで、axvspan、axvlineを使う

これで正しいグラフを描ける。

  • グラフの横軸が、日付の間隔を考慮したものになる
  • axvspanが正しく実行できる(ついでにaxvline関数も入れておいた。こちらは縦線を描く関数。)

下記のページを参考にした(再掲)。
matplotlibで一定区間に背景色をつける方法 – 分析小箱

fig, ax = plt.subplots(figsize=(12,4))
ax.plot(df_datetime['date'], df_datetime['val']) #★
# 横軸の範囲を指定して、一定区間に背景色をつける
start_datetime = datetime.datetime(2021, 3,1)
end_datetime = datetime.datetime(2021, 4,1)
ax.axvspan(start_datetime, end_datetime, color="gray", alpha=0.3)
# 横軸の位置を指定して、縦線を描く
ax.axvline(datetime.datetime(2021,2,1), color="red")

# --------------------

<matplotlib.lines.Line2D at 0x121f075e0>

f:id:soratokimitonoaidani:20210718124026p:plain

pandasやmatplotlibでなんか変だなと思ったら、データ型(dtype)が期待通りになっているかを再確認したほうが良さそうだ。
dtypeについては、以前公式ドキュメントを翻訳したので、そちらも合わせて参照してください。

linus-mk.hatenablog.com

それでは。

ARC116 D問題 「I Wanna Win The Game」解説

AtCoder Regular Contest 116 D問題 「I Wanna Win The Game」解説。

普段は個別問題の解説は書かない。けど、今回は本番中に解けたけど考えすぎてめっちゃ疲れたので、まとめておく。
細かい書き方はやや適当にしています。(個別の問題の解説を見に来る人はそれほど多くないだろうから、きっちり書き上げる重要性は低い)

atcoder.jp

しばらくは例1を使って考える。

まず重要なのは、bit XORを考える問題は、それぞれのbitを独立に考えれば良い。あるbitの結果は他のbitの結果に全く影響しない。

例1にある

5 20  
---
(1, 2, 3, 7, 7)

を考えて、それをbitに分解する。bitごとに出現回数を見ると

  • 4のbit→2回立っているからbit XOR = 0
  • 2のbit→4回立っているからbit XOR = 0
  • 1のbit→4回立っているからbit XOR = 0

となる。合計の20は、4*2 + 2*4 + 1*4 = 20と分解できる。

各bitの登場回数が分かったら、何通りか分かるか?

逆に考えると、

  • 4のbitが、2回立っている
  • 2のbitが、4回立っている
  • 1のbitが、4回立っている

という数列ならば、合計は20であり、そのXORは0なので条件を満たす。

では、このような数列はいくつあるか?

  • 4のbitの割り当て方は5C2 = 10通り
  • 2のbitの割り当て方は5C4 = 5通り
  • 1のbitの割り当て方は5C4 = 5通り

これをかければよく、10*5*5 = 250通りである。

合計Mから、各bitへの振り分けを全て考えてみよう

bit XORが0となる必要十分条件は、全てのbitに関して登場回数が偶数であることである。 したがって、bit XORが0となるためには、合計Mは偶数でなければならない。したがってMが奇数なら答えは0だ。

いまMを偶数とする。 登場回数は全て偶数なので、2で割ろう。合計もM=20を2で割った10になる。 10を各bitに振り分けるやり方をすべて書き出し、それぞれの場合の数を計算すると、以下の5通りになる。

10 = 8*0 + 4*2 + 2*1 + 1*0 → 5C0 * 5C4 * 5C2 * 5C0 = 50
10 = 8*0 + 4*2 + 2*0 + 1*2 → 5C0 * 5C4 * 5C0 * 5C4 = 25
10 = 8*0 + 4*1 + 2*2 + 1*2 → 5C0 * 5C2 * 5C4 * 5C2 = 250 (上の例)
10 = 8*1 + 4*0 + 2*1 + 1*0 → 5C2 * 5C0 * 5C2 * 5C0 = 100
10 = 8*1 + 4*0 + 2*0 + 1*2 → 5C2 * 5C0 * 5C0 * 5C4 = 50
↓
合計475

適切な振り分けのための条件

上の例では「M/2 = 10 を各bitに振り分けるやり方」を全部考えた。
一般の偶数Mの場合は、どうすれば振り分け方を全部考えられるだろうか?
いっぺんに決めるのは難しそうだ。 上位ビットから決めるか、下位ビットから決めるか。 上位ビットから決めることにしよう。

(N//2 は、N÷2の整数部分を表わす。)
今、振り分けるべき残りの数をrestとし、あるビット(digitと書く)にk個を振り分けたとしよう。(最終的には、N個のうち2k個の数の当該ビットを立てることになる。)

kが適切な値である条件は、以下3つである。

  • 0以上 N//2以下である (0 <= k <= N//2)
  • 今見ているビットよりも下位の桁に振り分けられる数は高々 (下位ビットの和) * (N//2)である。したがって、振り分けた残りがこれ以下でなければいけない。(rest - digit * k <= (digit-1) * N//2)
  • 振り分けた残りが負になってはいけない(rest - digit * k <= (digit-1) * N//2)

DP

天下り的だが、DPを導入する。
(DPに行き着くまでの思考過程は後述する)
M/2を各bitに振り分ける。
DP[bit][rest]を、今からbitの桁に数を振り分けようとしていて、残りの数がrestであるときの、N個の数の決め方、とする。(例えばbitが3だったら23 = 8の桁に振り分けようとしている。)

  • 初期条件:DP[0][rest] = N C 2*rest
    • 最後に1のビットに振り分けるという状態で、残った数がrestである。この場合のN個の数の決め方は N C 2*rest 通りである。
  • 最終的な答え:DP[12][M/2]
    • 振り分ける可能性のある最上位桁は、212 = 2048である。なぜならM/2は高々2500なので、4096以上のbitに与えたら残りが負になってしまい不適当となるからだ。
  • 漸化式:DP[bit][rest] = SUM(DP[bit-1][rest - (2**bit) * k] * N C 2k) (kの動く範囲は、上記3つの条件を全て満たす範囲)
    • 適切なkを選ぶと、それより下位のビットに振り分ける数はrest - (2**bit) * kである。今見ているbitに関しては、N個のうち2k個を選んでビットを立てる。その選び方はN C 2kである。

計算量について:
DPテーブルのマス目の個数は12 * M/2 <= 12 * 2500 = 30000
DPテーブルのマス目を1つ計算するための計算量は、正当なkの範囲なので高々 N//2 = 2500
単純にかけると75000000 = 7500万となる。厳しそうだが、kに関する他の条件により実際はこれより少ない。

なんで解くのに時間がかかったんだろうか

ここが本来書きたかったパートだわ。
Cが解けたのが40分、Dが解けたのが101分なので、61分もかかっている。これは時間がかかり過ぎたと思う。

コンテスト本番中の思考を再現すると、次のようになる。

  • 「M/2 を各bitに振り分けるやり方」を全部列挙して、それぞれについて掛けて最後に足し合わせれば良さそう
  • 上位ビットから順に決めれば良さそう
  • ということは……現在見ているビットに対して再帰関数になる?
  • しかも再帰を全部計算してると同じ状態を何度も計算し直すことになる。そのせいで間に合わない。
  • メモ化する必要がある。
  • メモ化再帰? メモ化再帰をちゃんと書くなんてめったに無いぞ? マジで?
  • あ、メモ化再帰ってことはDPと同等なのか。DPでいいのか?
  • DPテーブルの定義をこうやると……あ、DPでいけそう。

解法の指針がDPだということを確定するまでに時間がかかったんだと思う。

kyopro_friendsさんはメモ化再帰でやってるぽいけど。

あと、

  • 「適切な振り分けのための条件」を考えているときは、上位ビット
  • しかし、DPテーブルを計算するときは下位ビットから順に計算している

というのが腑に落ちない。どこで逆転したんだ?

matplotlibが初心者に分かりにくい理由を考える

久しぶりにmatplotlibを触ったら、やりたい処理がやりづらい……辛い……と改めて悩んでしまった。
matplotlibが分かりにくくて辛い、という理由を考察する記事である。

matplotlibが初心者にとって分かりにくいのはなぜか?

データ分析関連でコーディングをしている中で、pandasやnumpyに関しては、自分の知識の範囲を少しずつであっても広げられている実感がある。 例えば、このブログの過去の記事をいくつか見てみると、以下のような点については分かったぞ、と思える。

このあたりか。やっぱりブログにまとめると知識がしっかり定着するなぁ。
もちろん、pandas/numpyについて全てを知ることは到底無理だ。 しかし、一部については「少なくともこの部分については確固たる知識を習得できた。自分の血肉となった」という自信がある。

でもmatplotlibについては、そうはならない。断片的な知識だけが俺の中にバラバラに存在している。 なぜ知識が断片的になってしまうかというと、

  • 2つのインターフェース
  • ArtistとかFigureとかAxesとかその辺

をまず理解しないと、何も始まらないような感覚がある。
土台が固まっていないところの上に何の知識を積んでも、砂上の楼閣になりそうというか。 賽の河原みたいに、知識をいくら積み重ねたところですぐ吹き飛ばされそうというか。
matplotlibだけは、知識の習得の初手が厳しい……
譬えて言えば、「はい、ここがスタート地点です。先に進むにはまず、この3メートルの壁をよじ登って乗り越えてください。それ以外の方法では次に進めません」みたいな感じ。

そして、たまには「matplotlibの上記の土台を、ちゃんと勉強するか」と一念発起することもある。 3メートルの崖をよじ登って、ArtistとかFigureとかAxesとかその辺を理解しようとするが、それは簡単にいくものではない。と思う。 で、壁からずり落ちてスタート地点から進めない、というのが俺である。

公式ドキュメント

まずは公式ドキュメントを読め。 誰が書いたのか分からない、Qiitaや個人ブログの断片的な記事を読むよりも、まずは公式ドキュメントを読め。 最も頼りになって信用できる資料は公式ドキュメントに決まってるからな。

……ということはよく言われる。俺もそのとおりだと思う。

上記に関するまとまった意見がないかなと思って「公式ドキュメント」でググったら、「自走プログラマー」の抜粋版のサイトがあったので載せておきます。
自走プログラマー【抜粋版】 33:公式ドキュメントを読もう

しかし、matplotlibは公式ドキュメントすら読む気がしないのは、いったい何故なんだろうか?
自分の行動を振り返ってみると、Python本体・pandas・numpy・scikit-learn・seabornは、公式ドキュメントのうち必要なところは読むわ。必要に応じてその都度読んでるわ。
しかしmatplotlib……!
読む……!
読みには行くが分かった気にならない感覚……!
分からない……!
分からないから公式ドキュメントを読みにいかなくなる……!
読みにいかなくなるからますます分からなくなる……!
無限ループ!はまっている、すでに術中……!

なんだか福本伸行っぽくなってしまった。
matplotlibだけは、公式ドキュメントすら読むのを忌避したくなる感覚がある。何故かは分からないけど。「どこに何が書いてあるか」を把握できてないのかな?

英語で書かれたPythonブログでこの辺はどう論じられてきたか

「why matplotlib is hard to understand」とか「matplotlib confusing」とかで検索してみたら、Python関係の英語の技術ブログが見つかった。

Practical Business Python: 「Effectively Using Matplotlib」

Pythonのデータ分析関連ではよく見かける「Practical Business Python」の記事だ。
https://pbpython.com/effective-matplotlib.html

「Why all the negativity towards matplotlib?」の章で、matplotlibが分かりにくい3つの理由が挙げられている。その筆頭が「2つのインターフェース」である。これはもっともだと思う。以下に引用する。

First, matplotlib has two interfaces. The first is based on MATLAB and uses a state-based interface. The second option is an an object-oriented interface. The why’s of this dual approach are outside the scope of this post but knowing that there are two approaches is vitally important when plotting with matplotlib.
The reason two interfaces cause confusion is that in the world of stack overflow and tons of information available via google searches, new users will stumble across multiple solutions to problems that look somewhat similar but are not the same. I can speak from experience. Looking back on some of my old code, I can tell that there is a mishmash of matplotlib code - which is confusing to me (even if I wrote it).

拙訳: 第一に、matplotlibには2つのインターフェースがある。1つ目は、MATLABに基づいた、状態ベースのインターフェースである。2つ目は、オブジェクト指向のインターフェースである。この2つの方法がある理由についてはこの記事が扱う範囲の外であるが、しかしmatplotlibに2つの方法があると知っていることは、matplotlibを使って図を描く上で極めて重要である。
この2つのインターフェースは混乱の元となる。その理由は、StackOverflowがあってグーグル検索をすれば大量の情報が得られる世界で、初心者がある問題に対して複数の解決法を見つけてしまい、それらがある程度似ているのに同じではないからだ。これは私個人の経験からいってもそうだ。私が昔書いたコードを見返すと、(私自身が書いたのに)自分で読んで分かりにくい、ごちゃ混ぜになったmatplotlibコードが確実にあるのだ。

「matplotlibが分かりにくい3つの理由」のうち残りの2つについて。2番目が「デフォルトのスタイルの選択肢の中には、かなり見栄えが悪いものがある(訳注:見た目がきれいでなくて格好悪い、という話)」であった。そして3番めが「図を描くときに、純粋なmatplotlibを使うべきか、pandasやseabornのようなmatplotlibの上層にあるツールを使うべきかに関して分かりにくいこと。」であった。

「分かりにくい理由」を説明した後には具体的なコードを使って書き方の説明をしている。
書き方の説明の部分は、後に改稿してmatplotlibの公式ドキュメントに取り込まれている!
https://matplotlib.org/stable/tutorials/introductory/lifecycle.html

余談であるが、matplotlibに2つの方法がある話は極めて重要である。したがって、matplotlibについてのある程度の量がある記事・本などで、重要な「2つのインターフェース」の話に触れていないものは、matplotlibをロクに分かっていない人が書いたものである可能性が高いと考える。
少なくとも、私が見てきた秀逸な本やネットの記事は、例外なくこの「2つのインターフェース」の話に言及している。

以下の記事も参照。初めて「2つのインターフェース」を俺が知ってビックリしてメモに書いたものだけど。
メモ:Matplotlibのグラフの書き方が2通りある話 - 子供の落書き帳 Renaissance

Real PythonPython Plotting With Matplotlib (Guide)」

Python関係の英語の技術ブログをもう1つ見てみよう。 Real Python による「Python Plotting With Matplotlib (Guide)」という記事である。
https://realpython.com/python-matplotlib-guide/

Why Can Matplotlib Be Confusing?

  1. The library itself is huge, at something like 70,000 total lines of code.
  2. Matplotlib is home to several different interfaces (ways of constructing a figure) and capable of interacting with a handful of different backends. (Backends deal with the process of how charts are actually rendered, not just structured internally.)
  3. While it is comprehensive, some of matplotlib’s own public documentation is seriously out-of-date. The library is still evolving, and many older examples floating around online may take 70% fewer lines of code in their modern version.

拙訳: 1. ライブラリ自体が巨大であり、合計で約70000行もコードがある。 2. matplotlibにはいくつかの異なるインターフェース(図を描く方法)が存在する。少数の異なるバックエンドと相互作用することができる。(バックエンドは内部的な構成だけではなく、どのように図を実際に描画するかという過程も取り扱う。) 3. matplotlibの公式ドキュメントは広範囲にわたるが、その中には非常に古くなったものも存在する()。このライブラリは今も進化を続けていて、ネット上に出回っている古い例の中には、新しいバージョンのコードで書き直せば行数が70%少なくなるものもある。

matplotlibって実は変化が激しいのか? あんまりそんな印象は無いんだけど。

stackoverflow: 「Understanding matplotlib: plt, figure, ax(arr)?」

https://stackoverflow.com/questions/35677767/understanding-matplotlib-plt-figure-axarr

Understanding matplotlib: plt, figure, ax(arr)?

The matplotlib documentation is rather confusing to me. When one searches something really specific, like rescaling a legend, different plot markers and colors and so on the official documentation is really precise but rather general information is not that good in my opinion. Too much different examples, no real explanations of the purposes...looks more or less like a big listing of all possible API methods and arguments.

拙訳:matplotlibのドキュメントは、私にとってかなり分かりにくいです。本当に具体的なものを検索するとき、例えば凡例を拡大縮小するとか、プロットのマーカーや色を変えるとかですが、公式ドキュメントは非常に正確です。しかしもっと一般的な情報については私の意見ではそれほど良いものではありません。あまりにも多くの異なる例があって、その目的の説明も無いのです。まるで、全部のAPIのメソッドと引数を巨大な一覧表にしたように見えます。


っていう感じで「やっぱmatplotlibは知識習得しづらいわ」と悩む記事でした。いつかは「matplotlibの根幹をちゃんと理解したわ」っていう記事が書ければ良いんだけど、いつになることやら。

再度書いておくけど、知らなかった人は「matplotlibに2つのインターフェースがある」ことだけは覚えて帰ったほうが良いと思います!

linus-mk.hatenablog.com

クラスタリングの結果を、変数の値に従ってソートする

今回の記事の主題は、
クラスタリングの結果(ラベル、番号)を、ある変数の値の順序に従って並び替えるにはどうすればよいか?
という話である。
……しかし、こう書いただけで何のことか分かる人は多分少ないだろう。だから順を追って説明していく。 まずは、今回の問題が起きるクラスタリングの例を作ろう。

クラスタリングの例:2変数・5クラスターのデータをクラスタリングする

クラスタリングの対象となるデータの例を適当に作ろう。 scikit-learnのmake_blobを使って中心を指定し、2変数・5クラスターのデータを作成する。

import pandas as pd
import seaborn as sns
pd.options.display.notebook_repr_html = False  # jupyter notebook上での出力形式を制御するために書いています。無くても動きます。
import sklearn
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
# 動作環境の確認
print(pd.__version__)
print(sns.__version__)
print(sklearn.__version__)

# --------------------

1.1.2
0.11.0
0.24.1
sns.set_style('whitegrid') # seaborn見た目の変更。グラフ内にグリッド線を表示する
random_state = 123
# 例示用にクラスタリングするデータを作成する
center_coordinates = [[0, 0], [1, 2], [3, 1], [2, 3], [4, 4]] 
n_clusters = len(center_coordinates)
X, y = make_blobs(n_samples=30*n_clusters, centers=center_coordinates, n_features=2, cluster_std=0.3, random_state=random_state)

データの様子を散布図にしよう。今回はseabornを使う。

df = pd.DataFrame(data=X, columns=['x1', 'x2'])
ax = sns.scatterplot(x='x1', y='x2', data=df)
ax.set_aspect('equal') # グラフの縦横比を同じにする 参考:https://xnn.sakura.ne.jp/blog/2019/07/match-the-scatterplot-grid-width-in-matplotlib/

f:id:soratokimitonoaidani:20210214150556p:plain

期待通りに5つのクラスターができていることが見えた。

このデータをk-meansでクラスタリングし、結果を出力しよう。 *1

y_pred = KMeans(n_clusters=n_clusters, random_state=random_state).fit_predict(df)
df['y_pred'] =  y_pred
df.head()

# --------------------

         x1        x2  y_pred
0  4.190783  4.085381       0
1  1.917537  2.575175       2
2  1.771612  3.001094       2
3  0.992612  2.010243       1
4  1.925955  3.020636       2

ちょっと話が脇道に入るが、クラスタリングの結果、出力、番号、所属……これをなんと呼ぶか、呼び方に困るんだよね。scikit-learn公式のk-meansの説明によると、

labels_ ndarray of shape (n_samples,)
Labels of each point

と書いてあるので、「クラスタリングの結果、出力、番号」「各点がどのクラスタに分類されたか」を以降ではラベルと呼ぶことにする。

では本題に戻ろう。ラベルによって色を分けて、クラスタリングの結果を散布図にしよう *2

ax = sns.scatterplot(x='x1', y='x2', hue='y_pred', data=df, palette='colorblind')
ax.set_aspect('equal')

f:id:soratokimitonoaidani:20210214150612p:plain

scatterplotで散布図ができた。しかし、この散布図には問題がある。
散布図の上で、ラベル0と1が近い、ラベル3と4が近いというわけではない。 クラスタリングのラベルはクラスタ間の近さを考慮して付くわけではないからだ。どういう規則でラベルの番号がついているかは正直謎だが。
(予想:K-meansを使う場合、最初にランダムな点を取るので、それによって最終的なクラスターの番号が決まるんじゃないか? つまり初期の点の位置を決める乱数次第?)

しかし見づらい場合がある。 クラスター番号に規則性が無いので、0番がどこで1番がどこで、と探すのが大変だ。今回は5クラスターだからいいけど、もっとクラスター数が多い場合は探すのが大変になる。

クラスタリングのラベルを、ある変数の値の順序に従ってソートする方法

前提条件を説明するのが遅くなったが、ここまで今回の記事のための問題設定は完了である。

クラスタリングのラベルを、ある変数の値の順序に従って並び替えるにはどうすればよいか?

より正確にいうと、今回は、

  • x1の平均が最も小さいクラスターがラベル0
  • x1の平均が2番目に小さいクラスターがラベル1
  • ……

になるようにクラスターのラベルを振り直したい、としよう。(他の変数、昇順/降順の場合も同様である)

結論から言うと、このようにすれば良い。

df['y_pred_sorted'] =  df['y_pred'].replace(
    df.groupby('y_pred')['x1'].mean().sort_values().index,
    range(n_clusters)
)

正解を一気に書くと結構長いけど、pandasにある程度慣れていればそこまで難しい話ではない。

ラベルが入ったy_pred列の数値を、ある規則によって置換すれば良さそうだ。これにはreplace関数を使えば良い。

置換したい対称は、df['y_pred']の一列だけなので今回はSeriesに対するreplace関数となる。

https://pandas.pydata.org/pandas-docs/stable/reference/api/pandas.Series.replace.html

置換の指定方法は色々あって、ドキュメントを見ると細かく書いてある。今回は、list(状のもの)で指定する方法を使う。

「各クラスターのx1の平均値はいくつか」は df.groupby('y_pred')['x1'].mean() で求まる。
したがって、これをsort_valuesで昇順に並び替え、最後にindexを取れば 「クラスターのラベルを、クラスター内のx1の平均値が小さい順に並び替えたもの」が得られる。

あとは置換後のリストとしてrangeを指定すれば、「置換前のリストと置換後のリスト」が求まる。これをreplaceの引数に入れれば完成である。

最後に、もう一度seabornで散布図を描いてみよう。

ax = sns.scatterplot(x='x1', y='x2', hue='y_pred_sorted', data=df, palette='colorblind')
ax.set_aspect('equal')

f:id:soratokimitonoaidani:20210214150632p:plain

クラスターが、散布図で左から順に0, 1, 2, ……と並んでいる。 x1の平均値が小さい順にクラスター番号を振り直せたことが確認できた。

*1:クラスタリング自体は今回の記事においてそれほど重要ではない。したがって「手法としてk-meansを使う理由」は例を簡潔に説明するために一番シンプルな手法を選んでいるからです。「正解のクラスター数を知っている理由」もクラスタリングを簡単に済ませたいからです。

*2:余談:xとyを「機械学習における説明変数がX、目的変数がy」として使っている箇所と、「散布図(scatterplot)を描くときの横軸方向がx、縦軸方向がy」として使っている箇所があるけど、大丈夫だよね?
最初は'cluster_index_pred' という列名にしたけど、scatterplotの凡例が場所を取りすぎて汚くなったのでy_predに変えた。

新型コロナウイルスの「ステージ」とは何か? 分かりにくかったので調べてまとめた

新型コロナウイルスの話で使われている、ステージ3とか4とかいう概念が意味不明すぎる、という話。

私は暇さえあればインターネットばかり見ているような人間だ。私の知る限り、インターネットの世界では、2020年6月に出ていた「東京アラート」については否定的な意見が多かったように思う。「都庁を光らせたいだけだろ」「都民に何をしてほしいのか不明」みたいな意見が見られた。

ただ、この「ステージ」については否定的な意見がそれほど多くない。いや、肯定的な意見も否定的な意見も無い気がするので、誰も注目していないのかもしれない。でもニュースとかだと結構出てくるんだよね。調べてまとめてみたら、意味がよく分からないところが多かった。

注意事項、免責事項

私は報道関係者でも医療関係者でも行政関係者でもなく、一介のエンジニアです。

本記事の内容については細心の注意を払っておりますが、コンテンツの内容が正確であるかどうか、最新のものであるかどうか、安全なものであるか等について保証をするものではなく、何らの責任を負うものではありません。また、執筆者は通知することなく本記事に掲載した情報の訂正、修正、追加、中断、削除等をいつでも行うことができるものとします。
また、本記事のご利用により、万一、ご利用者様に何らかの不都合や損害が発生したとしても、執筆者は何らの責任を負うものではありません。

厚生労働省などの資料では「ステージIII」のようにローマ数字を使っていますが、本記事では「ステージ3」などの算用数字表記で統一します。ニュースとかで見るときは、ほぼ全部算用数字だし。

「ステージ」という概念は、いつ誰が言い出したのか?

Q. 「ステージ」という概念は、いつ誰が言い出したのか?
A. 2020年8月7日、政府の新型コロナウイルス分科会が提唱した。

https://www.cas.go.jp/jp/seisaku/ful/yusikisyakaigi.html
新型コロナウイルス感染症対策分科会」の「令和2年 8月7日 第5回資料 今後想定される感染状況と対策について」で、このステージという用語が書いてある。ここで「ステージ」という概念が初めて登場したのだと思う。

ステージ3
感染者の急増及び医療提供体制における大きな支障の発生を避けるための対応が必要な段階
ステージ2と比べてクラスターが広範に多発する等、感染者が急増し、新型コロナウイルス感染症に対する医療提供体制への負荷がさらに高まり、一般医療にも大きな支障が発生することを避けるための対応が必要な状況。

ステージ4
爆発的な感染拡大及び深刻な医療提供体制の機能不全を避けるための対応が必要な段階
病院間クラスター連鎖などの大規模かつ深刻なクラスター連鎖が発生し、爆発的な感染拡大により、高齢者や高リスク者が大量に感染し、多くの重症者及び死亡者が発生し始め、公衆衛生体制及び医療提供体制が機能不全に陥いることを避けるための対応が必要な状況。
(今後想定される感染状況と対策について p.3より なおローマ数字は算用数字に直した)

7月31日段階で、分科会は「(1)感染ゼロ散発段階(2)感染漸増段階(3)感染急増段階(4)感染爆発段階」という4段階に分けることを提案している(https://news.yahoo.co.jp/articles/7144a4abf31c94a588b8bc20cabc7e4ec9f1ec74)。具体的な指標と基準値を定めたのが8月7日だな。

どのステージなのかの判断は、指標から自動的に決まるのか?

Q. どのステージなのかの判断は、指標から自動的に決まるのか?
A. いいえ。各指標の数値はあくまで「目安」であり、どのステージなのかは総合的に判断する。

ただ尾身会長は、こうした数値はあくまで「目安」であり、1つでも数値が基準値を超えたら機械的に次のステージに移行するわけではないと強調。「指標は国、地方公共団体が総合的に判断するための目安であり、地域の実情に合わせた対策を講じる」必要があると説明した。 https://news.yahoo.co.jp/articles/6aca60a0f5e781f2a732e86c5173632dbfaa52a7

「この県はステージいくつです」を誰が決めるのか?

Q. では、「この県はステージいくつです」を決めるのは誰か?
A. おそらく、都道府県と国

分科会の「令和2年 8月7日 第5回資料 今後想定される感染状況と対策について」資料より。

提案する指標は「あくまで目安」であり、また、一つひとつの指標をもって機械的に判断するのではなく、国や都道府県はこれらの指標を「総合的に判断」して、感染の状況に応じ積極的かつ機動的に対策を講じていただきたい。
( 今後想定される感染状況と対策について p.4より)
以下の指標は目安であり、また、これらの指標をもって機械的に判断するのではなく、国や都道府県はこれらの指標を総合的に判断していただきたい。
( 今後想定される感染状況と対策について p.5より)

この資料を読むと「国や都道府県は」と、国と都道府県を並列に並べて判断主体にしている気がする。

しかし、都道府県知事、と単に書いてある記事もある。うーん、よく分からない。

Q:誰がどうステージを決めるの?
都道府県のステージを判断するのは、各々の知事という立て付けになっています。
https://news.yahoo.co.jp/articles/6aca60a0f5e781f2a732e86c5173632dbfaa52a7?page=2

分科会は「指標はあくまで目安」とする。尾身氏は「現場を知っているのは知事さん。知事が主体的にやるべきだ」と判断を都道府県に委ねた。
https://www.tokyo-np.co.jp/article/47720

これまで、どの都道府県もステージ2以下とみなされてきた。11月に入って北海道や東京都などでは、分科会が示したステージ3の六つの指標のうち多くで上回るが、判断は知事に委ねられ、分科会のステージに即した対策の議論は進んでいなかった。 https://www.asahi.com/articles/ASNCN6QCWNCNULBJ01P.html

分科会がステージを判断してはダメなの?

Q. 分科会がステージという概念を作ったんでしょ? 分科会がステージを判断しちゃダメなの?
A. 分科会が「個人的な意見」としていくつかの都道府県を挙げたことはある。しかし、分科会は判断するのは都道府県と国だという姿勢であり、分科会が判断することに対して否定的だ。

都道府県を名指しで挙げたことはある。11月20日新型コロナウイルス対策分科会の会見だ。分科会が判断するわけではないから、専門家の個人的な意見だけど、という留保がついている。

「(中略)現在の感染状況を考えれば、いくつかの都道府県でステージ3相当と判断せざるを得ない状況に、早晩至る可能性が高いとわれわれは判断している」と述べ、厳しい状況の地域が複数あるとの認識を示した。質疑で具体的な都道府県名を問われると「専門家としての個人的な意見」と前置きしたうえで「北海道の札幌はステージ3に入っているんじゃないか。東京や大阪などはステージ3に近づきつつある」と言及した。
https://news.yahoo.co.jp/articles/57194ece0c8ecb6f4b7746d7fac2ded63e1d2513

その後、11月25日の新型コロナウイルス対策分科会の会見でも、同様に留保をつけつつ地域名を挙げている。

その地域がどのステージに相当するかを判断するのは「都道府県が政府と連携してやる」ことで、「判断するのは我々の仕事ではない」と述べた。
しかし、記者からさらに具体的な地域名を求められると「(分科会としての)判断ではない」と断ったうえで、「おそらく札幌は(入る)。それから島しょは別だが、23区も。東京の場合は、以前は一部地域だったけど23区を中心に感染が、ほとんどの地域に拡散している。あとは、これも名古屋市もそう(ステージ3相当)じゃないか。大阪市なんかもそれだとわれわれは考えている」と語り、札幌市、東京23区、名古屋市大阪市が該当するとの見解を示した。
https://news.yahoo.co.jp/articles/8f973cdbbf30ff3b5aefedceb8b1cdad781cd9dd

ただ、分科会はステージの判断に対して「あくまで参考」という立場を崩していないようだ。
12月11日の会見では、記者が「分科会がステージ判断をした方がよいのでは」と質問したのに対して、分科会の尾身会長が否定している。「ステージを判断するのは、分科会の役割ではないから」という理由のようだ。

(12月11日の会見では、ステージ3を「減少」「高止まり」「拡大継続」という3つの「シナリオ」に分割する話があった。が、この「シナリオ」という話は、ステージ分類に輪をかけてよくわからないので、この記事では大きく扱わない)

その地域の感染状況がどのステージに該当するかのステージ判断は、都道府県知事と国が連携して決めることになっている。前述の通り、分科会はステージ3相当の地域ではGo Toトラベルを一時停止することを求めているが、Go Toトラベルからの除外を検討する局面で国と自治体の間でボールを投げ合うようなケースもあった。
 会見では、むしろステージ判断自体を専門家が主導する方が早いのではないかとの質問も出たが、尾身会長は役割分担の明確化を挙げて反論した。
「分科会(の役割)は対策を提案することで、実行するのは我々の仕事ではない。ここが専門家と政府の役割(分担)で、そのことが曖昧になったのが当初の専門家会議」
さらに言葉を強めて続けた。「ステージ3というのは、こういう状況を言うと(分科会は)ここまで示している。普通にやればステージ2なのかステージ3なのか分かるような書き方を(している)。自治体と国は、都道府県民・国民のために今まで以上の英断を、決断、判断をしてほしい」 https://news.yahoo.co.jp/articles/f793ea3f22baa81eb02e2f82f11574522a1c2000?page=2

分科会のこの日の記者会見では、政府や都道府県ではなく、分科会がステージ判断をした方がよいのでは、という質問が出たが尾身茂会長は否定した。
今春の「第1波」の際、医学的見地から対策を助言した「専門家会議」は「政府との役割分担が曖昧」と批判を浴び、現在の分科会に衣替えした。政策決定には踏み込まないようにしており、尾身会長は「知事が早く判断していただきたい。早めに手を打ってください」と訴えた。
https://www.tokyo-np.co.jp/article/73854

ステージという概念はどの程度活用されているのか?

Q. このステージという概念はどの程度活用されているのか?

A. 都道府県が独自に警戒レベルを作っているところが多く、分科会の定めるステージを活用している都道府県はそれほど多くない。 ただ分科会は基本的に「ステージ」を使って話をしていると思う

都道府県が「どのような指標や警戒レベルを使っているか」については日経の記事がよくまとまっていた。
https://www.nikkei.com/article/DGXZQODG115Z7011122020000000

国はこの「ステージ1〜4」、北海道は独自の「ステージ1〜5」、東京は「管理状況と医療提供体制について、それぞれ4段階」などなど。都道府県によって使うレベルはバラバラなのだ。

ただ、分科会がコメントするときは基本的に「ステージ2」「ステージ3」という概念を使って話をする。例えば、Go To トラベルとの関係だと、「ステージ3」ならGo Toは中止(尾身氏「ステージ3地域、GoTo停止を」 衆院厚労委感染急拡大ならGoTo停止も コロナ「大流行に最大警戒」―政府)、「ステージ2」ならばGo Toを再開してもよい(ステージ2なら事業再開 GoTo一時停止で―尾身氏)と発言している。

政府の新型コロナウイルス感染症対策分科会の尾身茂会長は17日の参院内閣委員会の閉会中審査で、年末年始に全国で一時停止する国の観光支援事業「Go To トラベル」に関し、東京都や大阪市の状況が感染の漸増を示す「ステージ2」まで改善すれば、全国で事業を再開しても問題ないとの考えを示した。
https://www.jiji.com/jc/article?k=2020121700972&g=pol

では、それぞれの都道府県はどこのステージなのか、を知りたくなるだろう。それが次の問題だ。

都道府県はステージいくつなのか?

Q. 各都道府県はステージいくつなのか?
A. 一覧は無い。

「この都道府県は現在ステージいくつ」という一覧表はあるかなと探したが、見つからなかった。

ステージ3

「ステージ3と判断した」という地域は探した限り以下の通りである。(判断した日付の順に 並んでいる)

最も感染者数が多い東京はいくつなのか? 「コロナ ステージ 東京」で検索したけど、「東京都はステージいくつです」と判断したという記述は無かった。(尾身会長は東京都をステージ3相当だと述べているけど、それはあくまで参考意見である。)
ところで、2021年1月2日には東京都などが政府に対して緊急事態宣言を発出するよう要請した。ステージ分類の資料では、ステージ4では「緊急事態宣言など、強制性のある対応を検討せざるを得ない(今後想定される感染状況と対策について p.8より)」と書いてある。ということは、東京都はステージ4に入っているか、入りそうになっているか、そのどちらかの状態だろう。しかし東京都自身は、現在に至るまで、ステージ3だとも4だとも明言していない。ここまで考えると、東京はこのステージという概念をほぼ無視している、と考えるのが妥当な気がする。

なお2020年12月9日の時点では、ステージ3に該当すると判断された都道府県は無いらしいです。

加藤勝信官房長官は9日の記者会見で「現時点でステージ3に該当すると判断された都道府県はないと承知している」と話した。
https://www.nikkei.com/article/DGXZQOFS098U30Z01C20A2000000

ステージ2

また、ステージ2に該当すると判断した都道府県は探した限り以下の通りである。

なお調べている中で興味深い記事があった。神奈川県の状況について記した東京新聞の記事だ。記事の日付は2020年12月22日なので、上記の「神奈川県 ステージ3」よりも前だ。「複数の県幹部が「ステージ引き上げに強く反対したのは、政府と横浜市だ」と断言した」らしい。
12月14日に、政府はGo To トラベルを全国一斉に一時停止することを決定している。12月14日より前に神奈川県を「ステージ3」に引き上げようとすると、そこだけGo To トラベルを停止する必要があるはずだ。

十一月以降、感染状況を表す七指標のほとんどが「ステージ3」(感染急増)に達しても、ステージ引き上げは判断しなかった。(中略)
「強いメッセージを出して感染増を抑える」ことを重視する知事が、最も端的に危機感を伝えられる「ステージ引き上げ」をしないのは、どう考えても異様だった。(中略)
ステージを引き上げなかった事情を問われた知事は「じくじたる思い」「県と国、政令市が一枚岩にならないといけない」と話した。思い切った判断ができない背景に、政府や政令市の意向があることを強くうかがわせた。横浜市は認めていないが、複数の県幹部が「ステージ引き上げに強く反対したのは、政府と横浜市だ」と断言した。
https://www.tokyo-np.co.jp/article/75853

分科会の「お願い」は一体誰に向けたお願いなのだろうか?

分科会の最新の資料は、「第19回資料 現在直面する3つの課題」という2020年12月23日の資料である。
この中の19〜24ページには「皆さんへのお願い」が書かれている。 その中でp.23を見てみよう。

シナリオ3の地域の皆さんへ
(中略)そのため、シナリオ3の地域では、年末年始に向けて、次のことをお願いします。 1. 忘年会・新年会は基本的に見送ってください。 2. 帰省(とりわけ感染地域とそれ以外の地域での往来)も、ご家族と相談の上、控えることや延期・分散も含め慎重に検討してください。
3. イルミネーションについては早めの消灯。カウントダウンイベントなどについてもオンラインを活用した形で開催。いずれにしても混雑する時間は避けることなどをお願いします。

ああ、「シナリオ3の地域の皆さん」は忘年会新年会をやるなという要請を分科会もしてたんだ。知らなかったわ。
3はイルミネーションやイベントの主催者に向けたお願いだろう。1、2は一般市民へのお願いだろう。お願いする相手が違うものを一緒くたに載せるのはどうなのかと思うのだけど。それよりも問題なのは、お願いする相手が誰なのか不明だという点である。

  • これは、ステージ3(感染急増)の中のシナリオ3(拡大継続)の地域の住民に対して分科会がお願いした事項である
  • ステージやシナリオの判断は「国と都道府県が連携して」やってくれ、と分科会はいう
  • 少なくともこの時点(12/23)でステージ3と宣言したのは北海道札幌市だけ
  • さらにステージ3の中でどのシナリオだと宣言した地域はない(私の知る限り)
  • じゃあこれは一体誰に向けたお願いなのだろうか?????

ここまでの感想

乱暴にまとめると、下みたいな感じの理解で良いのかな? 分科会と国と都道府県が全てバラバラに動いているのが分かった。分科会は「ステージ」という概念に立脚して話をしようとしている、しかし「ステージ」は多くの都道府県が採用していないので、根無し草のような議論になってしまう。話が噛み合ってないというわけだ。

  • 分科会「どのステージなのかは、都道府県が国と連携して判断してね」
  • 都道府県「いや、うちはこの独自基準で運用するんで。国のステージは分かりにくいから、使わなくていいや」
  • 国「都道府県が何も言ってこないから、ステージ3の地域はありません」
  • 分科会「ステージ3の地域ではGoToは中止すべき」
  • 俺「それはどこだよ」
  • 分科会「いや、ステージ3を判断するのは都道府県と国だけど」
  • 分科会「ステージ3の中のシナリオ3の地域の皆さん!忘年会と新年会はやめてください!」
  • 俺「だからそれはどこだよ」
  • 分科会「いや、ステージとシナリオを判断するのは都道府県と国だけど」

結局、「ステージ」がどういうふうに使われているか、を考えると、あれだわ。ニュース番組や情報番組が「各都道府県でステージ3と4の指標をこんなに上回っています! 東京も! 大阪も!」って表にまとめている。テレビを見た人が「ふーん、感染が拡大してるね、医療が逼迫してるね」って理解する、そのときだけ使われている気がする。個人的には、ステージという概念は何かの意思決定の判断根拠にはなってはいない、という理解である。

参考リンク

素人がまとめたものよりも、新型コロナウイルス「ステージ」に関するちゃんとした記事を見たいという人は、以下の記事をご覧ください。

【Q&A】新型コロナ報道で耳にする「ステージ」って何? 2020年10月13日の記事。

【Q&A】コロナ分科会が提言。“ステージ3地域”の「3つのシナリオ」とは? 2020年12月12日の記事。分科会が新たに言い出した「シナリオ」の話。

新型コロナ対応の目安、「ステージ」とは 2020年12月7日の記事。リンクで飛ぶと「会員限定です」と書いてあって記事が見られないが、Google検索からだと記事内容を閲覧できる。

政府の新型コロナ分科会 新型コロナ 各地で異なる“ステージ”分け 2020年11月17日の記事。

新型コロナ 感染状況のステージと6指標 毎週金曜日に厚生労働省が「各都道府県の指標の値」をまとめている。それを見やすくしたのがこのYahoo内の表である。ステージ3や4の指標を超えた地域には色を付けている。

AtCoder青になりました

AtCoderで青になりました、というAtCoder色変記事である。

手短に自己紹介

ちょっと前は水色で「競技プログラミングをそこそこしっかりやり込んでいる」と言えた気がするけど、競技人口が増えたせいか青色が目立つようになって、青色がそのポジションになった感がある(個人の感想です)。
あとは「数学が得意なタイプだと、この一つの上の青色に行きますが。(AtCoder(競技プログラミング)の色・ランクと実力評価、問題例 )」って書かれてたから数学が得意な人間としては青に行っておきたかったのよね。
なので青に上がれて一安心している。

この記事は
Competitive Programming (1) Advent Calendar 2020 - Adventar
の16日目の記事です。

レート推移、各種進捗のグラフ

色辺記事の定番である。レート推移と、各種進捗のグラフを見てみよう。

レート推移

f:id:soratokimitonoaidani:20201217002653p:plain

見ての通り、初めて青になったのは2020年3月である。ではなぜこのタイミングで書いているのか? というと、以下のような理由である。
青になる前後で、「青になったら一つの節目として振り返り記事を書こうかな。でも青になって『青色になりました』を書いて、すぐ水色に落ちるのは嫌だな。3回くらい連続で青なら、胸を張って青と言っていいかな」と考えていた。
そうしたら1回目も2回めも直後で水色に落ちたんだよね!
晴れて今回、2020年11月28日のAtCoder Regular Contest 109で3連続青になったので、自分の考えていた「書くための条件」を満たしたので、 このタイミングで書いているというわけだ。

AtCoder Problemsの各種進捗状況

問題を解いている状況を示すために、AtCoder Problemsの画像を色々貼る。

f:id:soratokimitonoaidani:20201217002935p:plain

f:id:soratokimitonoaidani:20201217002903p:plain

f:id:soratokimitonoaidani:20201217002849p:plain

f:id:soratokimitonoaidani:20201217003039p:plain

f:id:soratokimitonoaidani:20201217003034p:plain

上記だと「何点の問題をどれだけ解いたか」はわからないのね。
というわけで、AtCoder Scoresからもう2枚貼る。

f:id:soratokimitonoaidani:20201217003647p:plain

f:id:soratokimitonoaidani:20201217003650p:plain

解いた問題数×レートのグラフ

横軸(rated score sum)140000, 縦軸1600を見ると……あれ、成長遅い方(同レーティング内では解いたrated score sumが多い)なのか?

これだと「解いた問題が550問で青以上に上がれるのは30%くらい」なので、解いた問題の割には早めに青を達成できたと自認していたんだけど。

アルゴリズムのスクールに通ってたので

東京大学の工学部計数工学科→情報理工学系数理情報学専攻という経歴であった。 授業の中で計算量とか各種アルゴリズムとか叩き込まれるので。 (例えばダイクストラやワーシャル・フロイドは授業で扱う。) あと数学得意系の人生をしていたので。

普通に企業とかで超優秀って言ってるプログラマが居た時に、半分くらいはこのランクになると思います。数学が得意なタイプだと、この一つの上の青色に行きますが。
http://chokudai.hatenablog.com/entry/2019/02/11/155904

数学が得意なタイプなので青に行きたいんじゃ!と思っていた。

時系列的なもの。

  • 大学(学部)に在学中、ICPCについて書かれた「目指せ!プログラミング世界一―大学対抗プログラミングコンテストICPCへの挑戦」を買って「へーこんなのがあるんだ」と思ったけど、何していいかわからなかったから何もしなかった。
  • 「何をしていいかわからない」から脱出できたのはAtCoderのおかげである。
  • 水色に乗せる。
  • 2018年は何かめんどくさくなって離れた(特に明確な理由はない)
  • 2019年はじめに転職活動して、コーディング面接を受けたときに「やっば、コード書く力が全然無くなってる。Pythonの実装力を鍛えよう」と思い、競プロに復活した。
  • 2019年7月に前職退職時の有給消化でやり込む
  • 2019年7月にパソコンが壊れて萎える
  • 実家のPCでやってたけど、Kiが解けなくて萎えて離れる
  • 2020年1月にMacBook Proを買い、自由にパソコンが使えるようになり、やり込めるようになった。競技プログラミングのレートを上げるためには自分用のパソコンを買うのがオススメです(冗談)。
  • 3月に初めて青になるが、次のコンテストで水色に落ちる
  • 5月に再び青になるが、次のコンテストで爆死して水色に落ちる
  • 8〜9月に水色diffや青diffの問題に注力して解く
  • 10月に三たび青になる

ライブラリ一覧

色変記事を書くときにはとりあえず履修したアルゴリズム一覧を書けという慣習がありますね。 俺も慣習に倣って書いてみよう。ライブラリのフォルダの中にあるアルゴリズムは以下の通りである。

  • 二項係数(を109+7で割った余り)の計算
  • Union-Find
  • 整数の素因数分解関連
  • 二部グラフマッチング
  • Binary Indexed Tree(BIT)
  • Longest Increase Subsequence(LIS、最長増加部分列)
  • ワーシャル・フロイド

あと、幅優先探索深さ優先探索が出た場合は過去の問題のコードを適当に検索して書き換えて出している(ライブラリにまとめてはいない)。

これらの中で、重要なのは何かと聞かれたらこう答える。

  • 二項係数は最重要。特にPythonだと、数学的な考察を済ませて「あとは二項係数ライブラリを使ってちょっと書くだけですね」と思っていたら、TLEを起こして泣きを見ることがある。速度が出るライブラリを予め持っておくことを推奨。私が書いた以下の記事を参照→python競技プログラミングで、二項係数の計算でTLEしたので高速化した話 - 子供の落書き帳 Renaissance
  • Union-Findは次に重要。
  • ぶっちゃけその他はほとんど使わない。(セグメント木を使えないから、使う問題に出会っても「解けない」で終わるため、この感想になるのかもしれない。)
  • BITとセグメント木は未だによく分かってない。水色のうちに履修しておきなさいという感があるけど、ちゃんと履修しないまま青になってしまった。
    • ABC185のF
  • あとローリングハッシュやらZ-algorithmやらは何もわからない。

習得したアルゴリズムが、俺の場合は同じ青に上がった人に比べて少ないんだろうなー。
もうちょっとアルゴリズムを学習して覚えたらもっと強くなれるのかしら。

python競技プログラミングをやることについて

私がPythonでやっている理由は、上に書いた方に「まずpythonの実装力を付けなきゃ」……って言いながら競技プログラミングに復活したからである。 なお、それまでは主にRubyで書いていた。(競技プログラミングでふつう使われる「速い言語」を全然使っていない。どんだけ天邪鬼なんだ……)

python のいいところ悪いところ

いいところ

  • 変数の型を考慮しなくて良い
  • オーバーフローを考慮しなくて良い
    • したがって剰余を求めるタイプの問題では、途中での剰余計算が適当でも最後に割って剰余を求めれば良い
    • 100桁の数などを扱うことも可能(計算が重い場合はTLEになるが)
  • itertoolsのライブラリが便利

わるいところ

提出して結果がTLEだったときに、次の行動を考えると以下のいずれかになる。

  • (計算量が想定解よりも遅くてTLEなので)計算量のオーダーを改善する
  • (計算量には問題がないが、コードが遅くてTLEなので)定数倍高速化する
  • Pythonを捨ててC++(などの速い言語)で書き直す

上記のうちどれを選ぶかをミスると痛い目に遭うなぁ、という感覚である。 この間は「解法を思いつく→計算量を見積もる→これPythonだと厳しくね?どうする?どうする?仕方ない、C++で書くか?と書き始める→C++でうまく書けずに終わる→実はPythonでも間に合う」という事があったし(ARC104)。
C++の場合は、上記3つのうち一番下の選択肢は最初から無い。定数倍高速化が必要になることは絶対にないとは言えないが、かなり稀だろう。
したがって「(計算量が想定解よりも遅くてTLEなので)計算量のオーダーを改善する」と断定してほぼ差し支えないはずだ。迷いがなく次の動きに移れるのが良いなぁと思う。

いわゆる精進について

精進の定義って何なんだ? 「コンテスト本番中以外に問題を解くこと」で合ってる? みんな当たり前の用に使っているくせに、「競技プログラミングの用語集」みたいな記事を見ても全然意味の説明が出てこないんだが。
それはさておき。

精進のやり方は人によって異なる、合う方法合わない方法があるので、あくまで参考程度にしてください。

コンテスト外で集中して解くのすごい苦手……

全部埋めるのが苦手

難易度順に下からビッシリ埋めてる人が多いよね。無理です、俺にはできません。

音ゲーもこの傾向がかなり強く「とりあえず当該レベルを1周して全曲触れ」という意見には反発したくなる。
全曲ってそれ何曲あると思ってるの。何クレかかると思ってるの。好きな曲も嫌いな曲もあるのに構わず触れと?
……閑話休題

初期の問題の質は悪い、とchokudaiさん自ら言ってるし…… https://twitter.com/chokudai/status/1231612496600944641

AGC-A、diff 1200〜1299あたりは埋めようと頑張ったが、それでも完全に埋めてはいない。

AtCoder Problemで自分のレートと同じdiffの問題をやるな

自分がレート1500だからといってdiff1500をやろうとするな。もっと下の問題からやれ。

ちゃんと理解する

コンテストでは既存の問題と全く同じ問題は(基本的には)出題されない。 したがって、過去の問題を解いたとしても、それをそのまま転用することはできない。 過去の問題から何を得るかが重要になってくる。

ある程度雑でも良いから、方針や感想などを日本語の文章にして書いておくのが大事だ、と最近は考えている。 解法を考えるのに苦労した問題は、日本語で解法を書き留めるようにしている。 最近でちゃんと書いた例だとこの辺りか。

https://github.com/Linus-MK/AtCoder/commit/90388090eb293f762dc681f2687b7dce7d54aaec
https://github.com/Linus-MK/AtCoder/commit/8965e87d309b808826ac3d64917b38b6e88f9504

「どこに気づけばACできたか」というポイントが大事。 具体例を挙げよう。

「連結グラフ一般を対象とした問題は、木に対する問題に帰着できる場合がある」という

紙のノートを作って書いている人もいるけど、私はテキストエディタで書く派である。 (具体的な問題から離れて「今日は××のアルゴリズムを勉強するわ」という勉強のやり方をすることがほとんど無い。 したがって、学習内容のほとんどは具体的な問題と直接紐付いているので、 基本的に問題を解いたコードにコメントを添えておくのが良いのかなと思っている。 あとは「競プロの教訓の一覧」も作ってますね。全然綺麗にまとめずにメモ程度だけど。

https://github.com/Linus-MK/AtCoder/blob/master/lesson.md

  • やったこと
    • 問題の解法を抽象化して言語化しておく
    • いわゆるメタ解法みたいなやつ
  • やってないこと

ABCとARCのどちらが得意か把握しよう

「あなたのレートはどこから?」というサイトがある。
今見たら https://rating-history.herokuapp.com/rating.html?handle=Linus&number=12 で以下の結果だった。

All: 111
AGC: -47
ARC: 160
ABC: -134
Other: 132

このレート帯の人はAGCを解くと「A問題が解けない」という事態があり得るので、AGCを解いてレートを上げるという選択肢は難しい。 ABCかARCかの二択になると思う。

俺は「問題文はごちゃごちゃ書いてあるけど、要はこういうことでしょ?」をやるのが割と上手いという自覚があるので、ABCよりもARCのほうが得意なのだと思う。 本質的な部分を抽出できるとか、問題文の言い換えができるとか、アドホックな力があるとか、その辺かしら? ABCは1つ躓いただけでレートが大きく下がってしまう感があってヤバい。 あと、ABCに出てる人って、みんな過去問をビッシリ埋めてる人ばかりという印象である。 ABCでは典型力が問われるので、俺のようにアルゴリズムの学習に抜け漏れがある人がやると、「この問題はセグメント木の典型です」みたいな、俺の履修していない解法のド典型問題が出題されたときに容易に死ぬんだよね。 ARCが復活してからはABCには出ないことにした。そう言っておきながら、気まぐれで出るかもしれないけど。 最近のABCでは、あれもこれも緑diffになりすぎてマジ怖い。

水色〜青が最近難しすぎる話

  • 新規参入者の基準レートが下がっているせい
    • これは参考googleドキュメントを探す
  • 上に書いてあった、1問を解いたらレートが1上がるって何なのよ
    • 全然上がらないじゃんか
    • これは予想可能な理由がある
    • 多分なんだけど、このレート帯の他の人はyukicoder, CodeForcesに手を出しているので、見かけ上が「AtCoderを1問解く」であったとしても、実際に解いた問題数、実際の努力量は俺よりも他の人が多いと思われる
  • どっかで「青になれませんでした」という挫折記事でも出そうかと思っていたら、運良く青に上がれたのでこうして色変記事を書いている
  • 競プロはすべての問題を解決する万能薬ではない
    • 数学が強くて、しかもアルゴリズムを大学で一通りやったわという人(俺)でも、青になるまでにはこの程度の時間と労力をつぎ込む必要がある
    • 時間がある学生ならば良いけど、時間がない人(社会人とか)がやるときには費用対効果を考えたほうが良いと思う
    • モチベーションが下がったら離れるくらいで良いんじゃないの
    • 少なくとも俺は付かず離れずでやっています
  • 今回のアドベントカレンダーにも「なんか水色が厳しくない? 上がれないんだけど?」って記事があるね

今後の目標

青の次は黄色……いや、黄色とか無理だろ。遠すぎるわ。黄色までの真ん中の1800が当座の目標かなぁ。

青は上位7%である。せっかくの休日に競技プログラミングの大会に出続ける酔狂の中で7%なので、全人類の中では上位1%以内に入っていると思う。

組み合わせるのが一番ラクだからです。ある軸で上位3~5%にいるのはそんなに難しくないけど、100万分の1になるのは並大抵のことではないから。かけっこでウサイン・ボルトに勝つようなものですよね。だから、20分の1とか、30分の1のレベルで勝てる領域を3つ探すわけです。上位20分1を3つ組み合わせれば、8000分の1の稀少な存在になれる。
https://diamond.jp/articles/-/208123

このまま努力を続けていって、例えば赤コーダーになれるかって言ったらなれないじゃん。きっと。

この辺で青キープを目指しつつ、機械学習・データ分析の勉強に少し重心を移すのが正解かなぁと思っている。

GCJの予選1回戦突破は自分の中で1つの目標だったけど、2020年に初めて達成できたしなぁ。 ちょっと次の目標が見つからなくて迷子っぽいな。

それでは。

競技プログラミング関係の他の記事

こちらもどうぞ。

linus-mk.hatenablog.com

linus-mk.hatenablog.com

linus-mk.hatenablog.com

linus-mk.hatenablog.com

effective python 第2版の翻訳改善点 8〜10章

オライリー・ジャパンから発売された「Effective Python 第2版 Pythonプログラムを改良する90項目」の日本語訳の改善提案である。気になった箇所について、原文と照らし合わせて問題点を述べ、日本語訳を自分で書き直している。

注意事項

「Effective Python 第2版」の日本語版をAmazonで、原著(電子書籍版)をInformIT(ピアソン社の電子書籍販売サイト)で購入した。
以下でそれぞれの本の文章の一部を書いているが、著作権法で定められた引用に該当する。 これは訳文の批評のために必要不可欠な引用である。

  • 選んだ箇所は私が問題だと思った部分である。文章の意味が間違っているところ(誤訳)と、文意が分かりづらいところとが混じっている。(両者をハッキリ判別するのは難しいので、どの部分がどちらかを示すことはしていない。)
  • ページ数は日本語版のページ数を示す。原著のページ数は省略した。
  • 日本語版:」のあとに続く部分は「Effective Python 第2版」の日本語版からの引用である。
  • 原文:」のあとに続く部分は「Effective Python: 90 Specific Ways to Write Better Python (2nd Edition)」原著からの引用である。
  • また、「直訳」および「意訳」は原文から私がオリジナルで訳した文である。
  • 直訳」は英語の単語を極力そのまま日本語に置き換えたもの。
    • 常に常体である。
    • 「I / you」も訳出している。
    • 高校の授業でやる英文和訳のような結果になるので、日本語として不自然な場合もある。
  • 意訳」はそこから構文の変更などを加えて日本語として整えたものである。
    • 常体か敬体かは元の日本語訳と同じとした。
    • 「I / you」は日本語訳と同様、訳出しないことにした。
    • 仮に私が翻訳するとしたら「意訳」の文章を最終結果にするであろう。

その他、翻訳改善点を書く際に考えたことは以前に書いた1〜3章の記事を参照してほしい。

linus-mk.hatenablog.com

なお、前記事で1〜3章、本記事で8〜10章についてあつかっているので、残りは4〜7章である。 しかし、残りについてまとめる予定は今のところありません。翻訳改善点を書くのは、だいぶ労力がかかるので……。

8章

p.289 項目65

  • 日本語版:else節は、try/exceptの後で起こることは、見た目にも、exceptブロックとは異なるということを保証します。
  • 原文:The else clause ensures that what follows the try/except is visually distinguished from the except block.

「見た目にも……異なる」ってどういうこと?
逐語訳としては間違ってない気がするけど、何が言いたいのかどうにも伝わりにくいような……
主語の「else節」は思い切り無生物主語なので、うまく書き直したいところ。こんなもんでどうだろうか。意訳は2通り書いてみた。

  • 直訳:else節は、try/exceptの後で起こることがexceptブロックと視覚的に区別されていることを保証する。
  • 意訳:else節を使って書けば、try/exceptの後続の処理を、exceptブロックと見た目にも切り離しておくことができます。
  • 意訳:else節を使って書けば、try/exceptの後続の処理を、exceptブロックとは別々のものだと見て分かるようになります。

p.300 項目68

  • 日本語版:pickleの本来の目的は、Pythonオブジェクトを自分がコントロールしているバイナリチャネルでプログラム間をまたいで渡すことです。
  • 原文:The purpose of pickle is to let you pass Python objects between programs that you control over binary channels.
  • 直訳:pickleの目的は、あなたに、あなたが管理するプログラムの間で、バイナリの経路の上でPythonオブジェクトを渡させることである。
  • 意訳:pickleの目的は、自分が管理するプログラムどうしの間で、バイナリの経路を通じてPythonオブジェクトを渡すようにできることです。

このすぐ下の文も悪訳。(次項で扱う。)続けざまに悪訳が出てきたんだけど、どうした一体?

日本語版の翻訳だけど、多分これはcontrolとoverをセットで訳してるよね。 「自分がコントロールしているバイナリチャネル」のあたり。(冷静に考えるとこの訳なら原文はbinary channels (that) you controlじゃないとおかしくないか?)
controlが名詞ならそれにoverが結びつくのはよくある。が、今回のcontrolは動詞だ。動詞controlとoverを使う例は辞書でも見つからなかった。
正解は、passとoverがセットになって結びついているのだ。したがってcontrolとoverは意味の上では分かれている。下記に、pass X over Yの形になっている文の例を示す。
channel=経路 をオブジェクトが通っているので、through channelsかin channelsあたりのような気がするが、overが正解なのか……この辺の前置詞の感覚はよく分からないわ。
動詞letについては、ややenableっぽく訳してみた。

参考:
He passed his over his face. 手で顔をなでた
pass one's eye over a letter 手紙に目を通す
(英語活用大辞典より)

p.300 項目68

  • 日本語版シリアライズしたデータは、本質的には、元のPythonオブジェクトをどのように再構築すればよいかを記述したプログラムを含む。 これは、悪者のpickle情報がデシリアライズしようとするPythonプログラムのどの部分にも忍び込むのに使われうるということを意味する。
  • 原文:The serialized data contains what is essentially a program that describes how to reconstruct the original Python object. This means a malicious pickle payload could be used to compromise any part of a Python program that attempts to deserialize it.

日本語版では「pickle情報が」に対応する述語がどこなのか分かりにくいと思う。

日本語に翻訳するとき、普通は能動態か受動態かで迷ったら能動態で書いたほうが収まりが良いけど、 今回はcompromiseを受動態として訳したほうがスッキリしたのでそうした。
「誰かが不正にアクセスする」という文よりも「システムが不正にアクセスされる」という文を見かけることが多いからかな?

  • 直訳シリアライズされたデータは、本質的には元々のPythonオブジェクトを再構築する方法を記述したプログラムであるものを含む。 これは、悪意のあるpickleペイロードが、それをデシリアライズしようとするPythonプログラムの任意の部分に不正アクセスするのに使われる可能性があるということを意味する。
  • 意訳シリアライズされたデータには、元々のPythonオブジェクトを再構築する方法を記述したプログラムと同等のものが含まれている。 したがって、悪意のあるpickleペイロードがあると、それをデシリアライズしようとするPythonプログラムの任意の部分が不正にアクセスされてしまう可能性がある。

p.309 項目69

  • 日本語版:Decimalクラスでは、丸めのための組み込み関数があり、望ましい丸め操作を正確に必要な桁数で丸めてくれます。これで、抱えていた切り上げ問題が解決されます。
  • 原文:Luckily, the Decimal class has a built-in function for rounding to exactly the decimal place needed with the desired rounding behavior. This works for the higher cost case from earlier:

「丸め操作を……丸めてくれます」ってどういうことよ。「馬から落馬する」とか「頭痛が痛い」と同様にダメだと思うんだけど。

  • 直訳:幸運なことに、Decimalクラスは、所望の丸め挙動によって10進法地点へ正確に丸める操作のための組み込み関数を持つ。これは、始めにあったより高い料金の例でもうまくいく。
  • 意訳:幸いにもDecimalクラスには組み込み関数があり、希望どおりの丸め方で数値を10進法の数値に正確に丸めることができます。これは、始めに挙げたより高い料金の例でもうまくいきます。

rounding to exactly the decimal place(原文)と
rounding to the exact decimal placeの違いって何なんだ……exactlyがroundingを修飾するならtoの前になるんじゃないか……分からないや。

なおおまけの指摘だが、この項目69でずっと小数点2桁で四捨五入/切り上げをしているのはセント単位にしたいからである。
原文では「round to the nearest whole cent」つまり「最も近い、セント単位の数に丸める」という意味である。 「round ~ to the nearest whole number 小数点第1位で四捨五入して整数にする」が英辞郎にあったので、numberの代わりにcentが入った形だろう。 何でwholeなのかcentが単数なのかよく分からんけど。
英文にあった「セント」が日本語版では完全に消えている。 「最も近い整数への丸め方式(p.308 上部)」じゃ意味が通らないだろう。だって四捨五入の結果である5.36は整数じゃないんだから。

9章

p.357 項目78

  • 日本語版:厳密には、どのdatabaseオブジェクトでも取れるように、一部の引数が使えるのであれば、定数unittest.mock.ANYを、どんな引数でも取れることを示す値として使います。
  • 原文:If I actually don’t care about some of the individual parameters, such as exactly which database object was used, then I can indicate that any value is okay for an argument by using the unittest.mock.ANY constant.

「individual parameters」つまり個々のパラメータの一部の例として、「exactly which database object was used」=「正確にどのdatabaseオブジェクトが使われたのか」がある。日本語版では、exactlyに相当する「厳密には」が変なところにあるし、文意がよく分からない。
挿入句がちょっと訳しづらい。カッコに入れるくらいしか上手いやり方が思いつかない。以下のようになる。

  • 直訳:もし実際には私が個々のパラメータの一部(例えば「正確にどのdatabaseオブジェクトが使われたのか」など)には関心がないのであれば、私はunittest.mock.ANYという定数を使うことで、その変数にはどんな値でも大丈夫であることを示すことができる。
  • 意訳:もし実際には個々のパラメータの一部(例えば「正確にどのdatabaseオブジェクトが使われたのか」など)が重要でないのならば、unittest.mock.ANYという定数を使って、その変数にはどんな値を入れても構わないことを示すことができます。

単純な誤字脱字

気づいた範囲で書いておきます。

p.343
実際の型とか構成部分がはっきりしていなことです。

実際の型とか構成部分がはっきりしていないことです。

p.348
try/excep 文とよく似ていて、

try/except 文とよく似ていて、

p.356 (ページ中央のAtributeErrorのすぐ下)
daabase引数にはobjectを使います。

database引数にはobjectを使います。

関連記事

linus-mk.hatenablog.com

linus-mk.hatenablog.com

終わりに

目についたところを挙げた。しかし、すべて完全に読んだわけではないので、まだ見逃しているところがあると思う。 「Effective Pythonのこの部分の文章の意味がよくわからないんだけど!」というのがあれば、コメント欄とかTwitterで言ってくれれば見てみます。この記事に加筆するかもしれません。