[NCTSサミットレビュー] JD Logistics Fan Yu：配送先住所をより正確にする方法 - JD Logisticsのビッグデータアルゴリズムのテストと探索に近づく

2019年10月26日、Testinが主催する第2回NCTS中国クラウドテスト業界サミットが北京で開催されました。「AI+未来」をテーマにしたこのサミットには、国内外のテスト分野の著名な専門家や学者、大手企業の意思決定者、上級技術管理者、メディア関係者などが集まり、ハイエンドのクラウドテスト技術について議論し、テスト担当者が最先端の業界動向と最新の業界慣行を理解できるようにしました。

[[284798]]

会議では、JD Logisticsのシニアテスト開発エンジニアであるFan Yu氏が、「配達先住所をより正確にする方法 - JD Logisticsのビッグデータアルゴリズムテスト探究の旅にご案内」と題した基調講演を行いました。 Fan Yu氏は、「アルゴリズムテストを行うには、まずアルゴリズムテストモデルを確立し、次に実際の有効な履歴データを取得し、アルゴリズム関連のインターフェースの呼び出しを完了し、最後にテストプロセスを改善する必要があります」と指摘しました。

以下はファン・ユー氏のスピーチの記録です。

みなさんこんにちは。まずは自己紹介をさせてください。私はJD Logisticsから来ました。2013年にJDに入社しました。私たちのビッグデータアルゴリズムのテストは、2016年末から2017年初めにかけて徐々に始まりました。当初は、UI 自動化、インターフェース自動化、自動テスト ツール プラットフォーム、データ統合などの自動テストも行いました。今日はビッグデータ アルゴリズムに関するいくつかのテストについてお話しします。

まずディレクトリを紹介します。最初の部分はプロジェクトの背景、2番目の部分はアルゴリズムモデルの確立、3番目の部分はテストデータの取得、4番目の部分はアルゴリズムテストの実行プロセス、そして最後に要約があります。主にこれらの部分に分かれています。

まず、技術的な背景をご紹介します。JD Expressは昨年末から徐々にWeChatミニプログラムでの注文に対応し始めました。もともとJDは速達荷物の配達しかできませんでしたが、今では玄関先で荷物を受け取ることもできます。そこで、WeChatミニプログラムに「JD Express」という機能を追加しました。ミニプログラムのインターフェースには、キーワードを自動的に抽出するアルゴリズムが実装されています。住所全体をWeChatミニプログラムにコピーすると、住所情報、電話番号、アドレス帳が抽出されます。このプロセスにより、手動入力プロセスが削減され、ユーザーエクスペリエンスが向上します。全員の住所が共有されるため、たとえば、あるアプリケーションからコピーして別のアプリケーションに配置するのは非常に便利です。

これがスクリーンショットです。これが私たちのシステムのインターフェースです。住所を入力すると、名前、電話番号、詳細な住所が下から自動的に抽出されます。これが私たちのプロジェクトの背景です。

アルゴリズムモデルの確立についてお話しします。前回の紹介で簡単にお話ししたので、この部分についてはゆっくりお話しします。配送先住所が非常に長い文字列で、S2、S2 から S7 が第 1 レベルの住所と第 2 レベルの住所、S6 が名前、S7 が電話番号であるとします。このモデルを構築するにはどうすればいいですか?

アルゴリズムのテストでは、モデルの構築が必要になることがよくあります。左側の部分が、アルゴリズムのテストでよく使用されるモデルです。たとえば、最初のものは精度と再現率です。検索関連のテストを行ったことがある人なら、それについて何か知っているでしょう。精度と再現率は真理値表であることを知っています。たとえば、期待値は真、実際値は真、期待値は偽、実際の偽統計は精度率です。リコール率とは、結果が偽であると予想したのに実際の結果が真であったり、予想した結果が真であったのに実際の結果が真であったりする状況です。つまり、結果の一部は真の値です。これがリコール率です。次の部分は確率です。多くのアルゴリズムは確率で測定されます。最後の部分はコサイン類似度です。コサイン類似度は高倍数のベクトル結果を測定するため、多くのアルゴリズムテストでより多く使用されます。これには多くの次元があります。2 つのベクトルの違いは、主にコサイン類似度を比較することによって測定します。もちろん、テキストの比較に限定されず、他の比較も可能です。

