一種基于相關系數加權的離散型數據填補算法與分析

王志剛 田立勤 毛亞瓊

摘? 要： 為解決具有關聯性數據的缺失值問題，提出一種結合相關系數與相似性匹配作用于離散型數據填補缺失值的方法。首先，在非缺失數據源中挖掘頻繁項集并計算數據屬性間的相關性，計算出挖掘項的項內整體的相關性;然后，根據缺失數據所在項的非缺失前項與完整數據挖掘項的相似度選擇填補項;填補項相似性一致則利用加權置信度進一步選取填補規則，一方面提高了Apriori挖掘規則集合的數量及質量，另一方面也保證了規則匹配的可靠性。經實驗與相關方法比較，該方法提高了缺失數據填補的準確率與時間效率。

關鍵詞： 離散數據填補; 加權支持度; 相關系數加權; 缺失值填補; 頻繁項集挖掘; 填補規則選取

中圖分類號： TN911.1?34? ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼： A? ? ? ? ? ? ? ? ? ? ? ? 文章編號： 1004?373X（2020）09?0109?04

Analysis on discrete data filling algorithm based on correlation coefficient weighting

WANG Zhigang1， TIAN Liqin2， MAO Yaqiong1

（1. Qinghai Normal University， Xining 810008， China;

2. North China Institute of Science and Technology， Beijing 101601， China）

Abstract： In order to solve the problem of missing values of correlation data， a method combining correlation coefficient and similarity matching is proposed to fill the missing values of discrete data. The frequent item sets are mined in non?missing data sources and the correlation between the data attributes is calculated to get the overall inter?item correlation. Then， the items under filling are selected according to the similarity between the non?missing previous item in the item of missing data and the complete data mining item. If the similarity of the items under filling is similar， filling rules are further selected by weighted confidence， so as to improve the quantity and quality of Apriori mining rule sets and guarantee the reliability of rule matching. Contrastive experiments were performed between the proposed method and other related methods. The experimental results verify that the proposed method can improve the accuracy and time efficiency of missing data filling.

Keywords： discrete value filling; weighted support; correlation coefficient weighting; missing value filling; frequent item set mining; filling rule selection

0? 引? 言

數據分析的前提是要求數據本身具有較高的可用性，刪除相關數據或不作處理都將降低源數據庫的利用價值，而采用恰當的填補缺失的方法處理數據能夠提高數據質量，可靠的數據輸出能為精準的數據分析結果奠定基礎[1]。缺失數據的填補技術是指采用設計的方法策略將不完備的數據填補成完整的數據集，進而滿足數據分析的基本需求，提供完整可靠的數據集。缺失數據填補方法主要包括兩大類：一類是傳統的統計學方法[2]，該方法研究最為廣泛，包括均值替代法、最大期望值法、隨機回歸填充、馬爾科夫鏈蒙特卡洛法、熱卡填補方法等;另一類填補方法則基于數據挖掘，具體方法包含基于決策樹填補[3]、基于貝葉斯網絡填補[4]、基于中心聚類填補[5]、基于神經網絡填補[6?7]、基于支持向量機填補方法[8]以及關聯規則填補算法。將本文方法與經典Apriori填補算法以及長度優先選擇算法L?Apriori[9]在準確率、填補率及實時性方面進行比較。

統計學方法時間效率高，但準確率相對數據挖掘方法較低。在數據挖掘方法中，大多對連續型數值型數據精度高于離散數據。因此，本文提出一種將統計方法中的相關性（Correlation）計算與Apriori相結合的方法，針對離散型缺失數據填補方法進行研究。在關聯規則挖掘方法Apriori上改進支持度來挖掘頻繁項集，并采用余弦相似性度量選擇填補規則，彌補了對數據庫的缺失數據采用元組相似度填補數據[10]，時間效率相對較低的問題。本文方法與經典Apriori填補算法以及長度優先選擇算法L?Apriori[9]進行效率對比。

1? Apriori算法的概念及原理

1.1? 基本概念

關聯規則定義是滿足給定的支持度（Support）與置信度（Confidence）閾值的規則。

