非確定、不保真、復(fù)雜資源環(huán)境的正反雙向動(dòng)態(tài)平衡搜索服務(wù)

段玉聰，邵禮旭，曹步清，周長兵，唐朝勝，宋正陽

1(海南大學(xué) 信息科學(xué)與技術(shù)學(xué)院, 南海資源利用海洋國家重點(diǎn)實(shí)驗(yàn)室，?？?570228)2(湖南科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院, 湖南 湘潭 411201)3 (中國地質(zhì)大學(xué) 信息工程學(xué)院, 北京 100083)

1 引 言

網(wǎng)絡(luò)上資源存在時(shí)效性，在為特定用戶搜索答案時(shí)以前的資源在當(dāng)下可能失效或者不適用.同時(shí)，資源的來源也是衡量資源可信度的一個(gè)指標(biāo)，存在個(gè)人或機(jī)構(gòu)為了自身利益?zhèn)鞑A向于自身利益的虛假信息，正確的答案便會(huì)因?yàn)樘摷傩畔⒌南鄬?duì)高頻度出現(xiàn)而被淹沒.知識(shí)圖譜是一種用于存儲(chǔ)直接容納豐富語義的非結(jié)構(gòu)化和結(jié)構(gòu)化信息的知識(shí)庫.知識(shí)庫包含一組概念，實(shí)例和關(guān)系[1].基于對(duì)現(xiàn)有知識(shí)圖譜概念的拓展，[2,3]將知識(shí)圖譜擴(kuò)展為包括數(shù)據(jù)圖譜、信息圖譜和知識(shí)圖譜等三個(gè)層面的解決框架.Chaim[13]闡述了定義數(shù)據(jù)，信息和知識(shí)等概念.

在[4]中，作者提出通過構(gòu)建數(shù)據(jù)圖譜，信息圖譜和知識(shí)圖譜的架構(gòu)來回答5W問題[14].Sen[5]采用主題模型作為相似度計(jì)算的依據(jù)，消除不可見文本的引用.Malin等[6]提出利用隨機(jī)漫步模型對(duì)演員合作網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行實(shí)體消歧，并取得了比基于文本相似度模型更好的消歧效果.Wu等[7]選擇維基百科作為數(shù)據(jù)源，通過自動(dòng)抽取生成訓(xùn)練語料，用于訓(xùn)練實(shí)體屬性標(biāo)注模型.對(duì)于關(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).郭劍毅等[12]采用支持向量機(jī)算法實(shí)現(xiàn)了人物屬性抽取與關(guān)系預(yù)測(cè)模型.本文通過引入知識(shí)圖譜對(duì)資源進(jìn)行組織，在用戶進(jìn)行遞進(jìn)搜索遍歷處理資源框架時(shí)準(zhǔn)確推薦相應(yīng)的資源，并將此搜索策略應(yīng)用于醫(yī)療資源處理系統(tǒng)中，為醫(yī)療工作者提供高效高準(zhǔn)確度醫(yī)療數(shù)據(jù)檢索服務(wù).

2 數(shù)據(jù)、信息和知識(shí)圖譜處理架構(gòu)

本文提出基于數(shù)據(jù)圖譜(DGDIK)、信息圖譜(IGDIK)和知識(shí)圖譜(KGDIK)三層架構(gòu)對(duì)資源進(jìn)行建模，對(duì)數(shù)據(jù)圖譜上資源進(jìn)行去冗處理，集成相關(guān)資源得到信息圖譜，信息圖譜允許資源缺失現(xiàn)象存在，在知識(shí)圖譜上通過關(guān)系推理可以構(gòu)建出新的實(shí)體或關(guān)系，挖掘隱式存在的資源，增加圖譜的點(diǎn)密度和邊密度.經(jīng)過數(shù)據(jù)的采集和清洗、信息集成、知識(shí)描述和推理，最終構(gòu)建出資源處理架構(gòu).圖1 給出了基于數(shù)據(jù)圖譜、信息圖譜和知識(shí)圖譜的資源處理框架.

圖1 基于數(shù)據(jù)圖譜、信息圖譜和知識(shí)圖譜的資源處理框架Fig.1 Processing framework of data, information and knowledge graphs

2.1 數(shù)據(jù)圖譜