アルゴリズムモデルなので、分子とは何かを考慮する必要があります。分母は何ですか?左側の 4 つの統計モデルをもう一度見てみましょう。その結果にはすべて 1 つの特性があり、それは 0 から 1 の間の数値です。分子がどのように構成されているか想像してみましょう。分母はどのように構成されますか?

先ほどお話しした技術的な背景に戻りましょう。私たちがテストしているアルゴリズムのアプリケーションは、実はクロスドメインです。最近よく使われる新しい用語を使うと、クロスボーダーです。1つは自然言語処理、もう1つは地理位置情報サービスです。これは、この2つの分野の境界を越える点で、一般的なアルゴリズムのテストとは異なります。国境を越えた物事は一般的に難しく、私たちの通常のテストとはかなり異なる可能性があることは誰もが知っています。

最初に、ユーザーから住所を取得します。これは、テストの初期データとして考えることができます。住所には 2 つの部分があります。最初の住所は発送先住所で、2 番目は受取先住所です。機能テストの観点から、住所を逆にして、受取先住所を発送先住所として使用することができます。これにより、テストの範囲を広げることができます。次のステップは、ジオコーディングの概念です。LBS テスト機能を知っていれば、ジオコーディングの概念も知っているはずです。1 つはフォワード ジオコーディングで、もう 1 つはリバース ジオコーディングです。フォワード ジオコーディングとは、住所、番地を指定して、経度と緯度の座標を生成することです。もう 1 つは、経度と緯度の座標と最も近い住所を指定することです。これら 2 つをジオコーディングとして計算します。次に、対応する座標を取得します。座標に基づいて、距離を計算できます。距離は、2 点間の距離を計算するという最も簡単な方法でも計算できることを知っておく必要があります。私たちもこの方法を使用します。比較的言えば、このモデルは比較的単純です。

ただし、変換後の座標が正確かどうか、または元の住所変換に問題があるかどうかを測定する必要があります。住所変換が悪いと差が出てしまい、距離は数千メートル、場合によっては十数キロメートルにも達します。そのため、距離を変換する際に閾値を計算し、この閾値より低ければ許容されます。

続けて、正しく変換されたアドレスの数、つまり、正しく変換されたアドレスの数をカウントします。これは先ほど述べた分母です。また、フィルタリングも実行します。つまり、一致範囲内で誤って変換されたアドレスの数を計算します。なぜなら、私たちが始めた当初、JDデリバリーは全国でサポートされていませんでした。現在は全国でサポートされています。当時は北京や上海など一部の地域でしかサポートされていなかったため、範囲を超えてサポートされなくなるため、この部分のデータを除外する必要があります。最後に、このデータをもう一度見てみましょう。リコール率を使用して、アドレス変換にどのくらい問題があるかを確認します。これが、アルゴリズム モデルを確立するプロセスです。

アルゴリズム テストは、多くの場合、機能テストとは異なります。機能テストでは、注文データ、一部の販売者データ、その他のデータなどの独自に作成したデータを使用するか、開発中に提供されたプロトタイプのデータを使用します。ただし、アルゴリズムのテストはオンラインの履歴データを使用して行われることが多いので、テストデータの取得と抽出という 3 番目の部分について説明します。

この PPT は、誰にとってもあまり分かりやすくありません。最初のフレームは「履歴データ」、左側は「運送状データ」、中央のフレームは「ミニプログラム ログ データ」、最後の部分は配達員の PDA ログです。配送送り状データがあるので、送り状データ内の有効な住所をすべて取り出します。先ほど言ったように、送り状内には 2 つの住所があり、1 つは配送先住所、もう 1 つは集荷先住所です。すでに配送済みなので、住所は有効である必要があります。もちろん、このデータは当社のミニ プログラムには含まれていません。これは JD.com の元の履歴データです。次に、短期間内に同一ユーザーのアドレス変更行動を収集する PDA 部分について説明します。同じ期間内でもなぜ短い時間と言われているのでしょうか？ユーザーが入力時に間違った住所を入力した可能性があります。誰もが考えられる状況の 1 つは、元々は自宅住所だったが、実際には会社の住所を入力したかったため、入力後に直接変更したというものです。時間間隔は短くなります。たとえば、1 時間または 2 時間以内に住所が変更されるなど、時間間隔を設定します。

