陳小杰

一種基于灰色關(guān)聯(lián)分析的缺失數(shù)據(jù)填補(bǔ)優(yōu)化算法

陳小杰

（重慶師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，重慶 401131）

針對(duì)傳統(tǒng)KNN（k-NearestNeighbor）算法表示變量相關(guān)性不夠精確的問題，提出了改進(jìn)算法，即用灰色關(guān)聯(lián)度去替代算法中的傳統(tǒng)距離公式，得到近鄰數(shù)值，然后將KNN算法思想與DBSCAN算法思想進(jìn)行結(jié)合，排除異常值（噪聲點(diǎn)的干擾）。多次實(shí)驗(yàn)結(jié)果顯示，改進(jìn)算法的均方誤差和均方根誤差值比傳統(tǒng)方法小，證實(shí)了該改進(jìn)算法的有效性。

KNN；DBSCAN聚類；數(shù)據(jù)缺失；灰色關(guān)聯(lián)分析

1 改進(jìn)后的填補(bǔ)算法

1.1 數(shù)據(jù)標(biāo)準(zhǔn)化及缺失構(gòu)造

首先，將完整數(shù)據(jù)整理為矩陣模式，其中包含條數(shù)據(jù)實(shí)例，表示數(shù)據(jù)實(shí)例的維數(shù)，得到完整數(shù)據(jù)矩陣，記為：

1.2 缺失數(shù)據(jù)預(yù)填補(bǔ)

在R統(tǒng)計(jì)軟件中首先對(duì)以上訓(xùn)練集樣本數(shù)據(jù)進(jìn)行預(yù)填補(bǔ)，即將訓(xùn)練集樣本數(shù)據(jù)按照列分成i個(gè)樣本向量，算出每個(gè)屬性向量中數(shù)值的均值進(jìn)行初期填補(bǔ)，從而得到了一個(gè)完整無(wú)缺失的數(shù)據(jù)集記為1、2、3（對(duì)于三種缺失比例）。那么前述的數(shù)據(jù)矩陣就有：1→1、2→2、3→3。然后對(duì)缺失數(shù)據(jù)進(jìn)行預(yù)填補(bǔ)得到完整數(shù)據(jù)集。在完整數(shù)據(jù)集上進(jìn)一步工作，數(shù)據(jù)會(huì)更加有效反映出整個(gè)數(shù)據(jù)集的信息[4]，使得結(jié)果可靠精確。

1.3 灰色關(guān)聯(lián)度計(jì)算

基于傳統(tǒng)的KNN思想，對(duì)于上述缺失數(shù)據(jù)集可進(jìn)行缺失填補(bǔ)，它的算法流程大致如下[5]：

土木工程作為國(guó)民經(jīng)濟(jì)的重要組成部分，其對(duì)國(guó)民經(jīng)濟(jì)增長(zhǎng)與發(fā)展有重要作用。隨著當(dāng)前土木工程管理信息化發(fā)展速度的加快，提高管理的信息化水平，實(shí)現(xiàn)網(wǎng)絡(luò)信息技術(shù)的有效應(yīng)用對(duì)土木工程可持續(xù)發(fā)展發(fā)揮著積極作用。通過計(jì)算機(jī)技術(shù)可以實(shí)現(xiàn)信息資源的共享，同時(shí)為土木工程建設(shè)提供更加可靠的依據(jù)。時(shí)代的發(fā)展對(duì)土木工程提出了更高的要求，土木工程技術(shù)也在不斷創(chuàng)新與增加，這些都給管理提出來新的挑戰(zhàn)。實(shí)現(xiàn)土木工程信息化管理勢(shì)在必行。

1.4 KNN與DBSCAN聚類結(jié)合

KNN填補(bǔ)算法是用填補(bǔ)數(shù)據(jù)的全部個(gè)近鄰數(shù)據(jù)作為參考數(shù)據(jù)進(jìn)行計(jì)算然后得到填補(bǔ)值，在數(shù)據(jù)填補(bǔ)中不能排除異常值的影響[7]，所以筆者將DBSCAN聚類算法思想與KNN算法思想進(jìn)行結(jié)合，在聚類的同時(shí)發(fā)現(xiàn)異常點(diǎn)。DBSCAN聚類算法中有兩個(gè)重要參數(shù)，Eps是定義密度時(shí)的鄰域半徑，MinPts為定義核心點(diǎn)時(shí)的閾值，就是形成簇類所需要最小的樣本數(shù)據(jù)點(diǎn)[8]。

對(duì)于DBSCAN聚類算法可分為以下幾步：

第一步，首先確定Eps和MinPts，找到每一個(gè)樣本數(shù)據(jù)點(diǎn)的Eps領(lǐng)域內(nèi)的樣本個(gè)數(shù)，如果個(gè)數(shù)大于等于MinPts，那么該樣本就是核心點(diǎn)；

第二步，找出每一個(gè)核心樣本密度直達(dá)和密度可達(dá)的樣本，且該樣本亦為核心樣本，忽略所有的非核心樣本；

第三步，如果Eps鄰域內(nèi)包含非核心樣本，則該非核心樣本就是邊界樣本，反之為噪聲[5]。

2 實(shí)例分析

2.1 實(shí)驗(yàn)設(shè)置

首先進(jìn)行構(gòu)造缺失比例，數(shù)據(jù)的三種缺失模式直觀分布情況如圖1所示。

圖1將數(shù)據(jù)可視化后可以觀察到數(shù)據(jù)集每行數(shù)據(jù)是否缺失，橫軸表示數(shù)據(jù)矩陣列向量，縱軸表示數(shù)據(jù)矩陣的行向量，缺失值默認(rèn)表示為紅色，紅色部分代表該位置的數(shù)據(jù)是缺失的，淺色板塊代表該數(shù)值比較小，深色板塊代表該數(shù)值比較大。

