TW201741903A

TW201741903A - 關聯分析方法和裝置

Info

Publication number: TW201741903A
Application number: TW106103977A
Authority: TW
Inventors: Bin Dai; Xu Yang; xiao yan Jiang; Ning Cai; Shao Meng Wang
Original assignee: Alibaba Group Services Ltd
Priority date: 2016-02-22
Filing date: 2017-02-07
Publication date: 2017-12-01
Also published as: WO2017143908A1; US20190102383A1; TWI730043B; CN107102999A; US10956395B2; CN107102999B

Abstract

本發明提供了關聯分析方法和裝置，通過將原始資料庫劃分為相互之間不貢獻頻繁項集支持度的各投影資料庫，由各節點分別對所對應的投影資料庫進行序列模式的關聯分析，然後對各節點獲得的局部頻繁項集以及對應支持度進行匯總。由於所建立的投影資料庫相互之間不貢獻頻繁項集的支持度，可以由不同節點分別對不同的投影資料庫進行包括剪枝步驟在內的關聯挖掘，各節點所獲得的為資料量較小的局部頻繁項集，避免現有技術中需要傳輸各節點未經過剪枝步驟所獲得的資料量較大的局部候選頻繁項集的情況，從而節省了傳輸開銷，提高了效率。

Description

關聯分析方法和裝置

本發明關於計算機技術，尤其關於一種關聯分析方法和裝置。

關聯分析是進行資料挖掘中的一種分析技術，主要用於根據大量資料發現項目之間的關聯性。關聯分析的一個典型應用實例便是購物籃分析：基於購物資料進行關聯分析，發現顧客放入購物籃中的不同商品之間的關聯性。進而由這種關聯分析所獲得的關聯性體現出顧客的購買習慣，通過瞭解這些購買習慣可以有利於零售商制定營銷策略。

序列模式關聯分析不同於其他模式下的關聯分析，序列模式還考慮了項目發生的時間，從而使得各項目之間有一定的順序性。針對序列模式的關聯分析，其所進行分析的對象往往是超大規模的資料庫，因此，運算量很大不適宜採用單機進行資料處理。現有技術中通常採用對資料庫中的資料進行簡單分片，將每個分片資料在各節點進行單獨的關聯分析，獲得候選頻繁項集及其支持度，然後進行合併獲得各候選頻繁項集的全域支持度，進而依據預設的篩選條件進行剪枝後獲得全域頻繁項集。

但是，由於在進行關聯分析產生候選頻繁項集的過程中存在資料膨脹，導致候選頻繁項集的資料量是分片資料的資料量的指數倍，因此，在對各節點產生的候選頻繁項集及其支持度進行匯總以便執行合併操作時，傳輸資料量過大，導致執行效率較低。

本發明提供一種關聯分析方法和裝置，用於解決現有技術中進行並行關聯分析時由於匯總資料時資料傳輸量過大導致執行效率較低的技術問題。

為達到上述目的，本發明的實施例採用如下技術方案：第一方面，提供一種關聯分析方法，包括：將原始資料庫劃分為各投影資料庫，所述各投影資料庫相互之間不貢獻頻繁項集的支持度；由各節點分別對所對應的投影資料庫進行序列模式的關聯分析，獲得局部頻繁項集以及對應支持度；對各節點關聯分析所獲得的局部頻繁項集以及對應支持度進行匯總，獲得全域頻繁項集以及對應支持度。

第二方面，提供一種關聯分析裝置，包括：劃分模組，用於將原始資料庫劃分為各投影資料庫，所述各投影資料庫相互之間不貢獻頻繁項集的支持度；分析模組，用於由各節點分別對所述投影資料庫進行序列模式的關聯分析，獲得局部頻繁項集以及對應支持度；匯總模組，用於對各節點關聯分析所獲得的局部頻繁項集以及對應支持度進行匯總，獲得全域頻繁項集以及對應支持度。

本發明實施例提供的關聯分析方法和裝置，通過將原始資料庫劃分為相互之間不貢獻支持度的各投影資料庫，由各節點分別對所對應的投影資料庫進行序列模式的關聯分析，然後對各節點獲得的局部頻繁項集以及對應支持度進行匯總。由於所建立的投影資料庫相互之間不貢獻頻繁項集的支持度，可以由不同節點分別對不同的投影資料庫進行包括剪枝步驟在內的關聯挖掘，各節點所獲得的為資料量較小的局部頻繁項集，避免現有技術中需要傳輸各節點未經過剪枝步驟所獲得的資料量較大的局部候選頻繁項集的情況，從而節省了傳輸開銷，提高了效率。

上述說明僅是本發明技術方案的概述，為了能夠更清楚瞭解本發明的技術手段，而可依照說明書的內容予以實施，並且為了讓本發明的上述和其它目的、特徵和優點能夠更明顯易懂，以下特舉本發明的具體實施方式。

42‧‧‧劃分模組

43‧‧‧分析模組

44‧‧‧匯總模組

