投入驅(qū)動的存儲與計算一體化的事務(wù)處理效率優(yōu)化方法

段玉聰,邵禮旭,曹步清,孫小兵,齊連永

(1.海南大學(xué)信息科學(xué)技術(shù)學(xué)院,海南 ?？?570228;2.湖南科技大學(xué)計算機(jī)科學(xué)與工程學(xué)院,湖南 湘潭 411201;3.揚州大學(xué)信息工程學(xué)院,江蘇 揚州 225127;4.曲阜師范大學(xué)信息科技與工程學(xué)院,山東 濟(jì)寧 276826)

1 引言

知識圖譜已經(jīng)成為用帶有標(biāo)記的有向圖的形式來表示知識，并能賦予文本信息語義的強(qiáng)大工具。知識圖譜是以節(jié)點的形式將項目、實體或用戶表示出來，以邊的形式將相互作用的節(jié)點鏈接起來構(gòu)造的圖形，邊可以表示任何語義關(guān)系。知識庫包含一組概念、實例和關(guān)系[1]。劉嶠等[2]將知識圖譜的構(gòu)建按照知識獲取的過程分為信息抽取、知識融合和知識加工三個層次，定義知識圖譜是一個具有屬性的實體通過關(guān)系鏈接而成的網(wǎng)狀知識庫。Cowie等[3]將信息抽取劃分為實體、關(guān)系和屬性三個層次，Sekine等[4]提出了一種包含150種實體的命名實體分類體系。Sen[5]采用主題模型作為相似度計算的依據(jù)，從維基百科中獲取了實體目錄，消除不可見文本的引用。Malin等[6]提出利用隨機(jī)漫步模型對演員合作網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行實體消歧，并取得了比基于文本相似度模型更好的消歧效果。Wu等[7]選擇維基百科作為數(shù)據(jù)源，通過自動抽取生成訓(xùn)練語料，將其應(yīng)用于對非結(jié)構(gòu)化數(shù)據(jù)的實體屬性抽取。對于關(guān)系抽取，出現(xiàn)了大量基于特征向量或核函數(shù)[8]的監(jiān)督學(xué)習(xí)方法、半監(jiān)督學(xué)習(xí)方法[9]和弱監(jiān)督學(xué)習(xí)方法[10]。Banko等[11]提出了面向開放域的信息抽取方法框架并發(fā)布了基于自監(jiān)督學(xué)習(xí)方式的開放信息抽取原型系統(tǒng)。Chaim[12]定義了數(shù)據(jù)、信息和知識等概念，認(rèn)為軟件服務(wù)系統(tǒng)的開發(fā)可以從數(shù)據(jù)、信息和知識的角度分為數(shù)據(jù)共享、信息傳遞和知識創(chuàng)造等階段[13]。Duan等[14]分別從數(shù)據(jù)、信息、知識和智慧方面闡明了知識圖譜的架構(gòu)并提出通過構(gòu)建數(shù)據(jù)圖譜、信息圖譜和知識圖譜的架構(gòu)回答5W問題[15]。

2 資源類型及圖譜定義

從拓展現(xiàn)有知識圖譜(Knowledge Graph)概念的角度出發(fā)，本文提出了一種基于數(shù)據(jù)圖譜DGDIK(Data GraphDIK)、信息圖譜IGDIK(InformationDIK)和知識圖譜KGDIK(Knowledge GraphDIK)三層的可自動抽象調(diào)整的解決架構(gòu)，通過對海量資源進(jìn)行合理組織和存儲,達(dá)到在資源存儲空間中以最高搜索效率找到滿足用戶檢索需求資源的目標(biāo)。本文對資源元素形態(tài)和圖譜的定義如下所示：

定義1(資源元素(ElementsDIK)) 資源元素包括數(shù)據(jù)資源、信息資源和知識資源三種形態(tài)。ElementsDIK:=〈DataDIK,InformationDIK,KnowledgeDIK〉。

定義2(圖譜(GraphDIK)) 本文對已有知識圖譜的概念進(jìn)行拓展，將圖譜的表達(dá)分為數(shù)據(jù)圖譜、信息圖譜和知識圖譜三層。

GraphDIK:=〈(DGDIK)，(IGDIK)，(KGDIK)〉。

