跳到主要內容

Association Rule Mining

What is association rule mining?
 A:
  Given a set of transactions, find rules that will predict the occurrence of an item based on the occurrences of other items in the transaction

Definition
• Support count (\sigma):  itemset  出現的次數
∘ Frequency of occurrence of an itemset
∘ E.g.   \sigma({Milk, Bread,Diaper}) = 2
• Support: 某一個 itemset / itemset 的總數
∘ Fraction of transactions that contain an itemset
∘ E.g.    s({Milk, Bread, Diaper}) = 2/5
• Frequent Itemset
∘ An itemset whose support is greater than or equal to a minsup threshold
•  Rule Evaluation Metrics
∘ Support (s): Fraction of transactions that contain both X and Y, i.e.    \sigma({X, Y}}/T
∘ Confidence (c): Measures how often items in Y appear in transactions that contain X,   \sigma({X, Y}}/ \sigma (X)
  

Maximal Frequent Itemset:
• An itemset is maximal frequent if none of its immediate supersets is frequent(最相近的 superset 都不是 frequent itemset)
• example:
∘ Items: a, b, c, d, e
∘ Frequent Itemset: {a, b, c}
∘ {a, b, c, d}, {a, b, c, e}, {a, b, c, d, e} are not Frequent Itemset.
∘ Maximal Frequent Itemsets: {a, b, c}

Closed Itemset:[2]
       An itemset is closed if none of its immediate supersets has the same support as the itemset.

       So for example, if {Bread, Milk} is an itemset that has support=4, and all of its supersets has support<4, then {Bread, Milk} is a closed itemset.

       Counter e.g.: If, let's say, {Bread, Milk, Sugar} has support=4, then {Bread, Milk} is not a closed itemset anymore.

       Note: The definition states "the same" and doesn't say "the same or more" because it's impossible for a superset to have a support greater than one of its subsets

What is it purpose  to find the closed frequent itemset?
找 closed and frequent itemsets 的主要目的在於可以從 frequent itemset 但不是屬於 closed itemsets 中,找出所有 frequent itemsets 的 support 值,因為 maximun frequent itemset 可以找出所有 frequent itemsets,但是無法找出 frequent itemsets 的 support 值,所以必須找 closed itemset,然後求出 frequent itemset 的 support 值


Apriori Algorithm

• Apriori principle:
∘ If an itemset is frequent, then all of its subsets must also be frequent
• Apriori property:
∘
∘ Support of an itemset never exceeds the support of its subsets
∘ Apriori 使用 anti- monotone(單調,單音) 的特性,避免產生不必要的 candidate itemset, 以減小 search space[1]
∘ 例子參考ch6 ppt 14
• Apriori algorithm:
∘ uses a generate-and-test approach - generates candidate itemsets and tests if they are frequent

Apriori algorithm disadvantage

• Generation of candidate itemsets is expensive (in both space and time)
• Support counting is expensive
∘ Subset checking (computationally expensive)
∘ Multiple Database scans (I/O), 多次的掃描資料庫

Frequent Patten Growth(FP-Growth) Algorithm

FP-Growth Tree[3]

    

FP-Growth algorithm

1. Scan DB once, find frequent 1-itemset (single item pattern)
2. Order frequent items in frequency descending order
3. Scan DB again, construct FP-tree

   min_support = 50%



-----------------------------------------------------------------------------------------------------------
[1] http://dm07course.blogspot.com/search/label/chapter
[2] http://wiki.answers.com/Q/What_is_closed_frequent_itemset_in_datamining#ixzz1AeRZ8Nea
[3] http://www.florian.verhein.com/teaching/2008-01-09/

留言

這個網誌中的熱門文章

CodeBlocks 多國語言的設定步驟

