混合相似性度量的儀表詢價電子表格結(jié)構(gòu)識別

徐傳運,馬瑩麗,李 剛,舒 濤,李星光

(1.重慶理工大學(xué) 兩江人工智能學(xué)院, 重慶 401135;2.重慶師范大學(xué) 計算機與信息科學(xué)學(xué)院, 重慶 401331)

0 引言

在儀表詢價過程中,企業(yè)對無人化處理儀表詢價電子表格的需求快速上升。自動化處理用戶需求,實現(xiàn)無人化詢價,對提高員工工作效率,降低企業(yè)人力物力成本有十分重要的意義。

目前,電子文件詢價已成為國內(nèi)各儀表企業(yè)的主要詢價信息來源,其中各類報表文檔占多數(shù)。在詢價過程中,各個用戶提供的產(chǎn)品物料清單(BOM)不一致,產(chǎn)品參數(shù)描述相對模糊,表格結(jié)構(gòu)復(fù)雜多樣,導(dǎo)致儀表企業(yè)大多收到樣式不固定,數(shù)據(jù)排列混雜且具有嵌套表頭的半結(jié)構(gòu)化詢價電子表格。無人化詢價系統(tǒng)難以理解提供的儀表詢價電子表格,因此各儀表企業(yè)仍普遍采用人工處理詢價表格的生產(chǎn)經(jīng)營模式,但人工方式工作量大,成本高、效率低,且無法及時響應(yīng)。因此,本文對儀表詢價電子表格的結(jié)構(gòu)識別進(jìn)行了研究,達(dá)到自動化識別詢價電子表格的結(jié)構(gòu)和理解隱含的邏輯關(guān)系的效果,為構(gòu)建無人化詢價系統(tǒng)奠定基礎(chǔ)。

電子表格結(jié)構(gòu)識別的目標(biāo)是分析表格的行、列和單元格信息,提取表格中數(shù)據(jù)的結(jié)構(gòu)信息,得到行列分布規(guī)律與邏輯結(jié)構(gòu)。然而,當(dāng)進(jìn)行電子表格自動處理時,電子表格布局的復(fù)雜性和多樣性給表格結(jié)構(gòu)識別和計算機的自動處理帶來了挑戰(zhàn)[1]。

儀表詢價電子表格的結(jié)構(gòu)識別存在以下挑戰(zhàn):表格具有便于體現(xiàn)數(shù)據(jù)關(guān)系和靈活性強的特點[2],導(dǎo)致其往往會出現(xiàn)數(shù)據(jù)種類繁多、格式雜亂、不好整理的問題;詢價表格與實際應(yīng)用聯(lián)系緊密,具有結(jié)構(gòu)性低、數(shù)據(jù)冗雜,潛藏大量有價值數(shù)據(jù)[3]的特點;表格數(shù)據(jù)通常具有一定的專業(yè)性,表達(dá)的語義也不唯一,數(shù)據(jù)標(biāo)注難度大且成本高。但在已有研究中,并未以大量儀表詢價電子報表為對象,國內(nèi)外對電子表格的識別主要集中在表頭和屬性上,并且大多利用傳統(tǒng)方法,如基于規(guī)則、分類以及模式匹配[4]的方法研究表結(jié)構(gòu)。

針對以上問題,本文對儀表詢價電子報表數(shù)據(jù)特點進(jìn)行分析,通過相似性度量的方式對儀表詢價中大量使用的縱向電子表格結(jié)構(gòu)識別進(jìn)行研究,主要貢獻(xiàn)為:

1) 提出混合相似性度量電子表格結(jié)構(gòu)識別方法(hybrid similarity metrics for table structure recognition,HSMTSR):通過混合多種相似性度量的方法對表格的結(jié)構(gòu)進(jìn)行解析識別,將表格解析識別為表頭、表體(索引、屬性和數(shù)據(jù))和表尾等部分,可以高效識別各種儀表電子表格結(jié)構(gòu)。

2) 提出基于向量空間的單元格類型相似度(cell type similarity,TySim):有效提取電子表格單元格的類型特征,其結(jié)合特征向量化儀表詢價電子表格,并用余弦相似度處理向量化的電子表格。