假設DB為事物數據源采集組成的數據庫，屬性[A]（Attribute）集合[A={a1，a2，…，am}]是數據庫中[m]個事物屬性數據的集合。[T={t1，t2，…，tN}]為所有[N]個記錄條目的集合，數據庫中基于時間索引的記錄[ti∈T]，每個[ti]由[A]中任意個數元素構成，因此，可以得到[ti?A]。

定義1：定義頻繁項集，若[A]的任何單個子集[I]稱為項，[k]個屬性組成的集合稱為[k]?項集，滿足支持度閾值的項目集稱為頻繁[k]?項集。

定義2：記錄包含項的表示方法定義記為[ρ（I）]，在數據庫DB中，含有項集[I]所有記錄的集合公式表示為：

[ρ（I）={tiI?ti，ti?T，T∈DB}] （1）

同理，將數據庫DB中，部分含有缺失項（Missing item）記錄的集合記為MI（[I]），那么：

[MI（I）={ti?ai?ti，ti?T，T∈DB}] （2）

定義3：某一項集[I]，基于缺失值的支持度記為[σ（I）]，[?]表示集合中所含事務數目：

[σ（I）=ρ（I）DB-MI（I）=事物集I的次數數據庫DB非缺失次數] （3）

定義4：若對于某兩個數目分別為[p]和[q]的項集賦值：[X={a1∶x1，a2∶x2，…，ap∶xp}]，[Y={b1∶x1，b2∶x2，…，][bp∶xq}]，則挖掘關聯規則[X→Y]的置信度記為[θ（X→Y）]：

[θ（X→Y）=ρ（X?Y）ρ（X）=σ（X?Y）σ（X）] （4）

式中：[X]表示規則的前項;[Y]表示后項;關聯規則的置信度是[ρ]與[σ]的比值。

頻繁項通常必須滿足給定最小支持度即支持度閾值，標記為[σ?min]，同時最小置信度為[θ?min]。

1.2? Apriori算法步驟

頻繁項目集挖掘算法Apriori根據項集的先驗知識，采用迭代的方法逐層挖掘出滿足條件的頻繁項集，再根據最小置信度與支持度的條件來產生關聯規則，過程如下：

1） 設置最小支持度[σ?min]，掃描數據庫DB，單項候選集[C1]記錄次數與該支持度比較，找出所有滿足條件，得到頻繁1?項集[L1];

2） 根據[L1]的挖掘結果組成候選項集[C2]，根據支持度閾值的條件，自連接為長度為2的項集頻繁2?項集[L2];

3） 為得到最終的[Lk]，循環由單項至[k]項，逐一使用前挖掘頻繁項[Ck-1]產生的候選項集連接為[Lk]，直到不再產生新的項集為止。

2? 加權的Apriori缺失填補算法

通過頻繁項集的挖掘，Apriori算法對系統的要求較高，算法耗費資源較多。因此，利用挖掘出的規則來計算缺失數據等應用的效率就會降低，除此之外，挖掘出的規則并沒有權衡每個屬性元素的重要性，導致挖掘出的規則也不具有較高的利用價值。為此，本文對Apriori的算法進行改進，提高挖掘出規則的可利用性和數量較多的高質量規則，提出了基于屬性間相關性的加權規則挖掘算法，即C?Apriori算法。

2.1? 填補規則選擇

利用皮爾森相關系數計算屬性的相關性，經驗證該算法對具有正態分布的數據有良好的適用性。利用皮爾森相關系數作為規則支持度加權，從而提高規則質量，采用如下定義：

定義5：設[T]是所有事務的集合，則[T={t1，t2，…，tN}]為記錄[N]個事務的集合，數據庫DB屬性相關系數矩陣見表1。[P=（pij）n×n]，式中，當[i≠j]時，[pij]表示標記的當前記錄[t]的值域中，歸屬[a]的第[i]個屬性與第[j]個屬性的相關性度量值。

定義6：設數據庫中某條記錄[ti={ip，iq，…，ix，…，ir}]，[ti]中值[ix]的屬性為[ax]，那么定義該記錄的支持提升度為：

