「Pythonで座標からサイトの距離行列を計算する」

『Pythonを使用して座標からサイト間の距離行列を計算する』

地理座標から任意の２つのサイト間の距離を簡単に推定し、効果的にルーティング問題を解決するためのステップとして

👁️ これは、プロジェクト「An Intelligent Decision Support System for Tourism in Python」をカバーするシリーズの記事です。全体のプロジェクトの概要を把握するために、ぜひチェックしてください。
距離行列の作成にのみ興味がある場合は、この記事だけで十分で、自己完結しています。
距離行列を実践的な問題に適用したい場合は、このシリーズが役立つでしょう。

この記事では、スプリント 3で終わった場所から旅を続けます。ここ、スプリント 4では、モデリングから一時的に外れて、ジオスペーシャル機能を備えたクラスを開発します。このクラスは、一般的な巡回セールスマン問題、つまり、距離データがすぐに利用できない場合でも、任意のサイトの問題を解決する際に非常に便利です。前のスプリントでこの「要件」を述べましたが、このスプリントではそれを満たすためのサブシステムを構築します。

目次

1. 前のスプリントのまとめ

2. 入力データの読み込み

3. 位置データから距離行列の作成

• 3.1. 余分な距離を移動するべきか？
• 3.2. geopyを使用したジオロケーションユーティリティ
• 3.3. ポイントに移動する
• 3.4. 座標から距離行列へ

4. 締めくくり！（クラスの内部）

• 4.1. GeoAnalyzerクラスの設計
• 4.2. クラスの使用デモ

5. 結論（または次のスプリントの計画）

1. 前のスプリントのまとめ

前の記事、すなわちスプリント 3では、距離行列として各可能なサイトの距離を持つリストのために、巡回セールスマン問題（TSP）を解決できることを概念実証しました。この距離行列は、データ処理ではなくモデル構築に焦点を当てたため与えられました。ただし、モデルが完成した後、任意のセットのサイトのために一般的なTSP問題を解決する方法が必要であることを述べました。この一般化は、本当に便利なMVPを作成するために必要です。そのため、この記事では、関心のあるサイトの地理座標から距離行列を自動的に取得する方法について説明します。

そのため、私たちの新しい基本的な入力は、訪れたいサイトの地理座標だけでより簡単になります：

• リトリーバル オーグメンテッド ジェネレーション（RAG）推論エンジンは、CPU上でLangChainを使用しています
• 「インド、人工知能を利用し言語の壁を解消へと向かう」
• データエンジニアリング：初心者のためのフォーミュラ1にインスパイアされたガイド

そして、出力はTSPモデルの入力として使用したデータフレームであり、入力サイトの距離行列です：

一貫性のために、これまで考慮していたパリのサイトを使用します。次の記事では、この機能を旅行セールスマン問題の最適化モデルと統合し、より汎用性のあるMVPに到達します。

🎯 最終目標を念頭に置いて

このことを行う理由を簡単に振り返りましょう。解決しようとしている元の現実の問題は、一般的な観光客のための最適な旅行計画を作成するという問題です。そのために、彼女の「個人」データ（好み、予算など）と旅行「環境」データ（距離、価格、交通手段など）の両方を考慮します。

この現実の問題は複雑すぎると判断されたため、解決策のデザインをスタートさせるために、本質的なバージョンに簡略化しました。この「本質的問題」は、旅行セールスマン問題（TSP）と呼ばれ、都市の観光客の「興味のある場所」を訪れるポイントとして考えました。この記事で開発した機能により、TTPの一般的な解決策に、TSPがソリューションの中心となるより一歩近づいています。

2. 入力データの読み込み

今回の基本的な入力は、旅行で訪れたい場所の地理的座標です。ホテルは「興味のある場所」ではなく、複数日の旅行で眠るために訪れる場所なので、異なる種類のサイトとして扱います。ホテルの選択は異なる旅行や状況では異なるかもしれませんが、都市の興味のある場所は多くの旅行ガイドが同意するほぼ「一定の」場所です。この区別の有用性は、より高度な応用を探索する準備ができたときにより明確になります。

