---
# System prepended metadata

title: Foursquare - Location Matching
tags: [AI, Project, Kaggle]

---

# Foursquare - Location Matching
###### tags: `Project` `Kaggle` `AI`
## Introduction
### Brief
POI 的 big data 包含了豐富的真實訊息，但其中包含了許多的 **noise, duplicate, unstructured information, incomplete / inaccuracy data**，為了呈現高水準的 POI 資訊，machine learning 和人為驗證是最好的選擇。

在這個比賽中，需要做的事是藉由==預測哪些 place entries 代表相同的 POI==，來將 POI 匹配到一起，以確定在哪個地方開設新商店或企業能夠使得收益最大。

### Dataset
- **train.csv**
    - id
    - name
    - latitude
    - longitude
    - address
    - city
    - state
    - zip
    - country
    - url
    - phone
    - categories
    - point_of_interest
- **pairs.csv**
    - id_1, name_1, latitude_1, longitude_1, address_1, city_1, state_1, zip_1, country_1, url_1, phone_1, categories_1
    - id_2, name_2, latitude_2, longitude_2, address_2, city_2, state_2, zip_2, country_2, url_2, phone_2, categories_2
- **test.csv**
    - id, name, latitude, longitude, address, city, state, zip, country, url, phone, categories
- **sample_submission.csv**
    - id
    - matches: list of ids
- pairs.csv 是透過匹配 train.csv 中的 point_of_interest 生出來的。

### Q & A
- Q: point_of_interest 是否是永遠正確的？在一些相同 POI 的數據中，經緯度相差得很遠，照理來說這不應該是正確的，相同的 POI 應該要有相似的經緯度
  A: point_of_interest 永遠是正確的，可將它視為正確的 label。但是由於加入了 missing information 和 noise，所以可能有上述情況發生。
- Q: 該競賽是否需要在訓練數據中找到與測試數據匹配的數據？還是只需要在測試數據中尋找匹配的數據？
  A: 訓練數據測試數據並不重疊，只需要在測試數據中找到匹配的就好。
- Q: pairs.csv 是如何創建的？
  A: pairs.csv 中所有的 matching, non-matching 都來自 train.csv 中，它並沒有包含任何額外訊息，並且其中包含的數據遠沒有包括所有可以從 train.csv 中生成的組合，其目的僅是幫助模型訓練，可以依照原樣使用 pairs.csv，或者修改它（刪除、新增），也可以完全不使用它。
- Q: 類別數據是如何產生的？訓練、測試的數據中他們遵循相同的資料分佈嗎？
  A: 類別數據是由使用者自由上傳的，因此他們有 different grain，例如：同樣的地方可能一個分類是"服飾店"，另一個分類則是"大尺碼服飾店"。另外，訓練及測試的分佈是不同的，且在測試集中可能有不存在訓練集中的類別。
  
## Analysis
### Train.csv
| id               | name                    | latitude   | longitude  | address                | city       | state           | zip  | country | url | phone | categories            | point_of_interest |
|------------------|-------------------------|------------|------------|------------------------|------------|-----------------|------|---------|-----|-------|-----------------------|-------------------|
| E_000001272c6c5d | Café Stad Oudenaarde    | 50.859975  | 3.634196   | Abdijstraat            | Nederename | Oost-Vlaanderen | 9700 | BE      |     |       | Bars                  | P_677e840bb6fc7e  |
| E_000002eae2a589 | Carioca Manero          | -22.907225 | -43.178244 |                        |            |                 |      | BR      |     |       | Brazilian Restaurants | P_d82910d8382a83  |
| E_000007f24ebc95 | ร้านตัดผมการาเกด          | 13.780813  | 100.4849   |                        |            |                 |      | TH      |     |       | Salons / Barbershops  | P_b1066599e78477  |
| E_000008a8ba4f48 | Turkcell                | 37.84451   | 27.844202  | Adnan Menderes Bulvarı |            |                 |      | TR      |     |       | Mobile Phone Shops    | P_b2ed86905a4cd3  |
| E_00001d92066153 | Restaurante Casa Cofiño | 43.338196  | -4.326821  |                        | Caviedes   | Cantabria       |      | ES      |     |       | Spanish Restaurants   | P_809a884d4407fb  |
- 總資料量：

### Missing values
![](https://i.imgur.com/fQkuX2V.png)

### Category counts
![](https://i.imgur.com/3IyCePu.png)
![](https://i.imgur.com/utn238U.png)
- 大多數 category 出現的次數都很少，然而事實上一個完整的 category 應該要重複出現很多次，這代表了 category 的屬性應該可以進一步整合 (100 class $\rightarrow$ 10 class)。

### POI
#### Occurence
![](https://i.imgur.com/OQrKxRB.png)
![](https://i.imgur.com/0ODMl4P.png)

- POI 出現的頻率大多都介於 1~2 次。

#### Distance
![](https://i.imgur.com/1k8HBCp.png)

- 相同 POI 之間的距離大多都 < 50 公里。

#### Location
![](https://i.imgur.com/eeRQeIT.png)
![](https://i.imgur.com/Dc4aNB4.png)
![](https://i.imgur.com/raOhTe8.png)
![](https://i.imgur.com/UjGKAtL.png)

- 相同 POI 的 位址除了 country 外，大多都不相同，但造成不相同的原因是有一套標準或是使用者自由上傳還需要驗證。

### Feature selection
- id
- ==name==
- ==latitude==
- ==longitude==
- address
- ==city==
- ==state==
- ==zip==
- ==country==
- url
- phone
- ==categories==
- point_of_interest

## Idea
### Beacause
- category, name 相同字串出現的頻率低 (category, name)
- 相同的 POI 大部分的距離都小於 50 公里 (latitude, longitude)
- 相同的 POI 大部份都在相同的國家 (country)
- 相同的 POI 位置資訊可能由於使用者自行上傳而有干擾 (city, state, zip)

### So
1. KNN 
    - 使用 latitude, longitude 取 nearest neighbor.
2. Decision Tree
    - 由於 name, category, city, state, zip 的 missing value 較少，並且他們的錯誤可能是因為使用者自定義的上傳導致的，因此在 KNN 的基礎上分別計算這 5 個 feature 的相似度 (longest match, levenshtein distance, jaro similarity)，並使用 decision tree 決定輸出。
3. DNN
    - 自行建立 pairs.csv 作為輸入。
    - 利用 transformer 來替代方法 2 的 encoding，並計算 2 個資料的相似程度。
    - ![](https://i.imgur.com/ZJP7Zos.png)

