[發(fā)明專利]基于MapReduce的并行頻繁項(xiàng)集增量數(shù)據(jù)挖掘方法

有效

• 申請?zhí)枺?/td>: 202110177059.8
• 申請日: 2021-02-07
• 公開（公告）號: CN112925821B
• 公開（公告）日: 2022-05-13
• 發(fā)明（設(shè)計(jì)）人: 毛伊敏;鄧千虎
• 申請（專利權(quán)）人: 韶關(guān)學(xué)院
• 主分類號: G06F16/2458
• 分類號: G06F16/2458;G06K9/62;G06N3/12
• 代理公司: 重慶天成卓越專利代理事務(wù)所(普通合伙) 50240
• 代理人: 王宏松

1.一種基于MapReduce的并行頻繁項(xiàng)集增量數(shù)據(jù)挖掘方法，其特征在于，包括以下步驟：

S1，設(shè)計(jì)基于信息熵的相似項(xiàng)合并策略SIM-IE來合并數(shù)據(jù)集中的相似數(shù)據(jù)項(xiàng)，根據(jù)合并后的數(shù)據(jù)集進(jìn)行Can樹構(gòu)造；

所述S1包括：

S1-1，根據(jù)差值大小對數(shù)據(jù)項(xiàng)進(jìn)行分類；

S1-2，獲得S1-1劃分好的數(shù)據(jù)后，根據(jù)相似性評估公式SAF計(jì)算對應(yīng)的數(shù)據(jù)集之間的相似度；

S1-3，根據(jù)S1-2獲取所有劃分?jǐn)?shù)據(jù)集之間的相似性結(jié)果后，再根據(jù)提前設(shè)定的相似度閾值δ判斷是否需要進(jìn)行相似項(xiàng)合并；

S2，提出基于遺傳算法的動(dòng)態(tài)支持度閾值計(jì)算策略DST-GA，獲取大數(shù)據(jù)集中的相對最優(yōu)動(dòng)態(tài)支持度閾值，根據(jù)所述相對最優(yōu)動(dòng)態(tài)支持度閾值進(jìn)行頻繁模式挖掘；

所述S2包括：

S2-1，構(gòu)造支持度函數(shù)SF；

S2-2，利用遺傳算法的收斂性與不失一般性，對其進(jìn)行迭代優(yōu)化運(yùn)算用于求得最優(yōu)解，即相對最優(yōu)動(dòng)態(tài)支持度閾值；

所述構(gòu)造支持度函數(shù)SF包括：

其中，m為數(shù)據(jù)集D的總項(xiàng)目數(shù)，P(x_i)表示項(xiàng)目x_i在D中出現(xiàn)的概率，Weight(x_i)表示x_i的權(quán)重，r(x₁,x₂,...,x_m)為修正函數(shù)，|·|表示集合中元素?cái)?shù)量，x_i為第i個(gè)數(shù)據(jù)項(xiàng)；

S3，使用并行LZO數(shù)據(jù)壓縮算法對Map端輸出的數(shù)據(jù)進(jìn)行壓縮。

2.根據(jù)權(quán)利要求1所述基于MapReduce的并行頻繁項(xiàng)集增量數(shù)據(jù)挖掘方法，其特征在于，所述S1-1包括：

S1-1-1，對需要進(jìn)行相似性評估的數(shù)據(jù)集中的數(shù)據(jù)項(xiàng)進(jìn)行合并，然后按序排列，求出各相鄰數(shù)據(jù)的差值總和sum；令數(shù)據(jù)項(xiàng)數(shù)為n，那么求得的平均差為：avg＝sum/(n-1)；

S1-1-2，求得平均差avg后，將排序后的數(shù)據(jù)集根據(jù)avg進(jìn)行劃分；

所述將排序后的數(shù)據(jù)集根據(jù)avg進(jìn)行劃分包括：設(shè)劃分?jǐn)?shù)為d，如果相鄰的數(shù)據(jù)值之差小于平均差值，那么就將前一個(gè)劃分獲得的數(shù)據(jù)與當(dāng)前的數(shù)據(jù)之間的所有數(shù)據(jù)項(xiàng)歸為一個(gè)分區(qū)，重復(fù)執(zhí)行比較與分區(qū)操作直至所有數(shù)據(jù)都被劃分到對應(yīng)的數(shù)據(jù)分區(qū)。

3.根據(jù)權(quán)利要求1所述基于MapReduce的并行頻繁項(xiàng)集增量數(shù)據(jù)挖掘方法，其特征在于，所述S1-2的相似性評估公式SAF包括：

條件熵：H(S|C)＝-∑_c∈Cp(c)∑_s∈Sp(s|c)log(p(s|c)) (1)

信息熵：

相似性：

A、B為兩個(gè)相似性待判斷的數(shù)據(jù)集，S為決策模式屬性集，C為不確定匹配模式關(guān)系集，C與S交集為空；H(·|·)為條件熵函數(shù)，H(·)為信息熵函數(shù)，sim(·,·)為相似性函數(shù)；c、s分別為集合C、S中的項(xiàng)，p(c)為c發(fā)生的概率，p(s|c)為c發(fā)生的條件下s發(fā)生的概率，log(·)為對數(shù)函數(shù)；n為s中的事務(wù)數(shù)量，p(x_i)為s中事務(wù)x_i發(fā)生的概率。