62‧‧‧序列化模組

63‧‧‧反序列化模組

421‧‧‧獲得單元

422‧‧‧建立單元

4211‧‧‧計算子單元

4212‧‧‧確定子單元

4213‧‧‧篩選子單元

4221‧‧‧查詢子單元

4222‧‧‧建立子單元

通過閱讀下文較佳實施方式的詳細描述，各種其他的優點和益處對於本領域普通技術人員將變得清楚明瞭。圖式僅用於顯示較佳實施方式的目的，而並不是對本發明的限制。而且在整個圖式中，用相同的參考符號表示相同的部件。在圖式中：圖1為本發明實施例一提供的一種關聯分析方法的流程示意圖；圖2為本發明實施例二提供的一種關聯分析方法的流程示意圖；圖3為關聯分析方法執行過程的示意圖；圖4為本發明實施例所提供的一種關聯分析裝置的結構示意圖；圖5為實施例三提供的另一種關聯分析裝置的結構示意圖；圖6為實施例四提供的一種關聯分析裝置的結構示意圖。

下面將參照圖式更詳細地描述本發明的示範性實施例。雖然圖式中顯示了本發明的示範性實施例，然而應當理解，可以以各種形式實現本發明而不應被這裡闡述的實施例所限制。相反，提供這些實施例是為了能夠更透徹地理解本發明，並且能夠將本發明的範圍完整的傳達給本領域的技術人員。

在待進行關聯分析的資料庫中，通常記載了各個事務，事務又包括了各個項目，每一個項目包括至少一個元素。其中，一個元素用於指示一個操作對象，項目用於指示由同一用戶同時進行操作的各操作對象，而一個用戶在不同時刻所進行操作的操作對象可以用一個事務標識。由於序列模式下的關聯分析需要考慮時序性，因此，每一個事務所包括的各個項目是具有一定順序性的，這種具有順序的各個項目可以稱之為一個序列，因此，也可以說事務是由一個序列進行表示的。

比如資料庫中的一個事務為序列abc,abc,ac,d,cf，可以用於表示一個用戶分別在第一天買了商品a、b和c，第二天又買了商品a、b和c，第三天買了商品a和c。針對每一天買的總商品叫項目，每件商品叫元素。

發明人針對現有技術中的關聯分析方法進行分析，發現現有技術中在對各節點產生的候選頻繁項集及其支持度進行匯總以便執行合併操作時，傳輸資料量過大，主要是由於各節點未在本地執行剪枝的步驟。發明人在此基礎上，進行了進一步分析，現有技術中對原始資料僅進行了簡單分片，各個分片資料對於某個頻繁項級都存在貢獻支持度的可能，從而無法在本地執行剪枝的步驟，因此，需要將原始資料劃分為相互之間不存在支持度的資料庫才能夠在節點本地進行剪枝，進而避免傳輸候選頻繁項集及其支持度。基於這一思路，發明人提出了本發明所提供的關聯分析方法。

為了便於理解本發明所提供的關聯分析方法，在描述具體實施例之前，對實施例中所涉及的技術術語進行解釋：序列模式關聯分析是指：給定一個資料庫，其中，資料庫包括了各個事務，每一個事務由一個序列表示，每個序列由相互之間具有一定順序性的項目組成。序列模式挖掘就是在給定一個支持度閾值的基礎上，找出所有滿足在資料庫中的出現頻次不低於該支持度閾值的子序列，將這些子序列作為頻繁項集，從資料庫中找出這些頻繁項集的操作便是序列模式關聯分析。

項集是指：資料庫針對同一事務中所出現的項目有序排列所構成的集合。

項集的長度是指：用於表示該項集的序列的長度，數值上等於項集所包括的項目個數。

支持度是指：項集在資料庫中出現的頻次，若一個事務中包含該項集，則記為一次，從而支持度等於資料庫中包含某一項集的事務個數。

頻繁項集是指：資料庫中所有出現頻次不小於支持度閾值的項集。

投影資料庫是指：針對原始資料庫進行投影操作所獲得的資料庫，具體來說α的投影資料庫為S中所有以α為前綴的序列相對於α的後綴。

此處簡要解釋了技術術語的含義，以上技術術語會在後續結合具體實施例進行進一步地解釋。

下面結合圖式對本發明實施例提供的關聯分析方法和裝置進行詳細描述。

實施例一

圖1為本發明實施例一提供的一種關聯分析方法的流程示意圖，如圖1所示，包括：

步驟101、將原始資料庫劃分為各投影資料庫。

其中，各投影資料庫相互之間不貢獻頻繁項集的支持度。其中，支持度是指在資料庫中包含某一項集的事務個數。各投影資料庫相互之間不貢獻頻繁項集的支持度，也就是說基於一投影資料庫進行序列模式挖掘所獲得的頻繁項集未出現在另一投影資料庫中，從而另一投影資料庫不會增加頻繁項集的支持度，因此說另一投影資料庫不貢獻一投影資料庫的頻繁項集的支持度。