3) 收集真實流量儀表詢價參數(shù)電子表格,構(gòu)建流量儀表電子表格數(shù)據(jù)集(flowmeter spreadsheet dataSet,FSDS),便于研究儀表電子表格結(jié)構(gòu)。

4) 有效識別儀表詢價電子表格結(jié)構(gòu),為實現(xiàn)無人化儀表詢價系統(tǒng)提供便利,節(jié)省人力物力資源,提升工作效率。

1 相關(guān)工作

1.1 表格結(jié)構(gòu)識別

表格結(jié)構(gòu)識別是表格理解分析中重要的子任務(wù)之一,其目標(biāo)是識別表格的布局結(jié)構(gòu)和層次結(jié)構(gòu)。

據(jù)調(diào)研,近5年來針對表格識別的數(shù)據(jù)集多為PDF文件或者表格圖片,缺少直接針對電子表格的數(shù)據(jù)集。PDF表格數(shù)據(jù)集有ICDAR2013[5]和PubTables-1M[6]等。表格圖片數(shù)據(jù)集有ICDAR2019[7]、FUNSD[8]、PubTabNet[9]、WTW[10]和DECO[11]等。而電子表格數(shù)據(jù)集大多來自Web上的HTML表格或開放數(shù)據(jù)平臺的表格,它們在組成、大小和注釋方法上有很大差異,而且多數(shù)未公開數(shù)據(jù)集的標(biāo)注。同時,由于企業(yè)不愿分享公司內(nèi)部文件,且工商業(yè)電子表格的復(fù)雜性更高,因此研究者們對企業(yè)電子表格的研究要少得多。鑒于此,本文收集了某公司儀表詢價電子表格,通過分析、篩選和脫敏等預(yù)處理建立了真實數(shù)據(jù)集FSDS,該數(shù)據(jù)集體現(xiàn)了儀表詢價電子表格的不規(guī)范性和復(fù)雜性的特點,便于本文研究電子表格結(jié)構(gòu)。

國內(nèi)外相關(guān)研究也大多針對PDF表格或者表格圖片,研究者們早期通常使用基于規(guī)則和啟發(fā)的傳統(tǒng)方法來分析和識別表格結(jié)構(gòu),例如將表格結(jié)構(gòu)定義為一棵樹,根據(jù)幾何分布優(yōu)化參數(shù)來理解表格結(jié)構(gòu)[12]或從PDF文檔中反解表格視覺信息[13]。隨著深度學(xué)習(xí)和自然語言處理的發(fā)展,研究者們也開始利用各種語言模型處理表格圖片,如LSTM[14]、Transformer[15]、BERT[16]及LayoutLM[17]模型均取得了良好的效果,其中BERT及其變體RoBERTa[18]、LayoutLM及其變體LayoutLMv2[19]和PICK[20]在表格圖片結(jié)構(gòu)識別任務(wù)中表現(xiàn)出較為穩(wěn)定且高效的性能。而電子表格沒有語法和數(shù)據(jù)模型,也沒有統(tǒng)一的收集標(biāo)準(zhǔn)和收集格式[21],因此針對電子表格,大部分應(yīng)用程序主要通過HTML和XML從Web上的半結(jié)構(gòu)化數(shù)據(jù)中提取關(guān)系數(shù)據(jù)來進(jìn)行結(jié)構(gòu)識別,或使用VBA編程[22]實現(xiàn)啟發(fā)式或基于規(guī)則的電子表格結(jié)構(gòu)識別。但基于規(guī)則的方法成本高,且現(xiàn)有研究大多用于結(jié)構(gòu)復(fù)雜性不高的表格,因此本文采取新的研究思路,結(jié)合表格中的文本相似度進(jìn)行表格結(jié)構(gòu)識別研究。

1.2 文本相似性度量

儀表詢價電子表格中的數(shù)據(jù)具有專業(yè)性強、語義不唯一性和數(shù)據(jù)標(biāo)注難度大且成本高等特點,不利于計算機理解。而文本相似度是廣泛應(yīng)用的文本分析算法模塊,有助于計算機理解語言。受此啟發(fā),本文利用相似性度量的方法對表格結(jié)構(gòu)進(jìn)行解析識別,有助于計算機自動識別電子表格結(jié)構(gòu)。

相似度用來判斷事物之間的相似性,通常利用事物之間的距離來進(jìn)行衡量,一般距離值越小,相似度越大[23]。目前,基于距離的相似度度量方法可分為3類:基于序列的方法、基于集合的方法和基于向量空間的方法。

