基于真值發(fā)現(xiàn)的加油站車(chē)輛號(hào)牌缺損數(shù)據(jù)填充方法

彭新亮 程 力 王 軼 馬 博 趙 凡 周 喜*

1(中國(guó)科學(xué)院新疆理化技術(shù)研究所 新疆 烏魯木齊 830011)2(中國(guó)科學(xué)院大學(xué) 北京 100049)3(新疆理化技術(shù)研究所新疆民族語(yǔ)音語(yǔ)言信息處理實(shí)驗(yàn)室 新疆 烏魯木齊 830011)

0 引 言

隨著自動(dòng)化數(shù)據(jù)采集技術(shù)的發(fā)展,加油站車(chē)輛加油數(shù)據(jù)的采集工作正在逐漸由人工采集轉(zhuǎn)向物聯(lián)網(wǎng)設(shè)備自動(dòng)采集。由于數(shù)據(jù)采集設(shè)備的車(chē)牌識(shí)別精度不足、環(huán)境影響、網(wǎng)絡(luò)不穩(wěn)定等因素的影響，同一輛汽車(chē)在不同加油站終端數(shù)據(jù)系統(tǒng)中所采集到的車(chē)牌號(hào)碼也有可能不同。并且，從這些設(shè)備匯總得到的數(shù)據(jù)中車(chē)牌號(hào)碼存在大量丟失和錯(cuò)誤(以下簡(jiǎn)稱(chēng)缺損)情況。某地區(qū)收集的車(chē)輛加油數(shù)據(jù)中，缺損數(shù)據(jù)約占總數(shù)據(jù)的20%以上。由于未采用有效的方法對(duì)此部分?jǐn)?shù)據(jù)進(jìn)行處理，嚴(yán)重影響了后續(xù)對(duì)這些數(shù)據(jù)的分析工作，不利于數(shù)據(jù)融合的開(kāi)展。因此，針對(duì)這種多數(shù)據(jù)源離散型分類(lèi)數(shù)據(jù)的缺損值填充問(wèn)題的研究，對(duì)于提高原始數(shù)據(jù)的可用性和融合數(shù)據(jù)的正確性都至關(guān)重要。

在融合互聯(lián)網(wǎng)多源數(shù)據(jù)時(shí)，由于不同數(shù)據(jù)源自身數(shù)據(jù)不完整的原因，導(dǎo)致相同數(shù)據(jù)在融合時(shí)產(chǎn)生沖突，無(wú)法確定真值的問(wèn)題。Yin等[1]首次將此問(wèn)題定義為真值發(fā)現(xiàn)，并提出了TruthFinder算法解決此問(wèn)題。鑒于多源數(shù)據(jù)的特殊性和數(shù)據(jù)質(zhì)量的重要性，本文提出了一種基于真值發(fā)現(xiàn)的缺損數(shù)據(jù)填充方法。該方法將經(jīng)過(guò)預(yù)處理的數(shù)據(jù)通過(guò)改進(jìn)的Truth Finder迭代計(jì)算真值，再按照一定的策略對(duì)缺損數(shù)據(jù)進(jìn)行填充，有效地解決了多數(shù)據(jù)源離散型分類(lèi)數(shù)據(jù)的缺損值填充的問(wèn)題。

1 相關(guān)工作

對(duì)于缺損數(shù)據(jù)的處理在數(shù)據(jù)的預(yù)處理階段十分常見(jiàn)。就目前而言，在數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)領(lǐng)域?qū)τ谌睋p值的處理方式主要分為兩類(lèi)，直接刪除相應(yīng)缺失數(shù)據(jù)所在數(shù)據(jù)行和算法填充[2]。又根據(jù)填充數(shù)據(jù)的產(chǎn)生規(guī)則，可將數(shù)據(jù)填充分為基于數(shù)據(jù)集自身統(tǒng)計(jì)特征的填充和基于機(jī)器學(xué)習(xí)模型的預(yù)測(cè)值填充兩類(lèi)[2]。