具體地，首先，獲得至少兩個初始項集，其中初始項集是對原始資料庫進行關聯分析所獲得的項集，用於構建投影資料庫，並且至少兩個初始項集中的任意兩初始項集之間不存在相互包含關係。具體可以通過針對原始資料庫可以採用關聯分析算法進行計算，獲得前述的至少兩項集，這兩項集可以是相同長度也可以是不同長度，可以是執行過剪枝步驟獲得的頻繁項集也可以是未執行過剪枝步驟獲得的候選頻繁項集，本實施例中對此不做限定。

進而，將各初始項集作為前綴，建立各前綴的投影資料庫。具體可以通過將初始項集作為前綴，在原始資料庫的各事務中查詢前綴所對應的後綴，進而將各事務的後綴進行匯總，形成前綴的投影資料庫。其中，後綴是通過在每一條事務中查詢該前綴首次出現的位置之後的序列，若前綴的最後一個元素與所查找到的序列的第一個元素的時序相同，則將“_”和所查找到的序列作為後綴，否則，直接將所查找到的序列作為後綴。

由於初始項集兩兩之間的不存在包含關係，所以據此所建立的投影資料庫相互之間不貢獻頻繁項集的支持度，可以由不同節點分別對不同的投影資料庫進行包括剪枝步驟在內的關聯挖掘，各節點所獲得的為資料量較小的局部頻繁項集，避免現有技術中需要傳輸各節點未經過剪枝步驟所獲得的資料量較大的局部候選頻繁項集的情況，從而節省了傳輸開銷，提高了效率。

需要說明的是，這裡定義的包含關係是前綴的包含關係，也就說一個初始項集是否為另一初始項集的前綴，若是，則存在包含關係，例如：針對<a，b>和<a，c，b>，<a，b>不是<a，c，b>的前綴，因此<a，b>和<a，c，b>兩者之間不存在包含關係；針對<a，b>和<a>，<a>是<a，b>的前綴，因此<a，b>和<a>屬包含關係。

作為一種可能的實現方式，可以計算原始資料庫的K_頻繁項集，也就是項集中包含K個項目的頻繁項集，其中K為正整數，且1K<N，N為原始資料庫中所包含的元素數，將K_頻繁項集作為初始項集。

作為另一種可能的實現方式，還可以計算原始資料庫的K_頻繁項集之後，根據預設的支持度閾值，對K_頻繁項集進行篩選，保留支持度大於支持度閾值的K_頻繁項集，將篩選後的K_頻繁項集作為初始項集。經過篩選步驟之後，合理減小了後續進行處理的資料量，減輕了節點構建投影資料庫以及基於投影資料庫進行關聯分析的運算壓力，同時，也減少了後續對節點關聯分析所獲得的局部頻繁項集進行匯總時的資料傳輸總量。

步驟102、由各節點分別對所對應的投影資料庫進行序列模式的關聯分析，獲得局部頻繁項集以及對應支持度。

具體的，為每一投影資料庫分配節點，例如：可以為各投影資料庫分配負載能力與所述投影資料庫的資料量相匹配的節點。然後由各節點採用預設關聯分析算法並行進行序列模式的關聯分析，如廣義序貫模式(Generalized Sequential Pattern，GSP)算法，具體來說，各節點對投影資料庫執行掃描、合併和剪枝的步驟，獲得頻繁項集以及對應支持度。每個節點僅能夠獲得原始資料庫的各頻繁項集中的一部分頻繁項集，為了與原始資料庫的全部頻繁項集進行區分，將每個節點所獲得的頻繁項集稱為局部頻繁項集，將原始資料庫的全部頻繁項集稱為全域頻繁項集。另外需要說明的是，這裡所說的節點運行在一個單機上，單機可以是物理機也可以是虛擬機本實施例中對此不做限定。

通過為各投影資料庫分配負載能力與所述投影資料庫的資料量相匹配的節點，避免出現有些節點負載過重而另一些節點空閒的情況出現，從而更加合理和高效地利用現有節點，加快關聯分析速度，提高關聯分析的效率。

步驟103、對各節點關聯分析所獲得的局部頻繁項集以及對應支持度進行匯總，獲得全域頻繁項集以及對應支持度。

具體地，將各節點關聯分析所獲得的局部頻繁項集以及對應支持度匯總到一個文件既可，從而該文件中記錄的為全域頻繁項集以及對應支持度，而無需執行合併和剪枝的步驟。

本實施例中，通過將原始資料庫劃分為相互之間不貢獻支持度的各投影資料庫，由各節點分別對所對應的投影資料庫進行序列模式的關聯分析，然後對各節點獲得的局部頻繁項集以及對應支持度進行匯總。由於所建立的投影資料庫相互之間不貢獻頻繁項集的支持度，可以由不同節點分別對不同的投影資料庫進行包括剪枝步驟在內的關聯挖掘，各節點所獲得的為資料量較小的局部頻繁項集，避免現有技術中需要傳輸各節點未經過剪枝步驟所獲得的資料量較大的局部候選頻繁項集的情況，從而節省了傳輸開銷，提高了效率。

