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

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

0 引 言

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

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

1 相關(guān)工作

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

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

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

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

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

2 缺損值填充框架

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

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

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

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

2.2 問題的定義及分析

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

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

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

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

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

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

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

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

2.3 符號及其含義

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

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

2.4 TruthFinder算法

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

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

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

(1)

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

(2)

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

(3)

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

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

(4)

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

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

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

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

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

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)?？梢杂嬎愕玫蕉叩挠嘞蚁嗨贫葹?.857，顯然這樣的相似度表明這兩個數(shù)據(jù)之間存在較高的支撐關(guān)系。反映到實際的計算中就會導(dǎo)致異常高的支持度，這樣在進行迭代計算的過程中，某些實際錯誤的數(shù)據(jù)會因為其他數(shù)據(jù)的較高支持，也計算得到較高的準確度，從而影響最終進行數(shù)據(jù)填充的結(jié)果。為了解決加油站車牌數(shù)據(jù)中使用文本相似度所帶來的問題，本文提出采用0-1相似度來計算數(shù)據(jù)之間的支持度，其計算公式如下：

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

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

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

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

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

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

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

(2) Repeat:

(3) Fori< 1 to│M│ do

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

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

(5) End for

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

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

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

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

(7)

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

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

3 實驗與結(jié)果

3.1 實驗配置

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

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

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

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

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

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

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

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

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

圖4 不同γ取值對正確率的影響

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

3.4 實驗性能對比及分析

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

表3 不同算法的正確率對比

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

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

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

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

4 結(jié) 語

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