基于序列的方法指將字符串看成序列,利用序列的相似性來計算兩者之間的性質(zhì),主要包括Levenshtein距離[24]、Affine Gap距離[25]以及Jaro距離[26]等方法。

基于集合的方法指將字符串看成集合,利用集合的相似性或者距離來計算兩者之間的性質(zhì),主要包括Dice度量、Jaccard度量和TF/IDF度量[27-28]等方法。

基于向量空間的方法指將字符串向量化,利用向量之間的距離來計算兩者之間的性質(zhì),主要包括歐氏距離[29]和余弦相似度[30]等方法。

本文對具有多源、異構(gòu)和結(jié)構(gòu)多樣等特點的儀表詢價電子表格進(jìn)行了結(jié)構(gòu)識別研究,尤其是具有層次結(jié)構(gòu)的表格,提出了融合表格單元格特征的類型相似度TySim和表格結(jié)構(gòu)識別方法HSMTSR。同時,在構(gòu)建的FSDS數(shù)據(jù)集上達(dá)到高效自動識別儀表詢價電子表格結(jié)構(gòu)的效果。

2 電子表格結(jié)構(gòu)形式化定義

縱向電子表格RS通常由若干個行數(shù)據(jù)組成,可表示為

RS=[r1,r2,…,rn]T

(1)

式中:ri(i=1,2,3,…,n)表示表格中的一行數(shù)據(jù);n表示行數(shù);S表示sheet名。

本文把表格分為結(jié)構(gòu)化表格和非結(jié)構(gòu)化表格兩大類,將結(jié)構(gòu)化表格定義為表體區(qū)域不存在嵌套單元格的表格,反之為非結(jié)構(gòu)化表格。同時,將表格的行數(shù)據(jù)分為表格的表頭、屬性、數(shù)據(jù)和表尾4類,其中屬性(包括索引)和數(shù)據(jù)兩類數(shù)據(jù)共同構(gòu)成表格的表體,具體定義如表1所示。

表1 電子表格行數(shù)據(jù)類別定義

表格結(jié)構(gòu)識別可轉(zhuǎn)化為一個判斷每行數(shù)據(jù)類別的問題,即一個多分類問題。設(shè)電子表格RS的類別標(biāo)簽序列為AL,結(jié)構(gòu)識別方法為TSRM,則標(biāo)簽序列和模型可表示為

AL=[a1,a2,…,an]T

(2)

AL=TSRM(RS)

(3)

式中:ai(i=1,2,3,…,n)指表格中的某行數(shù)據(jù)ri的標(biāo)簽,ai∈{0,1,2,3},0為表頭標(biāo)簽,1為屬性標(biāo)簽,2為數(shù)據(jù)標(biāo)簽,3為表尾標(biāo)簽。

3 方法

結(jié)合第2節(jié)電子表格結(jié)構(gòu)形式化定義,提出結(jié)合Levenshtein距離、Dice系數(shù)和TySim相似度的混合相似性度量電子表格結(jié)構(gòu)識別方法HSMTSR。

3.1 HSMTSR表格結(jié)構(gòu)識別

如圖1所示,HSMTSR表格結(jié)構(gòu)識別方法將整個表格解析識別為表頭、屬性、數(shù)據(jù)、索引和表尾,其運行體系結(jié)構(gòu)如圖2所示,將整個電子表格作為輸入,經(jīng)過兩階段解析識別表格結(jié)構(gòu)。其中,第一階段為整體解析,將表格解析識別為表頭、表體和表尾;第二階段為局部解析,將表體解析識別為索引、屬性和數(shù)據(jù)。

圖2 HSMTSR方法運行體系結(jié)構(gòu)

整體解析:利用基于儀表參數(shù)詞庫的關(guān)鍵詞相似度匹配方法解析識別表頭和表體。在儀表領(lǐng)域?qū)＜抑笇?dǎo)下,通過分析數(shù)據(jù)集,積累專業(yè)知識,建立儀表屬性詞庫,其中包括儀表詢價所需的相關(guān)參數(shù)和別名信息。根據(jù)建立的詞庫進(jìn)行相似度匹配,把出現(xiàn)屬性的表格單元格標(biāo)記為1,沒有出現(xiàn)屬性的標(biāo)記為0,將整個表格轉(zhuǎn)化為一個n×m的矩陣,可表示為

