LCL Engineers' Blog

バス比較なび・格安移動・バスとりっぷを運営する LCLの開発者ブログ

人力の名寄せを機械学習のエッセンスを加えて自動化する

Androidアプリ兼バックエンドエンジニアの高橋です。

弊社のサービス「バス比較なび」では、たくさんのバス会社さんから頂いた高速バスデータを掲載していますが、バス会社さん間での「データの揺れ」が課題の一つとしてあります。

例えば、バスの「停車地」には以下のような表記揺れがあります。

A社 : JR東京駅八重洲南口 鍛冶橋駐車場
B社 : 八重洲口鍛冶橋駐車場<東京駅 八重洲南口>
C社 : 東京駅八重洲南口

この状態では、停車地をGoogle Mapにマッピングしようとしても、難しいですよね。

実は、弊社ではこれまで手作業によってこういった名称を「名寄せ」しています。

上記の例でいうと、JR東京駅 八重洲南口 鍛冶橋駐車場 が名寄せ後の名称です。

データが蓄積されている現在では手作業でもある程度はカバーできますが、休日や長期連休などに対応できないので、現在停車地の名寄せ自動化に挑戦しています。

そもそも名寄せとは

「名寄せ」という言葉をなんとなく使っていますが、ここでいう「名寄せ」を具体的(システム的)にいうと、

  • 実態は同じであるが、データの表記に揺れがある複数のレコードを統合すること
  • 統合後のレコードは任意に設定し、統合前のレコードを統合後のレコードにリンクさせる

つまり、統合後のレコード(いわゆるマスター)は運用者の手によって管理しつつ、新たに発生するレコードをマスターと自動で紐付けたい訳です。

共通のIDのようなものがあれば名寄せの必要はありませんが、それがないため表記が不確実なフィールドを基に紐付けを行う必要があります。(冒頭で紹介したような、停車地の呼称など)

また、名寄せの方法には重複のレコードを削除して一つだけ残す方法(deduplication)もありますが、今回やりたいのは、entity matchingとか、record linkageとか呼ばれたりするものです。

どうやるか

まず、「名寄せ」をするにあたって、機械学習を用いるか、ルールベースでやるか、それぞれのメリットとデメリットを検討しました。

機械学習は、手作業で既に名寄せ済みのデータを訓練データとして、教師あり学習で名寄せする方法です、

一方、ルールベースは、独自のロジックを作って、一定の基準に基づいて名寄せをします。例えば、「空白と記号を除去後、異なる文字数が3文字以内 かつ 全体の文字数の差が5文字以内」など。

機械学習の場合

メリット
  • ドメイン知識をあまり持っていなくても、実装ができる
  • 精度のチューニングが容易にできる
デメリット
  • どれくらいの精度が出るか、やってみないとわからない
  • 機械学習について多少の知見が必要

ルールベースの場合

メリット
  • 細かいルールを設ければ高い精度で名寄せができる可能性がある
デメリット
  • ドメイン知識が強く求められる (どういうデータがあるか精通している必要がある)
  • メンテナンスが大変
  • ルールを管理しないと属人化しやすい

今回、停車地の名寄せをするには、表記揺れが多すぎて、ルールベースだとあまりにも複雑なルールができそうでしたので、機械学習を取り入れることにしました。

名寄せの学習

ここからは具体的な名寄せの機械学習について、一部ご紹介します。

機械学習のアルゴリズムそのものには触れませんが、主に学習の前段階として注意した点をご紹介します

使用ツール

以下のpythonライブラリを実験的に使っています。

recordlinkage.readthedocs.io

名寄せに関するライブラリは他にも色々あるのですが、上記がシンプルで使いやすく、pythonのDataFrameをそのまま使えたので採用させていただきました。

SaaSにも以下のようなものがあるにはあるのですが、後述する精度の問題や既存システムへの組み込みの点で、結局は自前で用意するのがベストと判断し、採用しませんでした。

dedupe.io

https://docs.aws.amazon.com/glue/latest/dg/machine-learning.html

前処理