實施例二

圖2為本發明實施例二提供的一種關聯分析方法的流程示意圖，本實施例所提供的關聯分析方法可以由軟體執行，該軟體可以運行在大資料計算服務(Open Data Processing Service，簡稱ODPS)平臺上，本實施例所提供的方法可以運行在映射規約(MapReduce)軟體框架下由多個節點執行，在MapReduce軟體框架下包括一個主節點(master)，和多個從節點(workers)，主節點可以對各從節點分配映射(Map)作業(用來把一組鍵值對映射成一組新的鍵值對)或者規約(Reduce)作業(用來保證所有映射的鍵值對中的每一個共享相同的鍵組)，分配到Map作業的從節點又可以稱為Map節點，分配到Reduce作業的從節點又可以稱為Reduce節點。每一個節點可以運行在一個物理機或者虛擬機上，本實施例中對此不做限定。如圖2所示，方法包括：

步驟201、主節點對從節點進行調度以使從節點進行資料預處理。

具體地，主節點將資料預處理作為一項MapReduce任務，調度從節點執行該任務，從而針對原始資料進行資料序列化操作。具體通過根據映射表將原始資料中所記載的各用戶執行操作的不同的操作對象分別用數字或者字母序列進行標識，並針對同一用戶執行操作的操作對象按照操作時間進行排序。

步驟202、從節點在主節點調度下基於原始資料庫D計算K_頻繁項集，將每一個K_頻繁項集分配至一個Map節點進行處理。

需要說明的是，1K<N，N為原始資料庫中所包含的元素數。

步驟203、各Map節點根據每一個K_頻繁項集遍歷原始資料庫D中的一個分片資料，獲得每一個K_頻繁項集的投影資料庫D’的一部分。

具體地，每一個Map節點均根據各K_頻繁項集將原始資料庫D的一個分片資料中的資料劃分為前綴和後綴兩部分，由全部Map節點所獲得的對應某一個K_頻繁項集的後綴部分所構成的投影資料庫D’即為該K_頻繁項集的投影資料庫D’。具體來說，在各事務中，將該K_頻繁項集作為前綴，查詢該前綴首次出現的位置之後的序列，若前綴的最後一個元素與所查找到的序列的第一個元素的時序相同，則將“_”和所查找到的序列作為後綴，否則，直接將所查找到的序列作為後綴。構建由各事務中的後綴所構成的該K_頻繁項集的投影資料庫D’。

Map節點的個數可以為多個，各Map節點獲取到原始資料庫D中的一個分片資料，這裡的分片是簡單的資料分片，每一個Map節點將各K_頻繁項集作為鍵，遍歷分片資料中的各事務，獲得各個鍵或者說各個K_頻繁項集對應的鍵值，將所獲得的鍵值輸出至該K_頻繁項集對應的Reduce節點，從而該K_頻繁項集對應的Reduce節點從全部Map節點所接收到的資料構成了該K_頻繁項集的投影資料庫D’。例如：若存在m個K_頻繁項集，3個分片資料時，Map節點1基於m個K_頻繁項集將原始資料庫D的第一個分片資料劃分為前綴和後綴兩部分，Map節點2基於m個K_頻繁項集將原始資料庫D的第二個分片資料劃分為前綴和後綴兩部分，Map節點3基於m個K_頻繁項集將原始資料庫D的第三個分片資料劃分為前綴和後綴兩部分。

需要說明的是，投影資料庫D’中“_”用於表示前綴自身，且該前綴為後綴中第一個項目的元素，該第一個項目除了該前綴外還有其他元素。

對於相同前綴的各事務，可以看出其產生的頻繁項集也具有相同的前綴，因此將各事務中同一前綴首次出現的位置之後的序列合併為投影資料庫，不同投影資料庫所關聯分析獲得的頻繁項集不會出現重複的情況，因而也就互不貢獻支持度。從而不同的Reduce節點可以針對不同的投影資料庫獨立的進行關聯分析挖掘，包括對候選頻繁項集剪枝獲得頻繁項集的過程也在本地Reduce節點，避免了匯總候選頻繁項集及其本地支持度。

可見，本實施例中所提供的方法不同於目前不同的Reduce節點關聯分析獲得的候選頻繁項集會出現重複的情況，因而不需要匯總Reduce節點所關聯分析獲得的候選頻繁項集其本地支持度之後，才能夠進行合併和剪枝，最終獲得全域頻繁項集。因此，本實施例中的方法，能夠有效避免匯總候選頻繁項集及其本地支持度，而各Reduce節點候選頻繁項集的往往是該Reduce節點的分片資料的資料量的指數倍，因此，本實施例中的方法極大減少了進行資料傳輸的資料量。

