[發(fā)明專利]一種基于滑動(dòng)窗口的頻繁項(xiàng)集并行增量挖掘的方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202210077060.8
• 申請(qǐng)日: 2022-05-11
• 公開（公告）號(hào): CN114691749A
• 公開（公告）日: 2022-07-01
• 發(fā)明（設(shè)計(jì)）人: 馬漢達(dá);方偉
• 申請(qǐng)（專利權(quán)）人: 江蘇大學(xué)
• 主分類號(hào): G06F16/2458
• 分類號(hào): G06F16/2458;G06F16/182
• 代理公司: 成都智涌知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 51313
• 代理人: 魏振柯

本發(fā)明屬于數(shù)據(jù)處理分析領(lǐng)域，具體涉及一種基于滑動(dòng)窗口的頻繁項(xiàng)集并行增量挖掘的方法，針對(duì)現(xiàn)有并行增量挖掘方法在大數(shù)據(jù)環(huán)境下運(yùn)行效率低的問(wèn)題。本發(fā)明的主要實(shí)現(xiàn)步驟為：數(shù)據(jù)集獲取與預(yù)處理；數(shù)據(jù)集劃分為多塊增量數(shù)據(jù)集；挖掘單批次數(shù)據(jù)集的頻繁項(xiàng)集和準(zhǔn)頻繁項(xiàng)集；若當(dāng)前窗口中存在前批次數(shù)據(jù)集，則將當(dāng)前批次數(shù)據(jù)集的挖掘結(jié)果與前批次的挖掘結(jié)果合并更新；否則，進(jìn)入持久化當(dāng)前窗口中增量更新后的頻繁項(xiàng)集和準(zhǔn)頻繁項(xiàng)集并輸出頻繁項(xiàng)集；如此，繼續(xù)輸入增量數(shù)據(jù)集，循環(huán)上述增量挖掘步驟。本發(fā)明通過(guò)引入滑動(dòng)窗口等技術(shù)，加快了判定是否為頻繁項(xiàng)集的速度，結(jié)合Spark并行計(jì)算和Hadoop分布式存儲(chǔ)，使得該發(fā)明具有良好的挖掘效率。

技術(shù)領(lǐng)域

本發(fā)明屬于數(shù)據(jù)處理分析領(lǐng)域，尤其涉及一種基于滑動(dòng)窗口的頻繁項(xiàng)集并行增量挖掘的方法。

背景技術(shù)

關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘的一個(gè)重要研究領(lǐng)域，旨在發(fā)現(xiàn)數(shù)據(jù)集中頻繁模式。關(guān)聯(lián)規(guī)則挖掘已廣泛應(yīng)用在購(gòu)物推薦、網(wǎng)站點(diǎn)擊分析、電子商務(wù)、金融和醫(yī)療診斷等領(lǐng)域。靜態(tài)關(guān)聯(lián)規(guī)則挖掘是在固定數(shù)據(jù)集和支持度下發(fā)現(xiàn)頻繁項(xiàng)集。而多數(shù)時(shí)候支持度和數(shù)據(jù)集是會(huì)發(fā)生變化的，增量關(guān)聯(lián)規(guī)則挖掘便是在數(shù)據(jù)集增加下的頻繁模式挖掘，頻繁項(xiàng)集的增量挖掘則是關(guān)聯(lián)規(guī)則增量挖掘的主要部分。在面對(duì)大規(guī)模的數(shù)據(jù)集時(shí)，往往將其一次讀入內(nèi)存挖掘的方式不再可取，這需要足夠大的內(nèi)存空間和巨大的I/O開銷，可擴(kuò)展性不高，性能低下。