直接刪去缺損值所在的數(shù)據(jù)行的方法，可以非常簡(jiǎn)單地使得原始數(shù)據(jù)成為完整的數(shù)據(jù)集。在缺損數(shù)據(jù)所占比重較小的時(shí)候采用這種方法是很有效的。然而，操作簡(jiǎn)單意味著其局限性也十分突出。因?yàn)橹苯觿h去了原始數(shù)據(jù)的若干記錄會(huì)造成原始數(shù)據(jù)的缺失，一些隱藏在數(shù)據(jù)中的信息同時(shí)也會(huì)被遺棄，這將直接影響下一步的數(shù)據(jù)分析結(jié)果的有效性。甚至在缺損數(shù)據(jù)量較大時(shí)，使用這種方法會(huì)直接導(dǎo)致原始數(shù)據(jù)偏離正常分布，給出錯(cuò)誤的數(shù)據(jù)挖掘結(jié)果。

在統(tǒng)計(jì)學(xué)領(lǐng)域，一些學(xué)者提出了用統(tǒng)一值、平均值等一些基本統(tǒng)計(jì)量來(lái)對(duì)缺損值進(jìn)行直接替換，使得原始數(shù)據(jù)形成完備數(shù)據(jù)集。文獻(xiàn)[3]介紹了使用方差校正的方法，對(duì)缺損數(shù)據(jù)進(jìn)行插補(bǔ)。文獻(xiàn)[4]介紹了使用最大期望算法(Expectation Maximization Algorithm, EM)和貝葉斯網(wǎng)絡(luò)(Bayesian network)的丟失數(shù)據(jù)填充算法。該算法利用Naive Bayesian模型估計(jì)出EM算法的初始值，然后結(jié)合這兩種模型迭代確定更新器，同時(shí)對(duì)缺損值進(jìn)行填充。這些方法的優(yōu)點(diǎn)是簡(jiǎn)單快速，對(duì)于數(shù)據(jù)維度不大的數(shù)據(jù)集而言是一種有效的處理手段。但是在缺損數(shù)據(jù)所占比重較大或者數(shù)據(jù)較為復(fù)雜時(shí)，這種方法很可能會(huì)丟棄原始數(shù)據(jù)中的大量隱藏信息，甚至影響原始數(shù)據(jù)整體的分布情況，直接影響數(shù)據(jù)的可用性。

更為普遍的方法是對(duì)缺損值進(jìn)行預(yù)測(cè)填充，尋找缺損值的最近似值來(lái)進(jìn)行替換。研究者們提出了大量基于統(tǒng)計(jì)分析、機(jī)器學(xué)習(xí)的模型和算法。文獻(xiàn)[5]將數(shù)據(jù)分為決策屬性和條件屬性，利用支持向量機(jī)來(lái)預(yù)測(cè)條件屬性的值，從而填充缺失數(shù)據(jù)。除此之外，也有采用K最近鄰算法[6-8]、信息增益[9]、人工神經(jīng)網(wǎng)絡(luò)[10-12]等算法對(duì)缺損數(shù)據(jù)項(xiàng)進(jìn)行預(yù)測(cè)，找出最有可能的數(shù)值來(lái)進(jìn)行填充。

這些方法在處理缺失數(shù)據(jù)方面各有優(yōu)勢(shì)，某些算法模型在處理連續(xù)型數(shù)值數(shù)據(jù)時(shí)會(huì)取得較好的效果。而某些算法更適用于離散型數(shù)值數(shù)據(jù)。但是對(duì)于加油站車(chē)輛數(shù)據(jù)這種離散型分類(lèi)數(shù)據(jù)而言，目前仍未找到有效的處理方法，一種可行的方法是按照不同加油站根據(jù)車(chē)輛加油的頻率，按照少數(shù)服從多數(shù)的方式，使用投票(Voting)的策略估計(jì)缺失數(shù)據(jù)[13]。本文提出了使用改進(jìn)過(guò)的用于真值發(fā)現(xiàn)的TruthFinder算法將處理過(guò)的原始數(shù)據(jù)輸入到算法模型中，通過(guò)迭代計(jì)算的方式求得數(shù)據(jù)的真實(shí)值，然后按照一定策略對(duì)算法將得到的真值填充回原始數(shù)據(jù)中，以此解決加油站車(chē)輛號(hào)牌缺失數(shù)據(jù)的填充問(wèn)題。通過(guò)在真實(shí)加油站數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果證明，該方法相較于傳統(tǒng)的Voting算法有23%的正確率提升，很大程度上提高了加油站數(shù)據(jù)的可用性。

2 缺損值填充框架

