---
# System prepended metadata

title: 帳號分析 Minimum Edit Distance
tags: [Progress Report]

---

# 帳號分析 Minimum Edit Distance

### 資料來源

`nickname_email_alike.csv`
- 只取英文資料

### 前處理
- 樣本數取 [30000:50000]
- 過濾掉空格、重複字
- 將資料轉成np.array以利做運算加速
- 剩餘3882筆nickname

### 實作萊文斯坦距離
- 原理
    - ![](https://i.imgur.com/wtmyde7.png =300x200)
    - ![](https://i.imgur.com/kgyBGrR.png =300x250)

- 將3882筆資料轉成 3882*3882的矩陣
- 做矩陣運算讓字跟字之間都有一個最短距離分數

### 實驗結果
- 將得到的分數做排序，找出每個字對應最像的5個字
- 產出Dataframe
- 以之前Hierarchical Clustering分不出來的字為例：

![](https://i.imgur.com/k6JBRtk.png)

![](https://i.imgur.com/5TalHVz.png)

![](https://i.imgur.com/Okwmdsa.png)

![](https://i.imgur.com/YYEt67i.png)

![](https://i.imgur.com/FK6gtkB.png)

![](https://i.imgur.com/TewoWdP.png)



- 只有數字不同或是字符順序不同透過這演算法還是能判斷相似

### 運算時間
3882*3882矩陣
![](https://i.imgur.com/DtQQLiu.png)
 

### 結論
- 因為演算法很單純，所以找出相似詞的準確率非常高
- 目前算分數是輕鬆的事，但對於怎麼有效的拿這些分數去做分群，還不太清楚
- 運算效率的部分會比較麻煩，這次是有用jit加速，但要跑11萬個詞，11萬*11萬的矩陣memory一下就爆了


###### tags: `Progress Report`