# 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

### Category counts
- 大多數 category 出現的次數都很少，然而事實上一個完整的 category 應該要重複出現很多次，這代表了 category 的屬性應該可以進一步整合 (100 class $\rightarrow$ 10 class)。

### POI
#### Occurence

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

#### Distance

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

#### Location

- 相同 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 個資料的相似程度。
-