本文對應(yīng)于DataDIK、InformationDIK、KnowledgeDIK和智慧的遞進(jìn)層次在整體上澄清知識圖譜的表達(dá)，將知識圖譜劃分為DGDIK、IGDIK、KGDIK和智慧圖譜四個層面。現(xiàn)階段本文基于前三層架構(gòu)對類型化的資源進(jìn)行構(gòu)建、存儲、處理和展示，在DGDIK層面上對通過直接觀察到的DataDIK進(jìn)行建模，在IGDIK和KGDIK上分析自適應(yīng)的自動抽象的資源優(yōu)化過程，以支持兼容經(jīng)驗知識的引入和高效的自動語義分析，在KGDIK上通過關(guān)系推理擴(kuò)展圖譜的點密度和邊密度。表1為對DataDIK、IntormationDIK和KnowledgeDIK等形態(tài)的資源以及對應(yīng)圖譜層次的介紹。

Table 1 Explanation for resource type

定義3(數(shù)據(jù)圖譜(DGDIK))

DGDIK:=collection{array,list,stack,queue,tree,graph}。

DGDIK是各種數(shù)據(jù)結(jié)構(gòu)包括數(shù)組、鏈表、棧、隊列、樹和圖等的集合。DGDIK上未對DataDIK的準(zhǔn)確性進(jìn)行分析，可能出現(xiàn)不同名稱的DataDIK但表達(dá)相同含義，即冗余。DGDIK只能對圖譜上表示的DataDIK進(jìn)行靜態(tài)分析，無法分析和預(yù)測DataDIK的動態(tài)變化。DataDIK是通過觀察獲得的數(shù)字或其他類型信息的基本個體項目，在沒有上下文語境的情況下，DataDIK沒有意義。

定義4(信息圖譜(IGDIK))

IGDIK:=combination{relatedDataDIK}。

IGDIK是相互關(guān)聯(lián)的DataDIK的組合，InformationDIK是通過DataDIK和DataDIK組合之后的上下文傳達(dá)的，經(jīng)過概念映射和相關(guān)關(guān)系組合之后的適合分析和解釋的信息。在IGDIK上可進(jìn)行數(shù)據(jù)清洗，消除冗余數(shù)據(jù)。

定義5(知識圖譜(KGDIK))

KGDIK:=collection{StatisticRules}。

KGDIK實質(zhì)是語義網(wǎng)絡(luò)，包括由InformationDIK總結(jié)出的統(tǒng)計規(guī)則的集合。KGDIK蘊含豐富的語義關(guān)系，在KGDIK上通過信息推理和實體鏈接可提高KGDIK的邊密度和節(jié)點密度，KGDIK的無結(jié)構(gòu)特性使得其自身可以無縫鏈接。信息推理需要有相關(guān)關(guān)系規(guī)則的支持，這些規(guī)則可以由人手動構(gòu)建，但往往耗時費力，得到復(fù)雜關(guān)系中的所有推理規(guī)則更加困難。使用路徑排序算法將每個不同的關(guān)系路徑作為一維特征，通過在KGDIK中構(gòu)建關(guān)系路徑來構(gòu)建關(guān)系分類的特征向量和關(guān)系分類器提取關(guān)系。

3 面向事務(wù)處理的時空效率優(yōu)化方法

3.1 問題的輸入

首先，給出本文所討論的問題的輸入。

定義6(事務(wù)性搜索目標(biāo)資源集合) 本文將事務(wù)性搜索目標(biāo)資源集合定義為TSR:={TSRD,TSRI,TSRK}，TSR的類型集合為TTSR={ttsrD,ttsrI,ttsrK}，每種資源的規(guī)模為ATSR={atsrD,atsrI,atsrK}。

定義7(資源存儲空間(RSS)) 本文將資源存儲空間定義為RSS:={RSSD,RSSI,RSSK}，RSS的類型集合為TRSS={trssD,trssI,trssK}，每種資源的規(guī)模為ARSS={arssD,arssI,arssK}。

圖1展示了事務(wù)資源的元模型，對資源處理框架的構(gòu)建和資源建?？商峁┵Y源共享、個性化推薦等服務(wù)。在建模過程中，資源類型轉(zhuǎn)換是有必要的，資源類型轉(zhuǎn)換與目標(biāo)類型和資源轉(zhuǎn)換的規(guī)模有關(guān)，并取決于用戶期望投入。

Figure 1 Meta model of transaction resources圖1 事務(wù)型資源元模型

