一個超省錢的內容推送演算法(乞丐版)

【README.md】

Hi 我是栗子君,一枚身在美帝的小程序員。

我工作的公司加上老闆一共有五個人:老闆邁叔,維持著一切事物讓業務不至於垮掉的產品經理田田,顏值擔當吉米,吐槽擔當的我,還有剛剛加入的酷炫小哥DJ。

就像銀魂里的萬事屋,我們經常會接到各種客戶奇奇怪怪的委託,每天都要面對不一樣的技術問題。生活在充滿挑戰的環境里的我決定開通這個專欄,來記錄每一個挑戰,每一次嘗試,每一種解決方案,希望能夠幫到遇到同樣問題的你(圍笑)。

正確打開方式:

【太長不看】--> 沒時間或者沒興趣閱讀全文的話也沒關係,只要看【太長不看】標籤就可以 get到要點。

【參考鏈接】--> 研究問題的時候參考的材料鏈接。

【請講人話】--> 會對一些術語做出盡量通俗的解釋,如果有另外需要解釋的術語請在評論區 留言~我會在文中更新

歡迎轉發!歡迎點贊!轉載請聯繫專欄作者授權。

【序】

憑藉著python大法(python大法好,word, pdf變身html沒煩惱),上周輕鬆導入了500多篇關於健康的科普文章,緊接著又緊鑼密鼓地整了一個前端的demo出來,客戶大大點贊表示你們真是棒棒噠。

沒過幾天,客戶大大又不開心了,原因是他回家一查賬單,發現隨著網路用量的增加,費用也是蹭蹭蹭地水漲船高,達到了五千多刀一個月。為什麼這麼貴呢?最主要是因為美國一個叫HIPAA的法案。

HIPAA全稱是Health Insurance Portability and Accountability Act,目的是為了保護個人健康和醫療信息。這個法案規定了一系列網路安全措施,任何涉及到儲存、讀取和分享個人健康檔案的軟體都必須實行。這樣一來也就催生出一些幫助中小企業保障信息安全的網路服務,我們開發的個人健康檔案管理軟體就使用了這樣的服務,基本上就是在亞馬遜雲服務外面再包裹一層vpn還有加密演算法之類的。具體的價格我不清楚,總之很貴就是了!

順便說一下,美國這樣的法案不少,比如PCI, Payment Card Industry Data Security Standard, 是用來規範信用卡信息安全的。大家做項目的時候要注意一下,被告可是會傾家蕩產的!

【演算法設計】

眼看著就要開始做推送這部分的功能了,客戶大大提出了「省錢」這個要求,我們不得不考慮一個新的推送演算法,能夠盡量少地訪問資料庫。對了,我們還用的是非關係型資料庫,跨表查詢這部分功能真是要多彆扭有多彆扭。

但是好在我們拿到的文章結構比較完備,首先每一篇文章都屬於一個「系列」,「系列」就是話題,比如「心腦血管疾病」和「糖尿病」;其次,一個系列中的文章還有固定的順序,是按照內容由淺入深編號的;再次就是文章還有很多不同的標籤可以用來檢索。

按照原先的設計,只要用戶檔案里有「心臟病」這三個字元,就可以拿來匹配資料庫里的文章,返回所有在標題或者標籤里含有「心臟病」的文章。現在既然匹配單個文章不現實,那麼我么可以利用文章之間的聯繫來匹配「系列」名。一般來說,如果某一用戶有心臟病,應該會對心腦血管疾病的所有文章都比較感興趣。而「系列」名總共就那麼幾個,甚至可以放在前端代碼里進行匹配。匹配好之後再按照系列名檢索資料庫就可以了。

【內容匹配】

那麼怎麼把「心率不齊」,「中風」這樣的癥狀匹配到「心腦血管疾病」這個系列呢?我發現了一個超神的api:Datamuse API。Datamuse根據查詢的單詞返回相關的詞,比如我們查詢"stroke"這個詞,返回的數據是這樣的:

[n{"word":"cerebrovascular accident","score":29468,"tags":["syn","n"]},n{"word":"shot","score":25411,"tags":["syn","n"]},n{"word":"diagonal","score":21050,"tags":["syn","n"]},n{"word":"apoplexy","score":19249,"tags":["syn","n"]},n//...n]n

每一個關聯詞的score表示關聯度,關聯度越高得分越高。

為了保證準確性,我們只用25000分以上的關聯詞,把它們放在一個數組裡,稱為數組A。接下來把所有的系列名放在數組B裡面,然後挨個比較找出那個關聯度最高的系列。

【計算關聯度】

在讀了很多關於自然語言處理方面的帖子之後我看到了這樣一個演算法:萊文斯坦距離,能夠用數值表示兩個詞的相似程度,越相似的兩個詞距離值越小。

這樣一來就非常簡單啦,只要把數組A裡面的a1,a2...挨個跟B裡面的b1計算萊文斯坦距離,然後求和,就能算出A和b1的關聯度得分,以此類推得到b2,b3...最後得分最低的(也是就萊文斯坦距離最小的)就是關聯度最大的系列名了。

這裡是我用JavaScript寫的一個小demo:matching algorithm

【提高準確性】

所以說為啥是「乞丐版」呢...到此為止這個演算法還很簡陋,真正應用到軟體里還需要進一步提高準確性。我能想到有下面幾個方面可以進行調整:

  1. 兩個詞的萊文斯坦距離如果是1到2,很有可能是單複數的變化,如果是3-5,很有可能是詞性的變化。可以給這兩個區間的數值分配更大的權重,這樣關聯度高的詞才能在最後的結果中體現出來。
  2. 系列名也可以找到一組關聯詞,和用戶信息的關鍵詞進行匹配。
  3. 可以利用機器學習演算法給文章分類,一篇文章可以對應多個系列。

這麼想一下,可能性真的超多啊!

【參考鏈接】

各種編程語言寫的萊文斯坦距離演算法,可以直接用

JavaScript版萊文斯坦演算法

話說下一個挑戰應該就是我期盼已久的機器學習了吧!如果感興趣的話請關注 全棧萬事屋。


推薦閱讀:

NP=NP? 從計算到智能的終極問題
波士頓動力終於實現類人平衡力!全新演算法賦予機器人擺脫「摔倒」魔咒
從1~N的整數中隨機選M個
DNN論文分享 - Item2vec: Neural Item Embedding for Collaborative Filtering

TAG:算法 | 前端工程师 | 自然语言处理 |