したがって、ホテルの座標をlocation_hotel.csvというCSVファイルに保存し、都市の「興味のある場所」に関する座標を別個のCSVファイルsites_coordinates.csvに保存しました。両方のCSVは同じ構造を持っているため、それらを読み込んで1つのデータフレームに結合します：

import pandas as pd print(f"バージョン pandas: {pd.__version__}") DATA_FOLDER = ("https://raw.githubusercontent.com/carlosjuribe/" "traveling-tourist-problem/main/data") FILE_LOCATION_HOTEL = "location_hotel.csv" FILE_LOCATION_SITES = "sites_coordinates.csv" df_sites = pd.concat([ pd.read_csv(f"{DATA_FOLDER}/{FILE_LOCATION_SITES}", index_col='site'), pd.read_csv(f"{DATA_FOLDER}/{FILE_LOCATION_HOTEL}", index_col='site')]) display(df_sites)

ℹ️ 自分の場所データを素早く準備する方法

自分のサイトリストを使用してこの記事に従いたい場合は、座標を取得するための私の手順を再現する必要があります：

1. Google Mapsにアクセスし、リスト内の各サイトを検索します。

2. 各サイトは地図上のポイントとして表示されます。各ポイントを右クリックします。表示される最初の要素は、クリックしたポイントの緯度と経度のペアです。

3. それらの数値をクリックし、クリップボードに保存されるため、そのポイントの名前と一緒にファイルに貼り付ける準備ができます。

4. すべてのサイトに対して1から3を繰り返し、sites_coordinates.csvに相当するファイルが作成されます。

このプロセスは少数のサイトに対しては問題ありませんが、数百や数十のサイトの場合、非常に手間がかかります。[将来の記事]では、この手作業を自動化する方法であるジオロケーションを作成します。

3. 位置データから距離行列を作成する

距離行列を作成するには、どの2つの場所の距離を取得する必要があります。簡単なようですが、実際には「距離」とは文脈によって異なります。Googleマップなどのマッピングアプリが報告する数値は、道路ネットワーク、橋、公園などを考慮していることを考慮に入れますか？もしそうなら、徒歩で移動する場合の距離を取得しますか、それとも自動車で移動する場合の距離を取得しますか？それとも単に2点を結ぶ直線の長さだけを考慮しますか？明らかに、選択肢が多く、それぞれの精度も異なります。最初に答える必要があるのは、この特定の問題の文脈と、この段階で「距離」をどのように定義するべきかです。

3.1. 一番良い解を得るために一番良い解となる可能性があるのでしょうか？

正確なデータを使用することに魅力を感じるのは自然なことです。結局、正確性は本質的に価値があることを皆知っているため、より正確なデータを追求しようとする傾向があります。ただし、より正確なデータには、より複雑なコードと依存関係、そしてより多くの開発時間とメンテナンスが必要です。私たちは「アジャイルなアプローチ」を取り続けるので、ベストを敵にすることなく、できるだけシンプルに始め、必要であれば徐々に複雑さを加えていきます。

この場所間の距離を見つけるという状況では、私たちと同じように、アプリキー、資格情報、さらにはクラウドプロバイダのクレジットカード番号が必要なサードパーティのAPIベースのソリューションに直接飛びつくことができます。その方法は有効ですが、しばしば非効率であることに気付くことができます。正確な情報は付加価値をもたらす一方で、追加のコストもかかることを忘れてはいけないからです。

👁️ “無料の正確性”なんてものは存在しない

正確なデータへのアクセスには常に「価格」がかかることを忘れない（これは情報の価値の概念に密接に関係している）ことは、この問題にアジャイルなアプローチを取ることがより効率的な行動方針です。私たちは「必要な精度のレベル」という「単純な仮定」から始め、それらの妥当性を「自分自身の問題のデータ」で検証することで、データの精度を向上させる必要がある場合には、「改善された結果を期待して」（期待される）「価格」を支払うことができることを保証しています。