(1)DataDIK到InformationDIK的轉(zhuǎn)換。

在沒有上下文背景的情況下DataDIK沒有語義，通過概念映射和聚類對直接觀察得到的DataDIK進(jìn)行處理，將DataDIK進(jìn)行重組和分類，重組后的DataDIK集合對應(yīng)不同的類或者概念，由此得到InformationDIK。

(2)InformationDIK到KnowledgeDIK的轉(zhuǎn)換。

InformationDIK用來表達(dá)實體之間的交互和協(xié)作，通過分類和抽象交互記錄或行為記錄得到有關(guān)實體動態(tài)行為的統(tǒng)計規(guī)則，即KnowledgeDIK。KnowledgeDIK可以從已知資源中推斷得出，推斷過程中缺乏的必要信息可通過適當(dāng)?shù)难芯考夹g(shù)來收集，例如實驗、調(diào)查等。

(3)DataDIK到KnowledgeDIK的轉(zhuǎn)換。

DataDIK可以從標(biāo)準(zhǔn)的模式中繼承語義關(guān)系，被有效地集成并被其他應(yīng)用重用，海量的DataDIK在集成融合過程中會存在冗余、不一致等現(xiàn)象，在DataDIK向KnowledgeDIK的轉(zhuǎn)換過程中，通過鏈接數(shù)據(jù)來源以及納入語義約束識別出最可靠的DataDIK進(jìn)行融合得到KnowledgeDIK。

圖2給出了由DataDIK轉(zhuǎn)換成KnowledgeDIK的例子，不同來源的DataDIK(來源1的DataDIK和來源2的DataDIK)在集成融合過程中發(fā)生沖突，此時通過引入額外的語義約束“專利類型包括發(fā)明專利和實用新型專利”，排除錯誤DataDIK“A機(jī)構(gòu)專利數(shù)量為100”。

Figure 2 An example of conversion from DataDIK to KnowledgeDIK 圖2 DataDIK向KnowledgeDIK轉(zhuǎn)換示例

(4)InformationDIK到DataDIK的轉(zhuǎn)換。

InformationDIK到DataDIK的轉(zhuǎn)換過程是從概念集合到資源實例的轉(zhuǎn)換。InformationDIK表達(dá)了實體之間的動態(tài)交互和協(xié)作，觀察實體對象在某一時刻的靜態(tài)狀態(tài)得到DataDIK。

(5)KnowledgeDIK到DataDIK的轉(zhuǎn)換。

根據(jù)知識推理，對抽取出的KnowledgeDIK集合建立相關(guān)實例，知識節(jié)點之間的關(guān)系以屬性的方式與實例相關(guān)聯(lián)，得到DataDIK。

(6)KnowledgeDIK到InformationDIK的轉(zhuǎn)換。

由已知的KnowledgeDIK通過邏輯推理挖掘隱式存在的資源，知識圖譜的無結(jié)構(gòu)特征使得其可以鏈接和利用更豐富的知識庫幫助用戶做決策，從知識檢索到知識創(chuàng)造的過程中得到InformationDIK。

3.2 問題形式化描述

如圖3所示，其特征在于以計算來決定存儲，以存儲來服務(wù)搜索，將以DataDIK、InformationDIK和KnowledgeDIK等形態(tài)存在的資源根據(jù)在DGDIK、IGDIK和KGDIK上搜索的代價進(jìn)行存儲，發(fā)現(xiàn)資源搜索和存儲的最優(yōu)方案，優(yōu)化資源處理和存儲的時空效率。

Figure 3 Resource type combination scheme圖3 資源類型組合方案

3.2.1 資源類型轉(zhuǎn)移代價計算

問題假定1：假定TSR中資源已在RSS中以任意一種方式存儲完畢。

對TSR中資源的類型集合TTSR的每個元素依次取ElementsDIK中的值，形成組合情形TTSR={ttsrD,ttsrI,ttsrK}，TSR中單位資源向ElementsDIK中定義的資源類型轉(zhuǎn)換的原子代價如表2所示，則TSR中所有的資源向賦值后對應(yīng)類型資源轉(zhuǎn)移的代價(CostMT1)可根據(jù)公式(1)來計算：

*ARRS

(1)

Table 2 Atomic cost for conversionof unit resource type in TSR

*ARSS

(2)

Table 3 Atomic cost for conversion ofunit resource type in RSS

3.2.2 處理TSR中資源的計算代價