(4)

式中:rij∈{0,1};n為表格行數(shù);m為列數(shù)。

取矩陣Matn×m行元素之和的最大值所在位置作為表體開始位置,若最大值有多個,則取位置較大的行號值,即可解析識別出表頭和屬性所在位置。

利用混合相似度方法HSMTSR解析表體和表尾。根據(jù)式(5)計算出行數(shù)據(jù)的混合相似度 MixSim,并根據(jù)閾值λ判斷是否相似。若MixSim≥λ,則判斷2行數(shù)據(jù)相似,同為表體數(shù)據(jù);若MixSim<λ,則判斷2行數(shù)據(jù)不相似,所在位置中行號值大的行數(shù)據(jù)為表尾數(shù)據(jù),行號值小的數(shù)據(jù)為表體數(shù)據(jù)。由于表格的多樣化,判斷相似時設(shè)置固定閾值并不合適,于是將閾值λ動態(tài)的設(shè)置為每個表格行相似度的均值。

局部解析:又可稱為表體解析,將表體具體解析識別為索引、屬性和數(shù)據(jù)3類。把表體左上角的第一個單元格作為索引,通常指序號、位號或編號等信息。索引跨越的行數(shù)為索引區(qū)深度Dindex,并稱索引對應(yīng)的列數(shù)據(jù)為索引數(shù)據(jù)。根據(jù)Dindex可判斷屬性區(qū)跨越的行數(shù),將表體前Dindex行作為屬性區(qū)(除索引外),其余為數(shù)據(jù)區(qū)。值得注意的是,由于表格的不規(guī)范性,索引區(qū)深度Dindex可能與屬性區(qū)深度Datt不一致,這時需尋求索引區(qū)所在行的單元格深度最大值作為索引區(qū)深度,并更新索引和屬性區(qū)域。

3.2 混合相似性度量

3.2.1 混合相似度MixSim

結(jié)合Levenshtein距離、Dice系數(shù)和余弦相似度的優(yōu)缺點,本文中提出基于余弦相似度的類型相似度TySim來提取表格單元格類型特征,并采用線性加權(quán)的方式融合3種相似性度量方法生成混合相似度MixSim,可表示為

MixSim=αLevSim+βDiceSim+γTySim

(5)

式中:α+β+γ=1,α、β、γ是實驗值,經(jīng)實驗本文中α取0.35,β取0.35,γ取0.3。

3.2.2 基于向量空間的類型相似度TySim

結(jié)合電子表格單元格的類型特征向量化儀表詢價電子表格,用余弦相似度處理向量化的電子表格,從而得到行數(shù)據(jù)的TySim,并以此為基礎(chǔ)判斷行數(shù)據(jù)是否相似。

電子表格單元格的類型特征TyVector由單元格類型ctype、單元格數(shù)據(jù)類型dtype以及單元格數(shù)據(jù)長度slen組成,可表示為

TyVector=[ctype,dtype,slen]

(6)

式中:ctype∈{0,1,2,3,4,5},0表示空(empty),1表示字符串(string),2表示數(shù)字(number),3表示日期(date),4表示布爾型(boolean),5表示錯誤(error)。dtype∈{0,1,2},0表示單元格數(shù)據(jù)中全為字符,1表示全為數(shù)字,2表示既有數(shù)字又有字符。

向量A、B的余弦相似度可表示為

(7)

歸一化的余弦相似度可表示為

(8)

則單元格a,b的TySimcell可表示為

TySimcell(a,b)=NorCosine(TyVectora,TyVectorb)

(9)

行數(shù)據(jù)x,y的TySim可表示為

(10)

式中:m為表格列數(shù);xc為行數(shù)據(jù)x中第c個單元格;yc為行數(shù)據(jù)y中第c個單元格。

3.2.3 基于序列的Levenshtein相似度

Levenshtein距離是編輯距離的一種,指在2個字符串之間,由一個轉(zhuǎn)為另外一個所需的最少編輯次數(shù)。其中,編輯操作包括更換、刪除和插入,其相似度函數(shù)和距離函數(shù)可以通過一個遞減函數(shù)互相轉(zhuǎn)換。