[p（ti）=i=1，j=1i=C2ti，j=C2tipijC2ti=i=1，j=1i=C2ti，j=C2tip（ai，aj）C2ti，? ? i

計算上界為組成二元相關總個數，其中，[pij]與[p（ai，aj）]表示兩兩相關性。

定義7：項集的加權支持度[p-σ（ti）=p（ti）*σ（ti）]，其中，[σ（I）]為定義3的支持度。任意的[X]與[Y]集合，項集的條件支持度可記為：

[p-σ（X→Y）=P（X?Y）*σ（X?Y）] （6）

定義8：加權關聯規則的置信度根據定義4可得：

[p-θ（X→Y）=p-σ（X?Y）p-σ（X）] （7）

那么，假設[Ic]是在完整數據庫挖掘出的關聯規則，[Im]（[Im?Ic]）表示包含缺失屬性值的規則，且所含缺失項[Iai]包含在如定義4中[Y]所在規則的后項事務中，設含有缺失數據的記錄為[tm]，完整數據規則與缺失記錄的項集中不包含缺失項的部分用[Ic（Ai）]與[Im（Aj）]表示，則余弦相似度CS（Cosine Similarity）可表示為：

[CS（Ic（Ai），Im（Aj））=Ic（Ai）?Im（Aj）Ic（Ai）×Im（Aj）] （8）

式中[·]與定義3相同，作為公式中項的數目計算。利用相似度公式的計算，相似度區間為（0，1），若不存在缺失值為1。由于會出現相似度相同，根據定義8，基于缺失數據相關性優化的加權置信度計算，按置信度的降序排列選擇置信度最高的規則填補。

2.2? 算法流程

根據上文定義加權規則的算法，本文對缺失數據填補的策略主要步驟如下：

1） 將源數據DB分為非缺失數據部分與缺失部分，計算皮爾森相關系數，得到系數相關矩陣[P];

2） 結合Apriori挖掘算法，采用相對提升支持度的加權支持度計算方法挖掘頻繁項集;

3） 利用缺失數據項的非缺失部分，與完整數據集挖掘的規則計算余弦相似度CS，取相似度高者來填補數據，當相似度相同時，進一步利用加權置信度選擇填補規則;

4） 得到填補后的數據集[DB]。

基于C?Apriori缺失值填補算法偽代碼如下：

Input：源數據庫DB，支持度閾值[σmin]

Output：填充后數據集[DB]

1.Select non?missing and missing data to DBnon and DBmiss;

//掃描源數據庫DB，組成非缺失數據庫DBnon與缺失數據庫DBmiss

2.for [（i=1;ai∈A&&ai≠Null;i++）]

3.? ? ? for [（j=1;aj∈A&&aj≠Null;j++）]

4.? ? ? ? ?[fz]=（sum（[ai*aj]）-sum（[ai]）*sum（[aj]）） / length（[ai]）;

5.? ? ? ? ?[fm]= sqrt（（sum（[ai]^2）-（sum（[ai]））^2/length（[ai]））*（sum（[aj]^2）-（sum（[aj]））^2/length（[aj]）））;

6.? ? ? ? ?cor = fenzi/fenmu;

7.return? two?dimensional matrix array [P] from? DBnon;

//得到DBnon的相關系數矩陣[P]

8.[L1←{ll∈C1，σ（l）≥σmin}]

//1?項集不進行屬性間相關性計算

9.for [（k=2;Lk-1≠Null;k++）]

10.? ? ?for each [ti∈T&&?item≠Null]

//定義對每條不為空記錄的相關屬性計算

11. [σ（Lk）←p（ti）*σ（ti）];

//由矩陣[P]得到的相關系數計算加權支持度

12.? ? ? ? ?[Ck-1←Lk];

13.return? ?[Lk←{ll∈I1，σ（l）≥σmin}];

//算法得到所有完整數據集挖掘出的頻繁項集[Lk]

14.for each [ti?DBmiss]; //缺失數據的規則選擇填補

15.? ? ?[Iai=MissItem（ti），Iai];

//[Iai]表示[ti]的缺失項作為規則的后項，[Iai]表示非缺失項

16.? ? ?[Iai （ti）k←max{CSm（Iai（Ai），Iai（Aj））}];

//計算相同后項的前項相似度

17.? ? ?[if CSk（ti）=CSk（ti）]

18.? ? ? ? ? [t′i←max{p-θ（Iai）}];

//相關性相同采用置信度高的填補

19.return [DB]

3? 實驗結果及分析

為了驗證本文提出的C?Apriori算法的準確性與時效性，利用UCI數據集Vowel的871條包含6個屬性的源數據對算法進行驗證。本文從數據的填補準確率以及處理數據的時效性與傳統Apriori算法以及長度優先L?Apriori算法填補數據結果進行分析。

3.1? 準確率分析

數據準確率記為[A]（Accuracy），是用戶衡量填補數據質量的重要參數。在算法中，帶有缺失數據的數據庫DB中缺失數據個數記為DBM（DB?miss），填補后正確的數據個數記為DBR（DB?right），用二者的比值作為填補的準確率計算公式：

[A=DBMDBR×100%] （9）

由上式可知，準確率在0～100[%]之間，越高表示填補準確度越高。

由圖1可知，隨著支持度閾值的增加，數據填補準確率總體呈現出急速下降趨勢，但本文基于相關性的方法準確率相對較高且下降趨勢較緩慢。而圖2中隨著數據缺失率的增加，本文算法填補準確率與穩定程度均高于其他兩種算法，其中，基于傳統Apriori填補方法整體填補準確率顯著較低。

3.2? 填補時效性

在圖3中，隨著缺失數據量的增多，會導致在挖掘過程中提供的學習數據量減少，而且需填補數據比重增大，因此，這三種方法填補平均時間都呈上升趨勢。但本文方法在時間占用上稍優于對比方法，且較為穩定。

4? 結? 語

通過實驗結果分析，針對離散型數據，基于相關系數優化支持度挖掘頻繁項，能夠在一定程度上提高有效項集的挖掘，從而提高數據填補的準確率。另一方面，規則使用源數據中非缺失數據挖掘項集與缺失項之間計算相似度，避免了置信度條件不足導致的無法填充的情況，使得在數據缺失率較高的情況下依然能夠保持填充率及準確率。但由于本文選取的是適用關聯規則的離散數據驗證分析，若應用于數值型數據領域需進行專門的離散化計算與分析，在今后的研究中將進一步探索本文算法在連續數值型數據領域的應用效果。

參考文獻

[1] 曄沙.數據缺失及其處理方法綜述[J].電子測試，2017（18）：65?67.

[2] 張松蘭，王鵬，徐子偉.基于統計相關的缺失值數據處理研究[J].統計與決策，2016（12）：13?16.

[3] 沈思倩，毛宇光，江冠儒.不完全數據集的差分隱私保護決策樹研究[J].計算機科學，2017，44（6）：139?143.

[4] 王社會，楊俊安，尹海波.改進的貝葉斯矩陣修復方法[J].計算機應用，2014（z1）：127?130.

[5] 王妍，王鳳桐，王俊陸，等.基于泛化中心聚類的不完備數據集填補方法[J].小型微型計算機系統，2017，38（9）：2017?2021.

[6] 李彥，劉軍.面向大數據的多維數據缺失特征填補仿真研究[J].計算機仿真，2018，35（10）：432?435.

[7] 蔣麗麗，姜大慶.基于BP神經網絡的農資庫存數據插補技術[J].江蘇農業科學，2018，46（20）：268?271.

[8] 張嬋.一種基于支持向量機的缺失值填補算法[J].計算機應用與軟件，2013，30（5）：226?228.

[9] WU J， SONG Q， SHEN J. An novel association rule mining based missing nominal data imputation method [C]// Eighth ACIS International Conference on Software Engineering， Artificial Intelligence， Networking， and Parallel/Distributed Compu?ting. Qingdao， China： IEEE， 2007： 244?249.

[10] 王俊陸，王玲，王妍，等.基于元組相似度的不完備數據填補方法研究[J].計算機科學，2017，44（2）：98?102.