時(shí)序圖
?時(shí)序圖是一種UML交互圖及序列圖，通過描述對象之間發(fā)送消息的時(shí)間順序顯示多個(gè)對象之間的動(dòng)態(tài)協(xié)作。它可以表示用例的行為順序，當(dāng)執(zhí)行一個(gè)用例行為時(shí)，其中的每條消息對應(yīng)一個(gè)類操作或狀態(tài)機(jī)中引起轉(zhuǎn)換的觸發(fā)事件。
組成元素
時(shí)序圖中包括如下元素：角色，對象，生命線，控制焦點(diǎn)和消息。
1、角色（Actor）
系統(tǒng)角色，可以是人或者其他系統(tǒng)，子系統(tǒng)。
2、對象(Object)
對象代表時(shí)序圖中的對象在交互中所扮演的角色，位于時(shí)序圖頂部和對象代表
對象一般包含以下三種命名方式：
第一種方式包含對象名和類名。
第二種方式只顯示類名不顯示對象名，即為一個(gè)匿名對象。
第三種方式只顯示對象名不顯示類名。
3、生命線(Lifeline)
4、控制焦點(diǎn)(Activation)
控制焦點(diǎn)代表時(shí)序圖中的對象執(zhí)行一項(xiàng)操作的時(shí)期，在時(shí)序圖中每條生命線上的窄的矩形代表活動(dòng)期。它可以被理解成C語言語義中一對花括號(hào)“{}”中的內(nèi)容。
消息是定義交互和協(xié)作中交換信息的類，用于對實(shí)體間的通信內(nèi)容建模，信息用于在實(shí)體間傳遞信息。允許實(shí)體請求其他的服務(wù)，類角色通過發(fā)送和接受信息進(jìn)行通信。
結(jié)構(gòu)
時(shí)序圖描述對象是如何交互的，并且將重點(diǎn)放在消息序列上。也就是說，描述消息是如何在對象間發(fā)送和接收的。時(shí)序圖有兩個(gè)坐標(biāo)軸：縱坐標(biāo)軸顯示時(shí)間，橫坐標(biāo)軸顯示對象。每一個(gè)對象的表示方法是：矩形框中寫有對象和 / 或類名，且名字下面有下劃線；同時(shí)有一條縱向的虛線表示對象在序列中的執(zhí)行情況(即發(fā)送和接收的消息對象的活動(dòng)) ，這條虛線稱為對象的生命線。對象間的通信用對象的生命線之間的水平的消息線來表示，消息線的箭頭說明消息的類型，如同步，異步或簡單。瀏覽時(shí)序圖的方法是，從上到下查看對象間交換的消息，分析那些隨著時(shí)間的流逝而發(fā)生的消息交換。
時(shí)序圖中的消息可以是信號(hào)、操作調(diào)用或類似于C++ 中的RPC（ Remote Procedure Call,遠(yuǎn)程過程調(diào)用）或Java中的RMI（ Remote Method Invocation ，遠(yuǎn)程方法調(diào)用）。當(dāng)對象接收到一個(gè)消息時(shí)，該對象中的一項(xiàng)活動(dòng)就會(huì)啟動(dòng)，我們把這一過程稱做激活（ Activation ）。激活會(huì)顯示控制焦點(diǎn)，表明對象在某一個(gè)時(shí)間點(diǎn)開始執(zhí)行。一個(gè)被激活的對象或者是執(zhí)行它自身的代碼，或者是等待另一個(gè)對象的返回（該被激活的對象已經(jīng)向另一個(gè)對象發(fā)送了消息）。在圖形上，激活被繪制為對象生命線上的一個(gè)瘦高矩形。
消息可以用消息名及參數(shù)來標(biāo)識(shí)。消息還可帶有條件表達(dá)式，表示分支或決定是否發(fā)送消息。如果用于表示分支，則每個(gè)分支是相互排斥的，即在某一時(shí)刻僅可發(fā)送分支中的一個(gè)消息。消息也可以有順序號(hào)，但是在時(shí)序圖中，消息的順序號(hào)很少使用，因?yàn)闀r(shí)序圖已經(jīng)將消息的順序顯式地表示出來了。
一個(gè)對象可以通過發(fā)送消息來創(chuàng)建另一個(gè)對象，當(dāng)一個(gè)對象被刪除或自我刪除時(shí)，該對象用 "X"標(biāo)識(shí)。
創(chuàng)建步驟
1、確定交互過程的上下文；
2、識(shí)別參與過程的交互對象；
3、為每個(gè)對象設(shè)置生命線；
4、從初始消息開始，依次畫出隨后消息；
5、考慮消息的嵌套，標(biāo)示消息發(fā)生時(shí)的時(shí)間點(diǎn)，則采用FOC（focus of control）；
6、說明時(shí)間約束的地點(diǎn)。
影響算法
時(shí)序圖影響力最大化問題，即在時(shí)序圖上尋找K個(gè)頂點(diǎn)使得信息最大化的傳播。傳播模型的選擇和節(jié)點(diǎn)間傳播概率的計(jì)算是影響力最大化問題的基礎(chǔ)，由于基于靜態(tài)圖的IC(Independent Cascade model)傳播模型無法應(yīng)用于時(shí)圖，因此首先對 IC 模型進(jìn)行改進(jìn)提出了ICT(Independent Cascade model on Temporal Graph)傳播模型，使信息可以通過ICT傳播模型在時(shí)序圖上進(jìn)行傳播。而后通過改進(jìn)PageRank算法來進(jìn)行計(jì)算節(jié)點(diǎn)間的傳播概率。然后在此基礎(chǔ)上將時(shí)序圖影響力最大化問題分為兩步來進(jìn)行實(shí)現(xiàn)。
動(dòng)態(tài)圖最大化算法
通過對基于靜態(tài)圖的影響力最大化算法的研究并改進(jìn)，從而將影響力最大化問題的研究對象由靜態(tài)圖轉(zhuǎn)移到動(dòng)態(tài)圖上去，并提出了可以解決動(dòng)態(tài)圖影響力最大化問題的算法。
首次在動(dòng)態(tài)圖上進(jìn)行了影響力最大化問題的研究。其中對SKIM 算法進(jìn)行改進(jìn)將其適用于動(dòng)態(tài)圖的影響力最大化問題的實(shí)現(xiàn)。其采用反向可達(dá)采樣方法首先采樣處多個(gè)采樣集合，通過采樣集合來找出種子節(jié)點(diǎn)集合，而后圖中會(huì)有節(jié)點(diǎn)的添加或刪除操作，通過計(jì)算節(jié)點(diǎn)的刪除或添加對當(dāng)前采樣集合的影響來重新計(jì)算種子節(jié)點(diǎn)集合。由于其完全沒有考慮節(jié)點(diǎn)間聯(lián)系的因素，且是以全局的角度來研究時(shí)序圖影響力最大化問題，其間并無節(jié)點(diǎn)增刪的操作，所以研究方法無法解決所研究的問題。則是使用的一種新的窗口滑動(dòng)的模型來研究動(dòng)態(tài)圖上的實(shí)時(shí)影響力最大化問題，其研究思路為設(shè)置一個(gè)時(shí)間窗口w，將節(jié)點(diǎn)間的聯(lián)系看作一個(gè)action，并將這些 action 按照時(shí)間的先后順序存放在w中。窗口w會(huì)隨著時(shí)間向下滑動(dòng)，此時(shí)便涉及到新的action的進(jìn)入和舊的action的退出(因?yàn)榇翱诘拇笮∈强梢匀藶樵O(shè)定的)，根據(jù)節(jié)點(diǎn)的進(jìn)入和退出，來判斷是否需要對在上一個(gè)時(shí)間段所求出的窗口中的種子節(jié)點(diǎn)進(jìn)行重新計(jì)算。而由于是從全局的角度在時(shí)序圖上研究影響力最大化問題，所以研究思路也無法解決所要研究的問題。
時(shí)序圖
時(shí)序圖和靜態(tài)圖的本質(zhì)上的不同是時(shí)序圖在邊的權(quán)重上加入了時(shí)間戳這一因素。靜態(tài)圖上的邊一旦存在便不會(huì)因時(shí)間的變化而改變，而在時(shí)序圖中，邊會(huì)因時(shí)間的變化在兩種狀態(tài)下相互轉(zhuǎn)化：激活狀態(tài)和非激活狀態(tài)。時(shí)序圖中頂點(diǎn)間只在邊處在激活狀態(tài)下時(shí)是存在聯(lián)系的。
在現(xiàn)實(shí)生活中有很多常見的網(wǎng)絡(luò)都可以描述為時(shí)序圖。(1)點(diǎn)對點(diǎn)通信網(wǎng)絡(luò)：如電子郵件、手機(jī)短信等。(2)一對多的消息傳播網(wǎng)絡(luò)：在這種網(wǎng)絡(luò)中注重的是單一用戶對其余多個(gè)用戶的信息傳播。(3)生物信息網(wǎng)絡(luò)：如代謝網(wǎng)絡(luò)、蛋白質(zhì)互作用網(wǎng)絡(luò)等。研究表明，在生物信息網(wǎng)絡(luò)中，各節(jié)點(diǎn)間的交流是時(shí)間相關(guān)的，所以Teresa M. Przytycka等人認(rèn)為對于生物信息網(wǎng)絡(luò)的分析是需要借助于動(dòng)態(tài)網(wǎng)絡(luò)來實(shí)現(xiàn)的，且在對蛋白質(zhì)互作用和基因調(diào)控網(wǎng)絡(luò)的研究工作中已經(jīng)有研究者開始分析時(shí)間對網(wǎng)絡(luò)的影響。
時(shí)序圖影響力最大化基本算法
基本的時(shí)序圖影響力最大化算法的思想是：將時(shí)序圖影響力問題分為兩步解決，首先第一步計(jì)算節(jié)點(diǎn)影響力，然后第二步是根據(jù)第一步所得出的實(shí)驗(yàn)結(jié)果使用貪心算法逐次尋找出邊際效應(yīng)最大的那個(gè)節(jié)點(diǎn)作為種子節(jié)點(diǎn)，直到找出k個(gè)種子節(jié)點(diǎn)為止。
首先提出了時(shí)序圖節(jié)點(diǎn)影響力計(jì)算算法SIC算法以及其改進(jìn)算法ISIC算法，然后在此基礎(chǔ)上計(jì)算節(jié)點(diǎn)的邊際效應(yīng)，并由此提出基本的可以解決時(shí)序圖影響力最大化問題的基本算法BIMT算法。
風(fēng)險(xiǎn)預(yù)測
為每位病人構(gòu)建一個(gè)醫(yī)療時(shí)序圖，時(shí)序圍的表示形式壓縮了原始數(shù)據(jù)使其更緊湊，從而有效解決了醫(yī)療數(shù)據(jù)的稀疏性問題，并且為每位病人的分散數(shù)據(jù)提供了一種全景概括視圖
病人時(shí)序圖
疾病風(fēng)陰預(yù)測方法MTPGraph中病人時(shí)序圖將每位病人原始EHRs數(shù)據(jù)中的時(shí)序臨床事件轉(zhuǎn)變?yōu)闀r(shí)序圖，為所有病人提供了一種一致性表示形式，并考慮了不同臨床事件之間的時(shí)序關(guān)系。在形成圖的過程中，將用藥進(jìn)行了粗粒度劃分，例如，'地高辛（Digoxin）'和萬爽力（Vasorel）'可歸類為’抗心絞痛藥物（AntianginalAgents）'。畫像圖的節(jié)點(diǎn)表示粗粒度醫(yī)療事件（即，疾病名稱，粗粒度用藥，化驗(yàn)名稱等）；根據(jù)臨床事件的時(shí)間戳來形成有向邊，可以捕捉任意兩個(gè)醫(yī)療事件之間的時(shí)序關(guān)系；邊權(quán)重反映出相鄰兩個(gè)醫(yī)療事件之間的平均時(shí)間間隔，邊越粗權(quán)重越大，則平均時(shí)間間隔越短，這種表示形式簡便直觀，易于捕捉到不同臨床事件之間時(shí)序關(guān)系的強(qiáng)弱。
從疾病風(fēng)陰預(yù)測方法MTPGraph中可為各種分析任務(wù)捕捉到綜合全面的信息。在構(gòu)建時(shí)序圖時(shí)，與文獻(xiàn)不同的是需要根據(jù)實(shí)際的數(shù)據(jù)格式進(jìn)行以下幾方面考慮：首先需要從病人電子健康檔案記錄中抽取臨床事件，根據(jù)中國藥典（ChinesePharmacopoeia）將其劃分為粗粒度醫(yī)療事件，基于相對應(yīng)的時(shí)間戳形成時(shí)序序列，最后將得到的粗粒度事件序列轉(zhuǎn)變成時(shí)序圖。基于圖的表示方式能夠用更簡潔的方式捕捉到隱藏在事件序列中的時(shí)序關(guān)系，并且在時(shí)序序列中擁有一致順序重復(fù)出現(xiàn)的事件對在時(shí)序圖中只出現(xiàn)一次，意味著這種表示形式能夠幫助抵制稀疏性及不規(guī)則觀察。
疾病風(fēng)險(xiǎn)預(yù)測
疾病風(fēng)陰預(yù)測方法MTPGraph中疾病風(fēng)險(xiǎn)預(yù)測提出了一種挖掘頻繁時(shí)序特征圖的算法。為了執(zhí)行不同疾病風(fēng)險(xiǎn)預(yù)測任務(wù)，例如預(yù)測冠私病患者的病情是否好控制，或者預(yù)測慢性阻塞性肺病患者在未來90天內(nèi)是否會(huì)再次住院等任務(wù)，都需要采取以下步驟：首先要構(gòu)建信息量豐富的特征圖，利用提出的頻繁時(shí)序子序列挖掘算法TRApriori，Apriori是最成熟的頻繁項(xiàng)集挖掘算法之一，基于該方法去獲得頻繁時(shí)序子序列，隨后形成頻繁時(shí)序特征圖；其次如疾病風(fēng)陰預(yù)測方法MTPGraph中疾病風(fēng)險(xiǎn)預(yù)測所示基于病人時(shí)序圖及頻繁時(shí)序特征圖來構(gòu)建特征向量，每個(gè)病人時(shí)序圖都可由第一步得到的特征圖重新組成，隨之產(chǎn)生一個(gè)重構(gòu)系數(shù)，即生成的是特征向量，用來進(jìn)行有效的疾病風(fēng)險(xiǎn)預(yù)測。