では、非常にシンプルに始めましょう。私たちは座標を持っています。最初の考え：これらの座標は、地球の半径に比べて非常に小さな地球のパーセル上に広がっているため、緯度をY座標、経度をX座標として、ユークリッド距離（通常の「直線」のことを指す）を計算するだけです。

• 利点：距離の簡単な計算式、新しい依存関係やデータは不要で、場所間の空間的な関係が保たれます。
• 欠点：緯度と経度は無次元の数値なので、問題を解く際に得られる数値は実際の距離ではありません。つまり、最適なツアーを取得できたとしても、移動距離など重要な情報は利用できません。

欠点が利点を上回るため、より複雑なアプローチ（しかし依然としてシンプルなもの）が必要です。 2番目のアイデア：座標を地球上のポイントとして扱い、地球を球体として近似します。球体にはおなじみのユークリッド幾何学はありませんので、この球体のジオメトリーを考慮した「直線」距離を計算するために、非自明な計算式が必要となります。それでは、その式を地球の半径を使用して実装するだけですが、私たちはすでにそれを行ってくれる有名なライブラリに頼ります。

geopyを使用した位置情報ユーティリティ

この記事シリーズが特に地理空間データサイエンスに焦点を当てている場合、球体上のポイント間の「直線」距離を計算するための基本的なオプションである「大円距離」の計算式を説明し、実装するために時間をかけることが価値があるかもしれません。しかし、この記事シリーズは「最適化ベースの観光計画システム」の作成についてであり、地理空間ユーティリティのための独自の式を作り上げる代わりに、重い作業はGeopyに頼ることにします。それによって、解決策に迅速に到達するために焦点を保ちます。

以下のようにAnacondaプロンプトでコマンドを実行してインストールします（または、最初の記事内のconda環境で作成した場合）：

conda install -y -c conda-forge geopy=2.3.0

さて、geopyを使用して2つの場所でデモを行いましょう。

3.3. 目標地点へのアクセス

2つの地点の座標が与えられた場合、geopyのgeodesic関数は地球の表面上でそれらを結ぶ測地線の距離を計算します。幾何学では、測地線とは与えられた計量空間上の点間の最小距離の経路です。我々が馴染みのあるユークリッド空間では、直線が測地線です。球面上では、大円が測地線です。Geopyのgeodesic関数が考慮する下層の「空間」としては、地球の正確な楕円体モデルがあります。

👁 大円は偉大ですが、楕円はさらに優れています

先ほど、地球を単純な近似として球体とみなすと述べました。実際には、地球は球体ではなく、より複雑なジオメトリを持つ楕円体です。今回、geopyによって非ユークリッド幾何学の関数を自分でコーディングする手間が省けるようになったので、大円距離ではなく、より正確な楕円体距離を使った2点間の距離を計算して、地球の近似を改善することができます。同じ行数でより良い地球モデルを実現することができます。これは確かに精度の向上であり、無料の精度なので、なぜ利用しないでしょうか？

以下の関数は、2つの地点間の楕円体距離をメートル単位で計算する関数です：

from geopy.distance import geodesicdef ellipsoidal_distance(p1, p2) -> float:    """各地点がタプル (lat、lon) として表される場合、p1とp2の間の距離（メートル単位）を計算する"""    return geodesic(p1, p2).meters

エッフェル塔とルーヴル間の距離は？

p1 = df_sites.loc['エッフェル塔']p2 = df_sites.loc['ルーヴル']ellipsoidal_distance(p1, p2)  # 出力：3173.119635531859

3173メートル、およそ3.2キロメートルです。Googleマップでは3.5キロメートルと表示されます。計算された距離は「実際の」距離よりも8.6％少ないです。ただし、私たちの足は距離の絶対誤差にしか興味がありません。この場合、推定された距離に比べて追加で330メートル歩く必要があるだけです。観光客が大都市で一日中歩き回ることを想定すると、重要な誤差ではないように思えます。

