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

孫 蕊，韓 萌，張春硯，申明堯，杜詩語

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

0 引言

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

針對傳統(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）算法來挖掘含負(fù)項(xiàng)的高效用項(xiàng)集。但是，該算法還是存在產(chǎn)生候選項(xiàng)集過多的問題。Lin等［11］隨后提出了FHN（Faster High utility itemset miner with Negative unit profits）算法，該算法使用深度優(yōu)先的搜索策略，并使用基于效用列表的EUCS（Estimated Utility Co-occurrence Structure）來有效地修剪搜索空間。實(shí)驗(yàn)結(jié)果表明，F(xiàn)HN算法的執(zhí)行時間是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）算法，該算法提出挖掘同時考慮貨架時間和含負(fù)項(xiàng)集的高效用項(xiàng)集。TS-HOUN算法采用三階段挖掘方法，在每個時間段挖掘項(xiàng)集，然后使用合并操作合并每個時間段的項(xiàng)集。由于多次掃描數(shù)據(jù)集，因此TS-HOUN效率很低。

為了解決多次掃描數(shù)據(jù)集的問題，F(xiàn)OSHU（Faster On-Shelf High Utility itemset miner）［13］算法使用了基于效用列表的結(jié)構(gòu)，該結(jié)構(gòu)同時挖掘所有時間段的項(xiàng)集。實(shí)驗(yàn)結(jié)果表明，F(xiàn)OSHU算法的執(zhí)行時間是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）算法來挖掘含負(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快一個數(shù)量級。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）算法來挖掘含負(fù)項(xiàng)的高效用項(xiàng)集，EHIN算法提出了多種有效的數(shù)據(jù)結(jié)構(gòu)和修剪策略。同年，Singh等［20］提出了CHN（Closed High utility itemsets mining with Negative utility）算法來挖掘含負(fù)項(xiàng)閉合高效用項(xiàng)集。2019年，Singh等［21］提出了EHNL（Efficient High utility itemsets mining with Negative utility and Length constraints）算法來挖掘含負(fù)項(xiàng)和長度約束的高效用項(xiàng)集。

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

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

top-k高效用項(xiàng)集挖掘算法不需要設(shè)置最小效用閾值，直接根據(jù)用戶設(shè)置的高效用項(xiàng)集數(shù)量k進(jìn)行挖掘。最早的top-k高效用項(xiàng)集挖掘算法是TKU（Top-KUtility itemsets mining）［22］，它是UP-Growth算法的擴(kuò)展。TKU算法采用Two-Phase模型：在第一階段，該算法使用多種策略來提高內(nèi)部的最小效用閾值，并對搜索空間進(jìn)行修剪，生成潛在的top-k高效用項(xiàng)集；在第二階段，從潛在的top-k高效用項(xiàng)集集合中識別真正的top-k高效用項(xiàng)集。TKU算法使用SE（Sorting candidates and raising threshold by the Exact utility of candidates）策略對候選項(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算法依賴于UP（Utility Pattern）-Tree結(jié)構(gòu)，通過使用額外的策略來快速提高邊界最小效用閾值，從而提高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)行時間。

為了克服兩階段算法的局限性，研究者提出了一階段高效用項(xiàng)集挖掘算法。Lu等［26］提出了在數(shù)據(jù)流中挖掘top-k高效用項(xiàng)集的TOPK-SW（Sliding Window based TOP-K）算法，該算法將每批數(shù)據(jù)存儲在當(dāng)前窗口中，并將項(xiàng)的效用信息存儲在HUI-Tree中，而無需再次掃描數(shù)據(jù)集。王樂等［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）算法來挖掘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）來提高算法的性能。實(shí)驗(yàn)結(jié)果表明，該算法的性能優(yōu)于TKU和REPT算法。Duong等［29］提出一階段算法kHMC（top-kHigh utility itemset Mining using Co-occurrence pruning），它依賴于效用列表結(jié)構(gòu)，采用多種策略提升最小效用閾值。Singh等［30］提出了TKEH（Efficient algorithm for mining Top-KHigh utility itemsets）算法，該算法使用事務(wù)合并和數(shù)據(jù)集投影技術(shù)來降低數(shù)據(jù)集掃描的成本。Kumari等［31］提出了TKRHU（Top-KRegular High Utility itemset）算法，該算法使用RUL（Regular Utility-Lists）效用列表結(jié)構(gòu)來存儲每個規(guī)則表的規(guī)則信息和效用信息。Krishnamoorthy等［32］提出THUI（top-kHigh Utility Itemset）高效用項(xiàng)集挖掘算法，該算法使用LIU（Leaf Itemset Utility）結(jié)構(gòu)來提高挖掘效率。實(shí)驗(yàn)結(jié)果表明，在大型、密集和事務(wù)平均長度較長的數(shù)據(jù)集上具有更好的性能。

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

2 基本概念

事務(wù)數(shù)據(jù)集D由眾多事務(wù)組成，每條事務(wù)包含一些項(xiàng)，每條事務(wù)都由唯一的事務(wù)標(biāo)識符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個項(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的利潤，表示為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是用戶設(shè)置的最小效用閾值。如果項(xiàng)集X的效用值不小于min_util，則項(xiàng)集X是高效用項(xiàng)集；否則，它是一個低效用項(xiàng)集。

定義7 top-k高效用項(xiàng)集［22］。按照項(xiàng)集效用值從高到低的順序排序，令min_util為第k個項(xiàng)集的效用值。對于項(xiàng)集X，如果條件項(xiàng)集X的效用值不小于min_util，則項(xiàng)集X稱為top-k高效用項(xiàng)集。

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

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

屬性1 項(xiàng)集中的正效用和負(fù)效用之間的關(guān)系［9］。對于任何項(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 使用正效用對項(xiàng)集的效用上限［9］。項(xiàng)集X的效用上限為putil（X）。

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

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

例如，事務(wù)T2的重新定義的事務(wù)效用為RTU（T2）=U（C，T2）+U（E，T2）=5+1=6。通過添加僅計(jì)算重新定義的事務(wù)效用的項(xiàng)來增加了正項(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)在集合枚舉樹的重新定義的子樹中）。另外，項(xiàng)集α擴(kuò)展了單個項(xiàng)集Y（Y是集合枚舉樹中α的子代）。其中X∈E（α），Y=α∪｛X｝。在運(yùn)行的示例中，α=｛B｝，集合E（α）為｛C，D｝，詞典α的單項(xiàng)展開為｛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算法采用重新定義的本地效用和重新定義的子樹效用對搜索空間進(jìn)行了有效的修剪，基于這兩種方法該算法的效率得到了有效地提升。

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

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

屬性4 基于重新定義子樹效用的高估［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ò)展低子樹效用值。此外，在集合枚舉樹中修剪α∪｛x｝的子樹，可以修剪項(xiàng)集α的子樹。

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

定義14 主要項(xiàng)和次要項(xiàng)［19］。對于項(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］。對于項(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ù)。為了實(shí)現(xiàn)這一點(diǎn)，本文算法需要相互比較所有的事務(wù)。將所有事務(wù)與每個事務(wù)進(jìn)行比較的技術(shù)并不是一種有效的技術(shù)。為了解決這個問題，本文算法可以采用文獻(xiàn)［33］中提出的相同事務(wù)排序技術(shù)?T。這種排序技術(shù)在計(jì)算上并不昂貴。

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

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

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

定義19 效用數(shù)組［19］。I是數(shù)據(jù)集D中出現(xiàn)的一組項(xiàng)，UA是一個長度為||I的數(shù)組，其中每個項(xiàng)x∈I都有一個表示為UA［x］的條目。每個條目稱為UA，用于存儲效用值。

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

首先，UA初始化為0。其次，對于數(shù)據(jù)集D的每個事務(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)集挖掘算法的主要問題局限是，沒有預(yù)先提供min_util，運(yùn)行時的min_util從0或1開始，這嚴(yán)重降低了算法的效率。因此，這為如何自動提升min_util而不丟失任何高效用項(xiàng)集帶來了巨大的挑戰(zhàn)。為了解決這個問題，本文提出了有效的RTWU_strategy閾值提升策略。

RTWU_strategy閾值提升策略的詳細(xì)過程如下所述。首先，在第一次掃描事務(wù)數(shù)據(jù)集時，計(jì)算此過程中所有項(xiàng)的RTWU（x）。例如，項(xiàng)A同時出現(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)的效用列表。接下來根據(jù)定義18中的排序規(guī)則，對RTWU效用列表進(jìn)行排序。然后，RTWU_strategy將已排序的RTWU效用列表中的min_util提升到第k個最大值?，F(xiàn)在，使用這個新值作為min_util。例如，假設(shè)用戶將k值設(shè)置為5，然后掃描數(shù)據(jù)集并計(jì)算項(xiàng)的RTWU（x）。假設(shè)效用列表中RTWU的第5個值是88，那么，min_util提高到88。然后，該算法使用這個新的min_util。最后，直至找到用戶需求的效用值最高的前k個項(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和用戶定義的高效用項(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)建一個k大小的優(yōu)先隊(duì)列（名為k_Patterns）。第6）行掃描事務(wù)數(shù)據(jù)集D，同時使用UA技術(shù)計(jì)算所有項(xiàng)的RLU。第7）行通過比較每個項(xiàng)的RLU和min_util，可以獲得項(xiàng)集的次要項(xiàng)，次要項(xiàng)作為項(xiàng)集的擴(kuò)展項(xiàng)。第8）行計(jì)算每個項(xiàng)的RTWU，并將結(jié)果存儲在hashMap中。第9）行調(diào)用RTWU_strategy，主要功能是自動提升min_util。第10）行根據(jù)RTWU的升序?qū)?xiàng)集進(jìn)行排序。注意，當(dāng)按?T順序排序時，該算法首先考慮正效用項(xiàng)，然后考慮負(fù)效用項(xiàng)。第11）行掃描數(shù)據(jù)集D，并刪除事務(wù)中不是次要項(xiàng)的所有項(xiàng)集和空事務(wù)。根據(jù)重新定義的本地效用的剪枝策略，刪除的項(xiàng)不是高效用項(xiàng)集。第12）行根據(jù)字典排序?qū)κＳ嗍聞?wù)進(jìn)行排序，且正項(xiàng)集在負(fù)項(xiàng)集之前。此時，根 據(jù)EFIM（efficient algorithm for high-utility itemset mining）［33］的建議，此處執(zhí)行事務(wù)合并技術(shù)。第13）行掃描數(shù)據(jù)集D，并使用UA技術(shù)計(jì)算所有項(xiàng)的RSU。第14）行通過比較每個項(xiàng)的RSU和min_util，可以獲得項(xiàng)集的主要項(xiàng)。第15）行通過調(diào)用算法3從項(xiàng)集α開始遞歸執(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個項(xiàng)的優(yōu)先級隊(duì)列；輸出為前k個α項(xiàng)集擴(kuò)展的含正項(xiàng)高效用項(xiàng)集集合。

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

算法3 Search_P算法。

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

輸出：前k個α項(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個項(xiàng)的優(yōu)先級隊(duì)列；輸出為前k個α項(xiàng)集擴(kuò)展的含負(fù)項(xiàng)高效用項(xiàng)集集合。

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

算法4 Search_N算法。

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

輸出：前k個α項(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é)中，給出一個簡單的說明性示例，以展示THN算法如何從事務(wù)數(shù)據(jù)集中找到含負(fù)項(xiàng)top-k高效用項(xiàng)集。假設(shè)如表1所示的7條事務(wù)，并且有5個項(xiàng)的內(nèi)部效用。同時，表2顯示每個項(xiàng)的外部效用。此外，最終挖掘出的效用值最高項(xiàng)集的數(shù)量k被設(shè)置為20。THN算法從事務(wù)性數(shù)據(jù)集中挖掘高效用項(xiàng)集，THN算法首先計(jì)算事務(wù)中每一項(xiàng)的效用，并找到該事務(wù)的事務(wù)效用。例如，事務(wù)T2中有3個項(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)過上述過程，可以計(jì)算出T2的TU為（-3）+5+1=3。所有事務(wù)的TU值結(jié)果如表3所示。為了過高估計(jì)效用，THN算法使用RTU。為了找到RTU，THN算法只計(jì)算正效用值為5+1，即在T2中為6。同樣，所有RTU都可以計(jì)算出來。所有事務(wù)的RTU如表4所示。RLU是使用深度優(yōu)先搜索計(jì)算的。運(yùn)行示例中項(xiàng)A的RTWU值出現(xiàn)在三個事務(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)被刪除。因此，沒有從示例數(shù)據(jù)集中刪除任何項(xiàng)。同時，如果從事務(wù)中刪除了所有項(xiàng)，則刪除那些空事務(wù)。然后對剩余的事務(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)作為每個子樹的子代節(jié)點(diǎn)。為此，使用深度優(yōu)先搜索來查找子樹中的下行節(jié)點(diǎn)。使用算法2和算法3對節(jié)點(diǎn)進(jìn)行挖掘，然后遞歸地調(diào)用算法2來擴(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｝，其中每個項(xiàng)集旁邊的數(shù)字表示其效用值。

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

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

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

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

對于所有的數(shù)據(jù)集，項(xiàng)的內(nèi)部效用值在1～5的范圍內(nèi)隨機(jī)生成，項(xiàng)的外部效用值使用對數(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ì)

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

傳統(tǒng)上，測試新正項(xiàng)的top-k高效用項(xiàng)集挖掘算法是將其與挖掘相同結(jié)果集并設(shè)置最佳最小效用閾值的非top-k高效用項(xiàng)集挖掘算法進(jìn)行比較。對于新提出的THN算法，本文通過查找相關(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ù)據(jù)集中無法在圖中畫出來，因?yàn)樗枰嗟膱?zhí)行時間和內(nèi)存。因此，對比非top-k算法是HUINIV-Mine和FHN算法，這兩種算法均被用于挖掘含負(fù)項(xiàng)高效用項(xiàng)集。

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

4.2 執(zhí)行時間性能

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

從圖1中可以清楚地看到，在retail和kosarak稀疏數(shù)據(jù)集中，F(xiàn)HN算法的運(yùn)行時間少于HUINIV-Mine和THN算法。在retail數(shù)據(jù)集中，隨著k值的增加，F(xiàn)HN算法的運(yùn)行時間幾乎不變。在retail數(shù)據(jù)集中當(dāng)k的值小于500時，在kosarak數(shù)據(jù)集中當(dāng)k的值小于50時，THN算法的運(yùn)行時間和FHN算法的運(yùn)行時間幾乎持平。在retail數(shù)據(jù)集中，THN（RSU-Prune）算法的執(zhí)行時間小于THN算法。這一結(jié)果表明，retail數(shù)據(jù)集不支持TM技術(shù)。Retail數(shù)據(jù)集有大量不同的項(xiàng)，并且比所有其他數(shù)據(jù)集有更寬的最大長度，因此它不支持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)，幾乎沒有相同事務(wù)。由于在稀疏數(shù)據(jù)集中，事務(wù)數(shù)據(jù)庫中具有相同項(xiàng)的事務(wù)的概率顯著降低，所以事務(wù)合并策略變得開銷很大。THN算法提出的事務(wù)合并技術(shù)在高度稀疏的數(shù)據(jù)集中表現(xiàn)不佳，事務(wù)合并需要大量時間來合并事務(wù)，稀疏數(shù)據(jù)集中的相同事務(wù)較少，因此浪費(fèi)大量時間，效率很低。

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

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

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

從圖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)存消耗迅速增加。對于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)存的三倍。對于所有密集數(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時，THN算法及其THN（TM）和THN（RSU-Prune）算法的內(nèi)存消耗比FHN多。因?yàn)?，retail數(shù)據(jù)集是高度稀疏的，所提出的算法對高度稀疏數(shù)據(jù)集不是有效的。THN采用的TM技術(shù)不適用于retail等高度稀疏的數(shù)據(jù)集。

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

4.4 可擴(kuò)展性

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

圖3 不同算法運(yùn)行時間的可擴(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ù)。該算法在四個密集數(shù)據(jù)集和兩個稀疏數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)。對比算法使用了本身的變形算法THN（TM）和THN（RSU-Prune），還有挖掘含有負(fù)項(xiàng)高效用項(xiàng)集挖掘算法HUINIV-Mine［9］和FHN［11］。

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

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

5 結(jié)語

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

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