名寄せをするに当たり、フィールドの類似度を測る必要がありますが、より正確な類似度を測るために、以下の点に注意しました。

  • 全角・半角の差異をどちらかに統一
  • 長すぎる文字列を短縮 (先頭~文字までにトリムする)
    • 備考や米書きなどがフィールドに入ってくることがあり、類似度を測る邪魔になるので
  • 類似度を測るのに不要な文字を削除
    • 主に()「」・、などの記号は類似度を測る邪魔になるので
  • あったりなかったりするワードを削除
    • 「バス停」「乗り場」などのワードがあったりなかったりする表記ゆれがあるので。
    • そもそも停車地の類似度を測るのだから、これらのワードは停車地の特徴を示さないので不要。

これらは前処理に当たる段階で、機械的に正規化してあげます。

文字列の比較

今回レコードの類似度を測るのに有用なフィールドは、「停車地の呼称」だけですので、文字列の比較を行うことで類似度を測ります。

文字列の類似度を測る方法はいくつかありますが、有名なものでは「レーベンシュタイン距離」でしょうか。

ここでは解説しませんが、以下サイトの解説が参考になるかと思います。

https://mieruca-ai.com/ai/levenshtein_jaro-winkler_distance/

この類似度が実際の機械学習に用いる「特徴量」となります。

日本語の比較の問題

日本語は類似度を測るのがとても難しい言語です。

英語のように単語単位でトーカナイズされている言語は、単語同士の比較をすれば自ずと類似度が測れるのは想像しやすいかと思いますが、日本語の場合は(辞書を利用しない限り)言葉の区切りがわかりません。

例えば、「大宮駅東口」と「大宮駅西口」は1文字しか変わらず文字列の類似度はかなり高いため、機械学習の結果同じレコードとして認識されてしまうかもしれません。

今回は辞書のメンテナンスはしたくないため、例えば以下のような停車地の特徴を表す言葉を別のフィールドで持つことで、特徴量の種類を増やしてあげます。

  • 「東」「西」「南」「北」(東口、西口など)
  • 「~番」(バス停乗り場番号)

これらの言葉は多くのケースで完全一致している必要があるので、類似度は0(不一致)か1(一致)になります。

こういった自力による特徴量の抽出は若干のドメイン知識が入り込んでしまいますが、なるべく誰でも理解できる特徴量だけを抽出した方がいいと思います。

今回のように比較できるものが文字列しかない場合、こういった特徴量の抽出は学習結果に大きな影響を与えるので、検証を何度も繰り返した方が良さそうです。

類似度から特徴量が抽出できたら、あとは機械学習にかけるだけですね。(そんな単純ではないですが、、、割愛させていただきます。)

既存システムへの組み込み

既存システムの仕様や運用を大きくは変えたくなかったため、以下の方針で設計しました。

  • 現状の人力の名寄せは継続する(自動で100%名寄せできるわけではないので)
  • 自動名寄せのJOBを止めても、現行の運用に問題がないようにする。(精度に問題があったときのため)
  • 自動名寄せした結果は、運用者が手動で修正可能にする。

要するに機械学習による名寄せはあくまで、人力名寄せのサポートであって、それありきのシステム設計にはできない、ということですね。

大雑把に以下のような図です。

f:id:ktx_ku:20200129174151p:plain

結果

結論からいうと、名寄せの再現率(※1)は60~70%ほどで、そんなにいい結果は出ませんでした。

ただし、今回は名寄せの精度(※2)を重視した特徴量の抽出を恣意的に行ったため、精度は98%ほどでかなり高かったです。

ここら辺はトレードオフなのである程度は致し方ないですが、そもそも現状の人力による名寄せが間違っていたりするケースがあるので、現状のデータを整備すれば改善の余地があるとは思っています。

※1 全体の対象レコードのうち、名寄せができた割合

※2 名寄せを行ったレコードのうち、名寄せが正しかった割合

(再現率と精度については以下ページが参考になります) ibisforest.org

最後に

名寄せを自動化することで運用のコスト削減のメリットもありますが、将来的にもっと大きなデータを扱う時が来る時に備えて、今の段階で名寄せの知見を得られたのはよかったと思います。

弊社はまだ機械学習を取り入れているところが少ないので、アイデアがあれば今後も積極的に取り入れていきたいと思います。

ちなみに私自身は機械学習エンジニアではなくて、基本Androidアプリエンジニアですが今回挑戦させてもらいました。

未知な分野にでもどんどん挑戦できる風土が弊社にはあるので、好奇心旺盛な方は是非カジュアル面談からでもお待ちしてます!

www.lclco.com