[發明專利]一種應用哈希Hash劃分桶快速獲得鄰域的方法

有效

• 申請號: 201310261081.6
• 申請日: 2013-06-26
• 公開（公告）號: CN103345491B
• 公開（公告）日: 2016-11-23
• 發明（設計）人: 蔣云良;曾志勇;劉勇
• 申請（專利權）人: 浙江大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 浙江杭州金通專利事務所有限公司 33100
• 代理人: 劉曉春

技術領域

本發明屬于信息處理領域，尤其涉及一種以二范數距離為度量，采用哈希（Hash）劃分桶縮小鄰域信息粒子搜索空間的快速獲得鄰域的方法。

背景技術

隨著信息技術的迅速發展以及數據庫管理系統的廣泛應用，人們記錄的數據越來越多。激增的數據背后隱藏著許多重要的信息，人們希望能夠對其進行更高層次的分析，以便更好地利用這些數據。

T.Y.Lin于1988年提出了鄰域模型的概念，他通過使用空間鄰域實現對論域的粒化，并將空間鄰域理解為基本的信息粒子，而后利用這些基本信息粒子來描述論域中的其他概念。在1998年，姚一豫教授以及在2002年吳偉志教授對鄰域算子和鄰域系統的基本系統性質分別進行了深入的研究。Yao討論了粒計算與粗糙集、商空間等數據挖掘工具之間的關系，并且通過采用邏輯決策語言來描述粒度，構建粒度世界的邏輯框架。Skowron在文獻中也描述了粒語言，他將信息表上定義的邏輯公式的意義集看做信息粒，并討論了這種信息粒的語法和語義。在這些研究的基礎上，胡清華將鄰域模型引入到粗糙集中，對鄰域粗糙集模型進行了詳細的定義，并設計可以同時約簡名義型、數值型、混合型數據的約簡算法。

隨著數據的爆炸式增加，在運用鄰域模型處理大數據時，時間效率就成為了首要考慮的因素。如何減少搜索和計算鄰域信息粒子的時間，是一個值得考慮的問題。

鄰域有兩種定義方法：一種是由鄰域內所含對象的數量而定，如經典的k-近鄰方法；另一種是根據在某一度量上鄰域中心點到邊界的最大距離進行定義。本發明所涉及的鄰域為第2種方法。

實數空間上的非空有限集合U={x₁，x₂，x₃，…，x_n}，對于U上的任意對象x_i，其θ鄰域為θ(x_i)={x∈U，Δ(x,x_i)≤θ}，其中，θ≥0，θ(x_i)稱為由x_i生成的θ鄰域信息粒子，簡稱x_i的鄰域粒子，就二維實數空間而言，基于1范數、2范數和無窮范數的鄰域如圖3所示，分別為菱形、圓形和正方形區域。度量的性質有：(1)因為x_i∈θ(x_i);(2)x_j∈θ(x_i)→x_i∈θ(x_j);(3)鄰域信息粒子族{θ(x_i)|i=1，2，…n}構成U的一個覆蓋。

鄰域信息粒子族引導出論域空間U上的一個鄰域關系N，該關系可由一個關系矩陣來表示M(N)＝(r_ij)_n×n，如果x_j∈θ(x_i)，則r_ij=1否則r_ij=0。

發明內容

本發明的目的在于一種應用哈希Hash劃分桶快速獲得鄰域的方法，以減少搜索和計算鄰域信息粒子的時間，實現運用鄰域模型處理大數據的快速性。為此，本發明采用以下技術方案：

本發明方法的具體步驟如下：

一種應用哈希Hash劃分桶快速獲得鄰域的方法，其特征在于它包括如下步驟：

步驟一，求分桶坐標系的坐標原點x₀，

根據給定的鄰域系統NRS=<U，N，θ>，U是全部樣本記錄構成的集合，N表示鄰域關系，θ為鄰域半徑；

步驟二，求樣本的距離，

對于求樣本間的距離||x_i-x₀||;

步驟三，根據步驟二中的樣本距離，用Hash方法建立搜索桶：