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

有效

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

1.一種保證質量單調性的大規模數據挖掘方法，其特征在于該方法包括以下步驟：

步驟1)獲得用戶輸入的待進行挖掘的數據，數據的格式為表格的形式，一行為一條數據記錄，一行中的每一列為一個數據記錄的一個屬性，所述的數據由n'條數據記錄組成，每個數據記錄有p個屬性，將這p個屬性表示為p個變量[x₁,x₂,...,x_p]，有n'條數據記錄、每個數據記錄有p個屬性的數據集表示為：

的形式；

將該數據集按照用戶指定的比例分為訓練集和測試集兩部分，所述的訓練集是數據記錄的集合，當訓練集中的數據記錄條數為n，該訓練集表示為[X₁,X₂,...,X_i...,X_n]，其中X_i＝[x_1i,x_2i,...,x_pi],i＝1,...n；所述訓練集和測試集的比例根據用戶的要求劃分，訓練集取總樣本的80％到90％之間的任意一個值，輸入數據中訓練集之外的部分為測試集，

步驟2)對訓練集進行編碼，具體步驟如下：

步驟21)利用主成分分析PCA方法對訓練集進行預處理，獲得訓練子集具體過程如下：

①對訓練集進行標準化處理，標準化的過程按照下式進行：所述d＝1,2,…,p；j＝1,2,…n，標準化后的矩陣用“*”標記，

訓練集標準化后計算得到：

②計算樣本相關系數矩陣：

根據訓練集標準化得到的X^*，樣本相關系數為：其中t＝1,2,…n；

③求相關系數矩陣R的特征值(λ₁,λ₂,...,λ_n)和相應的特征向量a_j＝(a_1j,a_2j,…,a_nj)；

④根據相關系數矩陣R的特征值(λ₁,λ₂,...,λ_n)，依次計算貢獻率選取貢獻率較大的前g個主要屬性x₁,…,x_g，其中g＜n，將該g個屬性作為訓練數據集新的屬性，并形成訓練子集將該訓練子集表示為的形式；

所述的主成分分析是將原有的多個屬性轉化成少數具有代表性的綜合屬性，這幾個少數屬性能夠反映原來數據的大部分信息，并且各個屬性之間保持獨立；

步驟22)將訓練子集上的數據映射到R樹的數據結構上，具體過程如下：

①將訓練子集中的每個數據表示為一條記錄，并將屬性作為記錄字段存放在數據庫中，盡可能將屬性值接近的對象存放在數據庫相近位置；

②根據數據庫中存放的數據記錄從空樹開始構建R樹，從根節點r開始，根據插入數據對象后其最小包圍矩形MBR面積增加量最小的原則，插入r的臨近點作為r的子節點加入R樹，重復上述過程直到訓練子集上的所有數據都在R樹上為止，所述的R樹為一個高度平衡樹,用空間對象的MBR來近似表達空間對象，根據MBR建立R樹，直接對空間中占據一定范圍的空間對象進行索引，R樹的每個結點對應著數據庫中的數據；

步驟23)將R樹上的同層所有節點用一個二進制編碼(0,1)的一串數字表示，將R樹轉化為一組二進制編碼集；

所述編碼規則為：同層節點數越多的相應二進制編碼值大，二進制編碼集中元素的個數與R樹的層數相等；

步驟24)判斷編碼是否滿足熵的單調性；

所述熵的單調性為：假設給定一個數據集S及其上的一個數據s，如果對于任意兩個編碼值a≤b，H(S|C＝C(S＝s,a))＞＝H(S|C＝C(S＝s,b))，則證明滿足熵的單調性；所述H(S|C＝C)為條件熵H(S|C＝C)＝H(SC)-H(C),f為概率；S為數據集；C為編碼集；

選取步驟23)生成的任意多條編碼值，選取其中的兩條編碼值a、b，選取條件是a≤b，比較H(S|C＝C(S＝s,a))與H(S|C＝C(S＝s,b))兩者大小,并得到結果H(S|C＝C(S＝s,a))＞＝H(S|C＝C(S＝s,b))；根據熵的單調性可判斷該部分編碼值滿足該性質；

步驟3)獲取步驟23)中最大的編碼值，利用該編碼值對訓練數據進行挖掘；

步驟31)選定測試集中的一個數據q；

步驟32)求得q＝(x',y')與每個訓練樣例z(x,y)∈D之間的距離計算采用歐式距離計算方法，選取其中與測試數據q點帶權路徑最短的k個數據；

所述的k值選取利用k交叉驗證的方法選擇合適的k值，k交叉驗證是一種使用現有數據集的方法，將數據集分為大小相等的k份，每份輪流作為驗證集，其他k-1份則作為訓練集的驗證方法；

步驟33)分別求得k個數據中屬于同一類別的數據的個數其中然后依次比較的大小，獲得其中的最大值n_γ，其中測試樣例q的類標號由距離加權表決：根據求得的包含最多數據點q'的數據類別，對測試數據q的類別進行預測，并將q的類別判定為包含數目最多的數據q'的類別類型，所述的加權為：距離權值w_μ和距離β成反比關系,用公式計算，其中用歐式距離的計算方法來計算，即

步驟4)選取步驟23)生成的兩條編碼值a、b，根據步驟24)得到結果H(S|C＝C(S＝s,a))＞＝H(S|C＝C(S＝s,b))；分別求取H(OR|AR＝M(a))及H(OR|AR＝M(b))的值，通過比較兩者值的大小得到結果H(OR|AR＝M(a))＞＝H(OR|AR＝M(b))，根據保熵性可判斷該部分滿足其性質；

所述的保熵性描述為：假設給定一個數據集S，如果對于任意兩個長度的編碼值a＜＝b，假設H(S|C＝a)＞＝H(S|C＝b),若H(OR|AR＝M(a))＞＝H(OR|AR＝M(b))即Q(M(a))＜＝Q(M(b)),則證明挖掘部分滿足保熵性；所述M(a)為挖掘函數，輸入編碼值a輸出近似結果；所述M(b)為挖掘函數，輸入編碼值b輸出近似結果；OR為挖掘輸出的最優結果；AR為輸出的近似結果；Q(ar)為挖掘結果質量測量的測量方法；Q(ar)＝H(OR)-H(OR|AR＝ar)，ar為近似結果AR的某個值；所述Q(M(a))＝H(OR)-H(OR|AR＝M(a))，Q(M(b))＝H(OR)-H(OR|AR＝M(b))；

步驟5)