2.1 問(wèn)題的產(chǎn)生背景

數(shù)據(jù)質(zhì)量問(wèn)題作為制約數(shù)據(jù)可用性的關(guān)鍵問(wèn)題，長(zhǎng)久以來(lái)深受研究者的重視。如何對(duì)原始數(shù)據(jù)進(jìn)行清洗，提高其可用性，是大家關(guān)注的重點(diǎn)。文獻(xiàn)[14]針對(duì)數(shù)據(jù)質(zhì)量問(wèn)題提出了一個(gè)可以動(dòng)態(tài)配置規(guī)則的數(shù)據(jù)清洗框架，如圖1所示。

圖1 動(dòng)態(tài)配置規(guī)則的數(shù)據(jù)清洗流程

在對(duì)加油站數(shù)據(jù)進(jìn)行預(yù)處理階段，主要任務(wù)是對(duì)數(shù)據(jù)文件某些字段中的錯(cuò)誤、缺失和不一致問(wèn)題進(jìn)行修正。如圖1所示，該框架使用了三種可動(dòng)態(tài)配置的規(guī)則(DRDDLS、REGEX、FUNCTION)以及規(guī)則間的邏輯運(yùn)算，可以對(duì)臟數(shù)據(jù)進(jìn)行保留、丟棄、回填三種修復(fù)操作。但是在實(shí)際應(yīng)用于真實(shí)數(shù)據(jù)時(shí)發(fā)現(xiàn)，數(shù)據(jù)修復(fù)階段往往由于大量數(shù)據(jù)的丟失，而無(wú)法為其配置合適的規(guī)則，從而導(dǎo)致無(wú)法有效地對(duì)數(shù)據(jù)開(kāi)展清洗工作，使得最終的清洗結(jié)果無(wú)法達(dá)到要求。因此本文針對(duì)此問(wèn)題提出了解決方案。

2.2 問(wèn)題的定義及分析

在加油站車(chē)輛數(shù)據(jù)中，每條數(shù)據(jù)包含車(chē)輛的駕駛員信息、加油站信息、車(chē)輛的車(chē)牌號(hào)碼等內(nèi)容。

由于一些原因，數(shù)據(jù)中存在大量無(wú)法使用傳統(tǒng)圖像再識(shí)別等方式修復(fù)的數(shù)據(jù)，制約了數(shù)據(jù)的可用性。因此，如何使用算法將丟失的號(hào)牌盡可能修復(fù)出來(lái)，從而提高數(shù)據(jù)的可用性將十分有意義。

如圖2所示，車(chē)主在加油站A與加油站B等多個(gè)加油站進(jìn)行過(guò)加油。由于加油站設(shè)備的原因，導(dǎo)致不同的加油站數(shù)據(jù)庫(kù)中存放車(chē)輛號(hào)牌產(chǎn)生區(qū)別，至少有一個(gè)車(chē)牌識(shí)別結(jié)果是錯(cuò)誤的。在各加油站數(shù)據(jù)需要融合處理時(shí)，需要對(duì)其真值做出判斷。此外，若存在此車(chē)主在加油站C的加油記錄且此記錄中車(chē)牌號(hào)碼識(shí)別失敗產(chǎn)生缺失數(shù)據(jù)時(shí)，又涉及到如何填充此缺損值的問(wèn)題。因此，為了保證加油站數(shù)據(jù)的可用性，需要對(duì)這樣的數(shù)據(jù)進(jìn)行填充處理。

圖2 加油站數(shù)據(jù)真值問(wèn)題

在討論缺損值填充問(wèn)題之前，基于常識(shí)和對(duì)數(shù)據(jù)的觀察，提出一些基本的假設(shè)，以便于下述問(wèn)題的處理：

假設(shè)一：各個(gè)數(shù)據(jù)源之間不存在聯(lián)系，所提供的數(shù)據(jù)相互獨(dú)立，這個(gè)條件在加油站數(shù)據(jù)中顯然成立，不同的加油站之間并沒(méi)有任何數(shù)據(jù)間的聯(lián)系。

假設(shè)二：在某個(gè)區(qū)域內(nèi)的一段時(shí)間里，一個(gè)普通用戶(hù)(以用戶(hù)身份證號(hào)碼為區(qū)分)不會(huì)頻繁更換車(chē)輛加油。即一個(gè)用戶(hù)不會(huì)每次都駕駛不同的車(chē)輛進(jìn)行加油，顯然，大多數(shù)人是滿足該假設(shè)的。這樣車(chē)輛就與用戶(hù)關(guān)聯(lián)起來(lái)了。