また、変更動作は、以前のアドレスが間違って入力されたことを意味している可能性があり、これを入力データとして扱います。最後の部分は配達員のPDAログデータです。配達中の緯度経度座標位置もあります。この経度緯度座標をユーザーの入力として使用します。配達員が荷物を受け取るときにも異常なデータがあることを再度強調する必要があります。たとえば、ユーザーが間違った注文をし、住所Aに送るべきなのに住所Bに送られた場合、配達員は住所Bで受け取るように呼び出されます。このとき、PDAに変更記録があります。配達員が荷物を配達するときにも同様の動作が発生します。変更記録を入力データとして使用します。

私たちの実践では、ユーザーの住所データを取得するのは比較的複雑です。次に、新しい住所を変換し、前のSの住所をセグメント化するなど、途中で遭遇する新しい問題を検討します。これは、実際には私たちがよく使用する探索的テストと非常によく似ています。探索的テストは、元のプロジェクトに基づいて潜在的な問題があるかどうかを調べることだと思われるかもしれません。多くの場合、最初は、私たちのテストが関与する前に、以前のユーザーから報告された問題に基づいて開発していくつかの問題を見つけ、それらを1つずつ解決するためです。これは比較的非効率的であり、エクスペリエンスも特に良いものではありません。したがって、最も重要な点は、新しい住所を処理することです。ご想像のとおり、新しい住所には実際には 2 つのソースがあります。最初のソースは、新しい配達エリアです。私の街が以前は JD.com のドアツードアのピックアップをサポートしていなかったが、今はサポートしている場合、これは新しい配達エリアに属します。もう一つ、より長くて複雑な状況があります。配達エリアはサポートされていますが、新しい住所が追加されました。たとえば、私が住んでいる北京市朝陽区はサポートされていますが、ここに新しいコミュニティが構築され、コミュニティが新しくなりました。これは後者の状況に属します。この問題を解決する方法を考えることができます。

これが今回の議論の核心となる内容で、新しい座標を生成する状況です。実際にこの極座標を使ってこの問題を解決します。学校で学んだ極座標の概念を覚えているかもしれません。これは従来の直交座標とは異なります。1 つの座標は距離を表し、もう 1 つは角度を表します。すべてのユーザーのアドレスをクラスタ化します。クラスタリング後、クラスタの粒子を円の中心として使用します。二重ループを使用して新しいアドレスを生成し、それをフィルタリングして、これらのアドレスを使用して配信可能なアドレスを取得します。生成された逆アドレスは、交差点やバス停など、配信できない場合があるため、これらをフィルタリングして重複排除を行う必要があります。たとえば、半径数キロメートル以内のコミュニティは重複排除されます。住宅地をテストする場合、各建物まで正確に調べます。部屋や階まで正確に調べる必要はありません。これらは実際には住所と同じだからです。

これは、私たちが話しているより重要な部分であり、アルゴリズム テストの実行プロセスです。まず、履歴データを取得し、履歴の住所と座標を取り出し、ジオコーディングを実行し、ジオコーディングに基づいて座標のクラスタリングを計算し、最後に重複を効果的に削除します。重複を削除した後、逆ジオコーディング計算を実行して新しい座標を生成します。厳密に言えば、青い部分は、データを作成するという他のテストの準備段階に属しますが、私たちのデータは実際のデータに基づいて生成されています。右半分を見てみましょう。これは実際にテストを実行するプロセスです。この住所を単語の分割として使用し、名前や電話番号を追加するなど、ノイズや冗長な情報を追加します。次に、住所認識および変換インターフェイスを呼び出して期待値を比較し、期待値に基づいてジオコードを生成して、距離を比較します。距離がしきい値より大きい場合は問題があります。しきい値より小さい場合は問題はありません。これがテストプロセス全体の実行です。

中間のプロセスに焦点を当てて、たとえばクラスタリングについてお話します。テスト方法について少しでもご存知であれば、たとえば最も一般的なクラスタリングは平均クラスタリングですが、データ量が比較的多いため平均クラスタリングは使用しないことをご存じでしょう。ビジネス特性を考慮して、JD 配送ステーションには経度と緯度の座標があり、これを初期クラスター ポイントとして使用します。次に、この半径内の座標に基づいてクラスターが描画されます。座標がクラスター内のデータ量要件を満たさない場合は、2 つの配信ステーション アドレスが結合されます。要件が満たされた場合、たとえば、クラスターには 10,000 個の座標点が必要ですが、10,000 を超えると終了し、クラスタリングは終了します。次に、クラスターの要素を大きい順に並べ替えて最初の N 個の値を取得し、最後に粒子に応じて極座標を生成します。これがクラスタリング プロセスです。