對于字符串X、Y,用動態(tài)規(guī)劃的思想來計算Levenshtein距離,則X的前i個字符和Y的前j個字符的Levenshtein距離表示為

(11)

式中: |X|、|Y|分別表示字符串X、Y的長度;1X[i-1]≠Y[j-1]是一個指示函數(shù),僅當(dāng)X[i-1]=Y[j-1]時,值為0,其余時候為1。

字符串X、Y的Levenshtein相似度可表示為

(12)

式中:Lev(X,Y)表示字符串X、Y的Levenshtein距離。

3.2.4 基于集合的Dice相似度

Dice系數(shù)(dice coefficient)是衡量2個集合的相似度的一種指標(biāo)。當(dāng)把字符串理解為一種集合時,Dice系數(shù)也可用于度量字符串的相似性。

字符串集合A、B的Dice相似度可表示為

(13)

4 數(shù)據(jù)集構(gòu)建

4.1 數(shù)據(jù)集概況

本文以某儀表公司的電磁流量計詢價電子表格作為實驗數(shù)據(jù)集,表格中包括儀表概況、工藝條件、轉(zhuǎn)換器和變送器等相關(guān)參數(shù)信息。

電子表格通常按照內(nèi)容布局分為縱向表格、橫向表格和混合表格三大類。鑒于人們的使用習(xí)慣和數(shù)據(jù)集情況,本文主要針對縱向電子表格(表格中屬性和數(shù)據(jù)均為上下關(guān)系)進(jìn)行結(jié)構(gòu)識別。因此,本文的相關(guān)表格描述統(tǒng)一指縱向儀表詢價電子表格,典型表格樣例如表2所示。

表2 縱向表格樣例

本文對收集的電子表格進(jìn)行清洗、篩選和規(guī)范化,構(gòu)建了流量儀表電子表格數(shù)據(jù)集FSDS,其概況見表3。整個數(shù)據(jù)集包含714個Excel電子表格文檔(xls格式262個,xlsx格式452個),750個sheet(一個Excel電子文檔可能包含多個sheet,xls格式273個,xlsx格式477個)和8 574行數(shù)據(jù)。其中,結(jié)構(gòu)化表格54個、非結(jié)構(gòu)化表格660個;結(jié)構(gòu)化sheet數(shù)55個、非結(jié)構(gòu)化sheet數(shù)695個。

表3 數(shù)據(jù)集概況

4.2 數(shù)據(jù)預(yù)處理

數(shù)據(jù)預(yù)處理主要包括數(shù)據(jù)清洗和數(shù)據(jù)脫敏兩類。本文中數(shù)據(jù)清洗包括去除冗余信息和規(guī)范存儲數(shù)據(jù);數(shù)據(jù)脫敏主要采用數(shù)據(jù)替換的方式,隱藏了公司和個人相關(guān)的敏感信息。

4.3 數(shù)據(jù)標(biāo)注

針對提出的HSMTSR方法和表格結(jié)構(gòu)識別任務(wù)對數(shù)據(jù)集進(jìn)行標(biāo)注。標(biāo)注內(nèi)容包括表格結(jié)構(gòu)區(qū)域(表頭、表尾、數(shù)據(jù)、屬性)、表格類型(結(jié)構(gòu)化、非結(jié)構(gòu)化)、表格名稱、sheet名稱、表格編號等信息。其中,標(biāo)注區(qū)域格式采用電子表格中單元格坐標(biāo)的表示方式,如表體區(qū)域為A1:F9,采用json格式存儲標(biāo)注,并組合表名和sheet名稱命名標(biāo)注文件。

5 相關(guān)實驗

5.1 實驗設(shè)置

實驗硬件環(huán)境為Intel(R) Core(TM) i5-9500 CPU,NVidia GeForce RTX 2080 Super GPU。軟件平臺為Python3.7,利用xlrd、xlwt模塊對電子表格進(jìn)行讀寫,設(shè)置相似度閾值λ,取值為表格行相似度均值?；旌舷嗨贫萂ixSim中α為0.35,β為0.35,γ為0.3。

5.2 評價指標(biāo)

分別利用準(zhǔn)確率(accuracy)、查準(zhǔn)率(precision)、召回率(recall)和F1值(F1-Score)評估算法的優(yōu)劣程度。

