混合相似性度量的儀表詢價電子表格結構識別

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

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

0 引言

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

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

電子表格結構識別的目標是分析表格的行、列和單元格信息,提取表格中數據的結構信息,得到行列分布規律與邏輯結構。然而,當進行電子表格自動處理時,電子表格布局的復雜性和多樣性給表格結構識別和計算機的自動處理帶來了挑戰[1]。

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

針對以上問題,本文對儀表詢價電子報表數據特點進行分析,通過相似性度量的方式對儀表詢價中大量使用的縱向電子表格結構識別進行研究,主要貢獻為:

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

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

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

4) 有效識別儀表詢價電子表格結構,為實現無人化儀表詢價系統提供便利,節省人力物力資源,提升工作效率。

1 相關工作

1.1 表格結構識別

表格結構識別是表格理解分析中重要的子任務之一,其目標是識別表格的布局結構和層次結構。

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

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

1.2 文本相似性度量

儀表詢價電子表格中的數據具有專業性強、語義不唯一性和數據標注難度大且成本高等特點,不利于計算機理解。而文本相似度是廣泛應用的文本分析算法模塊,有助于計算機理解語言。受此啟發,本文利用相似性度量的方法對表格結構進行解析識別,有助于計算機自動識別電子表格結構。

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

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

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

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

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

2 電子表格結構形式化定義

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

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

(1)

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

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

表1 電子表格行數據類別定義

表格結構識別可轉化為一個判斷每行數據類別的問題,即一個多分類問題。設電子表格RS的類別標簽序列為AL,結構識別方法為TSRM,則標簽序列和模型可表示為

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

(2)

AL=TSRM(RS)

(3)

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

3 方法

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

3.1 HSMTSR表格結構識別

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

圖2 HSMTSR方法運行體系結構

整體解析:利用基于儀表參數詞庫的關鍵詞相似度匹配方法解析識別表頭和表體。在儀表領域專家指導下,通過分析數據集,積累專業知識,建立儀表屬性詞庫,其中包括儀表詢價所需的相關參數和別名信息。根據建立的詞庫進行相似度匹配,把出現屬性的表格單元格標記為1,沒有出現屬性的標記為0,將整個表格轉化為一個n×m的矩陣,可表示為

(4)

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

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

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

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

3.2 混合相似性度量

3.2.1 混合相似度MixSim

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

MixSim=αLevSim+βDiceSim+γTySim

(5)

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

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

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

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

TyVector=[ctype,dtype,slen]

(6)

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

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

(7)

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

(8)

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

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

(9)

行數據x,y的TySim可表示為

(10)

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

3.2.3 基于序列的Levenshtein相似度

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

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

(11)

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

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

(12)

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

3.2.4 基于集合的Dice相似度

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

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

(13)

4 數據集構建

4.1 數據集概況

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

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

表2 縱向表格樣例

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

表3 數據集概況

4.2 數據預處理

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

4.3 數據標注

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

5 相關實驗

5.1 實驗設置

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

5.2 評價指標

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

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

(16)

整表識別準確率:整表中全部解析識別正確的表格數目Nright和總表格數目Ntotal的比例。

(17)

5.3 對比實驗及分析

LevSim字符串匹配準確度高,DiceSim可解決字符串連續問題,TySim可提取表格單元格的特征,所以考慮利用級聯的思想,充分發揮各種相似度算法的優點,從單個相似度度量到結合2種相似性度量,再到結合3種相似性度量,以及設置不同權重在數據集FSDS上進行相關實驗,實驗結果如表4所示。

表4 實驗結果

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

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

圖3和圖4為單相似性度量、加權混合雙相似性度量和加權混合相似性度量的各個指標對比實驗柱狀圖。

圖4 表格準確率

〗

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

6 結論

對自動化儀表詢價電子表格的結構識別進行了研究,提出的HSMTSR方法可有效解析識別儀表詢價電子表格結構,構建的真實流量儀表詢價電子表格數據集FSDS為研究分析表格結構提供了便利。實驗結果表明,HSMTSR方法可使表格行分類準確率達到97.157%,整表結構識別精度達到92.533%,證明該方法的可行性和有效性。自動化儀表詢價電子表格結構識別的實現和準確率的提升為構建無人化詢價系統奠定了基礎,未來將結合語義進行表格內容識別和參數提取,完成無人化詢價系統的構建。