這時(shí)就出現(xiàn)了分批次的讀入內(nèi)存，進(jìn)行增量挖掘頻繁項(xiàng)集，但該方式在對(duì)增量更新后的候選項(xiàng)集的重新統(tǒng)計(jì)上，會(huì)嚴(yán)重依賴歷史數(shù)據(jù)集，隨著歷史數(shù)據(jù)集不斷增量輸入，掃描整個(gè)增量后的數(shù)據(jù)集的任務(wù)將變得異常繁重；也有通過(guò)Hadoop和Spark的分布式計(jì)算框架來(lái)加速整個(gè)增量挖掘的方法；另外，在增量更新頻繁項(xiàng)集時(shí)，若按照傳統(tǒng)的以項(xiàng)集支持度計(jì)數(shù)來(lái)作為模式樹的構(gòu)建，則其挖掘出的頻繁項(xiàng)集中的項(xiàng)排序是按支持度計(jì)數(shù)大小排序的，這對(duì)于同一個(gè)頻繁項(xiàng)集的各項(xiàng)支持度變化后，其內(nèi)部排序是非保序的，會(huì)導(dǎo)致頻繁項(xiàng)集更新時(shí)增量項(xiàng)集和歷史項(xiàng)集的匹配變得困難。

發(fā)明內(nèi)容

本發(fā)明對(duì)現(xiàn)有技術(shù)的不足，提出一種基于滑動(dòng)窗口的頻繁項(xiàng)集并行增量挖掘的方法，在優(yōu)化結(jié)構(gòu)減少數(shù)據(jù)掃描工作的同時(shí)，結(jié)合并行化計(jì)算框架進(jìn)一步提高在處理大規(guī)模增量數(shù)據(jù)時(shí)的效率。

本發(fā)明的技術(shù)方案如下：

一種基于滑動(dòng)窗口的頻繁項(xiàng)集并行增量挖掘的方法，具體包含如下步驟：

步驟1，獲取數(shù)據(jù)集；

步驟2，對(duì)獲取的數(shù)據(jù)集進(jìn)行數(shù)據(jù)預(yù)處理；

步驟3，將數(shù)據(jù)集劃分為n份增量數(shù)據(jù)集DB_k；

步驟4，對(duì)劃分出的數(shù)據(jù)集DB_k按批次輸入滑動(dòng)窗口進(jìn)行增量挖掘；

步驟5，挖掘當(dāng)前單批次數(shù)據(jù)集DB_k的頻繁項(xiàng)集和準(zhǔn)頻繁項(xiàng)集；

步驟6，將當(dāng)前批次數(shù)據(jù)集DB_k作為前序批次DB_1…k-1數(shù)據(jù)集的增量，合并滑動(dòng)窗口中當(dāng)前批次和前序批次數(shù)據(jù)集挖掘出的頻繁項(xiàng)集和準(zhǔn)頻繁項(xiàng)集；

步驟7，獲取更新后當(dāng)前滑動(dòng)窗口中的全部頻繁項(xiàng)集。

作為本發(fā)明一種基于滑動(dòng)窗口的頻繁項(xiàng)集并行增量挖掘的方法的進(jìn)一步優(yōu)選方案，在步驟2中，數(shù)據(jù)預(yù)處理包括對(duì)事務(wù)數(shù)據(jù)集中事務(wù)項(xiàng)的數(shù)值化處理，剔除臟數(shù)據(jù)。

作為本發(fā)明一種基于滑動(dòng)窗口的頻繁項(xiàng)集并行增量挖掘的方法的進(jìn)一步優(yōu)選方案，在步驟3中，數(shù)據(jù)集劃分方式為按數(shù)據(jù)集事務(wù)總條數(shù)等分為n份，每份數(shù)據(jù)集記為DB_k，k∈[1,n]；由于每份數(shù)據(jù)集事務(wù)記錄條數(shù)相等，每條事務(wù)記錄的事務(wù)項(xiàng)數(shù)目不同，因此最終每份數(shù)據(jù)集DB_k的大小不絕對(duì)相等。

作為本發(fā)明一種基于滑動(dòng)窗口的頻繁項(xiàng)集并行增量挖掘的方法的進(jìn)一步優(yōu)選方案，在步驟4中，有如下定義：