[發明專利]一種保證質量單調性的大規模數據挖掘方法

有效

• 申請號: 201510080263.2
• 申請日: 2015-02-13
• 公開（公告）號: CN104657473B
• 公開（公告）日: 2019-01-25
• 發明（設計）人: 陳志;黨凱樂;岳文靜;黃繼鵬;芮路
• 申請（專利權）人: 南京郵電大學
• 主分類號: G06F16/2458
• 分類號: G06F16/2458
• 代理公司: 南京經緯專利商標代理有限公司 32200
• 代理人: 葉連生

本發明給出一種保證質量單調性的數據挖掘方法，該方法將原始大數據集用PCA技術壓縮處理后映射到R?tree數據結構上；然后改進改進的K近鄰分類算法對數據集進行挖掘處理。本發明給出的方法主要包含兩部分：編碼部分及挖掘部分，其中編碼部分利用R?tree來表示數據，它將數據中有高相似性的數據組合在一起，作為R?tree的一個結點，以達到對海量數據壓縮的目的并提高挖掘部分的效率；挖掘部分利用改進的K近鄰分類算法的思想，對數據結點進行處理，預測輸入的測試點分類。本發明能解決傳統的算法在進行有限的時間及資源限制下對大數據挖掘時，很難做到挖掘結果的質量與資源限制的平衡以及保證近似結果質量單調性的問題。

技術領域

本發明涉及一種高效處理數據的方法，通過該方法來保證大規模數據挖掘結果質量的單調性，屬于數據挖掘、大數據和計算機軟件的交叉技術應用領域。

背景技術

大數據的數據容量及類型多樣性，使得我們愿意利用算法產生近似結果來對大數據進行數據挖掘，傳統的算法在進行有限的時間及資源限制下對大數據挖掘時，很難做到挖掘結果的質量與資源限制的平衡以及保證近似結果質量單調性的問題。為解決這個問題，我們在香農熵的基礎上，設計保證質量單調性的大數據挖掘方法，該挖掘方法分為兩部分：編碼部分及挖掘部分，通過保證算法編碼部分熵的單調性及挖掘部分的保熵性來確保挖掘算法輸出近似結果質量的單調性，原始數據集用PCA技術壓縮處理后映射到R-tree數據結構上的K近鄰分類的思想。該算法的編碼部分利用R-tree來表示數據，它將數據中有相似性的數據組合在一起，作為R-tree的一個結點，并盡量做到同節點內數據的高相似性，不同節點間的相對獨立性，以達到對海量數據壓縮的目的并提高挖掘部分的效率。挖掘部分利用K近鄰分類算法的思想，處理數據，建立數據分類模型，并對測試數據進行分類。

數據挖掘是數據庫知識發現(英語：Knowledge-Discovery in Databases，簡稱：KDD)中的一個步驟。數據挖掘一般是指從大量的數據中自動搜索隱藏于其中的有著特殊關系性的信息的過程。數據挖掘的一般步驟：(1)數據清理(2)數據集成(3)數據選擇(4)數據變換(5)數據挖掘(6)模式評估(7)知識表示。本發明使用的處理技術為主方法分析(PCA)技術。該技術方法通過減少數據的屬性來達到壓縮數據的目的，移除不重要的屬性。這種方法通過移除不重要的部分，保留重要部分來對海量數據壓縮，以便提高挖掘效率。

信息論中，熵表示的是不確定性的量度。信息熵可以理解成某種特定信息的出現概率(離散隨機事件的出現概率)。一個系統越是有序，信息熵就越低；反之，一個系統越是混亂，信息熵就越高。信息熵的函數說明：H＝entropy(P,r)為信息熵函數P為信源的概率矢量,r為進制數，H為信息熵。本發明中將信息熵用于R樹上，且定義如下：設R-tree為T，同層節點對應一條編碼CodeA不同層節點生成編碼集，如果編碼集中任意兩條編碼A，B都滿足ifA＜B,then A(x)＜B(x),那么編碼集單調，即該編碼集滿足熵的單調性。

發明內容

技術問題：本發明的目的是解決在計算機資源和內存有限的條件下大規模數據挖掘輸出結果質量的低效問題，該方法能夠通過保證編碼階段熵的單調性和挖掘階段的保熵性來確保挖掘質量的單調性，提高數據挖掘的輸出質量。

技術方案：本發明所述的保證質量單調性的大數據挖掘方法包括編碼、挖掘等兩個部分，其中編碼部分利用主成分分析(PCA)壓縮技術對數據進行壓縮，減少數據的屬性；壓縮處理后的數據用R樹表示，挖掘部分利用K最近鄰(KNN)算法對測試數據進行分類，并計算分類準確率。

本發明所述的保證質量單調性的大數據挖掘方法包括以下步驟：