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

王志剛 田立勤 毛亞瓊

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

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

中圖分類號： 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? 引? 言

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

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

1? Apriori算法的概念及原理

1.1? 基本概念

關聯(lián)規(guī)則定義是滿足給定的支持度（Support）與置信度（Confidence）閾值的規(guī)則。

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

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

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

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

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

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

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

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

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

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

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

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

1.2? Apriori算法步驟

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

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

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

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

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

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

2.1? 填補規(guī)則選擇

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

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

定義6：設數(shù)據(jù)庫中某條記錄[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

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

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

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

定義8：加權關聯(lián)規(guī)則的置信度根據(jù)定義4可得：

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

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

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

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

2.2? 算法流程

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

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

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

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

4） 得到填補后的數(shù)據(jù)集[DB]。

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

Input：源數(shù)據(jù)庫DB，支持度閾值[σmin]

Output：填充后數(shù)據(jù)集[DB]

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

//掃描源數(shù)據(jù)庫DB，組成非缺失數(shù)據(jù)庫DBnon與缺失數(shù)據(jù)庫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的相關系數(shù)矩陣[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]得到的相關系數(shù)計算加權支持度

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

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

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

14.for each [ti?DBmiss]; //缺失數(shù)據(jù)的規(guī)則選擇填補

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

//[Iai]表示[ti]的缺失項作為規(guī)則的后項，[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數(shù)據(jù)集Vowel的871條包含6個屬性的源數(shù)據(jù)對算法進行驗證。本文從數(shù)據(jù)的填補準確率以及處理數(shù)據(jù)的時效性與傳統(tǒng)Apriori算法以及長度優(yōu)先L?Apriori算法填補數(shù)據(jù)結果進行分析。

3.1? 準確率分析

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

[A=DBMDBR×100%] （9）

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

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

3.2? 填補時效性

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

4? 結? 語

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

參考文獻

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

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

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

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

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

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

[7] 蔣麗麗，姜大慶.基于BP神經(jīng)網(wǎng)絡的農資庫存數(shù)據(jù)插補技術[J].江蘇農業(yè)科學，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] 王俊陸，王玲，王妍，等.基于元組相似度的不完備數(shù)據(jù)填補方法研究[J].計算機科學，2017，44（2）：98?102.