假設(shè)三：車(chē)輛加油存在一定的連續(xù)性，某輛車(chē)大概率會(huì)在某地區(qū)內(nèi)頻繁加油，而小概率不在本地區(qū)加油。

2.3 符號(hào)及其含義

表1給出了真值發(fā)現(xiàn)問(wèn)題中的一些基本概念及其描述。

表1 規(guī)則、符號(hào)的意義

2.4 TruthFinder算法

在多源數(shù)據(jù)融合領(lǐng)域，不同數(shù)據(jù)源對(duì)數(shù)據(jù)的表示方式、格式等不同，在對(duì)多源數(shù)據(jù)進(jìn)行融合時(shí)會(huì)遇到無(wú)法判斷來(lái)自哪個(gè)數(shù)據(jù)源的值正確或者以哪個(gè)數(shù)據(jù)源的值為準(zhǔn)的問(wèn)題[15]。

為解決此問(wèn)題，TruthFinder算法將各個(gè)數(shù)據(jù)源看作一張圖上的節(jié)點(diǎn)，定義出了數(shù)據(jù)源的可信度和數(shù)據(jù)值的準(zhǔn)確度兩個(gè)變量描述這個(gè)圖，使用迭代計(jì)算的思路分別計(jì)算數(shù)據(jù)值的準(zhǔn)確度和數(shù)據(jù)值的可信度，直至收斂。

算法開(kāi)始時(shí)，統(tǒng)一設(shè)定所有數(shù)據(jù)源的初始可信度為t(s)，假設(shè)一個(gè)實(shí)體真值數(shù)據(jù)只存在一種數(shù)據(jù)值f,則某數(shù)據(jù)源的數(shù)據(jù)值錯(cuò)誤可能性為1-t(s)，故在全部數(shù)據(jù)源的基礎(chǔ)上可計(jì)算得到數(shù)據(jù)值的準(zhǔn)確度為：

(1)

在求得各個(gè)數(shù)據(jù)值的準(zhǔn)確度之后，算法即可根據(jù)簡(jiǎn)單的幾何概率模型求得某一數(shù)據(jù)源的可信度為該數(shù)據(jù)源所表示的所有數(shù)據(jù)準(zhǔn)確度之和與該數(shù)據(jù)源所描述數(shù)據(jù)值的個(gè)數(shù)|F(S)|的比值。即數(shù)據(jù)源S的可信度為：

(2)

以上是簡(jiǎn)單模型中求解數(shù)據(jù)源可信度和數(shù)據(jù)值準(zhǔn)確度的過(guò)程。由于一個(gè)現(xiàn)實(shí)實(shí)體真值在多源情況下不可能只有一個(gè)數(shù)據(jù)值描述值，因此，不同數(shù)據(jù)源中會(huì)有對(duì)同一數(shù)據(jù)的描述，往往這些描述是相互關(guān)聯(lián)的。將數(shù)據(jù)值f1對(duì)數(shù)據(jù)值f2的關(guān)聯(lián)記作imp(f1→f2)。故調(diào)整后的數(shù)據(jù)值準(zhǔn)確度如下，其中ρ是調(diào)節(jié)參數(shù)：

(3)

原算法考慮到不同數(shù)據(jù)源之間的并非完全獨(dú)立，在處理最終結(jié)果時(shí)加入了數(shù)據(jù)源獨(dú)立參數(shù)γ調(diào)節(jié)最終結(jié)果:

s*(f)=1-e-γ·s(f)

(4)

由式(2)和式(4)即可迭代計(jì)算數(shù)據(jù)源的可信度和數(shù)據(jù)值的準(zhǔn)確度，直至計(jì)算結(jié)果不再變化為止，所得到的準(zhǔn)確度最高的數(shù)據(jù)值即為所求的真值。

2.5 基于真值發(fā)現(xiàn)的缺損值填充方法

本文所用方法整體框架如圖3所示。

圖3 基于TFD(Truth Filling Declare)算法的 缺損值填充計(jì)算框架