アドレス変換アルゴリズムはアルゴリズムテストなので、欠陥リストに似たコンテンツをどのように提供すればよいでしょうか?機能テストを行うと、手動テストでも自動テストでも、テストを1回行うとバグが発生すると思います。欠陥管理システムについて説明しましたが、アルゴリズムテストは結局数字に過ぎないかもしれません。たとえば、リコール率が80％または90％であっても、欠陥はありません。一般的に言えば、製品、開発、テスト自体はあまり好きではありません。欠陥リストに似た機能を提供するにはどうすればよいでしょうか。どのように行うか見てみましょう。これらの履歴レコードに最も頻繁に出現する最初の N 個の座標に対応するアドレスを取得し、次に距離が最大となる最初の M 個を取得します。これらの最初の M 個の座標はしきい値よりも大きくなければなりません。次に、最初の N 個の中から最初の M 個のアドレスを選択します。これは TOP N 問題に相当します。エンジニアと確認します。問題がある場合は、不具合システムに不具合として投稿するか、フォームを添付したメールを直接送信します。不具合の数が多いため、1 回のテストで数百の不具合が見つかる場合があります。その後、開発チームに提供します。開発チームは不具合リストをチェックして、プログラムの問題なのか、データの問題なのか、他の構成によって引き起こされた問題なのかを確認します。これは、単にリコール率の合格または不合格を示すよりも優れており、より説得力があります。

入力パラメータを生成する方法という別の質問を見てみましょう。背景はインターフェースです。アドレスを入力して、S1 のアドレスを SN にフィードバックします。ノイズ ポイントを追加するとどうなるでしょうか?これが私たちの仕事です。私の住所が北京市豊台区范陽路XX号なのに、なぜここに行くのでしょうか?ここには落とし穴がありますが、それについては後で説明します。単語分割をしてみましょう。北京市/豊台区/ファンヤン路。私の姓はファンなので、名前を追加できます。すべて黄色で、ファンヤンロード、ファンユの後の番号と携帯電話番号を追加します。これは、ユーザーの実際の配送先住所または集荷先住所をシミュレートします。すべてファンであるため、システムは判断できますが、意味は異なり、1つは通りで、もう1つは姓です。これにより、一種のテストノイズが追加されます。位置が逆になっている別の状況もあります。携帯電話番号が名前の直後に入力され、番地が最後に入力されています。これは、ログでもこの状況が見られ、順序が異なり、規制されているためです。順序を逆にすると、特定のノイズ ポイントも生成されます。

ノイズポイントの最後の部分は、オフィスビルや住宅街に相当します。これらの特定の住所を住宅街の建物番号に置き換えます。ユーザーは、小包を送るときにこの方法を使用することがよくあります。実際には同じ住所ですが、表現が異なり、最終的にこの形式で置き換えられます。黄色の部分は追加されたノイズ ポイントに相当することがわかります。これにより、変換率テストの範囲が広がり、変換アルゴリズムの潜在的な問題をより適切に発見できるようになります。実際、私たちが行っているのは、通りからいくつかの姓を抽出し、その姓に基づいていくつかの名前をランダムに生成することです。

テスト実行プロセスを高速化するにはどうすればよいでしょうか?この目的のために、いくつかの並列計算を使用しました。並列計算を使用した理由は他にもあります。ジオコーディングや逆ジオコーディングなどの操作には時間がかかります。住所の逆ジオコーディングには数百ミリ秒かかり、累積時間が多くなるため、並列計算を使用して履歴データを読み取ります。不完全な情報はキャッシュに配置されます。住所は重複している可能性があります。キャッシュがある場合は、インターフェイスを呼び出す必要はなく、キャッシュから直接データを取得し、データベースやその他の場所に置くことができます。最後に、必要な結果を得るためにリコール率を計算し、実行を高速化できます。デバッグプロセス中は、1つまたは2つの項目のみを実行する必要があります。実際の操作では、並列計算で実行されます。