數(shù)據(jù)是通過觀察獲得的數(shù)字或其他類型信息的基本個(gè)體項(xiàng)目，但是在沒有上下文語境的情況下，它們本身沒有意義.數(shù)據(jù)圖譜可以通過數(shù)組、鏈表、隊(duì)列、樹、棧、圖等數(shù)據(jù)結(jié)構(gòu)來表達(dá).在數(shù)據(jù)圖譜上，通過計(jì)算數(shù)據(jù)的頻度，得出數(shù)據(jù)在數(shù)據(jù)圖譜上的支持度和置信度來刪除錯(cuò)誤或無用數(shù)據(jù)，刪除的條件是必須同時(shí)滿足支持度和置信度的閾值要求，閾值過大不利于圖譜表達(dá)的準(zhǔn)確性，過小會(huì)不利于表達(dá)的完整性，可以根據(jù)計(jì)算圖譜反饋的結(jié)果信息動(dòng)態(tài)調(diào)整.數(shù)據(jù)圖譜能記錄關(guān)鍵詞出現(xiàn)的頻度，包括結(jié)構(gòu)、時(shí)間和空間三個(gè)層次的頻度.但數(shù)據(jù)圖譜上未對(duì)數(shù)據(jù)的準(zhǔn)確性進(jìn)行分析，可能出現(xiàn)不同名稱的數(shù)據(jù)但表示同一含義，即數(shù)據(jù)冗余.綜上，數(shù)據(jù)圖譜只能對(duì)數(shù)據(jù)進(jìn)行靜態(tài)分析，無法分析和預(yù)測(cè)數(shù)據(jù)的動(dòng)態(tài)變化.結(jié)構(gòu)頻度、空間頻度和時(shí)間頻度的定義如下：

· 結(jié)構(gòu)頻度：表示數(shù)據(jù)出現(xiàn)在不同數(shù)據(jù)結(jié)構(gòu)中的次數(shù).數(shù)據(jù)的結(jié)構(gòu)頻度應(yīng)根據(jù)數(shù)據(jù)出現(xiàn)的最大數(shù)據(jù)結(jié)構(gòu)進(jìn)行計(jì)算.例如，如果在圖形結(jié)構(gòu)的分支中以樹結(jié)構(gòu)出現(xiàn)的數(shù)據(jù)，將按圖結(jié)構(gòu)來計(jì)算數(shù)據(jù)的結(jié)構(gòu)頻度為1，不重復(fù)計(jì)算數(shù)據(jù)在樹結(jié)構(gòu)中出現(xiàn)的頻度；

·空間頻度：本文將空間頻率定義為在不同空間位置出現(xiàn)的數(shù)據(jù)時(shí)間，描述多個(gè)對(duì)象的相對(duì)位置.利用空間頻率來識(shí)別物體之間的空間關(guān)系，一旦它們被下層識(shí)別并用邊界框標(biāo)記；

·時(shí)間頻度：本文將時(shí)間頻率定義為在不同時(shí)間段內(nèi)數(shù)據(jù)出現(xiàn)的次數(shù).初始獲取到的數(shù)據(jù)集合可能不完整，對(duì)于具有時(shí)間性的流式數(shù)據(jù)，一旦觀察到這些數(shù)據(jù)，應(yīng)該及時(shí)做出響應(yīng)，因?yàn)檫^期的數(shù)據(jù)是無意義的.

2.2 信息圖譜

信息是通過數(shù)據(jù)和數(shù)據(jù)經(jīng)過組合之后的上下文傳達(dá)的，經(jīng)過概念映射和相關(guān)關(guān)系連接之后的適合分析和解釋的信息.信息圖譜上的頻度指的是實(shí)體與實(shí)體之間的交互的頻度，信息圖譜可以表達(dá)實(shí)體之間的交互關(guān)系，根據(jù)數(shù)據(jù)圖譜上記錄的數(shù)據(jù)頻度和信息圖譜上記錄的交互頻度計(jì)算多個(gè)交互實(shí)體的綜合頻度，篩選綜合頻度低于閾值的結(jié)點(diǎn)，并把交互頻度高的實(shí)體進(jìn)行集成從而提高模塊的內(nèi)聚性.在信息圖譜上可以進(jìn)行數(shù)據(jù)清洗，消除冗余數(shù)據(jù)，根據(jù)實(shí)體之間的交互度進(jìn)行初步抽象，提高設(shè)計(jì)的內(nèi)聚性，降低耦合度.通過圈定特定數(shù)量的實(shí)體，計(jì)算內(nèi)部交互度和外部交互度，內(nèi)聚性等于內(nèi)部交互度和外部交互度的比值，設(shè)定所圈定的實(shí)體之間必須是相互連通的.

2.3 知識(shí)圖譜

