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