エッフェル塔とポールト・ド・シュフランの間の距離は？

ellipsoidal_distance(    df_sites.loc['エッフェル塔'],    df_sites.loc['ポールト・ド・シュフラン'])  # 出力：328.3147101635456

328メートル、この場合は350メートルのGoogleマップよりも6％少ないです（わずか22メートル短い）。公式を適用するには悪くはありません。予想通り、点が近いほど、道路がジグザグする可能性や曲がる場所が少なくなるため、楕円体モデルによる誤差も低くなります。現状の目的に十分なように見えます。

これで、すべての場所の組み合わせにこの関数を適用し、TSPモデルが必要とする距離行列を取得する必要があります。

3.4. 座標から距離行列へ

これは簡単な部分であり、すべてのサイトを2回ループして、各ペア間の距離を計算して保存するだけです。以下の関数がそれを行います。距離指標はオプション引数として渡され、デフォルトでは前述の楕円体距離になります。将来的により良い距離指標を受け取るための柔軟性を持たせています。

def compute_distance_matrix(df_sites, dist_metric=ellipsoidal_distance):    """ データフレーム内のNつの場所からN x Nの距離行列を作成する関数
    Nつの場所を持つデータフレームで、緯度の列と経度の列を持っている必要があります """    
    df_dist_matrix = pd.DataFrame(index=df_sites.index,
                                  columns=df_sites.index)
                                  
    for orig, orig_loc in df_sites.iterrows():  # それぞれの出発地点について
        for dest, dest_loc in df_sites.iterrows():  # それぞれの目的地について
            df_dist_matrix.at[orig, dest] = dist_metric(orig_loc, dest_loc)
    
    return df_dist_matrix

df_distances = compute_distance_matrix(df_sites)
display(df_distances)

以上が結果です！予想通り、行列の対角線はゼロであり、行列は対称です。出力データフレームのインデックスと列には入力場所の名前が含まれています。

機能のデモンストレーションは終わりです。これからは、この関数の使用を容易にするために、便利な方法でこの機能をクラス内にまとめていきましょう。また、前のスプリントで作成したTSPの最適化モデルとの統合もより簡単に行えるようにするために、クラス内に格納します。

4. 全体を包み込んで！（クラス内部）

4.1 GeoAnalyzerクラスの設計

ルーティング問題で発生する可能性のある地理空間ユーティリティに特化した新しいクラスGeoAnalyzerを作成しましょう。そのため、関数compute_distance_matrixは自然な形でメソッドに収まります。このクラスの主なパーツは次の通りです。

• 場所の位置が記録されたデータフレームとしての属性_df_locations。
• 純粋関数ellipsoidal_distance。
• メソッドget_distance_matrixは、前の関数compute_distance_matrixと同等であり、距離を計算するためにインスタンス属性_df_locationsを使用します。

ユーザーは分析のどの時点でも場所のリストに新しい場所を追加したい場合があるため、メソッドadd_locationsを含め、これに対応するデータフレームを受け入れて既存のものに追加するようにします。

以下に、GeoAnalyzerの定義を示します。ここでは言及されていない他の便利なメソッドやプロパティもあります。

from typing import Tuple
import pandas as pd
from geopy.distance import geodesic