知識(shí)是從積累的信息中獲得的總體理解和意識(shí)，將信息進(jìn)行進(jìn)一步的抽象和歸類可以形成知識(shí).知識(shí)圖譜可以通過包含結(jié)點(diǎn)和結(jié)點(diǎn)之間關(guān)系的有向圖來表達(dá).知識(shí)圖譜可以表達(dá)各種語義關(guān)系，在知識(shí)圖譜上通過信息推理和實(shí)體鏈接提高知識(shí)圖譜的邊密度和結(jié)點(diǎn)密度，知識(shí)圖譜的無結(jié)構(gòu)特性使得其自身可以無縫鏈接.信息推理需要有相關(guān)關(guān)系規(guī)則的支持，這些規(guī)則可以由人手動(dòng)構(gòu)建，但往往耗時(shí)費(fèi)力.使用路徑排序算法將每個(gè)不同的關(guān)系路徑作為一維特征，通過在知識(shí)圖譜中構(gòu)建大量的關(guān)系路徑來構(gòu)建關(guān)系分類的特征向量和關(guān)系分類器來提取關(guān)系，關(guān)系的正確度超過某一閾值后認(rèn)為新關(guān)系成立.關(guān)系的正確度Cr可以通過以下公式衡量，Q表示實(shí)體E1到實(shí)體E2的所有關(guān)系，π表示一類關(guān)系，θ(π)表示關(guān)系的權(quán)重，可由訓(xùn)練得出，最后正確度超過某一閾值后認(rèn)為該關(guān)系成立：

(1)

3 正反雙向動(dòng)態(tài)平衡搜索服務(wù)

3.1 正反向搜索投入分配

根據(jù)用戶對(duì)實(shí)際問題的描述，獲取用戶的搜索需求，而用戶的搜索需求在某個(gè)層面上完全能轉(zhuǎn)換成正反兩個(gè)傾向，例如，用戶在專利申請(qǐng)時(shí)的需求："聯(lián)系人變更要不要收費(fèi)？"，正面傾向?yàn)椋郝?lián)系人便變更要收費(fèi)，反面傾向?yàn)椋郝?lián)系人變更不收費(fèi).根據(jù)用戶的搜索需求進(jìn)行主動(dòng)建模，統(tǒng)計(jì)正向資源和反向資源在資源總數(shù)所占的比重，正反資源權(quán)重計(jì)算公式如下：

(2)

(3)

其中Resource正表示正向資源數(shù)，Resource反表示反向資源數(shù)，Resource總表示資源總數(shù).

用戶投入的預(yù)等待時(shí)間(T)已知，建立用戶投入模型.本文設(shè)定每次搜索的項(xiàng)數(shù)和每項(xiàng)要搜索的時(shí)間是固定的.根據(jù)公式(4)，利用用戶給出的預(yù)等待時(shí)間計(jì)算正反雙向遞進(jìn)搜索的次數(shù).

T=S_times*S_items*Pert_item

(4)

其中，S_times表示預(yù)等待時(shí)間決定搜索的次數(shù)，S_items表示每次搜索的項(xiàng)數(shù)，Pert_item表示每項(xiàng)要搜索的時(shí)間.

3.2 正反雙向動(dòng)態(tài)平衡遞進(jìn)搜索服務(wù)

對(duì)于用戶提出的問題，按照正向和反向傾向進(jìn)行雙向搜索，遍歷處理資源架構(gòu)，尋找相關(guān)資源.根據(jù)得到的資源按照資源中的關(guān)鍵詞進(jìn)行關(guān)聯(lián)因素遞進(jìn)搜索，并計(jì)算得到信息的熵值，熵值范圍是0到1，熵值越大，信息傾向越分散，可信度越低.

(5)

資源是有時(shí)效性的，entropyT是按照某一關(guān)聯(lián)因素進(jìn)行遞進(jìn)搜索時(shí)，在Tk時(shí)間下得到的資源的熵值，pi是每類答案出現(xiàn)的概率，Entropy表示按照某一關(guān)聯(lián)因素進(jìn)行遞進(jìn)搜索時(shí)，在不同時(shí)效下得到資源的加權(quán)平均熵值.

(6)

(7)

每遞進(jìn)搜索一次，根據(jù)得到的遞進(jìn)搜索項(xiàng)的熵，計(jì)算資源可信度(Confidence)：

(8)

圖2 正反向不同投入動(dòng)態(tài)平衡的有限次數(shù)遞進(jìn)搜索策略Fig.2 Incremental search strategy of investment driven balanced search