綜合考慮存儲代價和搜索代價的計算，在不超過用戶投入的方案中選擇綜合代價最低的方案對資源搜索機(jī)制和資源存儲方案進(jìn)行調(diào)整，根據(jù)公式(3)計算在RSS中搜索TSR中資源所要花費的計算代價(Costc)：

αARSS*SCost+βARSS′

(3)

其中,α和β分別表示圖譜規(guī)模和資源類型轉(zhuǎn)換代價占Costc的權(quán)重，均可通過數(shù)據(jù)訓(xùn)練得出，ARSS′表示進(jìn)行類型轉(zhuǎn)換之后的資源規(guī)模。RSS中搜索單位資源TSR的原子代價如表4所示。

Table 4 Atomic cost for searchingunit TSR resource in RSS

3.2.3 存儲與計算協(xié)同調(diào)整的總代價計算

本文假定已提前獲取到用戶的預(yù)期投入(Inve0)和用戶所能接受的最大總代價(Total_Cost0)。根據(jù)CostMT1、CostMT2和Costc，計算TSR資源從當(dāng)前狀態(tài)向TTSR中資源類型轉(zhuǎn)移的代價和TRSS中資源向RSS中資源狀態(tài)轉(zhuǎn)移的代價以及計算代價的總和(Total_Cost)，計算方式如公式(4)所示：

Total_Cost=CostMT1+CostMT2+Costc

(4)

將不同情形下Total_Cost的值與Total_Cost0進(jìn)行比較，并將與計算所得的Total_Cost對應(yīng)的方案所需用戶投入(Inve)和Inve0作比較，判斷是否滿足條件“Total_CostTotal_Cost0時，執(zhí)行下一步操作；用戶投入計算方法如公式(5)所示：

Inve=γ*Total_Cost0-Total_Cost

(5)

其中，γ表示單位代價所需投入，可通過數(shù)據(jù)訓(xùn)練得出。

抓培訓(xùn)，干部隊伍素質(zhì)進(jìn)一步提升。林芝市局領(lǐng)導(dǎo)班子高度重視干部培訓(xùn)工作，積極組織干部赴成都、北京、拉薩、廣東、福建等地參加“四品一械”相關(guān)培訓(xùn)，自主舉辦食品安全、食品藥品抽樣、食品藥品安全協(xié)管員培訓(xùn)班等各類培訓(xùn)16期，參訓(xùn)人數(shù)共計2000余人次。

算法1計算資源類型不同組合情形下的總代價

輸入：TSR，RSS，ElementsDIK，TotalCost0，Inve0。

輸出：TSR和RSS中資源類型組合的最小總代價。

FOR eachttsrDo

Assign value fromElementsDIK;

ComputeCostMT1;

FOR eachtrssDo

Assign value fromElementsDIK;

ComputeCostMT2,Total_Cost;

