iT邦幫忙

DAY 8
4

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

從降冪來降低計算量/貘的資料探勘30講

在大約了解甚麼是 Big O 後, 接下來知道資料越多的話, 演算法的 Big O 會造成計算量增加的多寡, 甚至是變成可以算或不可以算的決勝點, 當然上一篇說到 O(n log n) 是可以算的演算法, 但即使如此, 真的到 O (n^2) 還不至於不能算, 只是要有方法的降低須要計算的量, 還是可以算的, 但是要如何降低要計算的量, 有幾種方法:

  1. 因為這是眾人的眾多資料, 若是以矩陣的觀點來看, 這是一個 "近乎零的矩陣", 因此若是用真的矩陣計算是很浪費的, 可以利用其他的演算法來算距離與關係, 甚至在這種近乎零的量中, 只算一維的幾百筆資料, 比算上萬維的百萬筆計算, 一口氣少了幾萬分之一, 且實用性是相當夠了.

  2. 通常關係的演算法中, 真的要實用, 可能要做維度的展開, 有時要算很多次的 Relation 關係才會有資料, 也就是從少數的關係中展開出更多的關係, 不然算出來的資料總是很少 (本來就是趨零矩陣), 因此若是要展開三到四次的關係, 與其真的去算, 還不如先算好每次的展開後, 甚至先做好兩次的展開並儲存起來, 而算三到四次的展開時只要算兩次就好, 可以降低大量的計算.

  3. 雖然我們是要算出所有的結果, 但說要算出參考值, 一件事真的足以參考的量是有限的, 不是 50 項, 也是在 500 項以下, 一個人要看那麼多項參考是不太可能的, 但事實上最後還是會過濾一些不須要的資料, 因此最後只要準備個 2~3 倍有時就很夠了, 或者是說用最後的量來做之前要計算的量的篩選, 此時就又可以降低不少計算量了.

  4. 通常要有算出一定的關係, 一定要做 Normalization (一般化), 也就是把量度化成相同的平準點, 因此一開始計算時, 就先以附近的資料來直接作計算, 而乖離太多的數字就不用計算了, 畢竟真的算也排不上有效的結果量裏面, 如上面所說的, 真正要用的數量本來就不須要那麼多.

畢竟資料探勘是一個聚焦的動作, 只是要把這個如此離散的資料找到共同點, 要做的聚焦往往要多幾次發散才行, 因此在每次發散一定要降冪留下一定的資料再來算, 不然就真的算不完了..


上一篇
Big O 在 Data Mining 的意義/貘的資料探勘30講
下一篇
關聯購買(AlsoBuy)/貘的資料探勘30講
系列文
資料探勘的開發, 經驗與未來30
0
食夢黑貘
iT邦研究生 3 級 ‧ 2010-10-19 22:03:15

上一篇似乎已經大家看不下去了, 都沒人回應或按贊了, 但這篇還是必須多講一些理論, 下一篇再來些實務討論吧..

0
aqr199
iT邦新手 2 級 ‧ 2010-10-20 09:17:13

矩陣, 上萬維, Relation, 趨零矩陣, Normalization, 量度化, 平準點, 乖離, 聚焦, 離散, 發散, 降冪

如果不用這些名詞來解釋理論, 觀念想法會無法清楚表達嗎?
真的太深了~~洞裡還有深淵丫

食夢黑貘 iT邦研究生 3 級 ‧ 2010-10-20 12:48:54 檢舉

嗚, 是怪我無法深入淺出嗎? 淚奔~~~~

但的確也是這樣我一直是不能擔任 Document 的人, 在公司都頂多只能寫架構, 但這鐵人賽只好都自己寫了...

0
p12076
iT邦新手 4 級 ‧ 2010-10-20 21:31:50

我也是蠻有興趣的,但感覺像教授在上課...
能配合實際案例XXX公司探勘什麼東東來講解嗎?

食夢黑貘 iT邦研究生 3 級 ‧ 2010-10-20 22:21:13 檢舉

下一篇就要寫了, 嗯, 就是待會阿...

我要留言

立即登入留言