大數據中效用挖掘的快速單階段算法
2015-12-31 12:51:18劉君強周青峰王文慧
電信科學 2015年4期
劉君強 ，周青峰 ，王文慧 ，時 磊
（1.浙江工商大學 杭州 310018；2浙江水利水電學院 杭州 310018）
1 引言
效用模式挖掘[1～6]是近年來發展起來的大數據分析技術，不僅考慮數據統計顯著性，而且也考慮用戶興趣和目標[7]。例如，傳統頻繁模式挖掘技術[8～11]只能從銷售數據中挖掘出購買頻率較高的產品組合，而效用模式挖掘技術可以從中發現利潤回報較高的產品組合。效用模式挖掘不僅是各種挖掘問題的基礎[12～14]，也可以直接應用于各種大數據分析。例如，網絡傳媒的點擊率和轉化率分析、價值鏈分析、網購的消費者行為理解和預測等。
然而，效用模式挖掘技術還不成熟，只有很少量成果。由于效用模式不具有反單調性，即一個低效用模式的超集可能是高效用的，挖掘高效用模式要比挖掘頻繁模式困難得多，因為很難剪裁搜索空間。現有挖掘算法大多數采用兩階段法，即先在第1階段從原始數據中挖掘出候選模式，再在第2階段從候選模式中進一步挖掘出效用模式。其缺點是挖掘大數據時會產生大量候選模式，造成存儲空間開銷過大，形成可伸縮性瓶頸，并最終導致運行的時間效率低下。
不少工作[3,5]試圖降低第1階段生成候選模式數量。然而，對于海量的數據庫或給定較小的效用閾值時，候選模式數量還是巨大的。這不僅導致第1階段的伸縮性瓶頸，對于第2階段也是如此，并最終導致效率瓶頸。個別算法[15]雖然不生成候選模式，但是依賴于縱向數據表達形式和計算代價高昂的交集運算，缺少有效剪裁方法，運行效率比二階段算法還差[5]，不適合于大數據處理。為了克服這些問題，本文提出一個全新算法，在單個階段直接挖掘出效用模式。主要貢獻如下。
首先，提出一個全新算法SPUP（single phase utility pattern mining）來挖掘效用模式。具體地講，提出稀疏矩陣來表達事務效用的完整信息，使得單階段挖掘成為可能。這種稀疏矩陣表達比基于Fptree[9]的表達方法[1,2,5]結構更緊湊，避免多遍掃描數據庫[3,4]。
第二，提出前綴生長策略及相應的前綴擴展樹，用于引導效用模式的挖掘過程，并得到效用模式搜索空間剪裁技術的支撐，即通過估算任意子空間的模式效用上限值，有效地剪裁前綴生成樹。
第三，采用人工數據和真實數據，對比已有最先進算法[1,4,5,15]的實驗結果表明，本文提出的SPUP算法在運行時間和空間開銷上均優于其他算法。換言之，SPUP算法是效率最高、可伸縮性最佳的效用挖掘算法。
2 大數據分析中的效用模式挖掘問題
大數據分析的特點之一是數據來源的多樣性。多個不同的數據來源為每個被分析的對象提供了豐富多樣的屬性，但如何融合多源的數據卻是一個難題。效用挖掘通過引入效用模型，為融合多個屬性并從中提煉有價值信息提供一種通用方法。因此，效用挖掘在大數據分析中有著廣泛的應用。
簡要討論一個移動電子商務應用案例[12]。移動通信運營商保存大量移動設備軌跡數據，單純依賴軌跡數據只能分析“高頻繁度的軌跡”，例如“訪問A”以后很可能“訪問B”，其商業價值并不高。然而，如果將移動運營商的軌跡數據與消費者購物的支付數據結合起來進行大數據分析，通過融合網點、商品、商品價值等屬性進行效用挖掘，就可以找出“高價值的軌跡”，例如“訪問A購買唇膏”以后很可能“訪問B購買鉆戒”。另一個相似案例是電商平臺的大數據分析，通過效用挖掘分析客戶在線購物的消費行為，找出“高價值的網購軌跡”，用于改進電商平臺設計和指導網上促銷活動。
效用挖掘通過效用的概念將具體應用問題中多個屬性融合起來表達所研究對象的價值，并從中挖掘高價值的對象，即高效用模式。下面給出高效用模式挖掘的定義。
I={i1,i2,…,im}是所有項目的集合，D={t1,t2,…,tn}為數據庫，即事務記錄的集合。每個事務記錄t是一個項目集，即t哿I。而u(i,t)=iu(i,t)·eu(i)則是項目i在事務記錄t中的效用，其中iu(i,t)是項目i在事務記錄t中的份額，eu(i)是項目i獨立于任何事務記錄的外在效用。模式X是I的一個子集，如果模式X中的任意項目i在事務t中的份額非0，即iu(i,t)≠0，則模式X被事務記錄t所支持，即X哿t。
·TS(X)則是支持模式X的所有事務記錄的集合。
· 模式X稱作（高）效用模式，如果其效用值不低于給定閾值minutil，即u(X)≥minutil。
· 效用模式挖掘就是發現所有（高）效用模式，即求解HUPset={X|X哿I,u(X)≥minutil}。
例如，表1給定項目集合I={a,b,c,d,e,f,g}，數據庫D由5條事物記錄組成，其中t1包含3個項目a、c、e，并且iu(a,t1)=1、iu(c,t1)=1、iu(e,t1)=1。表 2是所有項目外在效用匯總。由eu(a)=1，可以得到u(a,t1)=iu(a,t1)×eu(a)=1。假定效用模式X={b,c}，由表 1可知：TS(X)={t2,t3}，X的總效用u(X)=u(X,t2)+u(X,t3)=u(b,t2)+u(c,t2)+u(b,t3)+u(c,t3)=24。給定最小效用閾值minutil=30，可以得到高效用模式的集合為{{a,b,c},{a,b,d},{a,d,e},{a,b,d,e},{b,d,e},{d,e},{a,b,c,d,e,g}}。
表1 事務數據庫D
表2 效用表UT
效用模式不具有反單調性，如上例中u({a,c})=28、u({a,b,c})=31、u({a,b,c,d})=13。因此，挖掘高效用模式要比挖掘頻繁模式困難得多。
3 相關工作
效用模式挖掘是頻繁模式挖掘的發展。頻繁模式挖掘算法以Agrawal和 Srikant的 Apriori算法[8]以及 Han等人的FP-Growth算法[9]最為著名。Apriori算法充分利用支持度的反單調性：任何頻繁模式的子集都是頻繁模式。FP-Growth算法采用基于樹的結構存儲事務數據庫，也利用反單調性。
近幾年，效用模式挖掘受到越來越多關注。Yao等人[7]指出效用指標不具有反單調性。因此，大量算法采用生成候選模式的二階段挖掘方法。Liu等人[4]提出事務加權效用TWU向下閉合性質，設計了兩階段算法TP，第1階段先找出具有高TWU的模式（候選模式），第2階段再次掃描數據庫來計算各個候選模式的實際效用，從而找出高效用模式。Li等人[3]提出孤立項剔除策略，用于逐層挖掘候選模式的第1階段，以減少多余候選模式。
為克服逐層生成候選模式時多遍掃描數據庫[3,4]的缺點，以便第1階段能高效率地生成候選模式，多個研究小組提出基于樹的效用模式挖掘算法[1,2,5]。Erwin等人[2]提出CTUPROL算法，運用事務加權效用TWU向下閉合性質[4]、基于效用模式樹 CUP-tree、FP-Growth算法[9]進行挖掘。Ahmed等人[1]提出一種基于樹的IHUP算法，采用IHUP-tree來存儲各個事務的TWU信息，改進FP-Growth算法[9]來挖掘效用模式的候選模式集。Tseng等人[5]設計基于樹的二階段算法UPG，利用UP-tree壓縮存儲TWU信息，并提出遞減TWU的策略，因而生成較少數量的候選模式。
Liu等人[15]提出HUIMiner算法，直接計算各模式的效用信息，避免產生和計算候選模式，但是所依賴的縱向數據表達形式不適用于大數據，同時代價高昂的交集運算使得其運行效率比二階段算法還差[5]。
本文提出剪裁搜索空間的有效辦法和節省內存的數據結構，解決可伸縮性與時間效率的瓶頸。
4 基于前綴生長的模式枚舉和剪裁策略
挖掘效用模式最基本的辦法是窮舉項目集合I的每一個子集X，但是組合爆炸的問題使得這種窮舉法行不通。因此，在挖掘效用模式過程中很有必要使用剪裁技術。本節首先引入一種新穎的枚舉效用模式的策略，然后提出剪裁技術。
4.1 前綴生長的模式枚舉策略
為了避免重復列舉效用模式，需要為數據庫中的所有項目指定一個排列順序。這樣，一個模式也可以表達為一個序列。因此，集合表達法（如{a,b,c}）與序列表達法（如
·prefix(X,t)是事務記錄t相對于模式X=
·preEXT(X,t)=prefix(X,t)∪X是模式X相對于事務記錄t的前綴擴展。
·前綴生長策略就是將空模式拼接前綴得到長度為1的模式，將長度為1的模式拼接前綴得到長度為2的模式，以此類推。
假定所有項目按照字典序進行排列，那么是空模式<>的一個前綴擴展，
根據所提出的前綴生長策略，枚舉效用模式可以看作使一顆前綴擴展樹不斷生長的過程。在前綴擴展樹中，根節點不標注任何項目代表一個空模式，其他每個節點標注數據庫的一個項目。樹中每一條到達根節點的路徑代表一個模式。對于標注項目i的節點來說，它的節點則標注那些按照指定順序排在項目i前面的項目。節點N到根節點的任一條路徑是一個有序序列，它與指定的項目排序是一致的，用pat(N)表示該路徑代表的模式。因此，在前綴擴展樹以節點N為根的子樹中，任何節點代表的模式是模式pat(N)的一個前綴擴展，可以表示為preEXT(pat(N))。圖1是一顆完整的前綴擴展樹，其中項目集合I={a,b,c,d}，采用字典序。
圖1 前綴擴展樹
4.2 基于效用上限值評估的前綴擴展樹剪裁
假定數據庫的項目集合I={i1,i2,…,im}，即有m個項目，完整的前綴擴展樹有2m個節點，表示序列
然而，在高效用模式挖掘過程中，反單調性不再適用。剪裁策略是評估以節點N為根的子樹中所有節點對應模式的效用上限值，當效用上限值小于minutil時，可以剪裁掉以節點N為根的子樹。
定理1 對于模式X的任何含有項目i的前綴擴展模式Y，其效用值u(Y)的一個上限值是：
證明 首先，Y是X的一個前綴擴展，并且i∈Y，因而{i}∪X哿Y，TS(Y)哿TS({i}∪X)。其次，Y是TS(Y)中的任何事務記錄t的子集，同時也是preEXT(X,t)的子集，所以u(Y,t)≤u(preEXT(X,t),t)，進而有：
根據定理1，如果效用上限值ubound(i,X)小于minutil，那么模式X的任何含有項目i的前綴擴展模式Y都不可能是高效用模式，因此在X的前綴擴展模式中，項目i可以被剔除。
· 當ubound(i,X) · 定義ppFix(X,t)為prefix(X,t)剔除無關項目后的前綴。 · 定義ppEXT(X,t)=ppFix(X,t)∪X為剔除無關項目后的前綴擴展。 證明 首先，由于Y是X的前綴擴展，TS(Y)哿TS(X)。其次，根據定理1，Y不包含任何無關項目，否則Y就不可能是高效用模式。再者，Y是TS(Y)中任何事務記錄t的子集，所以u(Y,t)≤u(preEXT(X,t),t)=u(ppEXT(X,t),t)，進而有： 在前綴擴展樹生長的過程中，對于節點N對應的模式pat(N)，如果效用上限值ubound(pat(N))低于minutil，以節點N為根的子樹可被剪裁掉。 高效用模式挖掘是使前綴擴展樹不斷生長的過程，是影響效率和伸縮性的因素之一，是有效表達新生節點N代表的模式所對應的事務記錄集合的效用信息。 準確地說，當搜索到前綴擴展樹的節點N時，在事務記錄集合TS(pat(N))中組成一個前綴擴展模式preEXT(pat(N),t)的所有項目的完整效用信息。為此，提出采用一種由穿線變長數組[11]實現的稀疏矩陣，如圖2所示。矩陣按行編排TS(pat(N))中的事務記錄，每行實現為變長數組；列按排列在pat(N)前的項目編排，每列實現為穿線鏈表；第t行第i列元素是u(i,t)，即項目i在事務記錄t中的效用。 圖2 表達效用信息的稀疏矩陣 這種表達法有3個長處：一是能夠完整地表達效用信息，克服了二階段法[1～5]只能表達TWU的缺陷；二是存儲開銷低，實際上比基于Fptree[9]的表達方法[1,2,5]更緊湊；三是計算開銷低，這種表達法是按事務記錄展開的橫向表達法，通過穿線的辦法可以快速確定各個模式的事務記錄集，計算開銷遠低于按項目展開的縱向表達法[15]所采用的交集運算。 表達一個模式X的事務記錄集TS(X)的效用信息的稀疏矩陣也稱為X的效用信息矩陣，記作uMatrix(X)。圖2是根據表1所示數據庫D和效用表UT確定的空模式{}的效用信息矩陣uMatrix({})。 因此，事務記錄集TS(X)和效用信息矩陣uMatrix(X)可以視為同一個數據結構，下面不再加以區分。 通過搜索前綴擴展樹來枚舉模式時，樹節點N所代表模式的效用信息矩陣是其父親節點P所代表模式的效用信息矩陣的子矩陣，可以通過虛擬投影獲得。 具體來講，對于節點N的標記項目i的節點C，可以從uMatrix(pat(N))中選擇那些含有i的事務記錄，然后得到模式pat(C)= ({i}∪pat(N))對應的效用信息矩陣uMatrix(pat(C))。這種操作被稱作投影，即節點C對應的效用信息矩陣uMatrix(pat(C))通過投影其父親節點N對應的效用信息矩陣uMatrix(pat(N))得到。實際上，除了根節點之外，任何節點對應的效用信息矩陣都嵌套在其父親節點對應的效用信息矩陣中。例如，從uMatrix({})可得到uMatrix({c})，從后者可得到uMatrix({b,c})。 因此，只需要在內存中保留根節點對應的效用信息矩陣，其他節點的效用信息矩陣只是父親節點的效用信息矩陣的子矩陣，不需要開辟獨立的內存空間。從節點N的uMatrix(pat(N))推導出節點C的uMatrix(pat(C))的操作稱為虛擬投影，采用虛擬投影能進一步提高算法的伸縮性。 本節提出單階段高效用模式挖掘算法SPUP。SPUP算法將第4.1節的前綴生長策略、第4.2節的基于效用上限值剪裁策略、第5節的基于稀疏矩陣的效用信息表達方法相結合，并應用到按深度優先搜索高效用模式的過程中。SPUP算法采用深度優先搜索時，只需要在內存中保存當前正在生長的前綴擴展樹分支，極大地節省了內存空間，進一步提高算法的伸縮性。下面是SPUP算法的偽代碼，大致分為5步，可以結合例子進行解釋。 算法 SPUP(D,UT,minutil) 步驟1 （第1～3行）：創建前綴擴展樹的根節點。通過掃描數據庫D，過濾掉全部無關的項目，得到根節點（空模式）對應的效用信息矩陣uMatrix({})。 步驟2 （第4～5行）：對于節點N對應的模式pat(N)= 例如，圖3是根據表1的數據庫D和表2的外在效用表UT生成的部分前綴擴展樹，其中所有項目按照字典序排序，最小效用閾值minutil=30。每個節點N都標明其效用信息矩陣uMatrix(pat(N))以及各項目i的效用值(u)和上限值(uB)，即u({i}∪pat(N))和ubound({i}∪pat(N))。 步驟 3 （第 6行）：如果效用值u({i}∪pat(N))≥minutil，那么模式{i}∪pat(N)是一個高效用模式，將它輸出保存。如圖3所示，有一個節點對應模式{b,c}，其節點對應模式{a}∪{b,c}的效用值u({a}∪{b,c})=31>minutil，因此{a,b,c}是一個高效用模式，將它輸出。 圖3 前綴擴展樹以及各個節點的效用信息矩陣 步驟4 （第 7～11行）：如果N的節點C對應模式{i}∪pat(N) 的效用上限值ubound({i}∪pat(N))≥minutil，需要通過虛擬投影得到節點C對應的效用信息矩陣uMatrix({i}∪pat(N))，然后深度優先搜索以節點C為根的子樹。如圖3所示，{a}、{b}和 {c}都是根節點 {}的節點，由于ubound({a})和ubound({b})都小于minutil，項目 a、b 對應的節點被剪裁掉。與此同時，由于ubound({c})=37>minutil，項目c對應的節點被創建，然后繼續深度優先搜索該節點對應的子樹。 步驟5 （第12～13行）：深度優先搜索完節點N的所有后，以節點N為根的子樹就被清除，然后回溯到節點N的父親節點P，繼續深度優先搜索P的下一個節點，以此類推。如圖3所示，搜索模式{a,b,c}相應的節點后，回溯到根節點，然后繼續深度優先搜索根節點的項目d對應的節點。 本節通過實驗對比，評估效用挖掘的效果，并且評估所提出的單階段模式挖掘算法SPUP的效率和可伸縮性。實驗用到兩個數據集：第一個是IBM Quest人工數據集T20I6N1kD1mL6k，有100萬條事務記錄，事務記錄平均長度為20個項目，最大頻繁模式平均長度為6個項目，每一條事務記錄中各個項目份額服從1～5的均勻分布，每一個項目對應的外在效用值服從0.01～10的對數正態分布；第二個是美國加州一所大型百貨超市連鎖店銷售的真實數據集[4]，有1 112 949條銷售事務記錄，每一條事務記錄由商品和商品銷售數量組成，表示某一個消費者在某個時間段購買商品情況。事務記錄平均長度為7.2，效用表描述每種商品的利潤。實驗環境為3 GHz CPU/3 GB RAM的PC一臺，運行于Windows 7系統的Cygwin。 本小節通過對比本文SPUP算法挖掘得到的TopK高效用模式和CAP算法[10]挖掘得到的TopK閉合頻繁模式，評估效用挖掘的效果。具體采用兩個指標：第一個是覆蓋度（recall），定義為TopK高效用模式被 TopK閉合頻繁模式所覆蓋（包含）的比例；第二個是精確度（precision），定義為TopK閉合頻繁模式中包含TopK高效用模式的比例。如果覆蓋度和精確度比較低，則表明挖掘高效用模式和挖掘頻繁模式有著不同的效果。 圖4（a）是人工數據集的TopK閉合頻繁模式和TopK高效用模式的挖掘效果對比。當TopK從1 000變到10 000時，覆蓋度均低于18.2%，精確度均低于45.6%。例如，前5 000個閉合頻繁模式只覆蓋5.6%的前5 000個高效用模式，44.8%的前5 000個閉合頻繁模式包含前5 000個高效用模式。其中，精確度大于覆蓋度的原因是多個閉合模式包含同一個高效用模式。這個結果表明，大部分高效用模式不是頻繁模式。 圖4 TopK模式的覆蓋度recall和精確度precision 圖4（b）是真實數據集的挖掘效果對比。當TopK從1 000變到10 000時，覆蓋度均低于6%,精確度均低于12.1%。例如，前5 000個閉合頻繁模式只覆蓋2.5%的前5 000個高效用模式，10.9%的前5 000個閉合頻繁模式包含前5 000個高效用模式。相對于人工數據集，真實數據集的TopK閉合頻繁模式比TopK高效用模式的覆蓋度和精確度更低，這更說明高效用模式挖掘在實際應用中的價值遠遠高于頻繁模式挖掘。 本小節通過對比現有最先進效用模式挖掘算法TP[4]、IHUP[1]、UPG[5]、HUIMiner[15]，評估所提出的單階段挖掘算法SPUP的效率，所有算法都采用C++實現。 圖5（a）是5種算法挖掘人工數據集的運行時間，其中橫坐標表示最小效用閾值minutil，范圍是0.005%～0.4%，縱坐標表示運行時間。當效用閾值minutil=0.2%時，SPUP算法運行 39 s，UPG算法運行 67 s，IHUP算法運行 98 s，HUIMiner算法運行118 s，而TP算法的運行時間達到1009 s。當效用閾值minutil<0.2%時，TP算法不能運行。當效用閾值minutil=0.005%時，SPUP算法運行 248 s，HUIMiner算法運行 1 052 s，UPG 算法運行 1 430 s，IHUP算法運行2 346 s。 圖5（b）是挖掘真實數據集的運行時間，minutil范圍是0.005%～0.2%。當效用閾值minutil≥0.2%時，高效用模式數量很少，此時HUIMiner算法運行最快；當minutil低于0.2%時，HUIMiner算法的運行時間增長很快。當效用閾值minutil=0.05%時，SPUP算法運行20 s，UPG算法運行52 s，IHUP算法運行55 s，HUIMiner算法運行630 s，而TP算法運行時間達到1 117 s；當效用閾值minutil=0.005%時，SPUP算法運行26 s，UPG運行116 s，IHUP算法運行154 s，HUIMiner算法運行1 797 s，TP算法不能運行。 圖5 各算法隨著minutil變動的運行時間比較 綜合比較可知，SPUP算法效率總是最高的，算法UPG[5]、HUIMiner[15]和IHUP[1]在不同情況下效率互有高低，SPUP算法的效率比后3個算法高5倍以上，TP算法[4]效率總是最低的，SPUP算法比TP算法高70倍。 圖6（a）分別是算法 SPUP、HUIMiner、UPG 和 IHUP 挖掘人工數據集的最大內存使用量，TP算法沒有統計內存使用情況。當效用閾值minutil=0.4%時，SPUP算法消耗內存295 MB，HUIMiner算法消耗內存373 MB，UPG算法消耗內存424 MB，IHUP算法消耗內存426 MB。當效用閾值minutil=0.01%時，SPUP算法消耗內存307 MB，HUIMiner算法消耗內存380 MB，UPG算法消耗內存485MB，IHUP算法消耗內存534MB。盡管沒有直接統計數據，但TP算法消耗內存最多，因為當效用閾值minutil<0.2%時，由于缺少內存，TP算法不能運行。 圖6 各個算法隨著minutil變動的內存開銷比較 圖6（b）是挖掘真實數據集的最大內存使用量。當效用閾值minutil=0.2%時，SPUP算法消耗內存26.8 MB，算法UPG和IHUP消耗內存 63.2 MB，HUIMiner算法消耗內存74.9 MB。當效用閾值minutil=0.05%時，SPUP算法消耗內存 86.2 MB，HUIMiner算法消耗內存 122.9 MB，UPG算法消耗內存126.1 MB，IHUP算法消耗內存126.5 MB。當效用閾值minutil=0.005%時，S PUP算法消耗內存116.2 MB，HUIMiner算法消耗內存149.9 MB，UPG算法消耗內存165.4 MB，IHUP算法消耗內存306.7 MB。TP算法消耗內存最多，因為當minutil<0.01%時，TP算法因缺少內存而不能繼續運行。 綜上可知，SPUP算法消耗內存最少，HUIMiner算法和UPG算法內存消耗量次之，IHUP算法消耗內存最多，SPUP算法比后3個算法少消耗20%～60%的內存，TP算法消耗內存最多。 最后，通過實驗評估SPUP算法的可伸縮性。實驗采用人工數據集T20I6N1kL6k，令記錄數從10萬條變到100萬條，效用閾值minutil=0.01%。如圖7所示，SPUP算法的運行時間與記錄數的關系近似線性，SPUP算法的內存開銷與記錄數的關系也是線性的，表明SPUP算法具有很好的可伸縮性。 圖7 SPUP算法的可伸縮性實驗結果 效用挖掘是融合多源的大數據進行綜合分析的一種通用方法，其挖掘效果顯著地不同于頻繁模式挖掘，但是遇到效率與可伸縮性難題。為此，本文提出大數據中發現效用模式的快速單階段挖掘算法SPUP，采用稀疏矩陣表達法保存事務記錄的完整效用信息，無須多次掃描數據庫，直接挖掘高效用模式；提出前綴生長策略和評估模式效用上限值的方法，能有效地剪裁搜索空間。實驗表明，SPUP算法的效率高于現有算法5倍以上，內存開銷減少20%～60%，可伸縮性高。 1 Ahmed C F,Tanbeer S K,Jeong B S,et al.Efficient tree structures for high utility pattern mining in incremental databases.IEEE Transactions on Knowledge and Data Engineering,2009,21(12):1708～1721 2 Erwin A,Gopalan R P,Achuthan N R.Efficient mining of high utility itemsets from large datasets.Proceedings of PAKDD,Osaka,Japan,2008 3 Li Y C,Yeh J S,Chang C C.Isolated items discarding strategy for discovering high utility itemsets.Data & Knowledge Engineering,2008,64(1):98～217 4 Liu Y,Liao W,Choudhary A.A fast high utility itemsets mining algorithm. Proceedings of the Utility-Based Data Mining Workshop in Conjunction With the 11th ACM SIGKDD,Chicago,Illinois,USA,2005 5 Tseng V S,Shie B E,Wu C W,et al.Efficient algorithms for mining high utility itemsets from transactional databases.IEEE Transactions on Knowledge and Data Engineering,2013,25(8):1772～1786 6 Yen S J,Lee Y S.Mining high utility quantitative association rules.Proceeding of the 9th International Conference on Data Warehousing and Knowledge Discovery,Regensburg,Germany,2007 7 Yao H,Hamilton H J,Geng L.A unified framework for utility-based measures for mining itemsets.Proceedings of ACM SIGKDD the 2nd Workshop on Utility-Based Data Mining,Philadelphia,PA,USA,2006 8 Agrawal R,Srikant R.Fast algorithms for mining association rules.Proceedings of the 20th International Conference on Very Large Databases,Santiago,Chile,1994 9 Han J,Pei J,Yin Y.Mining frequent patterns without candidate generation.Proceedings of ACM SIGMOD conference,Dallas,USA,2000 10 Liu J,Pan Y.An efficient algorithm for mining closed itemsets.Journal of Zhejiang University Science,2004,5(1):8～15 11 Liu J,Pan Y,Wang K,et al.Mining frequent item sets by opportunistic projection.Proceedings of SIGKDD,Edmonton,Canada,2002 12 Shie B E,Cheng J H,Chuang K T,et al.A one-phase method for mining high utility mobile sequential patterns in mobile commerce environments.Proceedings of IEA/AIE12,Dalian,China,2012 13 Wu C W,Lin Y F,Yu P S,et al.Mining high utility episodes in complex event sequences.Proceedings of the 19th ACM SIGKDD International Conference on KnowledgeDiscoveryand Data Mining,Chicago Illinois,USA,2013 14 Wu C W,Shie B E,Tseng V S,et al.Mining top-Khigh utility itemsets.Proceedings of SIG KDD,Beijing,China,2012 15 Liu M,Qu J.Mining high utility itemsets without candidate generation.Proceedings of CIKM,Maui,HI,USA,2012
5 基于稀疏矩陣和虛擬投影的效用信息表達
5.1 基于稀疏矩陣的效用信息表達
5.2 基于虛擬投影的模式效用信息計算
6 單階段挖掘高效用模式
7 實驗評價
7.1 效用挖掘的效果評價
7.2 算法效率評價
7.3 存儲開銷和伸縮性評價
8 結束語