多年來一直都是使用 CodeBlocks 英文的介面,不曾想過要將 CodeBlocks 設定成多國語言的開發環境,對於不習慣於英文介面的國人,設定中文的使用介面是非常需要的環境,在 CodeBlocks 論壇有一篇文章提到 :Do you know http://wiki.codeblocks.org/index.php?title=Internationalization ?這個連結說明在 Windows 系統如何設定 CodeBlocks 成為 Internationalization 的環境,整個設定過程如下: 到 CodeBlocks 翻譯文件網站 下載 .mo 檔案:下載時需要 Ubuntu One 的帳號及密碼,登入後點選 .mo 檔案(不要下載 .po 檔是可編輯檔) 系統會傳送一封信件,點選信件的連結,將 .mo 檔案下載 將檔案複製到 C:\Codeblocks\share\CodeBlocks\locale\zh_TW 目錄(沒有這個目錄請自己建立) 開啟 CodeBlocks >> Setting >> Environment >> View >> Internationalization 選項打勾 >> 點選 Chinese 重新開啟 CodeBlocks 要加入其他語言的 .mo 檔案,則在 locale 目錄中新增其他語言的目錄名稱,例如: 德國 de_DE,這樣 CodeBlocks 就是多國語言的開發環境了。 當如果要恢復英文的介面,只要取消 Internationalization 的選項勾選,然後再次重新開啟 CodeBlocks 就回到英文的開發環境。 後記: CodeBlocks 翻譯文件網站 要下載 .mo or .po 檔案需要等待系統回復信件到 Email 信箱,無法及時處理,將這些檔案儲存在 Google Driver 的 src/CodeBlocks 目錄,以後可以從這裡直接取用。

Programming Tutorial Website

Foundation is front-end framework for website, 提供網頁設計者設計各種不同 devices 的網頁,它是使用 Sass, Compass 這兩種 CSS framework 發展而成的。整個專案是採用 Ruby 的套件管理方式來運作,安裝它相當容易,使用 Ruby 的 gem install zurb-foundation 來安裝,若要調整 Foundation 的內容,需要再安裝 Sass, Compass, 網路上有介紹 Sass, Compass 的書籍,使用這兩種 CSS framework 對於寫 CSS 則更具有彈性[1]。   在安裝這些套件時,看見 Ruby 有安裝這些套件的文件,只是不知道如何從 Ruby 系統中讀出這些文件? 目前對於 Ruby 的系統不熟悉,需要找些資料來了解。在尋找資料時,找到一個不錯的教學網站,名為 Programming tutorials and source code examples 有許多教學文件及原始程式碼,其中包括 C++, HTML, Ruby, GIMP, etc ...,也有許多 free HTML templates 可以下載,可以做為做為教學時的教材。   另外, jQurey EasyUI 是另外一種開發 Website 的 framework, 是基於 jQuery UI 的基礎上,讓使用者不需要寫 Javascript 就可以容易的建立 jQuery 的 UI 介面。 --------------------------------------------------------------- [1] http://www.slideshare.net/kurotanshi/compass-sass

Ubuntu One

Tomboy 有了 Ubuntu One 變得更好用 - 您的私有雲能將您的數位生活統整在一起。 Ubuntu One 不只是同步您的檔案 - 不管您是需要從任何電腦或透過網路存取聯絡人資料、筆記、書籤,或是要從整合雲端技術的商店聆聽您喜愛的音樂,或是要將您的整個收藏傳送至 iPhone 或 Android 手機都可以 - 我們在私有雲的應用上領先群倫。若要深入瞭解,請見 http://one.ubuntu.com/。 已經擁有 Ubuntu One 帳號了嗎?只要按一下「編輯」>「偏好設定」,接著點選「同步化」分頁,就能將 Tomboy 設為與您的私有雲同步。從服務的清單中選取「Tomboy 網頁」,接著按一下「連接伺服器」按鈕。網路瀏覽器會顯現,並包含一些額外的指示內容。 您甚至可以讓 Tomboy 筆記與 Ubuntu One 自動同步! 最近(2010.12.20)因為 Data Mining Project 需要在 Linux 系統中 compile Netflix KNN source code, 開始使用 Tomboy notebook 來紀錄自己的筆記,也同時開始使用 Ubuntu One, Dropbox 雲端服務中的同步化功能,在[1]中有詳細介紹如何將 Tomboy 同步到 Ubuntu One 之中, 在 Windows 之中的同步主機應該輸入 https://one.ubuntu.com/notes/ 。 在申請 Ubuntu One 時,要求密碼必須是英文字大寫字母,所以就把常用的密碼改成大寫。 ---------------------------------------------------------------- [1] https://wiki.ubuntu.com/UbuntuOne/Tutorials/Notes