【Python】ふるさと納税をハックする Part.2
前回の記事
前回の記事はコチラ。
自治体選びのフローを自動化する（続き）
貪欲法によるフロー③の自動化
前回記事までの検討を通じ、フロー②まではプログラムに落とし込み、自治体リストを作成することができました。本節では、引き続きフロー③の自動化を検討していきます。
フロー③は「自治体リストから自治体を選ぶ：②で作成した自治体リストに基づき、どの自治体を選べば５自治体以内でウィッシュリスト中の項目を最大限カバーできるのか考えます。」ということでした。
これは一種の最適化問題と考えることができます。最適化問題には様々なアルゴリズムがありますが、今回は実装が比較的容易な貪欲法（greedy algorithm）を適用して近似解を求めてみようと思います。
貪欲法については、「問題解決力を鍛える！アルゴリズムとデータ構造」において次のように説明されています。
物事の選択を繰り返して結果を最適化するタイプの問題に対して適用できる考え方です。ただし動的計画法のように、考えられる遷移をすべて考えるのではなく、１ステップ先のことのみを考えて最善な選択を繰り返す方法論です。
今回の例に当てはめて考えると、次のような繰り返し処理に落とし込むことができます。
自治体リストにおいて出現頻度が最大の自治体を選出する。
手順１で選出した自治体で用意のある返礼品を、自治体リストから取り除く。
手順１、２を自治体リストが空になるか、選出した自治体数が５自治体となるまで繰り返す。
これらの処理を、前回考えた自治体リストを作成するプログラムに組み込むと次のようになります。
import requests
from bs4 import BeautifulSoup
import pandas as pd
import re
from collections import Counter
# 都道府県市町村パターン
prefecture_pattern = r"(.{2,3}[都道府県])(.+)"
# 検索キーワードリスト
keywords = ["鱧", "猪肉", "ラフランス"]
# 最終結果用DataFrame
final_df = pd.DataFrame()
# 全自治体を保存する辞書
all_data = {}
for keyword in keywords:
data = set()
page = 1
while True:
print(f"Processing keyword: {keyword}, page: {page}")
# URLエンコーディング
keyword_encoded = requests.utils.quote(keyword)
# HTMLを取得
url = f"https://www.satofull.jp/products/list.php?q={keyword_encoded}&cnt=120&p={page}"
response = requests.get(url, headers=headers)
html = response.text
# BeautifulSoupで解析
soup = BeautifulSoup(html, 'html.parser')
items = soup.select('.ItemList__city')
# データをセットに追加
for item in items:
match = re.match(prefecture_pattern, item.text)
if match:
prefecture = match.group(1)
city = match.group(2)
data.add((prefecture, city))
# 次のページが存在するかチェック
next_page_links = soup.select('.Pager__num__link')
if not any(f"p={page + 1}" in link['href'] for link in next_page_links):
print(f"All pages processed for keyword: {keyword}")
break
page += 1
# データをDataFrameに変換
df = pd.DataFrame(list(data), columns=[f'{keyword}_都道府県', f'{keyword}_市町村'])
# 最終結果用DataFrameに追加
final_df = pd.concat([final_df, df.reset_index(drop=True)], axis=1)
# 各キーワードの自治体を保存
all_data[keyword] = list(data)
# 選択された自治体とその詳細を保存するリスト
selected_municipalities = []
# 最大5回の操作、またはキーワードがなくなるまでループ
for _ in range(5):
if not all_data: # キーワードがなくなったら終了
break
# すべての自治体名を一つのリストにまとめる
all_municipalities = [municipality for municipalities in all_data.values() for municipality in municipalities]
# 各自治体が何回出現したかをカウント
counter = Counter(all_municipalities)
# 出現回数が多い順にソートして、最も多い自治体を選ぶ
most_common_municipality, _ = counter.most_common(1)[0]
# 選んだ自治体がどのキーワードで出てきたかを集計
included_keywords = [keyword for keyword, municipalities in all_data.items() if most_common_municipality in municipalities]
# 選択した自治体とその詳細を保存
selected_municipalities.append((most_common_municipality, included_keywords))
# 選んだ自治体を含むキーワードを取り除く
all_data = {keyword: municipalities for keyword, municipalities in all_data.items() if most_common_municipality not in municipalities}
# 選択された自治体とその詳細をDataFrameに追加
selected_df = pd.DataFrame(selected_municipalities, columns=["Selected_Municipality", "Included_Keywords"])
final_df = pd.concat([final_df, selected_df.reset_index(drop=True)], axis=1)
# Excelファイルとして出力
final_df.to_excel("Municipalities.xlsx", index=False)
# 結果を表示
selected_municipalities試行結果
上のコードをGoogle Colab上で実行すると次の結果が出力されます。
[(('福岡県', '岡垣町'), ['鱧', '猪肉']), (('新潟県', '加茂市'), ['ラフランス'])]この出力結果から、福岡県岡垣町に寄付することで「鱧」「猪肉」の返礼品が、新潟県加茂市に寄付することで「ラフランス」の返礼品が得られることが分かりますね。
今後の課題
今回のプログラムでは、少なくとも次の２点の課題があることを認識しています。
キーワードを一般的なもの（例えば「カニ」など）に設定すると、検索結果が１万件や２万件を超えてしまい、スクレイピングに非常に時間がかかってしまうことが分かりました。キーワードはできるだけ具体的に（「カニ」であれば「タラバガニ」や「ズワイガニ」など）設定した方が処理時間を短くすることができる点は注意が必要です。
フロー③を自動化するために採用した貪欲法は、あくまでも最適化問題に対して近似解を与えるものであり、最善解であることは保証されていません。
以上２点については、今後のスキルアップを通じて改善を図りたいと思っています。
おまけ：正規表現マッチングによる都道府県と市町村の分離
今回、貪欲法によるフロー③の自動化処理を組み込んだ他に、自治体を抽出する際に都道府県と市町村を分けて記録するように変更を加えています。
今回の目的に対し、都道府県と市町村を分けて記録することで特段の恩恵があるわけではありませんが、今後ふるさと納税に対して都道府県単位で何らかの分析を行いたくなった際に便利かも？と思ったことが動機です。
この都道府県と市町村の分離を実行している部分のみ上記のコードから取り出して見てみましょう。次の２箇所で分離を行っています。
# 都道府県市町村パターン
prefecture_pattern = r"(.{2,3}[都道府県])(.+)"# データをセットに追加
for item in items:
match = re.match(prefecture_pattern, item.text)
if match:
prefecture = match.group(1)
city = match.group(2)
data.add((prefecture, city))Pythonの標準ライブラリに含まれているreモジュールを活用し、都道府県名を表す正規表現パターンである(.{2,3}[都道府県])にマッチングする文字列を都道府県名として、都道府県名の後に続く文字列を市町村名として、それぞれ抽出することで分離を実現しています。
正規表現とreモジュールについては、次の公式ドキュメントが分かりやすく解説しています。
まとめ
本稿では、ふるさと納税においてワンストップ制度を最大限活用するための自治体選びを自動化する方法について検討し、実際に実装してみました。
皆さんも是非本稿を参考に、ふるさと納税をハックしてふるさと納税ライフをお楽しみください！
毎度お読みいただきありがとうございます！
ご意見・ご質問などございましたらお気軽にコメント欄に投稿してください。いただいたコメントは全て拝見し真剣に回答させていただきます。