Matching algorithms

[WolfgangFahl]

When we have different sources for countries, regions and cities we need to match the entries.

Fortunately the lat/lang is readily available to calculate the distance of places e.g. by haversine.

• https://stackoverflow.com/questions/25767596/vectorised-haversine-formula-with-a-pandas-dataframe
• https://stackoverflow.com/questions/4913349/haversine-formula-in-python-bearing-and-distance-between-two-gps-points

[somnathrakshit]

Edit distance: https://stackoverflow.com/questions/2460177/edit-distance-in-python
Cosine similarity in Pandas: https://stackoverflow.com/questions/25736861/python-pandas-finding-cosine-similarity-of-two-columns

[MusaabKh]

This might be helpful: https://github.com/roy-ht/editdistance

[somnathrakshit]

Fixed-radius near neighbors: https://en.wikipedia.org/wiki/Fixed-radius_near_neighbors

[MusaabKh]

More about KD-Trees implementation using dataframes and scipy: https://stackoverflow.com/questions/43020919/scipy-how-to-convert-kd-tree-distance-from-query-to-kilometers-python-pandas

[somnathrakshit]

GrisPy: https://grispy.readthedocs.io/en/latest/

[MusaabKh]

Run with BallTree the result is for the query of all of the trees in the radius of 500Kms sorted by distance.

[WolfgangFahl]

Great. Does this fix #43 and it's testcase?

[MusaabKh]

This has a bit of variation to #43 but can be used. I will work on a test case for the scenario

[WolfgangFahl]

It would be great to see the source code - since it's probably only a few lines you might want to integrate the source code and/or post it here. A git pull shows no changes to the sources of geograpy3

[MusaabKh]

I could not push unfortunately as I am not invited to the project yet.
Here is the test case:

    def testMatchingv2(self):
        locator = Locator()
        if not locator.db_has_data():
            locator.populate_db()
        countryList = CountryList.fromErdem()
        jsonLoad = json.loads(countryList.toJSON())
        countries = pd.DataFrame(jsonLoad['countries'])
        countries['lat'] = pd.to_numeric(countries['lat'], downcast="float")
        countries['lon'] = pd.to_numeric(countries['lon'], downcast="float")
        countries['rad_lat'] = countries['lat'].apply(lambda x: radians(x))
        countries['rad_lon'] = countries['lon'].apply(lambda x: radians(x))
        coordinatesrad = np.array(list(zip(countries['rad_lat'], countries['rad_lon'])))
        balltree = BallTree(coordinatesrad, metric='haversine')
        test_radius = 500  # Kms
        test_NN= 5
        cl2 = CountryList.from_sqlDb(locator.sqlDB)
        for country in cl2.countries:
            testpoint = np.array([(radians(country.lat), radians(country.lon))])
            name = country.name
            results = Location.getClosestLocations(name, 2, countries, balltree,coordinatesrad, 'number')

            if results is not None:
                print(results.Country.values[-1], " is closest to ", name)
            else:
                print(country.name, 'not found')

Here is the function for closest calculation:

     @classmethod
    def getClosestLocations(cls, name, test_parameter, locations, balltree, coordinatesrad, testType='distance'):
        """
        Gives the closest locations to the given location based on Nearest Neighbours or radius
        Args:
            name(str): Country Name for Query
            test_parameter(int): Radius if testType is distance and number of neighbours if testType is Number
            locations(DataFrame): Dataframe used to create ball tree
            balltree(sklearn.balltree): Balltree object
            coordinatesrad(np.array): Numpy array used to create balltree
            testType(str): Search in radius if "distance", search as Nearest Neighbours if "number"
        Returns:
            result(DataFrame): DataFrame with the nearest locations sorted by distance

        """
        earth_radius = 6371000  # meters in earth
        result = None
        index = locations.index[locations['name'] == name].to_list()
        for i in index:
            if testType == 'distance':
                test_radius = 1000 * test_parameter
                listoflocations = balltree.query_radius([coordinatesrad[i]], r=test_radius / earth_radius,
                                                        return_distance=True)
                result = pd.DataFrame(np.array([listoflocations[0][0], listoflocations[1][0]]).T,
                                      columns=['Country', 'Distance'])
            elif testType == 'number':
                listoflocations = balltree.query([coordinatesrad[i]], k=test_parameter, return_distance=True)
                result = pd.DataFrame(np.array([listoflocations[1][0], listoflocations[0][0]]).T,
                                      columns=['Country', 'Distance'])

            result['Country'] = result['Country'].apply(lambda x: locations['name'].loc[int(x)])
            result['Distance'] = result['Distance'] * earth_radius / 1000
            result = result.sort_values(by='Distance')
        return result

Here is the sample of the output of the test case:

[somnathrakshit]

@MusaabKh just invited you to the project.