在傳統(tǒng)的真值發(fā)現(xiàn)算法中，數(shù)據(jù)值之間的支持度imp(f1→f2)定義比較模糊，大部分直接將數(shù)據(jù)看作普通文本，使用兩個(gè)數(shù)據(jù)值的余弦相似度用于計(jì)算。由于處理數(shù)據(jù)的類(lèi)型不同，這樣的做法在加油站車(chē)輛數(shù)據(jù)這種短文本數(shù)據(jù)中顯然是不合理的。例如，用戶(hù)A在f1加油站加油時(shí)識(shí)別的車(chē)輛號(hào)牌為“京A12345”,在加油站f2加油時(shí)識(shí)別的車(chē)輛號(hào)牌為“津A12345”。這其中顯然有一個(gè)加油站的數(shù)據(jù)是錯(cuò)誤的，此時(shí)若按照傳統(tǒng)的相似度作為支持度的計(jì)算，則:

imp(f1→f2)=cosine(f1,f2)=

在上例中，根據(jù)詞頻可以將f1的向量表示為(1,0,1,1,1,1,1,1)，f2的向量可以表示為(0,1,1,1,1,1,1,1)?？梢杂?jì)算得到二者的余弦相似度為0.857，顯然這樣的相似度表明這兩個(gè)數(shù)據(jù)之間存在較高的支撐關(guān)系。反映到實(shí)際的計(jì)算中就會(huì)導(dǎo)致異常高的支持度，這樣在進(jìn)行迭代計(jì)算的過(guò)程中，某些實(shí)際錯(cuò)誤的數(shù)據(jù)會(huì)因?yàn)槠渌麛?shù)據(jù)的較高支持，也計(jì)算得到較高的準(zhǔn)確度，從而影響最終進(jìn)行數(shù)據(jù)填充的結(jié)果。為了解決加油站車(chē)牌數(shù)據(jù)中使用文本相似度所帶來(lái)的問(wèn)題，本文提出采用0-1相似度來(lái)計(jì)算數(shù)據(jù)之間的支持度，其計(jì)算公式如下：

這樣可以使得在短文本真值算法處理時(shí)獲得更加準(zhǔn)確的計(jì)算結(jié)果。

2.6 數(shù)據(jù)填充過(guò)程

如圖3所示，在原始數(shù)據(jù)預(yù)處理階段需要從數(shù)據(jù)庫(kù)中抽取數(shù)據(jù)，由于原始數(shù)據(jù)在維度、格式上與TFD算法要求的輸入存在差異，需要進(jìn)行相應(yīng)的格式轉(zhuǎn)換。格式轉(zhuǎn)換完成后，會(huì)對(duì)原始數(shù)據(jù)進(jìn)行適當(dāng)刪減，去除那些不滿足算法假設(shè)的數(shù)據(jù)。例如在整個(gè)數(shù)據(jù)集中只進(jìn)行過(guò)一次加油或者某輛車(chē)每次加油都是不同的車(chē)主駕駛，這些數(shù)據(jù)將無(wú)法被算法框架所計(jì)算。另外，在實(shí)際情況中，單個(gè)數(shù)據(jù)源內(nèi)部由于一些原因，其多次提供的數(shù)據(jù)值可能也存在偏差。因此需要統(tǒng)一單一數(shù)據(jù)源的描述值。

通過(guò)對(duì)原始數(shù)據(jù)的預(yù)處理，得到相應(yīng)的實(shí)驗(yàn)數(shù)據(jù)集，實(shí)驗(yàn)數(shù)據(jù)集將直接作為T(mén)FD算法的輸入。之后將采用迭代計(jì)算的方式計(jì)算真值，根據(jù)輸出結(jié)果即可知道不同數(shù)據(jù)的真實(shí)情況。計(jì)算過(guò)程的偽代碼如下：

輸入：經(jīng)過(guò)處理的各個(gè)加油站不同用戶(hù)的加油數(shù)據(jù){F(S)}S,∈M。

輸出：各個(gè)用戶(hù)所駕駛車(chē)輛的真實(shí)車(chē)牌號(hào)碼數(shù)據(jù)值{s(f)},f∈N和各個(gè)加油站數(shù)據(jù)可信度{t(S)},S∈M。

(1) Initialization, 初始化各個(gè)數(shù)據(jù)源的可信度{t(S)},S∈M;

(2) Repeat:

(3) Fori< 1 to│M│ do

//循環(huán)計(jì)算每個(gè)數(shù)據(jù)源

(4) 根據(jù)式(3)與式(5)計(jì)算數(shù)據(jù)值的準(zhǔn)確度s(f);

(5) End for

(6) 根據(jù)所求得的準(zhǔn)確度和式(2)更新此輪迭代計(jì)算 的數(shù)據(jù)源可信度t(S)；

(7) Until計(jì)算結(jié)果收斂;

(8) Return準(zhǔn)確度最高的數(shù)據(jù)值s(f),f∈N作為真實(shí)值，數(shù)據(jù)源的可信度{t(S)},S∈M。

經(jīng)過(guò)上述迭代計(jì)算之后，即可求出在此模型下某個(gè)用戶(hù)駕駛車(chē)輛車(chē)牌號(hào)碼的真實(shí)值。算法的最后一步中，真實(shí)值將被用于回填數(shù)據(jù)庫(kù)。此過(guò)程分為兩類(lèi)，對(duì)于缺失的數(shù)據(jù)，將直接填充TFD算法求得的數(shù)據(jù)值；對(duì)于錯(cuò)誤的數(shù)據(jù)，由于實(shí)際數(shù)據(jù)中存在一個(gè)用戶(hù)會(huì)駕駛多輛機(jī)動(dòng)車(chē)加油的情況，因此采用比較算法真實(shí)值與實(shí)際值編輯距離的方式進(jìn)行填充。編輯距離Levenshtein distance[16]是一種常用的比較文本相似度的算法，設(shè)兩個(gè)字符串為a、b。其長(zhǎng)度分別為i、j，則兩者編輯距離計(jì)算方法如下：

(7)

若兩者編輯距離小于某一閾值β，則表明原始數(shù)據(jù)中的錯(cuò)誤值可能是由算法真實(shí)值丟失數(shù)據(jù)產(chǎn)生，應(yīng)該進(jìn)行替換。否則二者應(yīng)該不是同一數(shù)據(jù)，不應(yīng)該進(jìn)行替換。根據(jù)對(duì)加油站數(shù)據(jù)的觀察，發(fā)現(xiàn)數(shù)據(jù)錯(cuò)誤字符個(gè)數(shù)為1～2個(gè)，因此實(shí)驗(yàn)中相似度閾值β取3。

至此，算法完成了對(duì)所有數(shù)據(jù)的缺損值填充過(guò)程，依此方法可以得到可用性提高的新數(shù)據(jù)集。

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

3.1 實(shí)驗(yàn)配置

為了驗(yàn)證上文中提出的缺損值填充算法的有效性，本次實(shí)驗(yàn)使用了真實(shí)環(huán)境中加油站車(chē)輛加油的數(shù)據(jù),抽取某一區(qū)域的部分?jǐn)?shù)據(jù)形成實(shí)驗(yàn)數(shù)據(jù)集。實(shí)驗(yàn)機(jī)器系統(tǒng)為Windows7 64位，CPU型號(hào)為Intel(R) Core(TM) i5-3470 CPU @ 3.20 GHz，內(nèi)存8 GB，全部代碼使用java語(yǔ)言實(shí)現(xiàn)，jdk版本為1.8。數(shù)據(jù)存儲(chǔ)使用Oracle 11g。

3.2 加油數(shù)據(jù)集

數(shù)據(jù)來(lái)源于新疆維吾爾自治區(qū)烏魯木齊市的真實(shí)加油站加油數(shù)據(jù)，該數(shù)據(jù)集從原始數(shù)據(jù)庫(kù)中，抽取市區(qū)了31個(gè)加油站2017年1月至2017年11月的加油數(shù)據(jù)總計(jì)702 508條。為了保證實(shí)驗(yàn)的準(zhǔn)確性，去除了數(shù)據(jù)中部分無(wú)效數(shù)據(jù)，例如整個(gè)時(shí)間段內(nèi)加油次數(shù)為1次、整個(gè)時(shí)間段內(nèi)所有車(chē)牌數(shù)據(jù)均為錯(cuò)誤等無(wú)法被填充框架處理的數(shù)據(jù)。經(jīng)過(guò)數(shù)據(jù)篩選和格式轉(zhuǎn)換等步驟，最終形成了總共659 155條記錄的實(shí)驗(yàn)數(shù)據(jù)集。其中完全缺失車(chē)牌號(hào)字段的數(shù)據(jù)128 354條，數(shù)據(jù)缺失率為24.18%。參與運(yùn)算的完整數(shù)據(jù)(包含錯(cuò)誤數(shù)據(jù)23 851條)530 801條。其中每條記錄主要包括唯一性標(biāo)識(shí)、加油人員身份證號(hào)碼、加油站編號(hào)、車(chē)牌號(hào)等信息。以某一用戶(hù)為例，數(shù)據(jù)集中了不同數(shù)據(jù)源對(duì)其描述數(shù)據(jù)以及真實(shí)情況下加油車(chē)輛的電子照片，如表2所示，其中“#”號(hào)表示數(shù)據(jù)缺失，(敏感部分以*代替)。