根據(jù)得到的資源的可信度，判斷正反雙向資源可信度的比值是否大于閾值T或小于1/T，該閾值可根據(jù)學(xué)習(xí)算法得到.若滿足閾值條件，返回可信度高的搜索結(jié)果給用戶；否則返回進(jìn)一步分配投入繼續(xù)遞進(jìn)搜索.圖2給出了正反向不同投入動(dòng)態(tài)平衡的有限次數(shù)遞進(jìn)搜索策略.

4 正反雙向動(dòng)態(tài)平衡搜索策略流程

圖3展示了基于數(shù)據(jù)圖譜、信息圖譜和知識(shí)圖譜的正反雙向動(dòng)態(tài)平衡搜索策略具體流程.首先根據(jù)已有資源體系建立處理資源框架，獲取用戶搜索需求.統(tǒng)計(jì)正向資源和反向資源在資源總數(shù)所占的比重(weight).根據(jù)問題所占權(quán)重確定投入分配比例，并確定正反向遞進(jìn)搜索次數(shù).

其次，對(duì)于用戶提出的問題，按照正向和反向傾向進(jìn)行雙向搜索.并對(duì)得到的資源進(jìn)行關(guān)聯(lián)因素遞進(jìn)搜索，計(jì)算得到各類資源的熵值.并計(jì)算各類資源的時(shí)效性，之后在不同時(shí)效下得到資源的加權(quán)平均熵值.每遞進(jìn)搜索一次，計(jì)算資源可信度.最后判斷與可信度法閾值的大小關(guān)系，推薦給用戶高可信度且可信度大于閾值的答案.

圖3 正反雙向動(dòng)態(tài)平衡搜索策略流程Fig.3 Bidirectional dynamic search process

5 正反雙向動(dòng)態(tài)平衡搜索服務(wù)的應(yīng)用

5.1 應(yīng)用背景

目前醫(yī)療數(shù)據(jù)有海量性、多態(tài)性、微觀性、隱私性、追蹤性、全面性、冗余性等特征.大量的醫(yī)療數(shù)據(jù)來源復(fù)雜，這些數(shù)據(jù)在存儲(chǔ)和搜索推薦時(shí)效率低下，且推薦準(zhǔn)確度低.本文提出的搜索策略可應(yīng)用于醫(yī)療資源處理系統(tǒng)，并以肝癌患者的治療方式搜索需求為例說明該策略的可行性.

5.2 正反雙向動(dòng)態(tài)平衡搜索服務(wù)示例

本文通過抽取部分互聯(lián)網(wǎng)資源并進(jìn)行統(tǒng)計(jì)，根據(jù)資源分布情況對(duì)正反向搜索進(jìn)行投入分配，根據(jù)關(guān)鍵詞"肝癌患者 治療方式 化療 可行？"搜索時(shí)獲得425,000條結(jié)果，有106250條數(shù)據(jù)表現(xiàn)為正向傾向，有246500條數(shù)據(jù)顯示為反向傾向.假定用戶的預(yù)投入時(shí)間為120分鐘，單次遞進(jìn)搜索投入固定為每次遞進(jìn)搜索的答案項(xiàng)數(shù)(20項(xiàng))和每項(xiàng)的投入時(shí)間(0.5分鐘)的乘積為10分鐘.得到資源后在正反向分別進(jìn)行遞進(jìn)搜索，以正向遞進(jìn)搜索為例，當(dāng)進(jìn)行第一次正向遞進(jìn)搜索時(shí)，用戶正向遞進(jìn)搜索需求是："肝癌患者 化療 治療金額？"，得到相應(yīng)資源歸類并統(tǒng)計(jì)第一次正向搜索相關(guān)資源.資源具有時(shí)效性，計(jì)算相應(yīng)正向資源的時(shí)效性，結(jié)果如表1所示.

表1 不同時(shí)間下資源熵及時(shí)效性計(jì)算

計(jì)算三類正向結(jié)果的平均熵，第一次正向遞進(jìn)搜索時(shí)，遞進(jìn)搜索次數(shù)(S_amount)是1，三種搜索結(jié)果的遞進(jìn)搜索的條目總數(shù)(Item_amount)分別為231000、97800、84700.利用公式(7)計(jì)算可信度.結(jié)果如表2所示.

表2 三類正向結(jié)果的平均熵和可信度計(jì)算

對(duì)計(jì)算得到的可信度進(jìn)行排序，推薦可信度高的答案給用戶，即付費(fèi)5萬元.本文設(shè)定可信度閾值T=100000，正向答案的最高可信度搜索結(jié)果為99330，小于可信度閾值T，因此，返回繼續(xù)投入進(jìn)行下一次遞進(jìn)搜索，進(jìn)行到第三次時(shí)正向搜索結(jié)束.圖4給出了正向遞進(jìn)搜索資源各項(xiàng)指標(biāo)計(jì)算.反應(yīng)第一次正向搜索時(shí)，各項(xiàng)指標(biāo)對(duì)推薦正確答案的影響程度.反向遞進(jìn)搜索同樣如此，反向遞進(jìn)搜索7次，輸出結(jié)果可信度大于閾值即推薦給用戶.

