亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        含負(fù)項(xiàng)top-k高效用項(xiàng)集挖掘算法

        2021-09-09 08:09:26張春硯申明堯杜詩(shī)語(yǔ)
        計(jì)算機(jī)應(yīng)用 2021年8期
        關(guān)鍵詞:項(xiàng)集事務(wù)效用

        孫 蕊,韓 萌,張春硯,申明堯,杜詩(shī)語(yǔ)

        (北方民族大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,銀川 750021)

        0 引言

        近年來(lái),數(shù)據(jù)挖掘技術(shù)引起了信息產(chǎn)業(yè)的極大關(guān)注。其中,頻繁項(xiàng)集挖掘是數(shù)據(jù)挖掘的重要組成部分之一。頻繁項(xiàng)集[1]的目標(biāo)是發(fā)現(xiàn)滿(mǎn)足最小支持度閾值的所有項(xiàng)集。但是,在實(shí)際應(yīng)用中,頻繁項(xiàng)集挖掘算法具有一定的局限性。它假定所有項(xiàng)具有相等的價(jià)值,并且每個(gè)項(xiàng)在每次事務(wù)中出現(xiàn)的次數(shù)不超過(guò)一次。但是,這兩個(gè)假設(shè)在現(xiàn)實(shí)生活中不是普遍存在的。例如,客戶(hù)購(gòu)買(mǎi)6袋面包和1臺(tái)電腦,客戶(hù)購(gòu)買(mǎi)多個(gè)相同的商品非常普遍,而出售面包和電腦的利潤(rùn)卻有所不同。為了解決這一問(wèn)題,研究人員提出了高效用項(xiàng)集挖掘算法。高效用項(xiàng)集(High Utility Iteme,HUI)[2]挖掘算法的主要目標(biāo)是通過(guò)考慮用戶(hù)的偏好(例如利潤(rùn)、數(shù)量和成本)來(lái)挖掘效用值高的項(xiàng)集。高效用項(xiàng)集挖掘算法克服了頻繁項(xiàng)集挖掘算法帶來(lái)的限制,在挖掘過(guò)程中,項(xiàng)的數(shù)量可能出現(xiàn)多次,并且每個(gè)項(xiàng)都有不同的價(jià)值。由于高效用項(xiàng)集挖掘算法缺乏向下閉合屬性,因此搜索空間很難縮小。隨后,Liu等[2]提出了一種Two-Phase算法,該算法使用向下閉合屬性來(lái)減小搜索空間,并有效地找到高效用項(xiàng)集。隨后,研究人員提出了IHUP(Incremental High Utility Pattern)[3]、TWU(Transaction Weighted Utility)-Mining[4]、IIDS(Isolated Items Discarding Strategy)[5]、UP-Growth(Utility Pattern Growth)[6]、UP-Growth+[7]算法。但是,以上提出的算法在挖掘過(guò)程中會(huì)生成大量的候選項(xiàng)集,這導(dǎo)致了算法執(zhí)行時(shí)間長(zhǎng)和內(nèi)存消耗大的問(wèn)題。Liu等[8]提出了一階段HUI-Miner(High Utility Itemset Miner)算法,該算法依賴(lài)效用列表結(jié)構(gòu),可以有效地修剪大部分搜索空間。

        對(duì)于高效用項(xiàng)集挖掘算法,研究人員進(jìn)行了許多研究。但是,絕大多數(shù)算法都是挖掘含有正效用的項(xiàng)集。在現(xiàn)實(shí)生活中,負(fù)效用項(xiàng)集也起著重要作用。例如,當(dāng)客戶(hù)去超市購(gòu)買(mǎi)計(jì)算機(jī)時(shí),客戶(hù)可以免費(fèi)獲得鍵盤(pán)和鼠標(biāo)。假設(shè)超市從每臺(tái)計(jì)算機(jī)上獲利50美元,鍵盤(pán)和鼠標(biāo)損失2美元,那么超市最終營(yíng)利48美元。因此,負(fù)效用在現(xiàn)實(shí)生活中也具有重要意義。但是,大多數(shù)高效用項(xiàng)集挖掘算法都只挖掘正效用項(xiàng)集,如果用該類(lèi)算法挖掘負(fù)效用項(xiàng)集,則會(huì)出現(xiàn)結(jié)果集遺漏問(wèn)題。

        針對(duì)傳統(tǒng)的高效用項(xiàng)集挖掘算法只能挖掘正效用項(xiàng)集的局限性,研究人員提出了挖掘單位利潤(rùn)為負(fù)效用項(xiàng)集的算法。但是,在挖掘高效用項(xiàng)集時(shí),最小效用閾值的設(shè)置問(wèn)題始終是一個(gè)挑戰(zhàn)。如果最小效用閾值設(shè)置得太低,將產(chǎn)生大量的高效用項(xiàng)集,這將降低用戶(hù)使用效率;如果最小效用閾值設(shè)置得太高,將生成很少的高效用項(xiàng)集,這將無(wú)法滿(mǎn)足用戶(hù)的需求;反復(fù)調(diào)整最小效用閾值將花費(fèi)大量的時(shí)間。

        為了克服這些局限,本文提出了含負(fù)項(xiàng)top-k高效用項(xiàng)集(Top-kHigh utility itemsets with Negative items,THN)挖掘算法。該算法不需要設(shè)置最小效用閾值,只需要設(shè)置k值,就能得到用戶(hù)需求效用值最高的項(xiàng)集結(jié)果集合。本文的主要工作如下:

        1)提出含負(fù)項(xiàng)top-k高效用項(xiàng)集挖掘算法——THN,該算法可以解決在挖掘同時(shí)含有正項(xiàng)和負(fù)項(xiàng)項(xiàng)集時(shí)需要設(shè)置最小效用閾值的問(wèn)題;

        2)該算法采用模式增長(zhǎng)方法,使用重新定義的子樹(shù)效用和重新定義的本地效用修剪大量沒(méi)有希望的候選項(xiàng)集;該算法利用事務(wù)合并和數(shù)據(jù)集投影技術(shù),提高了算法的時(shí)空性能;為了加快效用計(jì)數(shù)過(guò)程,該算法利用效用數(shù)組計(jì)數(shù)技術(shù)計(jì)算項(xiàng)集效用;

        3)該算法提出了自動(dòng)提升最小效用閾值的策略,實(shí)驗(yàn)結(jié)果表明,該策略可以明顯減少算法的執(zhí)行時(shí)間。

        1 相關(guān)工作

        目前,國(guó)內(nèi)外研究者對(duì)含負(fù)項(xiàng)高效用項(xiàng)集挖掘算法和top-k高效用項(xiàng)集挖掘算法進(jìn)行了研究。

        1.1 含負(fù)項(xiàng)高效用項(xiàng)集

        針對(duì)傳統(tǒng)的高效用項(xiàng)集挖掘算法只能挖掘含正項(xiàng)集的局限性,2009年Chu等[9]提出含負(fù)項(xiàng)的高效用項(xiàng)集挖掘算法HUINIV(High Utility Itemsets with Negative Item Values)-Mine。HUINIV-Mine算法是Two-Phase算法的擴(kuò)展,它需要在內(nèi)存中維護(hù)大量的項(xiàng)集,因此這嚴(yán)重影響了算法的效率。2011年,Li等[10]提出了MHUI-BIT(Mining High-Utility Itemsets based on BITvector)、MHUI-TID(Mining High-Utility Itemsets based on TIDlist)算法來(lái)挖掘含負(fù)項(xiàng)的高效用項(xiàng)集。但是,該算法還是存在產(chǎn)生候選項(xiàng)集過(guò)多的問(wèn)題。Lin等[11]隨后提出了FHN(Faster High utility itemset miner with Negative unit profits)算法,該算法使用深度優(yōu)先的搜索策略,并使用基于效用列表的EUCS(Estimated Utility Co-occurrence Structure)來(lái)有效地修剪搜索空間。實(shí)驗(yàn)結(jié)果表明,F(xiàn)HN算法的執(zhí)行時(shí)間是HUINIVMine算法的1/500,內(nèi)存消耗是它的1/250。2014年,Lan等[12]提出了TS-HOUN(Three-Scan mining approach to efficiently find High On-shelf Utility itemset with Negative profit values)算法,該算法提出挖掘同時(shí)考慮貨架時(shí)間和含負(fù)項(xiàng)集的高效用項(xiàng)集。TS-HOUN算法采用三階段挖掘方法,在每個(gè)時(shí)間段挖掘項(xiàng)集,然后使用合并操作合并每個(gè)時(shí)間段的項(xiàng)集。由于多次掃描數(shù)據(jù)集,因此TS-HOUN效率很低。

        為了解決多次掃描數(shù)據(jù)集的問(wèn)題,F(xiàn)OSHU(Faster On-Shelf High Utility itemset miner)[13]算法使用了基于效用列表的結(jié)構(gòu),該結(jié)構(gòu)同時(shí)挖掘所有時(shí)間段的項(xiàng)集。實(shí)驗(yàn)結(jié)果表明,F(xiàn)OSHU算法的執(zhí)行時(shí)間是TS-HOUN算法的千分之一,F(xiàn)OSHU算法的內(nèi)存消耗是TS-HOUN算法的十分之一。2017年,Dam等[14]提出了FOSHU的擴(kuò)展算法KOSHU(top-KOn-Shelf High Utility itemset miner)。2015年,Subramanian等[15]提出 了UP-GNIV(Utility Pattern-Growth approach for Negative Item Values)算法來(lái)挖掘含負(fù)項(xiàng)的高效用項(xiàng)集。2017年,Xu等[16]提出了HUSP-NIV(High Utility Sequential Patterns with Negative Item Values)算法,該算法用于挖掘含負(fù)項(xiàng)的高效用序列項(xiàng)集。2017年,Krishnamoorthy等[17]提出挖掘含負(fù)項(xiàng)的高效用項(xiàng)集挖掘算法——GHUM(Generalized High Utility Mining),GHUM比FHN快一個(gè)數(shù)量級(jí)。2017年,Gan等[18]提出 了HUPNU(High Utility patterns with both Positive and Negative unit profits from Uncertain data)算法,用于從不確定數(shù)據(jù)集中挖掘含負(fù)項(xiàng)的高效用項(xiàng)集。2018年,Singh等[19]提出了EHIN(Efficient High-utility Itemsets mining with Negative utility)算法來(lái)挖掘含負(fù)項(xiàng)的高效用項(xiàng)集,EHIN算法提出了多種有效的數(shù)據(jù)結(jié)構(gòu)和修剪策略。同年,Singh等[20]提出了CHN(Closed High utility itemsets mining with Negative utility)算法來(lái)挖掘含負(fù)項(xiàng)閉合高效用項(xiàng)集。2019年,Singh等[21]提出了EHNL(Efficient High utility itemsets mining with Negative utility and Length constraints)算法來(lái)挖掘含負(fù)項(xiàng)和長(zhǎng)度約束的高效用項(xiàng)集。

        盡管上述所有的算法都可以挖掘含負(fù)項(xiàng)的高效用項(xiàng)集,但是難以解決挖掘出滿(mǎn)足用戶(hù)需求的高效用項(xiàng)集數(shù)量的問(wèn)題。

        1.2 top-k高效用項(xiàng)集

        top-k高效用項(xiàng)集挖掘算法不需要設(shè)置最小效用閾值,直接根據(jù)用戶(hù)設(shè)置的高效用項(xiàng)集數(shù)量k進(jìn)行挖掘。最早的top-k高效用項(xiàng)集挖掘算法是TKU(Top-KUtility itemsets mining)[22],它是UP-Growth算法的擴(kuò)展。TKU算法采用Two-Phase模型:在第一階段,該算法使用多種策略來(lái)提高內(nèi)部的最小效用閾值,并對(duì)搜索空間進(jìn)行修剪,生成潛在的top-k高效用項(xiàng)集;在第二階段,從潛在的top-k高效用項(xiàng)集集合中識(shí)別真正的top-k高效用項(xiàng)集。TKU算法使用SE(Sorting candidates and raising threshold by the Exact utility of candidates)策略對(duì)候選項(xiàng)集進(jìn)行排序并提高內(nèi)部最小效用閾值。為了提高TKU的性能,Ryang等[23]提出了一種名為REPT(Raising threshold with Exact and Pre-calculated utilities for Top-khigh utility pattern mining)的算法,REPT算法依賴(lài)于UP(Utility Pattern)-Tree結(jié)構(gòu),通過(guò)使用額外的策略來(lái)快速提高邊界最小效用閾值,從而提高TKU的性能。由于TKU和REPT算法遵循Two-Phase模型,所以它們?nèi)匀划a(chǎn)生了大量的候選項(xiàng)集。Zihayat等[24]提出了T-HUDS(Top-kHigh Utility patterns over sliding windows of a Data Stream)算法,用于在數(shù)據(jù)流上挖掘top-k高效用項(xiàng)集,THUDS提出了一種新的前綴效用模型,該模型采用HUDS(High Utility patterns over sliding windows of a Data Stream)-tree的壓縮數(shù)據(jù)結(jié)構(gòu)。陳明福[25]提出了縮小候選項(xiàng)集TKDC(Top-Kpattern mining with Decreased Candidate)算法,該算法節(jié)省了大量的運(yùn)行時(shí)間。

        為了克服兩階段算法的局限性,研究者提出了一階段高效用項(xiàng)集挖掘算法。Lu等[26]提出了在數(shù)據(jù)流中挖掘top-k高效用項(xiàng)集的TOPK-SW(Sliding Window based TOP-K)算法,該算法將每批數(shù)據(jù)存儲(chǔ)在當(dāng)前窗口中,并將項(xiàng)的效用信息存儲(chǔ)在HUI-Tree中,而無(wú)需再次掃描數(shù)據(jù)集。王樂(lè)等[27]提出了一種TOPKHUP(TOP-kHigh Utility Pattern)算法,該算法有效地將項(xiàng)集和項(xiàng)集效用信息保存到HUP-Tree中,從而確??梢灾苯油诰騮op-k高效用項(xiàng)集。Tseng等[28]提出了TKO(Top-Kutility itemsets in One phase)算法來(lái)挖掘top-k高效用項(xiàng)集,TKO利用了HUI-Miner的效用列表結(jié)構(gòu),還提出了新的剪枝策略RUC(Raising the threshold by the Utilities of Candidates)、RUZ(Reducing estimated Utility values by using Z-elements)和EPB(Exploring the most Promising Branches first)來(lái)提高算法的性能。實(shí)驗(yàn)結(jié)果表明,該算法的性能優(yōu)于TKU和REPT算法。Duong等[29]提出一階段算法kHMC(top-kHigh utility itemset Mining using Co-occurrence pruning),它依賴(lài)于效用列表結(jié)構(gòu),采用多種策略提升最小效用閾值。Singh等[30]提出了TKEH(Efficient algorithm for mining Top-KHigh utility itemsets)算法,該算法使用事務(wù)合并和數(shù)據(jù)集投影技術(shù)來(lái)降低數(shù)據(jù)集掃描的成本。Kumari等[31]提出了TKRHU(Top-KRegular High Utility itemset)算法,該算法使用RUL(Regular Utility-Lists)效用列表結(jié)構(gòu)來(lái)存儲(chǔ)每個(gè)規(guī)則表的規(guī)則信息和效用信息。Krishnamoorthy等[32]提出THUI(top-kHigh Utility Itemset)高效用項(xiàng)集挖掘算法,該算法使用LIU(Leaf Itemset Utility)結(jié)構(gòu)來(lái)提高挖掘效率。實(shí)驗(yàn)結(jié)果表明,在大型、密集和事務(wù)平均長(zhǎng)度較長(zhǎng)的數(shù)據(jù)集上具有更好的性能。

        top-k高效用項(xiàng)集挖掘算法雖然可以不需要設(shè)置最小效用閾值就可以挖掘出用戶(hù)需求的高效用項(xiàng)集的數(shù)量,但是目前還沒(méi)有出現(xiàn)top-k高效用項(xiàng)集挖掘算法挖掘含負(fù)項(xiàng)的項(xiàng)集。

        2 基本概念

        事務(wù)數(shù)據(jù)集D由眾多事務(wù)組成,每條事務(wù)包含一些項(xiàng),每條事務(wù)都由唯一的事務(wù)標(biāo)識(shí)符Tid表示。I={i1,i2,…,in}指的是出現(xiàn)在事務(wù)數(shù)據(jù)集D中的不同項(xiàng)的集合。如表1所示,事務(wù)數(shù)據(jù)集D包含7條事務(wù)D={T1,T2,…,T7}和5個(gè)項(xiàng)I={A,B,C,D,E}。事務(wù)Tj∈D中項(xiàng)x的內(nèi)部效用指的是事務(wù)Tj中x的數(shù)量,表示為IU(x,Tj)。事務(wù)Tj∈D中項(xiàng)x的外部效用指的是事務(wù)Tj中x的利潤(rùn),表示為EU(x)。如表1所示,事務(wù)T1中項(xiàng)A的內(nèi)部效用為2;表2顯示了項(xiàng)的外部效用值,其中項(xiàng)A的外部效用值為2。

        表1 事務(wù)數(shù)據(jù)集Tab.1 Transaction dataset

        表2 外部效用值Tab.2 External utility values

        定義1 項(xiàng)在事務(wù)中的效用[2]。項(xiàng)x在事務(wù)Tj中的效用定義為U(x,Tj)=IU(x,Tj)×EU(x)。

        例如,TWU(D)=TU(D,T1)+TU(D,T3)+TU(D,T4)+TU(D,T6)=5+9+9+14=37。

        定義6 高效用項(xiàng)集[2]。假定min_util是用戶(hù)設(shè)置的最小效用閾值。如果項(xiàng)集X的效用值不小于min_util,則項(xiàng)集X是高效用項(xiàng)集;否則,它是一個(gè)低效用項(xiàng)集。

        定義7 top-k高效用項(xiàng)集[22]。按照項(xiàng)集效用值從高到低的順序排序,令min_util為第k個(gè)項(xiàng)集的效用值。對(duì)于項(xiàng)集X,如果條件項(xiàng)集X的效用值不小于min_util,則項(xiàng)集X稱(chēng)為top-k高效用項(xiàng)集。

        2.1 負(fù)項(xiàng)的屬性和定義

        在傳統(tǒng)的高效用項(xiàng)集挖掘算法中,大多數(shù)都是挖掘含有正項(xiàng)的項(xiàng)集。但是,挖掘含有負(fù)項(xiàng)的高效用項(xiàng)集時(shí),研究者提出了幾種處理負(fù)項(xiàng)集的屬性和定義。

        屬性1 項(xiàng)集中的正效用和負(fù)效用之間的關(guān)系[9]。對(duì)于任何項(xiàng)集X,假定putil(X)表示事務(wù)或數(shù)據(jù)集中項(xiàng)集X的正效用之和,并假定nutil(X)表示事務(wù)或數(shù)據(jù)集中項(xiàng)集X的負(fù)效用之和。U(X)=putil(X)+nutil(X)。從以上屬性可以得到,putil(X)≥U(X)≥nutil(X)。

        基本原理 項(xiàng)集X中效用值為正的項(xiàng)只能提高項(xiàng)集X的效用,而效用值為負(fù)的項(xiàng)只能降低項(xiàng)集X的效用。因此,屬性putil(X)≥U(X)≥nutil(X)成立。

        屬性2 使用正效用對(duì)項(xiàng)集的效用上限[9]。項(xiàng)集X的效用上限為putil(X)。

        基本原理 因?yàn)閁(X)=putil(X)+nutil(X),而nutil(X)是要減小U(X),所以上述推理成立。

        傳統(tǒng)的高效用項(xiàng)集挖掘算法使用TWU屬性來(lái)修剪搜索空間。但是,TWU屬性不能修剪含有負(fù)項(xiàng)的項(xiàng)集,因?yàn)門(mén)WU屬性假定修剪時(shí)不存在含有負(fù)項(xiàng)。為了解決這一挑戰(zhàn),HUINIV-Mine[9]重新定義了相關(guān)概念。

        例如,事務(wù)T2的重新定義的事務(wù)效用為RTU(T2)=U(C,T2)+U(E,T2)=5+1=6。通過(guò)添加僅計(jì)算重新定義的事務(wù)效用的項(xiàng)來(lái)增加了正項(xiàng)效果。表4顯示了每條事務(wù)的事務(wù)效用和重新定義的事務(wù)效用。

        表4 事務(wù)效用和重新定義的事務(wù)效用Tab.4 Transaction utility and redefined transaction utility

        例如,RTWU(A)=RTU(A,T1)+RTU(A,T5)+RTU(A,T6)=11+4+17=32。

        使用重新定義的事務(wù)加權(quán)效用修剪搜索空間,可以找到含負(fù)項(xiàng)高效用項(xiàng)集的完整高效用項(xiàng)集。事務(wù)中的項(xiàng)按總順序排序,因?yàn)镽TWU按升序排序。

        定義10 項(xiàng)集的擴(kuò)展[19]。如果Y=α∪{X}(其中X∈2E(α),X不能為空),則項(xiàng)集α可以擴(kuò)展為項(xiàng)集Y(Y出現(xiàn)在集合枚舉樹(shù)的重新定義的子樹(shù)中)。另外,項(xiàng)集α擴(kuò)展了單個(gè)項(xiàng)集Y(Y是集合枚舉樹(shù)中α的子代)。其中X∈E(α),Y=α∪{X}。在運(yùn)行的示例中,α={B},集合E(α)為{C,D},詞典α的單項(xiàng)展開(kāi)為{B,C}和{B,D},α的其他擴(kuò)展是{B,C,D}。

        定義11 負(fù)項(xiàng)的擴(kuò)展項(xiàng)集[19]。項(xiàng)集α可以擴(kuò)展到項(xiàng)集Y,其中Y=α∪{X},并且X是含負(fù)項(xiàng)的一組項(xiàng)。

        基本原理α∪{X}僅以少于或等于包含項(xiàng)集α的事務(wù)數(shù)量發(fā)生。項(xiàng)集X包含正項(xiàng)項(xiàng)集,并且其擴(kuò)展可能大于或等于或小于項(xiàng)集X的效用。項(xiàng)集X包含負(fù)項(xiàng)項(xiàng)集,并且其擴(kuò)展必須小于項(xiàng)集X的效用。從上面的描述,可以得出結(jié)論,如果項(xiàng)集X的效用值不小于min_util,則將負(fù)項(xiàng)集添加到項(xiàng)集X。如果擴(kuò)展項(xiàng)集X的效用值仍大于或等于min_util,則該項(xiàng)集為高效用項(xiàng)集。

        2.2 剪枝策略

        THN算法采用重新定義的本地效用和重新定義的子樹(shù)效用對(duì)搜索空間進(jìn)行了有效的修剪,基于這兩種方法該算法的效率得到了有效地提升。

        屬性3 基于重新定義本地效用的高估[19]。對(duì)于項(xiàng)集α和項(xiàng)x,其中x∈E(α)。令x可以是α的擴(kuò)展,即x∈X。因此,RLU(α,x)≥U(X)始終成立。詳細(xì)證明見(jiàn)文獻(xiàn)[14]。

        這是使用重新定義的本地效用修剪搜索空間的方法。對(duì)于項(xiàng)集α和項(xiàng)x,其中x∈E(α)。如果RLU(α,x)

        屬性4 基于重新定義子樹(shù)效用的高估[19]。令項(xiàng)集α和項(xiàng)x,其中x∈E(α)。RSU(α,x)的效用值大于等于U(α∪{x}),則相應(yīng)的取值。其中,RSU(α,x)≥U(x)保持α∪{x}的擴(kuò)展X。

        使用RSU修剪空間。設(shè)項(xiàng)集α和項(xiàng)x,其中x∈E(α)。如果RSU(α,x)小于min_util,則將項(xiàng)集擴(kuò)展為單項(xiàng)(α∪{x}),并擴(kuò)展低子樹(shù)效用值。此外,在集合枚舉樹(shù)中修剪α∪{x}的子樹(shù),可以修剪項(xiàng)集α的子樹(shù)。

        目前,高效用項(xiàng)集挖掘算法在挖掘高效用項(xiàng)集時(shí)通常使用剩余效用進(jìn)行剪枝。在利用剩余效用進(jìn)行剪枝的過(guò)程中,如果項(xiàng)集α帶有項(xiàng)x的效用小于min_util,則只刪除子節(jié)點(diǎn)。在利用重新定義的子樹(shù)效用進(jìn)行剪枝的過(guò)程中,如果項(xiàng)集α帶有項(xiàng)x的效用小于min_util,則刪除子項(xiàng)集。因此,使用重新定義的子樹(shù)效用進(jìn)行修剪時(shí),將極大地提高算法的性能。

        定義14 主要項(xiàng)和次要項(xiàng)[19]。對(duì)于項(xiàng)集α,項(xiàng)集α的主要項(xiàng)表示為Primary(α)={x|x∈E(α)∧RSU(α,x)≥min_util}。項(xiàng) 集α的 次 要 項(xiàng) 表 示 為Secondary(α)={x|x∈E(α)∧RLU(α,x)≥min_util}。其 中RLU(α,x)≥RSU(α,x),因此Primary(α)?Secondary(α)。

        3 THN算法

        本章詳細(xì)介紹了THN算法,包括使用的事務(wù)合并和投影數(shù)據(jù)集技術(shù)、使用效用數(shù)組計(jì)算效用上界的方法、提出的閾值提升策略和THN算法的偽代碼。

        3.1 數(shù)據(jù)集掃描技術(shù)

        該算法利用事務(wù)合并和數(shù)據(jù)集投影技術(shù)減小數(shù)據(jù)集的大小,從而降低了數(shù)據(jù)集的掃描成本。投影數(shù)據(jù)集只被掃描一次,以合并相同的事務(wù)。

        表5 事務(wù)合并后的數(shù)據(jù)集Tab.5 Dataset after transaction merging

        定義16 投影數(shù)據(jù)集[19]。對(duì)于項(xiàng)集α,投影數(shù)據(jù)集D表示為α-D,定義為α?D={α?T|T∈D∧α?T≠0}。

        為了進(jìn)一步壓縮數(shù)據(jù)集,本文算法需要合并投影數(shù)據(jù)集中的事務(wù)。投影事務(wù)合并比原始事務(wù)合并產(chǎn)生更高的數(shù)據(jù)集縮減量,因?yàn)橥队笆聞?wù)比原始事務(wù)小,因此,投影事務(wù)更有可能是相同的。

        表6 項(xiàng)C投影數(shù)據(jù)集Tab.6 Projected dataset of item C

        表7 事務(wù)合并投影后的數(shù)據(jù)集Tab.7 Dataset after transaction merging projection

        為了減小數(shù)據(jù)集的大小,需要使用事務(wù)合并技術(shù)。實(shí)現(xiàn)此技術(shù)的主要問(wèn)題是識(shí)別相同的事務(wù)。為了實(shí)現(xiàn)這一點(diǎn),本文算法需要相互比較所有的事務(wù)。將所有事務(wù)與每個(gè)事務(wù)進(jìn)行比較的技術(shù)并不是一種有效的技術(shù)。為了解決這個(gè)問(wèn)題,本文算法可以采用文獻(xiàn)[33]中提出的相同事務(wù)排序技術(shù)?T。這種排序技術(shù)在計(jì)算上并不昂貴。

        定義18 事務(wù)的總順序[33]。在事務(wù)數(shù)據(jù)集D中,當(dāng)向后讀取事務(wù)時(shí),總順序?T被定義為字典順序。有關(guān)?T的更多闡述可以參考文獻(xiàn)[33]。

        為了降低數(shù)據(jù)集掃描的成本,THN算法使用了事務(wù)合并和數(shù)據(jù)集投影技術(shù)。當(dāng)數(shù)據(jù)集包含相同的事務(wù)時(shí),事務(wù)合并技術(shù)識(shí)別這些相同的事務(wù),并將其替換為單條事務(wù)。事務(wù)合并技術(shù)是減小數(shù)據(jù)集大小的理想方法。數(shù)據(jù)集投影技術(shù)使較長(zhǎng)的事務(wù)變得較短,當(dāng)搜索較長(zhǎng)的項(xiàng)集時(shí),投影數(shù)據(jù)集的大小也會(huì)減小,從而降低了數(shù)據(jù)集掃描成本。目前,F(xiàn)HN算法使用垂直數(shù)據(jù)集且沒(méi)有使用事務(wù)合并技術(shù)。

        3.2 效用數(shù)組結(jié)構(gòu)

        定義19 效用數(shù)組[19]。I是數(shù)據(jù)集D中出現(xiàn)的一組項(xiàng),UA是一個(gè)長(zhǎng)度為||I的數(shù)組,其中每個(gè)項(xiàng)x∈I都有一個(gè)表示為UA[x]的條目。每個(gè)條目稱(chēng)為UA,用于存儲(chǔ)效用值。

        1)用UA計(jì)算RLU(α)。

        首先,UA初始化為0。其次,對(duì)于數(shù)據(jù)集D的每個(gè)事務(wù)Tj,所有項(xiàng)x∈Tj∩E(α)的UA[x]計(jì)算為UA[x]=UA[x]+U(α,T)+RU(α,T)。掃 描 數(shù) 據(jù) 集 后,UA[x]包 含RLU(α,k),?k∈E(α)。

        2)用UA計(jì)算RSU(α)。

        3.3 閾值提升策略

        top-k高效用項(xiàng)集挖掘算法的主要問(wèn)題局限是,沒(méi)有預(yù)先提供min_util,運(yùn)行時(shí)的min_util從0或1開(kāi)始,這嚴(yán)重降低了算法的效率。因此,這為如何自動(dòng)提升min_util而不丟失任何高效用項(xiàng)集帶來(lái)了巨大的挑戰(zhàn)。為了解決這個(gè)問(wèn)題,本文提出了有效的RTWU_strategy閾值提升策略。

        RTWU_strategy閾值提升策略的詳細(xì)過(guò)程如下所述。首先,在第一次掃描事務(wù)數(shù)據(jù)集時(shí),計(jì)算此過(guò)程中所有項(xiàng)的RTWU(x)。例如,項(xiàng)A同時(shí)出現(xiàn)在事務(wù)T1、T5和T6中。項(xiàng)A在事務(wù)T1、T5和T6中的RTWU為RTWU(A)=RTU(T1)+RTU(T5)+RTU(T6)=32。根據(jù)此方法,計(jì)算所有項(xiàng)的RTWU(x)。然后,令RTWU={RTWU1,RTWU2,…,RTWUn}為I中項(xiàng)的效用列表。接下來(lái)根據(jù)定義18中的排序規(guī)則,對(duì)RTWU效用列表進(jìn)行排序。然后,RTWU_strategy將已排序的RTWU效用列表中的min_util提升到第k個(gè)最大值?,F(xiàn)在,使用這個(gè)新值作為min_util。例如,假設(shè)用戶(hù)將k值設(shè)置為5,然后掃描數(shù)據(jù)集并計(jì)算項(xiàng)的RTWU(x)。假設(shè)效用列表中RTWU的第5個(gè)值是88,那么,min_util提高到88。然后,該算法使用這個(gè)新的min_util。最后,直至找到用戶(hù)需求的效用值最高的前k個(gè)項(xiàng)集,RTWU_strategy閾值提升策略的偽代碼如算法1所示。

        算法1 RTWU_strategy。

        輸入:所有項(xiàng)的RTWU集合,k:所需的高效用項(xiàng)集的數(shù)量;

        輸出:提升min_util。

        1)SortRTWUvalues;

        2)Setmin_utilto thekthlargestRTWUvalue;

        3)returnmin_util.

        3.4 THN算法描述

        本文提出的THN算法利用了前面介紹的幾種策略。算法2為主算法,將事務(wù)數(shù)據(jù)集D和用戶(hù)定義的高效用項(xiàng)集的數(shù)量k作為輸入,輸出是top-k高效用項(xiàng)集。

        第1)至4)行分別表示初始化α為空項(xiàng)集,ρ表示一組正項(xiàng)集,η表示一組負(fù)項(xiàng)集,將min_util初始化為1。第5)行創(chuàng)建創(chuàng)建一個(gè)k大小的優(yōu)先隊(duì)列(名為k_Patterns)。第6)行掃描事務(wù)數(shù)據(jù)集D,同時(shí)使用UA技術(shù)計(jì)算所有項(xiàng)的RLU。第7)行通過(guò)比較每個(gè)項(xiàng)的RLU和min_util,可以獲得項(xiàng)集的次要項(xiàng),次要項(xiàng)作為項(xiàng)集的擴(kuò)展項(xiàng)。第8)行計(jì)算每個(gè)項(xiàng)的RTWU,并將結(jié)果存儲(chǔ)在hashMap中。第9)行調(diào)用RTWU_strategy,主要功能是自動(dòng)提升min_util。第10)行根據(jù)RTWU的升序?qū)?xiàng)集進(jìn)行排序。注意,當(dāng)按?T順序排序時(shí),該算法首先考慮正效用項(xiàng),然后考慮負(fù)效用項(xiàng)。第11)行掃描數(shù)據(jù)集D,并刪除事務(wù)中不是次要項(xiàng)的所有項(xiàng)集和空事務(wù)。根據(jù)重新定義的本地效用的剪枝策略,刪除的項(xiàng)不是高效用項(xiàng)集。第12)行根據(jù)字典排序?qū)κS嗍聞?wù)進(jìn)行排序,且正項(xiàng)集在負(fù)項(xiàng)集之前。此時(shí),根 據(jù)EFIM(efficient algorithm for high-utility itemset mining)[33]的建議,此處執(zhí)行事務(wù)合并技術(shù)。第13)行掃描數(shù)據(jù)集D,并使用UA技術(shù)計(jì)算所有項(xiàng)的RSU。第14)行通過(guò)比較每個(gè)項(xiàng)的RSU和min_util,可以獲得項(xiàng)集的主要項(xiàng)。第15)行通過(guò)調(diào)用算法3從項(xiàng)集α開(kāi)始遞歸執(zhí)行深度優(yōu)先搜索。THN算法的偽代碼算法2所示。

        算法2 THN算法。

        輸入:事務(wù)數(shù)據(jù)集D,潛在高效用項(xiàng)集的數(shù)量k;

        輸出:top-k高效用項(xiàng)集。

        1)α←?;

        2)ρ←set of positiveutility items inD;

        3)η←set of negativeutility items inD;

        4)min_util←1;

        5)Createa priority queuek_Patternsof sizek;

        6)Scan datasetD,computeRLU(α,X)for all itemsX∈ρ,usingUA[X];

        7)Secondary(α)={X|X∈ρ∧RLU(α,X)≥min_util};

        8)ComputeRTWU(X)for all itemsk∈Iand store theseRTWUvalues them in a hashMap;

        9)RTWU_strategy(hashMapRTWU,k);

        10)Let?Tbe the total order ofRTWUincreasing values onSecondary(α);

        11)ScanD,remove itemx?Secondary(α)from the transactionsTjand delete empty transactions;

        12)Sort all the remaining transactions in the datasetDaccording to?Twith positive utility items followed by negative utility items;

        13)ScanD,compute theRSU(α,X)of each itemx∈Secondary(α),usingUA[x];

        14)Primary(α)={X|X∈Secondary(α)∧RSU(α,X)≥min_util};

        15)Search_P(η,α,D,Primary(α),Secondary(α),min_util,k_Patterns);

        16)return top-kHUIs.

        算法3的輸入如下:η表示一組負(fù)項(xiàng)集,α為項(xiàng)集,α-D代表投影數(shù)據(jù)集,Primary(α)代表項(xiàng)集α的主要項(xiàng),Secondary(α)代表項(xiàng)集α的次要項(xiàng),min_util表示最小效用閾值,k_Patterns表示為k個(gè)項(xiàng)的優(yōu)先級(jí)隊(duì)列;輸出為前k個(gè)α項(xiàng)集擴(kuò)展的含正項(xiàng)高效用項(xiàng)集集合。

        算法3第1)~2)行只能找到具有正項(xiàng)的擴(kuò)展,每次都遞歸地調(diào)用自己用主要項(xiàng)來(lái)擴(kuò)展每個(gè)次要項(xiàng)α。單項(xiàng)集的擴(kuò)展技術(shù)遵循定義11。第3)行掃描數(shù)據(jù)集α-D,計(jì)算每個(gè)擴(kuò)展項(xiàng)集β的效用,然后構(gòu)造新的投影數(shù)據(jù)集β-D。在這個(gè)過(guò)程中,執(zhí)行事務(wù)合并與投影數(shù)據(jù)集技術(shù)。第4)行項(xiàng)集β的效用值不小于min_util,然后把它添加到優(yōu)先級(jí)隊(duì)列k模式中。同時(shí),將該min_util提升到優(yōu)先級(jí)隊(duì)列元素min_util的頂部。第6)行當(dāng)項(xiàng)集β的效用值大于min_util,則調(diào)用算法4用負(fù)項(xiàng)來(lái)擴(kuò)展該項(xiàng)集;否則,第8)行掃描投影數(shù)據(jù)集β-D,并使用UA技術(shù)計(jì)算每個(gè)項(xiàng)的RSU和RLU。第9~10)行找到項(xiàng)集β的主要和次要項(xiàng)。第11)~12)行算法3利用深度優(yōu)先搜索的方法反復(fù)執(zhí)行用主項(xiàng)對(duì)項(xiàng)集β的擴(kuò)展,一直執(zhí)行到滿(mǎn)足條件為止,Search_P算法的偽代碼如算法3所示。

        算法3 Search_P算法。

        輸入:一組負(fù)項(xiàng)η,項(xiàng)集α,投影數(shù)據(jù)集α-D,α的主要項(xiàng)Primary(α),α的次要項(xiàng)Secondary(α),最小效用閾值min_util,k個(gè)項(xiàng)的優(yōu)先級(jí)隊(duì)列k_Patterns;

        輸出:前k個(gè)α項(xiàng)集擴(kuò)展的含正項(xiàng)高效用項(xiàng)集集合。

        1)for each itemx∈Primary(α)do;

        2)β=α∪{x};

        3)Scanα-D,computeU(β),and createβ-D;

        4)ifU(β)≥min_utilthen addβink_Patterns.And raise themin_utilto the top of priority queueelement’sutility;

        5)end if

        6)ifU(β)>min_utilthen search_N(η,β,β-D,min_util,k_Patterns);

        7)end if

        8)Scanβ-D,computeRSU(β,x)andRLU(β,x)where itemx∈Secondary(α),using twoUAs;

        9)Primary(β)={x∈Secondary(α)|RSU(β,x)≥min_util};

        10)Secondary(β)={x∈Secondary(α)|RLU(β,x)≥min_util};

        11)search_P(η,β,β-D,Primary(β),Secondary(β),min_util,kPattens);

        12)end for.

        算法4的輸入如下:η表示一組負(fù)項(xiàng)集,α為項(xiàng)集,α-D是投影數(shù)據(jù)集,min_util表示最小效用閾值,k_Patterns:表示k個(gè)項(xiàng)的優(yōu)先級(jí)隊(duì)列;輸出為前k個(gè)α項(xiàng)集擴(kuò)展的含負(fù)項(xiàng)高效用項(xiàng)集集合。

        當(dāng)項(xiàng)集β的效用值大于min_util時(shí),算法4的調(diào)用條件才存在。第2)行該算法是使用負(fù)項(xiàng)進(jìn)行擴(kuò)展的。它使用定義11對(duì)所需項(xiàng)集負(fù)擴(kuò)展的搜索空間進(jìn)行修剪。第3)行掃描數(shù)據(jù)集α-D,計(jì)算每個(gè)擴(kuò)展項(xiàng)集β的效用,然后構(gòu)造新的投影數(shù)據(jù)集β-D。在這個(gè)過(guò)程中,執(zhí)行事務(wù)合并與投影數(shù)據(jù)集技術(shù)。第4)行項(xiàng)集β的效用值不小于min_util,然后把它添加到優(yōu)先級(jí)隊(duì)列k模式中。同時(shí),將該min_util提升到優(yōu)先級(jí)隊(duì)列元素min_util的頂部。第6)行掃描投影數(shù)據(jù)集β-D,并使用含負(fù)項(xiàng)UA技術(shù)計(jì)算每個(gè)項(xiàng)的RSU。第7)行找到項(xiàng)集β的主要項(xiàng)。第8)~9)行該算法將遞歸調(diào)用自身,用負(fù)項(xiàng)對(duì)項(xiàng)集β進(jìn)行擴(kuò)展,一直執(zhí)行到滿(mǎn)足條件為止,Search_N算法的偽代碼如算法4所示。

        算法4 Search_N算法。

        輸入:一組負(fù)項(xiàng)η,項(xiàng)集α,投影數(shù)據(jù)集α-D,最小效用閾值min_util,k個(gè)項(xiàng)的優(yōu)先級(jí)隊(duì)列k_Patterns;

        輸出:前k個(gè)α項(xiàng)集擴(kuò)展的含負(fù)項(xiàng)高效用項(xiàng)集集合。

        1)for each itemx∈ηdo;

        2)β=α∪{x};

        3)Scanα-D,computeU(β),and createβ-D;

        4)ifU(β)≥min_utilthen addβink_Patterns.And raise themin_utilto the top of priority queue element’s utility;

        5)end if

        6)CalculateRSU(β,x)for all itemx∈ηby scanningβ-Donce,using thenegativeUA;

        7)Primary(β)={x∈η|RSU(β,x)≥min_util};

        8)search_N(β,β-D,Primary(β),min_util,k_Patterns);

        9)end for.

        3.5 THN算法示例

        在本節(jié)中,給出一個(gè)簡(jiǎn)單的說(shuō)明性示例,以展示THN算法如何從事務(wù)數(shù)據(jù)集中找到含負(fù)項(xiàng)top-k高效用項(xiàng)集。假設(shè)如表1所示的7條事務(wù),并且有5個(gè)項(xiàng)的內(nèi)部效用。同時(shí),表2顯示每個(gè)項(xiàng)的外部效用。此外,最終挖掘出的效用值最高項(xiàng)集的數(shù)量k被設(shè)置為20。THN算法從事務(wù)性數(shù)據(jù)集中挖掘高效用項(xiàng)集,THN算法首先計(jì)算事務(wù)中每一項(xiàng)的效用,并找到該事務(wù)的事務(wù)效用。例如,事務(wù)T2中有3個(gè)項(xiàng)B、C和E,它們的內(nèi)部效用值分別是1、5和1。表2中的B、C和E的外部效用分別為-3、1和1。那么T2中B、C和E的效用值可以分別計(jì)算為1*(-3)=(-3),5*1=5和1*1=1。經(jīng)過(guò)上述過(guò)程,可以計(jì)算出T2的TU為(-3)+5+1=3。所有事務(wù)的TU值結(jié)果如表3所示。為了過(guò)高估計(jì)效用,THN算法使用RTU。為了找到RTU,THN算法只計(jì)算正效用值為5+1,即在T2中為6。同樣,所有RTU都可以計(jì)算出來(lái)。所有事務(wù)的RTU如表4所示。RLU是使用深度優(yōu)先搜索計(jì)算的。運(yùn)行示例中項(xiàng)A的RTWU值出現(xiàn)在三個(gè)事務(wù)T1、T5和T6中,它們的RTU值分別為11、4和17。因此,項(xiàng)A的RTWU可計(jì)算為11+4+17=32。根據(jù)項(xiàng)的RLU不小于min_util,然后找到次要項(xiàng)集。Secondary={A,B,C,D,E}。在這之后,所有的項(xiàng)都按照RTWU升序排序,負(fù)項(xiàng)總是在正的項(xiàng)集之后。

        然后,不屬于次要項(xiàng)集的項(xiàng)被刪除。因此,沒(méi)有從示例數(shù)據(jù)集中刪除任何項(xiàng)。同時(shí),如果從事務(wù)中刪除了所有項(xiàng),則刪除那些空事務(wù)。然后對(duì)剩余的事務(wù)按總順序?T進(jìn)行排序。之后,本文提出的THN算法再次掃描數(shù)據(jù)集,計(jì)算所有項(xiàng)集的RSU。RSU不小于min_util的項(xiàng)位于主要項(xiàng)中。因此,Primary={A,C,D,E},只使用主要項(xiàng)集的項(xiàng)進(jìn)行深度優(yōu)先搜索。所有次要項(xiàng)集{A,C,D,E,B}的項(xiàng)作為每個(gè)子樹(shù)的子代節(jié)點(diǎn)。為此,使用深度優(yōu)先搜索來(lái)查找子樹(shù)中的下行節(jié)點(diǎn)。使用算法2和算法3對(duì)節(jié)點(diǎn)進(jìn)行挖掘,然后遞歸地調(diào)用算法2來(lái)擴(kuò)展所有具有正項(xiàng),然后調(diào)用算法3擴(kuò)展具有負(fù)項(xiàng)。在運(yùn)行的示例中,假設(shè)k值為20,最終的top-k高效用項(xiàng)集如表8所示。運(yùn)行示例的高效用項(xiàng)集是{{A}:12,{C}:14,{A,C,D}:16,{C,D}:31,{A,C,D,B}:13,{C,D,B}:16,{A,C,D,E}:17,{C,D,E}:37,{A,C,D,E,B}:14,{C,D,E,B}:19,{A,D}:20,{C,E}:23,{A,D,B}:11,{D}:28,{A,D,E}:24,{D,E}:37,{A,D,E,B}:15,{D,E,B}:15,{A,E}:12,{E}:12},其中每個(gè)項(xiàng)集旁邊的數(shù)字表示其效用值。

        表8 top-k高效用項(xiàng)集Tab.8 top-k high utility itemsets

        4 實(shí)驗(yàn)與結(jié)果分析

        為了測(cè)試THN算法的性能,本文做了大量的實(shí)驗(yàn)。通過(guò)擴(kuò)展spm f[34]上的開(kāi)源Java庫(kù),可以實(shí)現(xiàn)該實(shí)驗(yàn)。該實(shí)驗(yàn)運(yùn)行環(huán)境的CPU為3.00 GHz,內(nèi)存為256 GB,操作平臺(tái)是Windows 10企業(yè)版。該實(shí)驗(yàn)使用了六個(gè)真實(shí)的數(shù)據(jù)集mushroom、chess、accidents、pumsb、retail和kosarak,所有數(shù)據(jù)集都是從spm f上下載的。表9顯示了數(shù)據(jù)集的基本特征,每一列從左到右分別表示數(shù)據(jù)集名稱(chēng)、事務(wù)數(shù)量、項(xiàng)的個(gè)數(shù)和數(shù)據(jù)集密度。

        表9 數(shù)據(jù)集的基本特征Tab.9 Basic characteristicsof datasets

        對(duì)于所有的數(shù)據(jù)集,項(xiàng)的內(nèi)部效用值在1~5的范圍內(nèi)隨機(jī)生成,項(xiàng)的外部效用值使用對(duì)數(shù)正態(tài)分布在-1 000~10 000生成。為確保結(jié)果的穩(wěn)健性,本文所有的實(shí)驗(yàn)都進(jìn)行了10次,并統(tǒng)計(jì)了平均結(jié)果。

        4.1 實(shí)驗(yàn)設(shè)計(jì)

        本文為了評(píng)估所提出的技術(shù)在THN中的影響,因此檢驗(yàn)了THN(RSU-Prune)和THN(TM)的性能。THN算法同時(shí)利用了數(shù)據(jù)集合并技術(shù)TM和剪枝策略RSU。THN(RSU-Prune)僅在TM被禁用的情況下使用修剪策略RSU。類(lèi)似地,THN(TM)僅使用數(shù)據(jù)集合并技術(shù)TM,其中剪枝策略RSU是禁用這種變化。本文提出的THN算法是第一個(gè)挖掘含負(fù)項(xiàng)top-k高效用項(xiàng)集挖掘算法。因此,找不到具有相同性能的另一算法進(jìn)行比較。

        傳統(tǒng)上,測(cè)試新正項(xiàng)的top-k高效用項(xiàng)集挖掘算法是將其與挖掘相同結(jié)果集并設(shè)置最佳最小效用閾值的非top-k高效用項(xiàng)集挖掘算法進(jìn)行比較。對(duì)于新提出的THN算法,本文通過(guò)查找相關(guān)文獻(xiàn)得出,F(xiàn)HN算法[11]是挖掘含負(fù)項(xiàng)最先進(jìn)的高效用項(xiàng)集挖掘方法。HUINIV-Mine[9]算法也是產(chǎn)生負(fù)效用的高效用項(xiàng)集挖掘算法,但是HUINIV-Mine的執(zhí)行時(shí)間在有的數(shù)據(jù)集中無(wú)法在圖中畫(huà)出來(lái),因?yàn)樗枰嗟膱?zhí)行時(shí)間和內(nèi)存。因此,對(duì)比非top-k算法是HUINIV-Mine和FHN算法,這兩種算法均被用于挖掘含負(fù)項(xiàng)高效用項(xiàng)集。

        為了確保挖掘出相同的結(jié)果集,本文為HUINIV-Mine和FHN算法選擇了最佳min_util。這樣,可以以相同數(shù)量相同結(jié)果集的模式進(jìn)行性能比較。為了評(píng)估性能,本文通過(guò)提高k值來(lái)執(zhí)行所有數(shù)據(jù)集上的所有變化,直到所有的變化花費(fèi)太多的時(shí)間或內(nèi)存不足。

        4.2 執(zhí)行時(shí)間性能

        本節(jié)評(píng)估了THN算法和對(duì)比算法在所有數(shù)據(jù)集中的運(yùn)行時(shí)間性能。圖1顯示了THN算法和對(duì)比算法在所有數(shù)據(jù)集的運(yùn)行時(shí)間情況。從圖1中可以清楚地看到,在mushroom、chess、accidents和pumsb密集數(shù)據(jù)集中,THN算法的運(yùn)行時(shí)間遠(yuǎn)少于HUINIV-Mine、FHN算法。因?yàn)镠UINIV-Mine在chess和accidents數(shù)據(jù)集中,即使k值設(shè)置為1,也需要耗費(fèi)長(zhǎng)達(dá)數(shù)小時(shí)的執(zhí)行時(shí)間,因此在圖1中沒(méi)有畫(huà)出。在mushroom和pumsb數(shù)據(jù)集中,當(dāng)k的值設(shè)置得較大時(shí),THN算法與HUINIV-Mine、FHN算法之間的運(yùn)行時(shí)間間隔變大。在mushroom、chess、accidents和pumsb數(shù)據(jù)集中k的值小于100時(shí),THN算法和FHN算法的運(yùn)行時(shí)間沒(méi)有太大差異。當(dāng)k值超過(guò)500時(shí),mushroom、chess、accidents和pumsb數(shù)據(jù)集在FHN算法中的運(yùn)行時(shí)間會(huì)激增,而THN算法的運(yùn)行時(shí)間則相對(duì)穩(wěn)定。從圖5中可以看出,數(shù)據(jù)集掃描技術(shù)和基于重新定義子樹(shù)效用的剪枝技術(shù)相結(jié)合在密集數(shù)據(jù)集中得到了很好的使用。但是在mushroom、chess、accidents數(shù)據(jù)集中THN(TM)和THN(RSUPrune)總是比THN算法執(zhí)行時(shí)間長(zhǎng),但是在pumsb數(shù)據(jù)集中THN(TM)比THN算法執(zhí)行更少的時(shí)間。這種現(xiàn)象表明,事務(wù)合并對(duì)于具有大量不同項(xiàng)和項(xiàng)的平均長(zhǎng)度較大的數(shù)據(jù)集執(zhí)行得很好。從密集數(shù)據(jù)集中可以看出,當(dāng)k值設(shè)置較高時(shí),本文算法與FHN之間的差距較大,說(shuō)明本文算法比FHN運(yùn)行的k值更高。FHN的性能不好的主要原因是,它加入了較小項(xiàng)集的效用列表,以生成較大的項(xiàng)集。FHN考慮沒(méi)有出現(xiàn)在數(shù)據(jù)集中的項(xiàng)集,因?yàn)樗鼈兺ㄟ^(guò)合并較小的項(xiàng)集來(lái)探索項(xiàng)集的搜索空間,而不掃描數(shù)據(jù)集。由于密集的數(shù)據(jù)集包含大量的長(zhǎng)項(xiàng)和事務(wù),因此提出的THN算法性能更好。

        從圖1中可以清楚地看到,在retail和kosarak稀疏數(shù)據(jù)集中,F(xiàn)HN算法的運(yùn)行時(shí)間少于HUINIV-Mine和THN算法。在retail數(shù)據(jù)集中,隨著k值的增加,F(xiàn)HN算法的運(yùn)行時(shí)間幾乎不變。在retail數(shù)據(jù)集中當(dāng)k的值小于500時(shí),在kosarak數(shù)據(jù)集中當(dāng)k的值小于50時(shí),THN算法的運(yùn)行時(shí)間和FHN算法的運(yùn)行時(shí)間幾乎持平。在retail數(shù)據(jù)集中,THN(RSU-Prune)算法的執(zhí)行時(shí)間小于THN算法。這一結(jié)果表明,retail數(shù)據(jù)集不支持TM技術(shù)。Retail數(shù)據(jù)集有大量不同的項(xiàng),并且比所有其他數(shù)據(jù)集有更寬的最大長(zhǎng)度,因此它不支持TM技術(shù)。實(shí)驗(yàn)結(jié)果表明,在數(shù)據(jù)集高度稀疏的情況下,THN算法可以放棄TM技術(shù),有效地挖掘高效用項(xiàng)集。因此,在retail和kosarak稀疏數(shù)據(jù)集中,THN(TM)算法的性能遠(yuǎn)低于FHN算法。因?yàn)橄∈钄?shù)據(jù)集,它們具有大量不同的項(xiàng),幾乎沒(méi)有相同事務(wù)。由于在稀疏數(shù)據(jù)集中,事務(wù)數(shù)據(jù)庫(kù)中具有相同項(xiàng)的事務(wù)的概率顯著降低,所以事務(wù)合并策略變得開(kāi)銷(xiāo)很大。THN算法提出的事務(wù)合并技術(shù)在高度稀疏的數(shù)據(jù)集中表現(xiàn)不佳,事務(wù)合并需要大量時(shí)間來(lái)合并事務(wù),稀疏數(shù)據(jù)集中的相同事務(wù)較少,因此浪費(fèi)大量時(shí)間,效率很低。

        圖1 不同算法的運(yùn)行時(shí)間對(duì)比Fig.1 Comparison of runtimeof different algorithms

        4.3 內(nèi)存消耗性能

        本節(jié)評(píng)估了THN算法與對(duì)比算法在所有數(shù)據(jù)集中的內(nèi)存消耗的性能。圖2顯示了THN算法和對(duì)比算法在所有數(shù)據(jù)集的運(yùn)行時(shí)間情況。

        從圖2中可以清楚地看到,在所有密集數(shù)據(jù)集mushroom、chess、accidents和pumsb中,THN算法的內(nèi)存消耗值遠(yuǎn)低于HUINIV-Mine和FHN算法。在chess、accidents和pumsb密集數(shù)據(jù)集中,THN(TM)和THN(RSU-Prune)的內(nèi)存消耗遠(yuǎn)比HUINIV-Mine和FHN算法小。隨著k值的增加,F(xiàn)HN的內(nèi)存消耗迅速增加。對(duì)于mushroom密集數(shù)據(jù)集,THN算法的內(nèi)存消耗遠(yuǎn)小于HUINIV-Mine和FHN算法。但是,THN(TM)和THN(RSU-Prune)算法的內(nèi)存消耗大于FHN算法。在chess和accidents數(shù)據(jù)集中,隨著k值的增加,THN算法消耗的內(nèi)存幾乎保持不變,而FHN算法消耗的內(nèi)存是THN算法消耗的內(nèi)存的三倍。對(duì)于所有密集數(shù)據(jù)集,在THN算法中,TM技術(shù)和RSU技術(shù)可以更好地結(jié)合在一起。因此,THN算法比其他算法使用更少的內(nèi)存。HUINIV-Mine和THN算法在大多數(shù)情況下都需要高內(nèi)存,其中,因?yàn)镕HN算法將所有的效用列表保存在內(nèi)存中以進(jìn)行連接,因此需要消耗大量的內(nèi)存空間。

        從圖2可以清楚地看到,在稀疏數(shù)據(jù)集kosarsk中,THN算法的內(nèi)存消耗遠(yuǎn)遠(yuǎn)小于HUINIV-Mine和THN算法。THN(RSU-Prune)算法的內(nèi)存消耗也小于HUINIV-Mine和THN算法,可以看出RSU的剪枝策略在THN算法中得到很好的使用。但是,THN(TM)算法的內(nèi)存消耗大于THN算法,可以得出在稀疏數(shù)據(jù)集kosarsk中,TM技術(shù)并不能提高內(nèi)存消耗的性能。在retail數(shù)據(jù)集中,THN的內(nèi)存消耗遠(yuǎn)小于HUINIV-Mine算法。但是,在k值小于500時(shí),THN算法及其THN(TM)和THN(RSU-Prune)算法的內(nèi)存消耗比FHN多。因?yàn)?,retail數(shù)據(jù)集是高度稀疏的,所提出的算法對(duì)高度稀疏數(shù)據(jù)集不是有效的。THN采用的TM技術(shù)不適用于retail等高度稀疏的數(shù)據(jù)集。

        圖2 不同算法的內(nèi)存消耗對(duì)比Fig.2 Comparison of memory usageof different algorithms

        4.4 可擴(kuò)展性

        本節(jié)從算法的可擴(kuò)展性角度對(duì)所有算法進(jìn)行了實(shí)驗(yàn)。該實(shí)驗(yàn)選取了密集數(shù)據(jù)集accidents和稀疏數(shù)據(jù)集retail,實(shí)驗(yàn)數(shù)據(jù)大小20%~100%不等,k值設(shè)置為100。通過(guò)以上設(shè)置,可以更好地展示所有算法的可伸縮性。圖3顯示了THN算法的運(yùn)行時(shí)間隨著數(shù)據(jù)集大小的增加而線(xiàn)性增加。圖4顯示了THN算法隨著數(shù)據(jù)集大小的增加內(nèi)存消耗也線(xiàn)性增加,但在FHN算法中,內(nèi)存消耗則急劇增加。以上實(shí)驗(yàn)結(jié)果表明,THN算法在不同數(shù)據(jù)集和參數(shù)下都具有可擴(kuò)展性。

        圖3 不同算法運(yùn)行時(shí)間的可擴(kuò)展性Fig.3 Scalability of runtimeof different algorithms

        圖4 不同算法內(nèi)存消耗的可擴(kuò)展性Fig.4 Scalability of memory usageof different algorithms

        4.5 實(shí)驗(yàn)結(jié)論

        THN算法是挖掘含負(fù)項(xiàng)top-k高效用項(xiàng)集挖掘算法,使用基于RSU搜索空間的剪枝策略,為了減少數(shù)據(jù)集的掃描次數(shù),使用了事務(wù)合并和數(shù)據(jù)投影相結(jié)合的技術(shù)。該算法在四個(gè)密集數(shù)據(jù)集和兩個(gè)稀疏數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)。對(duì)比算法使用了本身的變形算法THN(TM)和THN(RSU-Prune),還有挖掘含有負(fù)項(xiàng)高效用項(xiàng)集挖掘算法HUINIV-Mine[9]和FHN[11]。

        由于在實(shí)驗(yàn)中為HUINIV-Mine和FHN算法設(shè)置min_util,這對(duì)于THN算法是不公平的,因?yàn)閠op-k高效用項(xiàng)集挖掘問(wèn)題總是比相應(yīng)的非top-k高效用項(xiàng)集問(wèn)題更困難。主要原因是非top-k高效用項(xiàng)集挖掘算法直接設(shè)置了最佳min_util,top-k高效用項(xiàng)集挖掘算法min_util開(kāi)始為0,然后逐漸增加min_util直到找到k個(gè)項(xiàng)集。非top-k高效用項(xiàng)集挖掘算法將在此過(guò)程中減少很大一部分搜索空間。在本實(shí)驗(yàn)中,本文直接為HUINIV-Mine和FHN算法設(shè)置了最佳min_util,這使得該算法具有很大的優(yōu)勢(shì)。對(duì)于每個(gè)不同的數(shù)據(jù)集,在運(yùn)行THN算法時(shí)會(huì)設(shè)置不同的k值。在不同的數(shù)據(jù)集上運(yùn)行HUINIV-Mine和FHN算法之前,將min_util設(shè)置為HUINIVMine和FHN算法以挖掘k個(gè)項(xiàng)集中的最小效用值。

        從實(shí)驗(yàn)結(jié)果可以看出,THN算法在mushroom、chess、accidents、pumsb和kosarak數(shù)據(jù)集的運(yùn)行時(shí)間效率上有了顯著提高,在retail數(shù)據(jù)集上的執(zhí)行時(shí)間是可比較的。HUINIVMine算法在accidents、chess、pumsb和kosarak數(shù)據(jù)集中,因?yàn)樾枰L(zhǎng)的執(zhí)行時(shí)間和內(nèi)存消耗而崩潰。因此,運(yùn)行時(shí)間和內(nèi)存消耗沒(méi)有顯示。此外,THN在所有數(shù)據(jù)集上的內(nèi)存改進(jìn)是相當(dāng)顯著的。與HUINIV-Mine和FHN算法相比,THN在除retail外的所有數(shù)據(jù)集上的運(yùn)行時(shí)間效率和內(nèi)存消耗性能都有顯著提高。

        5 結(jié)語(yǔ)

        本文提出含負(fù)項(xiàng)top-k高效用項(xiàng)集挖掘算法——THN。當(dāng)用戶(hù)挖掘含負(fù)項(xiàng)高效用項(xiàng)集時(shí),可以直接設(shè)置所需的項(xiàng)集數(shù)k,而無(wú)需反復(fù)調(diào)整min_util挖掘用戶(hù)需求高效用項(xiàng)集的個(gè)數(shù)。THN算法是一階段高效用項(xiàng)集挖掘方法,該算法使用深度優(yōu)先進(jìn)行搜索。為了減少數(shù)據(jù)集的掃描次數(shù),該算法使用事務(wù)合并技術(shù)和數(shù)據(jù)集投影技術(shù)。為了更好地修剪搜索空間,該算法使用了基于重新定義的子樹(shù)修剪策略。為了提高算法的性能,該算法提出了自我提升最小效用閾值的策略。實(shí)驗(yàn)結(jié)果表明,THN算法的性能明顯優(yōu)于對(duì)比算法,并且該算法在密集數(shù)據(jù)集中的表現(xiàn)尤其出色。但是,該算法在稀疏數(shù)據(jù)集的運(yùn)行時(shí)間上效果較差。盡管THN算法在稀疏數(shù)據(jù)集上運(yùn)行需要更長(zhǎng)的時(shí)間,但其仍然是第一個(gè)挖掘含負(fù)項(xiàng)top-k高效用項(xiàng)集挖掘算法。最后,本文還對(duì)THN算法進(jìn)行了可擴(kuò)展性測(cè)試,結(jié)果表明該算法具有良好的可擴(kuò)展性。

        由于該算法在稀疏數(shù)據(jù)集上的表現(xiàn)不佳,未來(lái)的工作可以研究如何降低該算法在稀疏數(shù)據(jù)集上運(yùn)行的時(shí)間。目前,含負(fù)項(xiàng)高效用項(xiàng)集挖掘算法較少,在下一步的工作中,我們可以研究在增量數(shù)據(jù)集和大數(shù)據(jù)中挖掘含負(fù)項(xiàng)高效用項(xiàng)集和挖掘精簡(jiǎn)的含負(fù)項(xiàng)高效用項(xiàng)集。

        猜你喜歡
        項(xiàng)集事務(wù)效用
        “事物”與“事務(wù)”
        基于分布式事務(wù)的門(mén)架數(shù)據(jù)處理系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)
        河湖事務(wù)
        小學(xué)美術(shù)課堂板書(shū)的四種效用
        納米硫酸鋇及其對(duì)聚合物的改性效用
        幾種常見(jiàn)葉面肥在大蒜田效用試驗(yàn)
        玉米田不同控釋肥料效用研討
        關(guān)聯(lián)規(guī)則中經(jīng)典的Apriori算法研究
        卷宗(2014年5期)2014-07-15 07:47:08
        一種頻繁核心項(xiàng)集的快速挖掘算法
        SQLServer自治事務(wù)實(shí)現(xiàn)方案探析
        无码一区二区三区亚洲人妻| 国产精品国产三级国产专区51区 | 亚洲精品一区二区高清| 黑人巨茎大战俄罗斯美女| 国产午夜三级一区二区三| 在线亚洲AV成人无码一区小说| 国产一区二区美女主播| 精品国产午夜肉伦伦影院| 亚洲av无码av男人的天堂| 亚洲最新版无码AV| 成人短篇在线视频夫妻刺激自拍| 爆操丝袜美女在线观看| 首页 综合国产 亚洲 丝袜| 久久88综合| 狼人综合干伊人网在线观看| 青青草精品视频在线播放| 亚洲色在线v中文字幕| 国产精品久久久久久久久免费观看 | 久久精品女人天堂av| 丝袜欧美视频首页在线| 蜜桃传媒免费观看视频| 色婷婷五月综合激情中文字幕| 久久久久亚洲av无码专区体验 | 国产精品久久久福利| 一区二区三区国产亚洲网站| 久久亚洲日本免费高清一区| 亚洲精品在线97中文字幕| 日本一二三区视频在线| 欧美性群另类交| 国产精品性一区二区三区| 男女18视频免费网站| 久久久久女人精品毛片| 久久综合视频网站| 免费人成在线观看播放视频| 综合色就爱涩涩涩综合婷婷| 日韩精品大片在线观看| 久久精品国产亚洲av蜜桃av| 国产午夜在线视频观看| 少妇高潮潮喷到猛进猛出小说| 丰满熟妇人妻无码区| 亚洲一区二区刺激的视频|