步驟204、各Reduce節點從全部Map節點接收所對應的K_頻繁項集的投影資料庫D’的一部分，獲得所對應的K_頻繁項集的投影資料庫D’，對投影資料庫D’進行並行關聯分析處理。

具體的，MapReduce軟體框架包括多個Reduce節點，每一個Reduce節點對應一個K_頻繁項集。每一個Reduce節點從全部Map節點接收所對應的K_頻繁項集的投影資料庫D’的一部分，從而獲得所對應的K_頻繁項集的投影資料庫D’，進而對該K_頻繁項集的投影資料庫D’進行關聯分析處理，獲得頻繁項集及其支持度。

例如：Reduce節點1基於投影資料庫D’₁進行關聯分析處理，Reduce節點2基於投影資料庫D’₂進行關聯分析處理，……Reduce節點m基於投影資料庫D’_m進行關聯分析處理。

其中，各Reduce節點可以採用GSP算法進行關聯分析處理從而獲得前述的頻繁項集及其支持度，也可以採用其他關聯分析算法而不會影響本實施例所提供的方法的使用效果，本實施例中GSP算法僅作為示範說明本實施例所提供的方法。GSP算法是通過掃描投影資料庫D’得到長度為i的序列作為初始序列，然後根據長度為i的初始序列，經過合併和剪枝的操作，產生長度為i+1的序列，並將產生的序列作為新的初始序列，重複迭代執行掃描、合併和剪枝的操作，直至不再產生新的序列，用所獲得的序列表示候選頻繁項集。基於投影資料庫D’計算候選頻繁項集的支持度，然後根據預設的篩選條件進行篩選，獲得頻繁項集。

需要說明的是，i的初始取值應當等於作為前綴的頻繁項集的序列長度。

具體可以採用如下所示的GSP算法偽代碼：

其中，candidate-gen-SPM(F_k-1)的算法流程如下：

1、合併：對所產生的k-1_候選頻繁項集F_k-1進行合併，產生k_候選頻繁項集F_k。

具體地，當k=2時，對於兩個1_候選項集F₁的序列s₁和s₂，需要將s₂的項目要以s₁的項目中的一部分和以一個單獨的項目兩種方式合併到s₁。即合併<a>和<b>，產生的候選頻繁項級有<(a，b)>、<a，a>、<a，b>、<b，a>和<b，b>。

需要說明的是，<(a，b)>表示a，b同時發生，<a，b>表示先發生a，後發生b。

當k取大於2的正整數時，對於兩個序列s₁和s₂，如果將s₁的第1個項目去掉後得到的餘串和將s₂的最後一個項目去掉後得到的餘串相同，則可以將s₁和s₂合併。所得的候選序列是將s₂的最後一個項目添加到s₁末尾，這裡針對兩種不同情況有兩種添加方式：如果s₂最後一個項目是一個單獨的元素，則這個項目將以一個單獨項目的形式加到s₁的末尾，否則，s₂最後一個項目將作為s₁的最後一個項目中的一個部分合併入s₁。

2、剪枝：對合併所獲得的k_候選頻繁項集F_k進行剪枝，獲得k_頻繁項集F_k。

具體地，剪枝是指如果一個k_候選頻繁項集F_k的任何一個子集是非頻繁的，則這個k_候選頻繁項集F_k將被去除。

Reduce節點基於前述掃描、合併和剪枝的步驟以及篩選的步驟，獲得關聯分析處理結果，即頻繁項集及其支持度。

步驟205、各Reduce節點對關聯分析處理結果輸出。

具體的，各節點可以直接輸出關聯分析處理結果，還可以在輸出之前，根據映射表對結果進行反序列化處理，從而輸出反序列化處理後的關聯分析處理結果。

步驟206、對各Reduce節點輸出的關聯分析處理結果進行匯總。

具體的，可以主節點調度從節點直接合併各Reduce節點輸出的結果，匯總為一個文件既可。由於各K_頻繁項集的投影資料庫D’相互之間不貢獻支持度，可以由不同節點分別對不同的投影資料庫進行包括剪枝步驟在內的關聯挖掘，各節點所輸出的關聯分析處理結果為資料量較小的局部頻繁項集，避免現有技術中需要傳輸各節點未經過剪枝步驟所獲得的資料量較大的局部候選頻繁項集的情況，從而節省了傳輸開銷，提高了效率。

為了清楚說明本實施例，本實施例提供了一個具體的實例以對本實施例所提供的方法進行詳細說明。

例如：圖3為關聯分析方法執行過程的示意圖，如圖3所示，針對表1中的原始資料進行序列化。在表1中，原始資料的每一行對應一個用戶，列向量從左至右依次為用戶標識和操作對象以及對該操作對象執行操作的操作時間。

表1中的原始資料記錄到了甲、乙、丙用戶分別於不同日期執行了三次購買操作，根據如下映射表：蘋果→a 梨→b 桃→c 香蕉→d

執行資料序列化操作，獲得原始資料庫D。在原始資料庫D中所記載的內容如下所示：abc,abc,ac；bc,a,ab；a,b,d。

