王志剛 田立勤 毛亞瓊

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

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

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

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

1? Apriori算法的概念及原理

1.1? 基本概念

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

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

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

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

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

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

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

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

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

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

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

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

頻繁項(xiàng)通常必須滿足給定最小支持度即支持度閾值，標(biāo)記為[σ?min]，同時(shí)最小置信度為[θ?min]。

1.2? Apriori算法步驟

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

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

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

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

2? 加權(quán)的Apriori缺失填補(bǔ)算法

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2? 算法流程

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

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

2） 結(jié)合Apriori挖掘算法，采用相對(duì)提升支持度的加權(quán)支持度計(jì)算方法挖掘頻繁項(xiàng)集;

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

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

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

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

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

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

//掃描源數(shù)據(jù)庫(kù)DB，組成非缺失數(shù)據(jù)庫(kù)DBnon與缺失數(shù)據(jù)庫(kù)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的相關(guān)系數(shù)矩陣[P]

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

//1?項(xiàng)集不進(jìn)行屬性間相關(guān)性計(jì)算

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

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

//定義對(duì)每條不為空記錄的相關(guān)屬性計(jì)算

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

//由矩陣[P]得到的相關(guān)系數(shù)計(jì)算加權(quán)支持度

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

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

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

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

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

//[Iai]表示[ti]的缺失項(xiàng)作為規(guī)則的后項(xiàng)，[Iai]表示非缺失項(xiàng)

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

//計(jì)算相同后項(xiàng)的前項(xiàng)相似度

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

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

//相關(guān)性相同采用置信度高的填補(bǔ)

19.return [DB]

3? 實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證本文提出的C?Apriori算法的準(zhǔn)確性與時(shí)效性，利用UCI數(shù)據(jù)集Vowel的871條包含6個(gè)屬性的源數(shù)據(jù)對(duì)算法進(jìn)行驗(yàn)證。本文從數(shù)據(jù)的填補(bǔ)準(zhǔn)確率以及處理數(shù)據(jù)的時(shí)效性與傳統(tǒng)Apriori算法以及長(zhǎng)度優(yōu)先L?Apriori算法填補(bǔ)數(shù)據(jù)結(jié)果進(jìn)行分析。

3.1? 準(zhǔn)確率分析

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

[A=DBMDBR×100%] （9）

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

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

3.2? 填補(bǔ)時(shí)效性

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

4? 結(jié)? 語(yǔ)

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

參考文獻(xiàn)

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

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

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

[4] 王社會(huì)，楊俊安，尹海波.改進(jìn)的貝葉斯矩陣修復(fù)方法[J].計(jì)算機(jī)應(yīng)用，2014（z1）：127?130.

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

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

[7] 蔣麗麗，姜大慶.基于BP神經(jīng)網(wǎng)絡(luò)的農(nóng)資庫(kù)存數(shù)據(jù)插補(bǔ)技術(shù)[J].江蘇農(nóng)業(yè)科學(xué)，2018，46（20）：268?271.

[8] 張嬋.一種基于支持向量機(jī)的缺失值填補(bǔ)算法[J].計(jì)算機(jī)應(yīng)用與軟件，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ù)填補(bǔ)方法研究[J].計(jì)算機(jī)科學(xué)，2017，44（2）：98?102.