加權(quán)宏平均(Weighted-average):給不同類別分配不同權(quán)重(權(quán)重根據(jù)該類別的真實分布比例確定),每個類別加權(quán)后再相加。

(16)

整表識別準(zhǔn)確率:整表中全部解析識別正確的表格數(shù)目Nright和總表格數(shù)目Ntotal的比例。

(17)

5.3 對比實驗及分析

LevSim字符串匹配準(zhǔn)確度高,DiceSim可解決字符串連續(xù)問題,TySim可提取表格單元格的特征,所以考慮利用級聯(lián)的思想,充分發(fā)揮各種相似度算法的優(yōu)點,從單個相似度度量到結(jié)合2種相似性度量,再到結(jié)合3種相似性度量,以及設(shè)置不同權(quán)重在數(shù)據(jù)集FSDS上進(jìn)行相關(guān)實驗,實驗結(jié)果如表4所示。

表4 實驗結(jié)果

表4中列舉了在單相似性度量、雙相似性度量、混合相似性度量、加權(quán)雙相似性度量和加權(quán)混合相似性度量等多種條件下的實驗結(jié)果對比。從表4可知,LevSim和DiceSim可有效對表格中文本字符串進(jìn)行精確匹配,結(jié)合TySim提取了表格中的特征,對類別2和類別3的精確分類有正向作用?；旌舷嗨菩远攘繉嶒炛?整表識別準(zhǔn)確率SAcc、查準(zhǔn)率WP及類別3分類效果Class3Acc均有所改善,證明混合相似度方法的有效性。

上述3種單相似性度量方法各具優(yōu)勢,但在融合各種方法時,需要優(yōu)化各種方法的權(quán)重占比。由表4可知,未加權(quán)的混合相似度的算法識別準(zhǔn)確率SAcc雖有所改善,但效果不明顯,可考慮利用線性加權(quán)的方式對各種相似性方法進(jìn)行平衡。實驗結(jié)果表明,混合相似度中平均分配權(quán)重不合理,需要重新分配不同的權(quán)重。而單個相似度實驗表明,LevSim和DiceSim方法實驗效果基本持平,而TySim提取了表格單元格的類型特征,并基于余弦相似度來計算,是從向量方向上進(jìn)行區(qū)分,與前2種相似性度量區(qū)別較大,因此我們選擇給LevSim和DiceSim分配同樣的權(quán)重,給TySim分配不同權(quán)重。加權(quán)實驗結(jié)果表明,當(dāng)分配不同權(quán)重給TySim時,準(zhǔn)確率開始發(fā)生較大變化,當(dāng)TySim的權(quán)重稍小時,效果更加明顯,且當(dāng)α=0.35,β=0.35,γ=0.3時效果最好。

圖3和圖4為單相似性度量、加權(quán)混合雙相似性度量和加權(quán)混合相似性度量的各個指標(biāo)對比實驗柱狀圖。

圖4 表格準(zhǔn)確率

〗

由圖3、圖4可知,與未加權(quán)的相似度實驗對比,加權(quán)的混合相似度在SAcc、WP、WR和WF1上表現(xiàn)較好,且在混合雙相似性度量的實驗中加對應(yīng)權(quán)重,實驗效果也有相應(yīng)的提升,證明了加權(quán)平衡的有效性,有效提高了表格識別的準(zhǔn)確率。

6 結(jié)論

對自動化儀表詢價電子表格的結(jié)構(gòu)識別進(jìn)行了研究,提出的HSMTSR方法可有效解析識別儀表詢價電子表格結(jié)構(gòu),構(gòu)建的真實流量儀表詢價電子表格數(shù)據(jù)集FSDS為研究分析表格結(jié)構(gòu)提供了便利。實驗結(jié)果表明,HSMTSR方法可使表格行分類準(zhǔn)確率達(dá)到97.157%,整表結(jié)構(gòu)識別精度達(dá)到92.533%,證明該方法的可行性和有效性。自動化儀表詢價電子表格結(jié)構(gòu)識別的實現(xiàn)和準(zhǔn)確率的提升為構(gòu)建無人化詢價系統(tǒng)奠定了基礎(chǔ),未來將結(jié)合語義進(jìn)行表格內(nèi)容識別和參數(shù)提取,完成無人化詢價系統(tǒng)的構(gòu)建。