需要說明的是，每一行代表一個事務，在每一個事務中，用逗號分隔各個項目。

基於前述原始資料庫D，進行序列模式的關聯分析，計算1_候選頻繁項集及其支持度，如下表所示。

若預先設置了以支持度2作為最小支持度閾值，也就是說支持度小於2的候選頻繁項集將會被過濾掉，從而獲得1_頻繁項集<a>，<b>，<c>。

在每一個Map節點中構建各1_頻繁項集的投影資料庫的一部分，Reduce節點從每個Map節點接收對應1_頻繁項集的投影資料庫一部分，匯總獲得該1_頻繁項集的投影資料庫，進行關聯分析處理。

將1_頻繁項集<a>作為前綴a，構建前綴a的投影資料D’_a，所構建的前綴a的投影資料庫D’_a如下所示：_bc,abc,ac ab b,d。

將1_頻繁項集<b>作為前綴b，構建前綴b的投影資料D’_b，所構建的前綴b對應的投影資料庫D’_b如下所示：_c,abc,ac _c,a,ab d。

將1_頻繁項集<c>作為前綴c，構建前綴c的投影資料D’_c，所構建的前綴c對應的投影資料庫D’_c如下所示：abc,ac a,ab

在前面的步驟中已獲得1_頻繁項集<a>，<b>，<c>。根據1_頻繁項集所獲得的2_候選頻繁項集如下所示：<(a，b)>，<(a，c)>，<(b，c)>，<a，a>，<a，b>，<a，c>，<b，a>，<b，b>，<b，c>，<c，a>，<c，b>，<c，c>。

資料庫D已被劃分為前綴a的投影資料庫D’_a，前綴b的投影資料庫D’_b，前綴c的投影資料庫D’_c，並分別由不同Reduce節點進行關聯分析處理，如在Reduce節點1中，對於<(a，b)>，<(a，c)>，<a，a>，<a，b>，<a，c>只需要基於投影資料庫D’_a計算支持度。

同理，Reduce節點2對於<(b，c)>，<b，a>，<b，b>，<b，c>只需要基於投影資料庫D’_b計算支持度。

Reduce節點3對於<c，a>，<c，b>，<c，c>只需要基於投影資料庫D’_c計算支持度。

可以針對各個Reduce節點設置相同的支持度閾值作為篩選條件，當頻繁項集的支持度大於該支持度閾值時，篩選通過並保留，否則篩選掉而不進行保留。當支持度閾值為1時，各Reduce節點分別保留如下頻繁項集：

各個Reduce節點對篩選後的頻繁項集，根據映射表進行反序列化處理，進而各個Reduce節點輸出反序列化處理後的關聯分析處理結果，下表為各Reduce節點輸出的反序列化處理後的關聯分析處理結果示意。

對各Reduce節點輸出的結果進行匯總，匯總獲得的文件內容如下所示

本實施例中，通過對原始資料庫進行關聯分析計算，獲得至少兩個初始項集之後，將各初始項集作為前綴，建立各前綴的投影資料庫，由各節點分別對所對應的投影資料庫進行序列模式的關聯分析，然後對各節點獲得的局部頻繁項集以及對應支持度進行匯總。由於至少兩個初始項集之間不存在相互包含關係，所以據此所建立的投影資料庫相互之間不貢獻頻繁項集的支持度，可以由不同節點分別對不同的投影資料庫進行包括剪枝步驟在內的關聯挖掘，各節點所獲得的為資料量較小的局部頻繁項集，避免現有技術中需要傳輸各節點未經過剪枝步驟所獲得的資料量較大的局部候選頻繁項集的情況，從而節省了傳輸開銷，提高了效率。

實施例三

圖4為本發明實施例所提供的一種關聯分析裝置的結構示意圖，如圖4所示，包括：劃分模組42、分析模組43和匯總模組44。

劃分模組42，用於將原始資料庫劃分為各投影資料庫，所述各投影資料庫相互之間不貢獻頻繁項集的支持度。

分析模組43，用於由各節點分別對所述投影資料庫進行序列模式的關聯分析，獲得局部頻繁項集以及對應支持度。

具體地，分析模組43具體用於採用預設關聯分析算法，由節點對所述投影資料庫執行掃描、合併和剪枝的步驟，獲得局部頻繁項集以及對應支持度。其中，關聯分析算法包括GSP算法。

匯總模組44，用於對各節點關聯分析所獲得的局部頻繁項集以及對應支持度進行匯總，獲得全域頻繁項集以及對應支持度。

進一步，本實施例還提供了一種關聯分析裝置的結構示意圖，圖5為實施例三提供的另一種關聯分析裝置的結構示意圖，如圖5所示，劃分模組42，包括：獲得單元421、建立單元422。

獲得單元421，用於對原始資料庫進行序列模式的關聯分析，獲得至少兩個初始項集。

其中，所述至少兩個初始項集之間不存在相互包含關係。