然后，求參數(shù)Eps和MinPts。以距離矩陣中第一個(gè)樣本數(shù)據(jù)（第一列數(shù)據(jù)）為例，數(shù)據(jù)分布如圖2所示。

圖1 數(shù)據(jù)缺失分布情況

圖2 樣本數(shù)據(jù)散點(diǎn)圖

圖3 排序后數(shù)據(jù)距離升序圖

圖3是距離矩陣排序后的距離走勢(shì)圖。由圖可知在dist=0.60時(shí)出現(xiàn)了拐點(diǎn)，所以取Eps=0.60，最小鄰居數(shù)的取值范圍應(yīng)為2≤MinPts≤。在本文運(yùn)用中，我們選擇樣本量平方根[6]作為確定的值，結(jié)合本文運(yùn)用的數(shù)據(jù)量，選取值為9。由于我們的數(shù)據(jù)量較小且數(shù)據(jù)變化比較小，所以更適合DBSCAN聚類算法，且密度閾值應(yīng)滿足2≤MinPts <9，綜合考慮，設(shè)置密度閾值MinPts=7。

2.2 實(shí)驗(yàn)結(jié)果

均方誤差（MSE）均方根誤差（RMSE）是衡量真實(shí)值與填補(bǔ)值之間的差距的一個(gè)指標(biāo)并以此作為評(píng)價(jià)缺失數(shù)據(jù)填補(bǔ)效果的指標(biāo)，其值越小說明填補(bǔ)數(shù)據(jù)效果越好，其計(jì)算公式為[8]：

表1 數(shù)據(jù)缺失實(shí)驗(yàn)結(jié)果

表1中，最好的填補(bǔ)效果值用黑體進(jìn)行標(biāo)注。從表中可以清晰地觀察到，在多種情況下，基于KNN改進(jìn)的算法的均方根誤差值（或者均方誤差值）都比改進(jìn)前的KNN算法較小，說明經(jīng)過改進(jìn)的KNN算法比傳統(tǒng)KNN的算法要更有效[9]，填補(bǔ)缺失值能力更高[10]。

3 結(jié)論

在傳統(tǒng)的KNN算法在基礎(chǔ)上，提出了優(yōu)化改進(jìn)，引入灰色關(guān)聯(lián)度替換傳統(tǒng)的歐氏距離。實(shí)驗(yàn)結(jié)果證實(shí)，在填補(bǔ)缺失值時(shí)，改進(jìn)算法明顯提高了填補(bǔ)效果。

[1] 曄沙.數(shù)據(jù)缺失及其處理方法綜述[J].電子測(cè)試,2017, 24(18):65-67.

[2] H. Toutenburg. Little, R. J. A. and D. B. Rubin: Statistical analysis with missing data[J]. Statistical Papers, 1991, 32(1): 70-75.

[3] 毛冬焰.在“灰”色的世界里探索──鄧聚龍教授訪談[J].統(tǒng)計(jì)與決策,1995,11(2):6-9.

[4] 張赤.基于聚類分析的缺失數(shù)據(jù)填補(bǔ)算法研究[D].武漢:武漢輕工大學(xué),2013:7-12.

[5] 謝霖銓,趙楠,徐浩,等.基于屬性相關(guān)性的KNN近鄰填補(bǔ)算法改進(jìn)[J].江西理工大學(xué)學(xué)報(bào),2019,40(1):95-101.

[6] 劉莎,楊有龍.基于灰色關(guān)聯(lián)分析的類中心缺失值填補(bǔ)方法[J].四川大學(xué)學(xué)報(bào)(自然科學(xué)版),2020,57(5):871- 878.

[7] 張曉斌.基于出行特征的純電驅(qū)動(dòng)客車儲(chǔ)能系統(tǒng)設(shè)計(jì)與能效優(yōu)化[D].北京:清華大學(xué),2017:9-16.

[8] 解小東,陳治華.基于KNN-DBSCAN的缺失數(shù)據(jù)填補(bǔ)優(yōu)化算法[J].工業(yè)控制計(jì)算機(jī),2020,33(4):58-63.

[9] Yonghua Wang, Jingyi Lu, Kaidi Zhao. A locally weighted KNN algorithm based on eigenvector of SVM[J]. Inter- national Journal of Wireless and Mobile Computing, 2020, 19(3): 256-266.

[10] 王治和,曹旭琰,杜輝.一種優(yōu)化初始點(diǎn)與自適應(yīng)半徑的密度聚類算法[J].計(jì)算機(jī)工程,2022,48(1):51-59.

A Missing Data Filling Improved Algorithm Based on Grey Relational Analysis

CHEN Xiao-jie

(School of Mathematical Sciences, Chongqing Normal University, Chongqing 401131, China)

Aiming at the problem that the traditional KNN algorithm is not accurate enough in expressing variable correlation, an improved algorithm is proposed. The grey correlation degree is used to replace the traditional distance formula in the algorithm to obtain the nearest neighbor value, and the idea of KNN algorithm is combined with the idea of DBSCAN algorithm to exclude outliers (interference from noise points). The experimental results show that the MSE and RMSE of the improved algorithm are smaller than those of the traditional method, which proves the effectiveness of the improved algorithm.

KNN; DBSCAN; missing data; grey relational analysis

TP301.6

A

1009-9115(2022)03-0014-03

10.3969/j.issn.1009-9115.2022.03.005

2021-07-12

2022-04-19

陳小杰（1996-），女，重慶開州人，碩士研究生，研究方向?yàn)閼?yīng)用數(shù)理統(tǒng)計(jì)。

（責(zé)任編輯、校對(duì)：趙光峰）