IF (Total_Cost

Total_Cost0=Total_Cost;

事務(wù)處理效率優(yōu)化方法的流程如圖4所示。

Figure 4 Process of the collaborative storage and computation adaptation 圖4 存儲與計算一體化方法流程

算法1描述了TSR和RSS中資源不同類型的組合情況，計算每種情況下TSR中資源向TTSR中資源類型轉(zhuǎn)移的代價，TRSS中資源狀態(tài)向RSS轉(zhuǎn)移的代價，以及每種組合情況下在RSS中搜索TSR中資源的計算代價，找出不超過用戶投入且具有最小Total_Cost的方案作為協(xié)同調(diào)整資源的最優(yōu)方案。

4 資源類型轉(zhuǎn)換效果示意

本文將提出的優(yōu)化方法應(yīng)用于以下場景：資源庫中有一個用戶訂單表，并關(guān)聯(lián)了用戶信息表，訂單表中有1 000萬條用戶記錄信息，用戶信息表中有100萬條用戶采購記錄信息。依據(jù)用戶的訂單記錄給用戶推薦合適的產(chǎn)品時，傳統(tǒng)方法是從這1 000萬條記錄中查找出對應(yīng)用戶id的記錄然后通過分庫、分表等操作進(jìn)行查詢，然而要在一臺服務(wù)器的基礎(chǔ)上不做分庫、分表，就要從這100萬個用戶數(shù)據(jù)關(guān)聯(lián)的1 000萬個訂單記錄中，提取出用戶消費相關(guān)產(chǎn)品的知識體系，例如按年齡劃分等，依據(jù)知識來給用戶進(jìn)行推薦。本文構(gòu)建的知識體系形成了新的表，這些新的包含知識的表比原有記錄表的規(guī)模小很多，時間是查詢某個用戶id訂單記錄的時間和通過知識推理得出的時間。如圖5所示，本文將不轉(zhuǎn)換資源類型(方案0)推薦結(jié)果準(zhǔn)確度設(shè)為1，通過比較不同方案向用戶推薦的產(chǎn)品的相似度來衡量用戶滿意度。

Figure 5 Accuracy comparison of resource type conversion results圖5 資源類型轉(zhuǎn)換結(jié)果準(zhǔn)確度比較

本文將用戶訂單表關(guān)聯(lián)的用戶根據(jù)年齡進(jìn)行劃分，再結(jié)合采購記錄，建立不同年齡段對商品的偏好體系，例如15～20歲用戶常買學(xué)習(xí)用品，20～40歲用戶常買服裝個護(hù)用品，40～55歲用戶常買生活用品。同時為500個用戶進(jìn)行商品推薦，方案1～方案4分別是為100個、200個、300個、400個用戶按推理出的商品采購偏好知識體系進(jìn)行推薦，剩余用戶按分庫分表進(jìn)行查詢，根據(jù)查詢結(jié)果進(jìn)行相似商品推薦。不同方案之間資源類型轉(zhuǎn)換的目標(biāo)類型和轉(zhuǎn)換規(guī)模不同，隨著用戶采購商品的記錄數(shù)量增多，推薦商品一致性與傳統(tǒng)方法的相似度逐漸升高。知識體系是經(jīng)過抽象后的可推理的規(guī)則，在提取知識體系的過程中所消耗的計算資源和存儲資源都會降低，通過計算未轉(zhuǎn)換資源類型和轉(zhuǎn)換資源類型后不同方案的代價差異，選擇在用戶投入范圍內(nèi)具有最大效益比的方案對優(yōu)化資源存儲和計算。

5 相關(guān)工作

Mccarthy等[16]使用決策樹來學(xué)習(xí)如何在商業(yè)合資企業(yè)領(lǐng)域分類不同短語的系統(tǒng)，解決共指消解問題。本體被用作語義網(wǎng)中的知識表示的標(biāo)準(zhǔn)形式[17]，微軟發(fā)布的Probase利用統(tǒng)計機(jī)器學(xué)習(xí)算法以數(shù)據(jù)驅(qū)動的方法構(gòu)建本體[18]。MongoDB作為一種基于分布式文件存儲的數(shù)據(jù)庫，不適用于高度事務(wù)性的系統(tǒng)，基于DGDIK、IGDIK和KGDIK三層架構(gòu)對資源進(jìn)行建模，以節(jié)點和邊的形式存儲資源，圖譜對自然語言的映射更完整，可以表達(dá)實體間任意的語義關(guān)系及與或非等邏輯關(guān)系。Wang 等[19]通過概念注釋來促進(jìn)跨語言知識鏈接，促進(jìn)不同語言的知識共享。潘偉豐等[20]提出服務(wù)分類方法并用于服務(wù)注冊管理系統(tǒng)中，為服務(wù)提供分類信息，提高服務(wù)發(fā)現(xiàn)、檢索以及服務(wù)資源管理的效率。

6 結(jié)束語

本文的貢獻(xiàn)在于將以數(shù)據(jù)、信息和知識等形態(tài)的資源根據(jù)資源的存儲代價和搜索代價綜合考慮來協(xié)同調(diào)整資源的搜索機(jī)制和存儲方案，優(yōu)化時空效率?；贒GDIK、IGDIK和KGDIK建立資源處理框架，對不同的資源需求在最匹配的資源層面上進(jìn)行查找，有效提高查找效率。合理地處理系統(tǒng)中的類型化資源，通過分析和抽象事務(wù)處理中海量的DataDIK、InformationDIK和KnowledgeDIK等形態(tài)的資源，消除概念歧義，剔除冗余和錯誤概念，提高DataDIK、InformationDIK和KnowledgeDIK等資源的質(zhì)量。當(dāng)前工作在各個環(huán)節(jié)進(jìn)行了實例討論，下一步將擴(kuò)大數(shù)據(jù)規(guī)模進(jìn)行驗證。