最後に、アルゴリズム テストの方法論をご紹介します。これは私たちのチームの理解です。一般的に、アルゴリズム テストでは、まずアルゴリズム テスト モデルを確立する必要があります。たとえば、リコール率の計算を使用します。リコール率が適切でない場合もあるため、コサイン類似度を使用する必要があります。 2 番目の部分では、実際の有効なデータである履歴データを取得します。これを回帰テストに使用すると、アルゴリズムを使用した場合と使用しない場合の状況の前後の比較を反映できます。 3 番目の部分はアルゴリズム関連のインターフェースですが、一部のアルゴリズムは他の周辺インターフェースを呼び出す場合があり、上流インターフェースと下流インターフェースの両方が存在する場合もあるため、誰もがこの側面を考慮する必要があります。最後の部分は、テスト プロセスの改善です。先ほどお話ししたのは、新しい座標を生成する方法ですが、これは改善プロセスの 1 つです。これもイノベーションです。もう 1 つはノイズ ポイントを増やす方法ですが、これらはすべてテスト プロセスの改善に関係しています。

この部分では、導入について説明します。多くの企業がこのようなアルゴリズムテストに取り組み始めている、または徐々に取り組みたいと考えていると思います。アルゴリズムテストにはどのような基礎が必要ですか?簡単にまとめました。まず、数学的な基礎を身につけておく必要があります。この場合に関係する極座標、距離などはすべて数学的な手法です。アルゴリズムの開発を必ずしも理解している必要はありません。これは純粋なブラックコアですが、独自のアルゴリズムを理解する必要があります。つまり、アルゴリズムモデルを確立し、リコール率を計算し、分母と分子をどのように取るかです。これらはすべて考慮する必要があることです。 3 番目の部分は、自動化されたインターフェース テストです。インターフェースは比較的高速で、基本的に UI を必要としないため、多くのチームがこの機能を備えていると思います。実際のテストとデータ取得は、インターフェースを通じてトリガーされます。 4 番目の部分は並列コンピューティング機能です。テスト速度を上げるには、マルチスレッド、マルチプロセス、分散コンピューティング機能が必要になる場合があります。オンラインでリリースされるのを待っている開発作業がたくさんあるため、1 日でテストが完了しなかったとは言えません。もう 1 つは、データ マイニング機能、つまり、テスト対象のデータをどこから取得し、どのようなデータに変換する必要があるかということです。これが、私が知る必要があることです。最後の部分は、すべてのテストが習得する必要があるものであり、私が個人的に考えるビジネス シナリオです。ビジネス シナリオによってテストの焦点は異なり、使用するアルゴリズム モデルや結果に違いが生じます。上記の点は、アルゴリズム テストがすべての人に期待することの一部です。

最後に、将来を見据えたお話です。現在はオフラインテストを行っているため、将来的にはオンラインテスト環境、つまり完全にオンライン化して、CI/CDやデータ統合手法を活用していく予定です。これが完了すれば、運用期間中に地域外テストの準備を進めます。というのも、JDのデリバリーは基本的に今全国に対応していますが、地域外の状況が発生するからです。地域外というのは、配信に問題があるということです。もともと非常に近かったのに、数キロ離れた拠点に配信されてしまい、運用効率の低下につながります。 JD.comのサードパーティアドレス変換のテストを実施し、それをピックアップアドレスとして使用します。 JD Logistics も多くの商店と接触しており、それらの商店の住所は実際にはサードパーティの住所だからです。

最後の2つの部分は中国本土以外の部分、つまり海外の住所です。JD Logisticsは国際業務を多く行っており、海外の住所は国内の住所とは異なり、その多くは英語であり、分子システムも当社とは異なります。今後、この領域に介入する必要があります。最後に、現在、多くのものがまだ手動で識別されているため、手動識別の割合を減らす予定です。 計算しきい値が非常に大きい場合もありますが、実際には状況は正常である可能性があります。 たとえば、川にいくつかの橋がある川があります。 川を渡ってアイテムを拾うには、橋を渡らなければなりませんが、橋を渡る距離は長くなります。 このとき、手動識別が必要です。 今後は、他の手段を使用して、手動識別の難易度を軽減します。

上記は私があなたと共有したものです。