建立單元422，用於將各初始項集作為前綴，建立各前綴的投影資料庫。

進一步，獲得單元421，包括：計算子單元4211、確定子單元4212篩選子單元4213。

計算子單元4211，用於計算原始資料庫的k_頻繁項集。

其中k為正整數，且1k<N，N為原始資料庫中所包含的元素數。

確定子單元4212，用於將所述k_頻繁項集作為所述初始項集。

篩選子單元4213，用於根據預設的支持度閾值，對k_頻繁項集進行篩選，保留支持度大於所述支持度閾值的k_頻繁項集。

進一步，建立單元422，包括：查詢子單元4221和建立子單元4222。

查詢子單元4221，用於將所述初始項集作為前綴，在所述原始資料庫的各事務中查詢所述前綴所對應的後綴；建立子單元4222，用於將各事務的後綴進行匯總形成所述前綴的投影資料庫。

本實施例中，通過對原始資料庫進行關聯分析計算，獲得至少兩個初始項集之後，將各初始項集作為前綴，建立各前綴的投影資料庫，由各節點分別對所對應的投影資料庫進行序列模式的關聯分析。由於至少兩個初始項集之間不存在相互包含關係，所以據此所建立的投影資料庫相互之間不貢獻頻繁項集的支持度，可以由不同節點分別對不同的投影資料庫進行包括剪枝步驟在內的關聯挖掘，各節點所獲得的為資料量較小的局部頻繁項集，避免現有技術中需要傳輸各節點未經過剪枝步驟所獲得的資料量較大的局部候選頻繁項集的情況，從而節省了傳輸開銷，提高了效率。

實施例四

圖6為實施例四提供的一種關聯分析裝置的結構示意圖，在上一實施例的基礎上，本實施例中的裝置，還包括：分配模組61。

分配模組61，用於為各投影資料庫分配負載能力與所述投影資料庫的資料量相匹配的節點。

進一步，關聯分析裝置還包括：序列化模組62和反序列化模組63。

序列化模組62，用於根據映射表，對原始資料進行序列化獲得原始資料庫。

反序列化模組63，用於對各節點關聯分析所獲得的局部頻繁項集以及對應支持度進行匯總之前，對所述局部頻繁項集進行反序列化；或者，獲得全域頻繁項集以及對應支持度之後，對所述全域頻繁項集進行反序列化。

本實施例中，通過對原始資料庫進行關聯分析計算，獲得至少兩個初始項集之後，將各初始項集作為前綴，建立各前綴的投影資料庫，由各節點分別對所對應的投影資料庫進行序列模式的關聯分析。由於至少兩個初始項集之間不存在相互包含關係，所以據此所建立的投影資料庫相互之間不貢獻頻繁項集的支持度，可以由不同節點分別對不同的投影資料庫進行包括剪枝步驟在內的關聯挖掘，各節點所獲得的為資料量較小的局部頻繁項集，避免現有技術中需要傳輸各節點未經過剪枝步驟所獲得的資料量較大的局部候選頻繁項集的情況，從而節省了傳輸開銷，提高了效率。另外，針對各投影資料庫可能具有不同的規模的特點，為各投影資料庫分配負載能力與所述投影資料庫的資料量相匹配的節點，避免出現有些節點較為空閒，而另外一些節點過載的情況發生從而進一步提高關聯分析的效率。

本領域普通技術人員可以理解：實現上述各方法實施例的全部或部分步驟可以通過程式指令相關的硬體來完成。前述的程式可以儲存於一計算機可讀取儲存媒體中。該程式在執行時，執行包括上述各方法實施例的步驟；而前述的儲存媒體包括：ROM、RAM、磁碟或者光碟等各種可以儲存程式代碼的媒體。

最後應說明的是：以上各實施例僅用以說明本發明的技術方案，而非對其限制；儘管參照前述各實施例對本發明進行了詳細的說明，本領域的普通技術人員應當理解：其依然可以對前述各實施例所記載的技術方案進行修改，或者對其中部分或者全部技術特徵進行等效替換；而這些修改或者替換，並不使相應技術方案的本質脫離本發明各實施例技術方案的範圍。

Claims