圖4 正向遞進(jìn)搜索資源各項(xiàng)指標(biāo)計(jì)算Fig.4 Calculation on the indicators of incremental search

6 相關(guān)工作

Mccarthy等[15]使用決策樹來學(xué)習(xí)如何在商業(yè)合資企業(yè)領(lǐng)域分類不同短語的系統(tǒng)，解決共指消解問題.本體(特別是OWL中表達(dá)的形式本體)被用作語義網(wǎng)中的知識(shí)表示的標(biāo)準(zhǔn)形式[16]，微軟發(fā)布的Probase利用統(tǒng)計(jì)機(jī)器學(xué)習(xí)算法抽取出概念之間的"IsA"關(guān)系，以數(shù)據(jù)驅(qū)動(dòng)的方法構(gòu)建本體[17].對(duì)于復(fù)雜的實(shí)體關(guān)系，借助TBox和ABox將基于描述邏輯的推理歸結(jié)為一致性檢驗(yàn)問題，簡化并實(shí)現(xiàn)關(guān)系推理[18].楊志等[19]利用動(dòng)態(tài)規(guī)劃的思想提出了一種基于本體的服務(wù)推薦方法，在這種方法中，隸屬度作為衡量指標(biāo)在服務(wù)推薦結(jié)果中區(qū)分相關(guān)度高低的服務(wù).彭建偉[20]中提出了一種改進(jìn)的Memetic算法以及一種基于Memetic算法的個(gè)性化學(xué)習(xí)路徑推薦策略.Fader等[21]提出一張開放問答(OQA)方法，從未標(biāo)記的問題語料庫和多個(gè)知識(shí)庫中挖掘數(shù)百萬個(gè)規(guī)則來解決問題解析和查詢重構(gòu)等問題.Wang等[22]提出一種通過概念注釋來促進(jìn)跨語言知識(shí)鏈接的方法，豐富跨語言知識(shí)的鏈接.Fu等[23]提出了一種語義導(dǎo)向的跨語言本體映射(SOCOM)框架，以增強(qiáng)涉及多語言知識(shí)庫的基于本體的系統(tǒng)的互操作性.王泊學(xué)[24]設(shè)計(jì)并實(shí)現(xiàn)了一種基于上下文感知的自適應(yīng)服務(wù)組合系統(tǒng)，將原本由服務(wù)提供者處理的上下文環(huán)境轉(zhuǎn)移到服務(wù)組合系統(tǒng)中.[25]提出了一種協(xié)同過濾方法，用于預(yù)測(cè)Web服務(wù)的QoS值，并通過利用用戶的過去使用體驗(yàn)來優(yōu)化Web服務(wù)推薦.

7 結(jié) 論

面對(duì)非確定、不保真、超復(fù)雜資源環(huán)境，本文通過引入數(shù)據(jù)圖譜、信息圖譜和知識(shí)圖譜三層架構(gòu)，提出了一種正反雙向動(dòng)態(tài)平衡搜索策略，在面對(duì)檢索出的高時(shí)效性且超復(fù)雜的非確定不保真資源時(shí)，按照資源正反傾向進(jìn)行遞進(jìn)搜索，同時(shí)在執(zhí)行策略時(shí)建立了模糊詞匯表，過濾掉傾向不明確的無用資源，通過對(duì)問題進(jìn)行有限次數(shù)的遞進(jìn)搜索，避免面對(duì)無窮盡超復(fù)雜性問題時(shí)搜索陷入死循環(huán)的情況，通過每次搜索的條目數(shù)以及每項(xiàng)條目對(duì)應(yīng)資源的熵值計(jì)算該傾向資源的可靠性，虛假信息以及失效信息會(huì)隨著遞進(jìn)搜索的次數(shù)被排除，提高了搜索資源的質(zhì)量.同時(shí)，本文應(yīng)對(duì)當(dāng)前醫(yī)療數(shù)據(jù)的高時(shí)效性以及復(fù)雜資源環(huán)境，將此搜索策略應(yīng)用于醫(yī)療資源處理系統(tǒng)中，為醫(yī)療工作者提供高效高準(zhǔn)確度醫(yī)療數(shù)據(jù)檢索服務(wù).