iT邦幫忙

DAY 4
5

資料探勘的開發, 經驗與未來系列 第 4

從關聯分析來看效率的重點(I)/貘的資料探勘30講

本來是依我的開發時間來講我的開發實務經驗的, 但若這樣的話前四五講都是失敗經驗, 可能大家都看得不耐煩了, 因此我先跳過較早的失敗經驗, 直接講第一個成功經驗, 然就再來穿插好了.

在資料探勘的教科書都會講到一個很有名的例子, 叫 "脾酒與尿布" 的關連式分析, 這是一個很有趣的情境與對像案例, 但他也說到, 這案例是採樣一個賣場一個星期的購買記錄, 然後算一個月出來的結果, 而到底算出多少個關係 Relation, 書上是沒有說的.
事實上我在進入 B 公司時, 他們也想做關聯式分析, 這個演算法都寫在書上, 任何人都可以如法泡製的相當輕易的寫出程式, 只是他們沒想到他們先拿第一個商品來做關聯分析, 花了快一個星期才算完, 那時這賣場的商品數並不多, 只有 5 萬個, 但即使這樣, 要算完一輪也須要 1000 年的時間.

所以也不難想像我之前的失敗經驗, 因為要追求一個普遍性, 即時性, 完整性, 有效性的資料探勘, 困難點跟本不是在能不能算得出來的演算法, 而是在於其效率, 即使我們知道關聯的關係並不常變動, 甚至即使一開始因為資料少須要一段時間收斂, 但在大家的行為邏輯不改變的情型下, 這關係最終會是固定的, 因此說即時算出來的最低要求應該是:

  1. 8 成已經賣很久的商品只要 1 個月到 2 個月更新一次.
  2. 剛開始買不到半年的商品須要 1 個星期到 2 個星期更新一次.

若是以 10 萬個商品來看, 一個月的更新次數至少為:
10*0.8/2+10*0.2*2= 8 萬次, 也就是說 80,000/(60*24*30) = 1.85次/每分鐘...
若是以原本的每 60*24*7 = 10,080 分鐘一次的話,
也就是要提升效率 1 萬倍才能夠計算得了....

這當然是很困難的任務, 因此就假設若是用 10 台 Cluster 來計算, 演算法只要提升 1000 倍, 再加上系統調校, 這個工作花了將近兩年的時間, 先做出每 15 分鐘算一個物件的關聯, 也就是 0.07 次/分鐘, 而最後弄到了 16 個 CPU 來計算, 因此第一次可以實現的效率是每分鐘算一個, 而這個離目標雖然有點距離, 但還是在可以實用的範圍...

有人在想, 這個一分鐘算一個商品的關聯, 看起來是沒甚麼, 事實上是在處理 10 萬的平方的關聯, 也就是每秒計算 17 萬次的關聯關係, 這是一個須要很高的 Computing Power 計算效能才能達到的.

但在實務上大家都知道, 真正的瓶頸不是 CPU 的 Computing Power, 而是 I/O 處理的速度, 也就是硬碟的傳輸速度, 事實上在這第一次的實現中, 例用了許多中間表, 先把會用上的關聯先整理起來, 讓每次的 I/O 讀取中, 就能夠讀到 10 萬筆的 Relationship, 而再花 CPU time 去展開, 不然要 I/O 每秒去讀 17 萬次, 這幾乎是跨國公司的資源才能做到的.

所以把 I/O 的效率的瓶頸丟給 CPU 來做, 每次讀一個 Block 區塊後, CPU 再做切割再來計算, 這個效能的確就提升了 100 倍, 而為甚麼這一次的改善能夠提升到 1 萬倍呢? 就待下回分解....


上一篇
資料探勘 -- 資料探勘的不同點
下一篇
做效率調校的基本能力有那些/貘的資料探勘30講
系列文
資料探勘的開發, 經驗與未來30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

1 則留言

0
食夢黑貘
iT邦研究生 3 級 ‧ 2010-10-15 15:54:02

到底一篇要寫多少阿, 真難拿捏阿, 不要說這個一寫就寫不完了...

SunAllen iT邦研究生 1 級 ‧ 2010-10-15 17:29:18 檢舉

genehong 提到:
一篇要寫多少

genehong 大大,上限5000個字,寫多了,留到下一篇就好啦!!沙發

我要留言

立即登入留言