[發明專利]一種基于位圖數據結構的數據分析方法及裝置

有效

• 申請號: 201710872848.7
• 申請日: 2017-09-25
• 公開（公告）號: CN107622121B
• 公開（公告）日: 2020-06-23
• 發明（設計）人: 劉東岳;吳斌;王柏;卜堯;郭志紅;楊祎;馬艷;辜超;白德盟;林穎;秦佳峰
• 申請（專利權）人: 北京郵電大學
• 主分類號: G06F16/2458
• 分類號: G06F16/2458
• 代理公司: 北京柏杉松知識產權代理事務所(普通合伙) 11413
• 代理人: 馬敬;項京

本發明實施例提供了一種基于位圖數據結構的數據分析方法及裝置，該方法包括：獲得主節點分配的第一事務子集合；獲得總數目及排序；根據排序確定每一目標項目的位圖數據；統計每一目標項目的位圖數據中第一數據與總數目之間的比例，根據統計的比例確定目標項目中的頻繁1項集；將為頻繁1項集的目標項目和為頻繁1項集的目標項目的位圖數據，廣播至主節點和其他分布式子節點；接收統計項目和統計項目的位圖數據；基于接收到的統計項目、統計項目的位圖數據和為頻繁1項集的目標項目的位圖數據，計算目標項集是否為頻繁項集；若目標項集為頻繁項集，確定目標項集中各個項目之間的關聯規則。這樣，可以快速地得到關聯規則以及項目之間的關聯關系。

技術領域

本發明涉及數據挖掘技術領域，特別是涉及一種基于位圖數據結構的數據分析方法及裝置。

背景技術

隨著數據爆炸式地增長，人們越來越迫切地想要從大量已有數據中挖掘出有價值的信息，進而根據這些有價值的信息制定相應的決策。

例如，對于大型零售商場而言，這些商場每年都會產生數以萬計的交易記錄，其中，每條交易記錄對應有一個訂單號，一個訂單號對應有多個物品名。然而，在未經數據挖掘之前，人們無法得到在交易過程中各個物品之間的關聯規則(例如買咖啡的人中，60％的人同時還買了糕點)。而通過數據挖掘后，便可挖掘得到交易過程中各個物品之間的購買關系，即各個物品之間的關聯規則，進而可以根據得到的關聯規則為商場的營銷決策提供支持。

其中，在數據挖掘過程中，常常通過該大型零售商場中的一條交易記錄得到一個事務，并將該大型零售商場中不同的物品記為不同的項目。具體地，針對每條交易記錄而言，可以將該條交易記錄對應的訂單號作為對應事務的事務標識，并將該訂單號對應的每一種物品名作為該事務的一個項目。這樣，對于該大型零售商場一年的交易記錄而言，可以得到由多個事務構成的事務集合，且每個事務中可以包含一個或多個項目。然后，利用頻繁項集挖掘算法：ECLAT算法來挖掘出事務集合中的頻繁項集，進而，再根據頻繁項集計算出各個項目之間的關聯規則。

具體地，假設事務集合中存在10000個事務，利用ECLAT算法計算得到：該事務集合中項集{項目A，項目B}出現了100次，即項目A和項目B同時出現的次數為100次。從而，可以算出項集{項目A，項目B}出現的概率為0.01，即項集{項目A，項目B}的支持度為0.01。若0.01大于預設最小支持度，那么項集{項目A，項目B}即為頻繁2項集，進而可以根據該頻繁2項集{項目A，項目B}計算出項目A和項目B之間的關聯關系。

但是，發明人發現，在使用ECLAT算法計算頻繁項集的過程中，需要利用項目B與每個包含項目A的事務中每個項目進行匹配，若匹配成功，則表明包含項目A的事務中也包含事務B，此時對項集{項目A，項目B}出現的次數增一。然后，利用項目A與每個包含項目B的事務中每個項目進行匹配，若匹配成功，則表明包含項目B的事務中也包含事務A此時對項集{項目A，項目B}出現的次數增一，這樣，可以統計得到項集{項目A，項目B}出現的次數。但是，這種的匹配速度非常慢，從而使得獲得關聯規則的速度較慢。

發明內容

本發明實施例的目的在于提供一種基于位圖數據結構的數據分析方法及裝置，以快速地分析得到關聯規則，從而快速獲得項目之間的關聯關系。

第一方面，本發明實施例提供了一種基于位圖數據結構的數據分析方法，應用于分布式系統所包含分布式子節點中的一個分布式子節點，該分布式系統包括：主節點和分布式子節點，該方法可以包括：

獲得主節點分配的第一事務子集合，其中，第一事務子集合為：事務集合的子集合；

獲得事務集合中事務的總數目及事務集合中事務的排序；