表2 加油數(shù)據(jù)集部分?jǐn)?shù)據(jù)

本文中采用真值發(fā)現(xiàn)常用的正確率[1-13]來(lái)衡量最終結(jié)果準(zhǔn)確性。其計(jì)算方式如下：

式中：TP表示算法計(jì)算的結(jié)果中為真的數(shù)據(jù)值個(gè)數(shù)，P表示算法返回的結(jié)果集對(duì)應(yīng)取樣數(shù)據(jù)的數(shù)量。為更加真實(shí)地計(jì)算算法的準(zhǔn)確性，本文采用真值發(fā)現(xiàn)通用的Gold standards[1]準(zhǔn)則進(jìn)行評(píng)價(jià)，測(cè)試數(shù)據(jù)的具體選擇方法為：隨機(jī)挑選實(shí)驗(yàn)數(shù)據(jù)集中的數(shù)據(jù)，采用人工的方式在后臺(tái)數(shù)據(jù)庫(kù)中尋找此數(shù)據(jù)未缺失的真實(shí)值，真值以數(shù)據(jù)庫(kù)中記錄的圖片數(shù)據(jù)為準(zhǔn)。

本次實(shí)驗(yàn)共分為兩個(gè)部分，第一部分比較TruthFinder算法中的兩個(gè)參數(shù)ρ和γ對(duì)于實(shí)驗(yàn)結(jié)果的影響，并選擇合適的參數(shù)進(jìn)行第二部分實(shí)驗(yàn)。第二部分實(shí)驗(yàn)中比較Voting算法、原始TruthFinder算法與改進(jìn)后的TFD算法在實(shí)驗(yàn)性能對(duì)比及分析。

3.3 參數(shù)對(duì)結(jié)果的影響

為了更好地建模數(shù)據(jù)源之間的關(guān)系，原算法加入了兩個(gè)參數(shù)ρ和γ。其中ρ表示最終結(jié)果中本數(shù)據(jù)源和其他相關(guān)數(shù)據(jù)源對(duì)結(jié)果的貢獻(xiàn)比例，一般取0.5；γ是數(shù)據(jù)源的獨(dú)立性參數(shù)，為了防止數(shù)據(jù)源不獨(dú)立時(shí)迭代結(jié)果異常的現(xiàn)象產(chǎn)生。不同參數(shù)對(duì)實(shí)驗(yàn)結(jié)果的影響如圖4所示。

圖4 不同γ取值對(duì)正確率的影響

上述實(shí)驗(yàn)中，固定算法支持度參數(shù)ρ為0.5，即數(shù)據(jù)的準(zhǔn)確度計(jì)算同時(shí)考慮當(dāng)前數(shù)據(jù)源結(jié)果與其他數(shù)據(jù)源對(duì)本數(shù)據(jù)的描述，這是大多數(shù)真值發(fā)現(xiàn)算法所采取的策略。得到參數(shù)γ在不同數(shù)值下算法最終正確率的情況。參數(shù)γ在算法中描述的是不同數(shù)據(jù)源之間的獨(dú)立性，即一個(gè)數(shù)據(jù)源的數(shù)據(jù)是否與其他數(shù)據(jù)源的數(shù)據(jù)有關(guān)。由實(shí)驗(yàn)結(jié)果可知，隨著γ在參數(shù)范圍0～1內(nèi)變化，最終算法正確率雖然有少許波動(dòng)，但整體來(lái)看變化不大。

3.4 實(shí)驗(yàn)性能對(duì)比及分析