一種關聯分析方法，包括：將原始資料庫劃分為各投影資料庫，所述各投影資料庫相互之間不貢獻頻繁項集的支持度；由各節點分別對所對應的投影資料庫進行序列模式的關聯分析，獲得局部頻繁項集以及對應支持度；對各節點關聯分析所獲得的局部頻繁項集以及對應支持度進行匯總，獲得全域頻繁項集以及對應支持度。
根據申請專利範圍第1項所述的關聯分析方法，其中，所述將原始資料庫劃分為各投影資料庫，包括：對所述原始資料庫進行序列模式的關聯分析，獲得至少兩個初始項集；其中，各初始項集之間不存在相互包含關係；將各初始項集作為前綴，建立各前綴的投影資料庫。
根據申請專利範圍第2項所述的關聯分析方法，其中，所述對原始資料庫進行關聯分析計算，獲得至少兩個初始項集，包括：計算原始資料庫的K_頻繁項集；其中K為正整數，且1K<N，N為原始資料庫中所包含的元素數；將所述K_頻繁項集作為所述初始項集。
根據申請專利範圍第3項所述的關聯分析方法，其中，所述將K_頻繁項集作為所述初始項集之前，還包括：根據預設的支持度閾值，對K_頻繁項集進行篩選，保留支持度大於所述支持度閾值的K_頻繁項集。
根據申請專利範圍第2項所述的關聯分析方法，其中，所述將各初始項集作為前綴，建立各前綴的投影資料庫，包括：將所述初始項集作為前綴，在所述原始資料庫的各事務中查詢所述前綴所對應的後綴；將各事務的後綴進行匯總形成所述前綴的投影資料庫。
根據申請專利範圍第1項所述的關聯分析方法，其中，所述由各節點分別對所對應的投影資料庫進行序列模式的關聯分析之前，包括：為各投影資料庫分配負載能力與所述投影資料庫的資料量相匹配的節點。
根據申請專利範圍第1項所述的關聯分析方法，其中，所述由各節點分別對所對應的投影資料庫進行序列模式的關聯分析，獲得局部頻繁項集以及對應支持度，包括：採用預設關聯分析算法，由所述節點對所述投影資料庫執行掃描、合併和剪枝的步驟，獲得局部頻繁項集以及對應支持度。
根據申請專利範圍第7項所述的關聯分析方法，其中，所述關聯分析算法包括GSP算法。
根據申請專利範圍第1-8項任一項所述的關聯分析方法，其中，所述對原始資料庫進行關聯分析計算，獲得至少兩個初始項集之前，還包括：根據映射表，對原始資料進行序列化獲得原始資料庫。
根據申請專利範圍第9項所述的關聯分析方法，其中，所述對各節點關聯分析所獲得的局部頻繁項集以及對應支持度進行匯總之前，對所述局部頻繁項集進行反序列化；或者，獲得全域頻繁項集以及對應支持度之後，對所述全域頻繁項集進行反序列化。
一種關聯分析裝置，包括：劃分模組，用於將原始資料庫劃分為各投影資料庫，所述各投影資料庫相互之間不貢獻頻繁項集的支持度；分析模組，用於由各節點分別對所述投影資料庫進行序列模式的關聯分析，獲得局部頻繁項集以及對應支持度；匯總模組，用於對各節點關聯分析所獲得的局部頻繁項集以及對應支持度進行匯總，獲得全域頻繁項集以及對應支持度。
根據申請專利範圍第11項所述的關聯分析裝置，其中，所述劃分模組，包括：獲得單元，用於對原始資料庫進行序列模式的關聯分析，獲得至少兩個初始項集；其中，各初始項集之間不存在相互包含關係；建立單元，用於將各初始項集作為前綴，建立各前綴的投影資料庫。
根據申請專利範圍第12項所述的關聯分析裝置，其中，所述獲得單元，包括：計算子單元，用於計算原始資料庫的K_頻繁項集；其中K為正整數，且1K<N，N為原始資料庫中所包含的元素數；確定子單元，用於將所述K_頻繁項集作為所述初始項集。
根據申請專利範圍第13項所述的關聯分析裝置，其中，所述獲得單元，還包括：篩選子單元，用於根據預設的支持度閾值，對K_頻繁項集進行篩選，保留支持度大於所述支持度閾值的K_頻繁項集。
根據申請專利範圍第12項所述的關聯分析裝置，其中，所述建立單元，包括：查詢子單元，用於將所述初始項集作為前綴，在所述原始資料庫的各事務中查詢所述前綴所對應的後綴；建立子單元，用於將各事務的後綴進行匯總形成所述前綴的投影資料庫。
根據申請專利範圍第11項所述的關聯分析裝置，其中，所述裝置，還包括：分配模組，用於為各投影資料庫分配負載能力與所述投影資料庫的資料量相匹配的節點。
根據申請專利範圍第11項所述的關聯分析裝置，其中，所述分析模組，具體用於採用預設關聯分析算法，由節點對所述投影資料庫執行掃描、合併和剪枝的步驟，獲得局部頻繁項集以及對應支持度。
根據申請專利範圍第17項所述的關聯分析裝置，其中，所述關聯分析算法包括GSP算法。
根據申請專利範圍第11-18項任一項所述的關聯分析方法，其中，所述裝置，還包括：序列化模組，用於根據映射表，對原始資料進行序列化獲得原始資料庫。
根據申請專利範圍第19項所述的關聯分析裝置，其中，所述裝置，還包括：反序列化模組，用於對各節點關聯分析所獲得的局部頻繁項集以及對應支持度進行匯總之前，對所述局部頻繁項集進行反序列化；或者，獲得全域頻繁項集以及對應支持度之後，對所述全域頻繁項集進行反序列化。