家計簿をつけたら二部グラフの最小重み完全マッチングが必要だった

2024-09-08 #tech

#前置き

もう約一年くらい、個人の家計簿を自作の複式簿記用プログラミング言語である Qash でつけています。もともとこれを作ったモチベーションの大部分は家計簿を SQL でクエリしたいというところにあったのですが、ちゃんとその役目を果たしてくれています。

ただ実のところ、家計簿をつける全ての作業を Qash でどうにかしているというわけではありません。具体的には、クレジットカードや銀行口座、各種交通系 IC カードの履歴などをスクレイプして Qash に打ち込む部分は、手でやるとあまりも面倒なので、 Money Forward ME を契約して使っています。Money Forward ME は（説明不要な気もしますが）銀行口座やクレカのログイン ID・パスワードを献上するのと引き換えに、これらのサイトにアクセスして使用履歴を引っ張ってきてくれます。普通は Money Forward ME 上でその使用履歴を分析すると思うのですが、自分はその類の機能は全く使用せず、単なるスクレイパとして使っています。つまり Money Forward ME に集めてもらったデータを CSV として出力させ、それを、これまた自作の（そして非公開の）秘伝の Ruby スクリプトに食わせて Qash に入力するための Qash プログラム（より正確にはそれと等価な JSON ファイル）を作っています。

秘伝の Ruby スクリプトの役目の一つは、クレカの各購買履歴に適切な勘定科目をつけることです。クレカの履歴には一般的に、クレカを使用した日付と決済金額の他に、店舗名などの説明がついています。そこで、私の様々な購買傾向にオーバーフィットしたような、言ってしまえば ad hoc な分岐や処理を大量に書くことで、この説明部分から勘定科目（食費・書籍・税金、など）を推論します。仮にここで間違えてしまっても、Qash には後からこれを修正する機能もあるので、それほど困りません。とにかく体感 9 割くらい勘定科目が当たるようなスクリプトを書いています。

さて、クレカの利用履歴にはまともな説明（購入した店舗の情報など）が載ることが多いのですが、使用の仕方によっては、ほとんど意味のないものが載っていることもあります。代表的な例が Amazon です。 Amazon で商品を購入すると、説明のところには「Amazon.co.jp」としか表示されず、何を購入したかはさっぱりわからないため、大変不便です。

そこで私は、Money Forward ME に Amazon アカウントを紐付けスクレイプさせています。これによって、Amazon での購買履歴もスクレイプして CSV に含めることができます。秘伝のスクリプトでは、この情報を使って Amazon での購買履歴を補完しています。

#仕訳のマッチング

とは言っても、この補完はそれほど簡単ではありません。というのも、Amazon アカウントから引っ張ってきた履歴と、クレカから引っ張ってきた履歴を、うまくマッチングさせる必要があるからです。

もう少し具体的に状況を整理します。Money Forward ME が出力する CSV はおおよそ、次のようになっています：

"ID","日付","内容","金額（円）","保有金融機関"

# ...

# これはクレカから出てきた情報
"ID10","2024/08/20","AMAZON.CO.JP","-1000","XXXクレジットカード"
"ID11","2024/08/22","AMAZON.CO.JP","-2000","XXXクレジットカード"

# ...

# これは Amazon アカウントから出てきた情報
"ID50","2024/08/20","YYY が死ぬほどわかる本","-1000","Amazon.co.jp"
"ID51","2024/08/22","完全理解 ZZZ","-1000","Amazon.co.jp"

# ...

このような CSV を受け取って

『YYY が死ぬほどわかる本』を『XXX クレジットカード』で 2024/08/20 に購入した。
『完全理解 ZZZ』を『XXX クレジットカード』で 2024/08/22 に購入した。

と認識する必要がある、というのが「うまくマッチングさせる」と言った意味です。

一見、日付と値段が同じものをまとめるだけで良いように思えるので、この問題はそれほど難しくないように思えます。しかし実際には、決済のタイミングによって日付がずれたり、Amazon ポイントを一部使用して購入したために値段がずれたりということが往々にして起こります。そこで、日付と価格が一番近そうなものをうまくまとめる必要があります。

#定式化

本来ならここでもっと説明を挟むべきだと思うのですが、眠くなってきたので端折ると、今回のケースでは、クレカから出てきた情報と Amazon アカウントから出てきた情報を、以下のような二部グラフにまとめることができます。

ID10 --- (0, 0) -------- ID50
    \                  /
     --- (1000, 2) ----- ID51
                     /  /
     --- (1000, 2) --  /
    /                 /
ID11 --- (0, 0) -----/

ここで、各頂点は購買情報の ID で、左側にクレカ、右側に Amazon アカウントのものを配置しています。その間を edge で結び二部グラフを構成します。各 edge には、それぞれの価格・日付の差を組にしたものを重みとしています。例えば (0, 0) というのは日付と価格に差が無いことを表しています。また (1000, 2) というのは日付が 2 日ずれていて、価格が 1000 円差があるということを表しています。

解きたい問題はこの二部グラフのマッチングです。特に、今回は日付・価格を一番近くしたいので、 edge の重みの総和が最小になるようにする必要があります。こういう問題は最小重み完全マッチング（minimum weight perfect matching; MWPM）と呼ばれ、量子コンピュータの文脈でよく使われているようです。これを解きます。

#実装

基本的には上で定式化した問題を解くだけです。解くだけなんですが、ぐぐってみると意外と面倒というか、自分が知らない話がたくさんありそうなので、実は手元の実装ではしばらく（1 年弱）サボっていました。

代わりに適当な greedy で解いていたんですが、最近ついに最適解を出せない仕訳が発生するような買い物をしてしまい、仕方ないのでまともな解き方をするようにしました。

と言っても自分で実装したわけではなく、Python の networkx にある minimum_weight_full_matching を呼ぶようにしました。秘伝のスクリプトは Ruby で書いてあるので、別途 Python スクリプトを用意して、それを open3 で呼び出す形にしています。

ここまで書いてから気づいたんですが、組の重みに対してどうやって最小性を定義するかは議論があるような気がします。とりあえず手元の実装では、以下のような形で重みを整数にエンコードして、一応動いています：

(日付の差) + (価格の差)*100

また、あまりにも日付が離れすぎている場合はそもそも edge を作らないようにしています。手元では 1 日差までだけ許容してうまく動いています。

#まとめ

というわけで家計簿をつけていたら二部グラフの最小重み完全マッチングが必要になった話でした。最小重み完全マッチングという問題自体、今回の件で初めて知ったのですが、家計簿という具体的なのことを突き詰めていくと抽象的な CS の問題が出てきて、しかもそのレベルでは量子コンピュータともつながっているという面白い体験ができました。

面白いと言いつつ、数学周りではよくある話のような気もしますし、そもそも重みのエンコードの部分が微妙な気もしますが、とりあえず手元の問題が解決できて良かったということにしておきます。

この記事はヨルシカの「あの夏に咲け」を聞きながら書きました。

#追記（2024/09/08）

実装で、1 日差しか許容していないので、日付の差を足すのはほぼ無意味そうだなということに起きてから気づきました。多分ほぼ価格の差だけが効力を持っていそうです。あと、量子コンピュータに使っているのは二部グラフではないので、厳密には違う問題だと知り合いに教えてもらいました。なるほどなぁ。