本小節(jié)比較了三種算法在實(shí)驗(yàn)數(shù)據(jù)集上的效果。具體包括作為對(duì)比的Voting投票算法[17]，即按照少數(shù)服從多數(shù)的方式選擇真值、基于原始未修改的TruthFinder填充算法和本文提出的改進(jìn)原TruthFinder算法中關(guān)于數(shù)據(jù)值支持度的TFD算法。本實(shí)驗(yàn)中所選取的參數(shù)均以上述實(shí)驗(yàn)中獲得最優(yōu)結(jié)果為準(zhǔn)：ρ=0.5，γ=0.1。實(shí)驗(yàn)結(jié)果如表3所示。

表3 不同算法的正確率對(duì)比

由實(shí)驗(yàn)結(jié)果可以看出：基于TFD的缺損值填充方法取得了最高的結(jié)果正確率。相較于TruthFinder算法和基于投票的Voting算法有了7%和23%的正確率提高。Voting算法作為處理類(lèi)似問(wèn)題的通用計(jì)算方法，采用少數(shù)服從多數(shù)的經(jīng)典處理策略，并未考慮到不同數(shù)據(jù)源本身的特點(diǎn)，計(jì)算模型過(guò)于簡(jiǎn)單，僅考慮某一數(shù)據(jù)值的出現(xiàn)次數(shù)。雖然在處理離散型多源數(shù)據(jù)填充問(wèn)題上有一定的使用價(jià)值，但是正確率不高。

基于TFD的填充算法在TruthFinder的基礎(chǔ)上改進(jìn)了其支持度的計(jì)算規(guī)則，最終在正確率上有一定的提高，說(shuō)明在加油站數(shù)據(jù)中，相較于余弦相似度這種在文本相關(guān)性方面較為優(yōu)勢(shì)的算法，離散的0-1相似度更具有效性。TFD算法將車(chē)牌之間的支持度離散化處理，因此在實(shí)際實(shí)驗(yàn)中獲得了比TruthFinder算法更好的效果。

如圖5所示，算法在最開(kāi)始的三輪迭代中正確率有明顯變化，且變化率不斷降低，之后正確率穩(wěn)定，表明迭代已收斂。而且，即使是在首輪迭代中，算法的正確率依然有0.866，可見(jiàn)，在一輪迭代后其結(jié)果已有一定的可用性?；赥FD的缺損值填充算法在處理數(shù)據(jù)量較大的數(shù)據(jù)集時(shí)，也可以在較短的時(shí)間內(nèi)得到令人滿意的結(jié)果。

圖5 算法正確率隨迭代次數(shù)的變化

4 結(jié) 語(yǔ)

針對(duì)于多源離散型分類(lèi)數(shù)據(jù)缺損值填充問(wèn)題，本文提出了一種基于改進(jìn)的TFD算法進(jìn)行填充的思路。該方法使用真值發(fā)現(xiàn)，迭代計(jì)算各個(gè)數(shù)據(jù)源的可信度和數(shù)據(jù)值的準(zhǔn)確度，使用改進(jìn)的二值相似度解決了數(shù)據(jù)之間支持度的計(jì)算問(wèn)題，以最終迭代收斂時(shí)的計(jì)算結(jié)果作為缺損值填充的備選值。最后通過(guò)在實(shí)際數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證了這種方法的有效性。本文為解決此類(lèi)問(wèn)題提供了一種全新的解決思路。但是真值發(fā)現(xiàn)算法發(fā)展至今已有大量的研究進(jìn)展[18-20]，本文所使用的算法只是其中較為簡(jiǎn)單易于理解的一種。由于采用迭代計(jì)算的方式，其時(shí)間效率不高。其次，由于算法的局限性[21]，僅能處理單真值的問(wèn)題。在后期對(duì)填充結(jié)果分析的過(guò)程中，發(fā)現(xiàn)小部分?jǐn)?shù)據(jù)存在多真值的現(xiàn)象，導(dǎo)致算法填充結(jié)果不準(zhǔn)確。因此，后續(xù)工作中將對(duì)真值發(fā)現(xiàn)問(wèn)題進(jìn)行更深入的研究，考慮采用不同的運(yùn)算模型，提高在實(shí)際數(shù)據(jù)上的準(zhǔn)確度和時(shí)間效率。