class GeoAnalyzer:
    """地理位置情報と処理のためのユーティリティ"""

    _GeoPoint = Tuple[float, float]

    def __init__(self):
        """メソッド`add_locations`を使用して一部の場所を内部に保存し、
        geoユーティリティを使用できるようにする"""
        self._df_locations = pd.DataFrame(columns=['latitude', 'longitude'])

    #####################   距離   #####################

    @staticmethod
    def ellipsoidal_distance(point1: _GeoPoint, point2: _GeoPoint) -> float:
        """point1とpoint2の楕円体距離（メートル単位）を計算します。
        それぞれの点はタプル（緯度、経度）で表されます"""
        return geodesic(point1, point2).meters

    #########################################################

    @property
    def locations(self):
        return self._df_locations

    @property
    def num_locations(self):
        return len(self._df_locations)

    def add_locations(self, df_locations: pd.DataFrame):
        """分析に必要な地理的座標のデータ。
        パラメータ
        ----------
        df_locations : pd.DataFrame
            最初の列が 'latitude' という名前で、2番目の列が 'longitude' という名前の
            地理座標を持つデータフレーム
        """
        df_updated = pd.concat([self._df_locations, df_locations.copy()])
        # ユーザーが場所を繰り返し追加した場合に備えて重複を削除する
        self._df_locations = df_updated.drop_duplicates()

    def get_distance_matrix(self) -> pd.DataFrame:
        """与えられた場所データに基づいて距離行列をデータフレームとして計算します"""
        df_locations = self._df_locations
        dist_metric = self.ellipsoidal_distance  # 利用可能な距離のみ
        # マトリックスdfの初期化
        df_dist_matrix = pd.DataFrame(index=df_locations.index,
                                      columns=df_locations.index)
        # それぞれの出発地点と目的地のペアについて、距離を計算する
        for orig, orig_loc in df_locations.iterrows():
            for dest, dest_loc in df_locations.iterrows():
                df_dist_matrix.at[orig, dest] = dist_metric(orig_loc,
                                                           dest_loc)
        # メタデータを少し追加しても問題ない
        df_dist_matrix.distance_metric = dist_metric.__name__
        return df_dist_matrix

    def __repr__(self):
        """現在考慮されている場所の数を表示する"""
        return f"{self.__class__.__name__}(n_locs={self.num_locations})"

4.2. クラスの使用デモ

さて、クラスの主な機能を少し探ってみましょう。まずは、インスタンスを作成し、パリの興味深い場所を追加します：

geo_analyzer = GeoAnalyzer()geo_analyzer.add_locations(df_sites)

この時点で、インスタンスの表現をチェックしてみると、私たちが提供した場所の数が9であることがわかります。これに関する詳細は、locations属性で確認できます：

display(geo_analyzer)display(geo_analyzer.locations)

もちろん、このオブジェクトから距離行列を抽出することもできます。すでに馴染みのある操作ですね：

df_distances = geo_analyzer.get_distance_matrix()display(df_distances)

最後に、これらの値がどこから取得されているのか気になる場合は、データフレーム自体から確認することができます：

print(f"使用される距離メトリック：{df_distances.distance_metric}")# [Out]: 使用される距離メトリック：ellipsoidal_distance

より多くの距離メトリックが利用可能な場合は、これがより価値ある情報になるでしょう。これについては、将来のスプリントで見ていくことになります。

5. 結論（または次のスプリントの計画）

私たちの作業の最終結果は、GeoAnalyzerという便利なメソッドを備えたクラスです。このクラスは、旅行セールスマン問題を任意の場所のセットに一般化するのに役立ちます。この一般化は、次のスプリントで具体的な目標となります。このスプリントでは、被訪問地の地理座標を入力として受け取り、モデルの構築手順を隠蔽するエスティメータのようなクラスを作成します。GeoAnalyzerクラスは、この新しいエスティメータクラスの重要なコンポーネントとなり、私たちが構築したTSP最適化モデルの真の一般化を可能にする役割を果たします。この新しいエスティメータクラスは、GeoAnalyzerの柔軟性とTSPモデルの汎用性を組み合わせたものであり、私たちが解決を目指すより一般的な「旅行観光問題」のコアとなるでしょう。本物の取り組みに進むため、次のスプリントに進んでください！

私の活動をフォローしたり、質問をしたり、フィードバックをくれたり、LinkedInで連絡を取ったりしても構いません。読んでくださってありがとうございました！📈😊

We will continue to update VoAGI; if you have any questions or suggestions, please contact us!