季金鑫，姜麗紅，蔡鴻明

(上海交通大學 軟件學院，上海 200240)

基于聚類的個人健康檔案補全方法的研究與實現(xiàn)

季金鑫，姜麗紅，蔡鴻明

(上海交通大學 軟件學院，上海 200240)

診療記錄對病人和醫(yī)生而言都是十分有用的,但是由于同一個病人在不同的時間會以不同的識別信息在醫(yī)院進行治療，那么這個病人的診療信息就會分布在不同的記錄中，這樣使得醫(yī)生無法判斷這些診療記錄是否來自同一個病人.為了解決這個問題，提出了個人健康檔案補全的方法, 利用數(shù)值聚類、特征分析、實例類別匹配和診療記錄補全的方法來識別相同病人的不同診療記錄，繼而實現(xiàn)個人健康檔案的補全.最后，通過在某個醫(yī)院特定的數(shù)據(jù)庫對文中提出的方法進行試驗來驗證方法的可用性.

診療記錄；個人健康檔案補全；數(shù)值聚類；特征分析；實例類別匹配；記錄補全

醫(yī)療數(shù)據(jù)可以較有效地描述診療過程的業(yè)務邏輯，但是，目前缺乏較好的方法對醫(yī)療數(shù)據(jù)之間的關聯(lián)進行分析.比如，同一個病人在不同的時間段進入不同的醫(yī)療機構進行治療，這個病人的診療記錄就會分布在不同的數(shù)據(jù)庫中，即使同一個病人在不同的時間段在同一個醫(yī)療機構進行治療，病人的治療記錄也會分布在不同的科室或醫(yī)院信息系統(tǒng)中，導致病人的歷史診療信息不完整和個人健康檔案數(shù)據(jù)更新不及時等問題.

針對這一問題，國內(nèi)外很多學者都提出了一些方案來解決.文獻[1]基于局部CON模型的記錄匹配方法，利用關聯(lián)規(guī)則挖掘和標準的tableau來匹配分布式數(shù)據(jù)庫中的記錄，識別相同身份人的記錄. 文獻[2]通過對數(shù)據(jù)庫中不一致數(shù)據(jù)的修復以及用概率來表示記錄上的屬性值從而識別數(shù)據(jù)庫中的相似重復記錄.

本文旨在解決病人的歷史診療信息不完整和個人健康檔案數(shù)據(jù)更新不及時的問題，涉及數(shù)值聚類、對象匹配等方面的內(nèi)容.

目前數(shù)值聚類方法被廣泛應用于各種數(shù)據(jù)挖掘和數(shù)據(jù)分析. 文獻[3]通過最小化不可連接性來進行數(shù)值聚類，使用MinDisconnect算法通過不斷減小不可連接性來合并聚類. 文獻[4]提出了通過計算基于上下文的數(shù)值之間的距離來對數(shù)值進行聚類的方法，即采用DILCA(distance learning for categorical attributes)方法來計算任意兩個數(shù)值之間的距離.

為了實現(xiàn)對象與對象之間的匹配，不少學者做了巨大的努力，當然，對于對象匹配，最常用的就是相似度計算方法.文獻[5]基于描述性特征，不依賴于模型的實例來對相似度進行度量，將實例匹配問題轉化為二元分類問題來進行實例的匹配.文獻[6]針對圖像的匹配，提出了一個圖像描述符的方法，利用這個圖像描述符來比較相似的圖像.

但是，上述方法均沒有考慮數(shù)據(jù)缺省的情況，并且在上述的方法中只是識別相同實體的記錄，并沒有對這些記錄進行融合. 因此，本文在考慮數(shù)據(jù)缺省的情況下提出了個人健康檔案補全方法，基于數(shù)據(jù)庫中病人的基本信息以及診療記錄，對相同病人的診療記錄進行融合.使用數(shù)值聚類和對實例類別匹配的方法來識別不同記錄中的相同病人，針對特定醫(yī)院的數(shù)據(jù)類型進行個人健康檔案的補全，補全后實現(xiàn)了病人的診療記錄的融合，可為今后的個性化治療等提供幫助.

1 個人健康檔案補全方法框架

針對目前的業(yè)務需求，專門針對醫(yī)院數(shù)據(jù)庫中病人信息表設計了個人健康檔案補全方法.針對醫(yī)院數(shù)據(jù)庫中有關病人信息的數(shù)據(jù)庫表，個人健康檔案補全的方法分為4步，如圖1所示. 具體步驟如下：

(1) 第一階段為數(shù)值聚類.即通過分析數(shù)據(jù)庫中的病人的基本信息以及診療等信息，提取病人的姓名、年齡、性別、身份證號和疾病特征，使用改進后的K-Means聚類算法將具有類似特征值的診療記錄歸為一類.

圖1 個人健康檔案補全框架Fig.1 Personal health records completion framework

(2) 第二階段為聚類特征分析.即對于每個類別，使用文檔頻度的方法分析類別的特征，得出每一個類別所具有的共同特征，比如一些治療方案等.

(3) 第三階段為實例類別匹配.即根據(jù)第一階段得到的聚類分析的結果，對于每一個新的診療記錄，提取其姓名、年齡、性別、身份證號和疾病特征，然后利用相似度計算的方法，將這個新的診療記錄匹配到某一個類別中.

(4) 第四階段為診療記錄的補全.即在判定了一條新的診療記錄屬于某一個類別之后，將這個類別所擁有的共同特征賦予這條診療記錄，比如一些通用的治療方案可以賦予這個診療記錄對應的病人，同時，判斷記錄是否屬于同一病人.此時有兩種情況：第一種情況，若存在身份證號，相同的身份證號對應的一定是相同的病人；第二種情況，若身份證號信息缺省，則判斷對于相同姓名和相同性別的記錄，若在同一個聚類中，具有相同的群特征，則可以初步判定這些病人是同一個病人.此時可以進行相同病人診療記錄的補全.由于每一條診療記錄被賦予了群特征，這樣對于醫(yī)生而言，就多了一些可供參考的治療方案，可以讓醫(yī)生知道之前類似的病癥有哪些成功治療的案例，醫(yī)生就可以參照這些治療方案對病人進行更加有效的治療.

2 個人健康檔案補全實現(xiàn)方法

2.1 數(shù)值聚類方法

通過分析數(shù)據(jù)庫中數(shù)據(jù)記錄的特點，找出關鍵屬性值，利用關鍵屬性值定義“距離”來衡量兩個記錄間的接近程度或相似程度，把比較接近的或類似的歸為一類，而把不怎么接近或不怎么類似的分在不同的類別中.利用改進的K-Means算法實現(xiàn)數(shù)據(jù)庫中記錄的數(shù)值聚類.

(1) 第一步：特征提取.利用特征提取的方法對病人進行聚類，提取病人的姓名、年齡、性別、身份證號和疾病這些屬性，用這5種特征來代表一個病人，即S代表一個病人，S(name， age，gender， ID， disease)即代表病人的一條記錄，現(xiàn)有數(shù)據(jù)集S={S1,S2, …,Sn}，代表了n個病人，每個病人包含5個屬性，即姓名、年齡、性別、身份證號和疾病.

(2) 第二步：利用多維坐標系表示診療記錄.建立空間多維坐標系，共5個維度，分別代表5個關鍵屬性，即姓名、年齡、性別、身份證號和疾病.年齡按0～100排列；性別用0和1表示，0表示男性，1表示女性；身份證號取前6位表示；疾病按照類別排列，用數(shù)據(jù)0～200表示，相似的疾病放到相鄰的坐標位置，其值越接近，例如腰椎間盤突出和腰椎病就是類似的病，可以放到相鄰的坐標位置.

(3) 第三步：數(shù)據(jù)記錄之間“距離”的定義.由第一步得到的每條記錄有5個屬性，給每個屬性分配一定比例的權重，姓名屬性權重(w1)為0.2，年齡屬性權重(w2)為0.1，性別屬性權重(w3)為0.1，身份證號屬性權重(w4)為0.5，疾病權重(w5)為0.1，權重相加為1.每一條記錄表示為空間坐標軸上的一個點S(A,B,C,D,E)，其中，屬性A,B,C,D,E分別表示姓名、年齡、性別、身份證號和疾病，D(Si,Sj)表示兩條記錄Si和Sj在空間坐標系中的距離，計算式如下.

D(Si, Sj)=|Ai-Aj|*w1+|Bi-Bj|*w2/100+|Ci-Cj|*w3+|Di-Dj|*w4+|Ei-Ej|*w5/200

(1)

其中：|Ai-Aj|表示姓名屬性之間的距離，若姓名相同，則距離為0，否則距離為1；|Bi-Bj|表示年齡屬性之間的距離，即為年齡的差值，這里要進行歸一化處理；|Ci-Cj|表示性別屬性之間的距離，性別相同則距離為0，否則距離為1；|Di-Dj|表示身份證號屬性之間的距離，該距離用編輯距離表示，取身份證號前6位，這里身份證號前6位的編輯距離即為身份證號屬性之間的距離；|Ei-Ej|表示疾病屬性之間的距離，即為疾病數(shù)據(jù)對應的差值，同樣，這里要進行歸一化處理.因為身份證號信息是缺省信息，不一定所有的記錄都會提供這一信息，所以若兩條記錄的身份證號信息均不存在，此時身份證號屬性權重w4變?yōu)?，重新分配屬性權重，即姓名屬性權重(w1)為0.3，年齡屬性權重(w2)為0.2，性別屬性權重(w3)為0.3，疾病屬性權重(w5)為0.2，距離仍按式(1)計算.

(4) 第四步：利用改進后的K-Means算法進行聚類.傳統(tǒng)的K-Means算法簡單、快速，并且可以處理大規(guī)模的數(shù)據(jù)，但是K-Means算法的第一步是隨機選擇K個對象作為聚類中心，這樣就容易得到局部最優(yōu)解，并且這個局部的最優(yōu)解完全依賴于初始聚類中心的選擇.同時，對于不同初始聚類中心的選擇會得到不同的聚類結果，算法比較不穩(wěn)定.所以這里對K-Means算法稍作改進，假設聚類的個數(shù)為K個，改進后的K-Means算法偽代碼如下所述.

Input:

All records with property values of name, age, gender, ID and disease

Output:

Kclusters and records in each cluster

Find two records with the longest distance

The number of clusterm=2

Make the two records be the cluster center ofmclusters

WhileK>m

Find one record has the longest distance to themcluster centers

m++

Make the record be center of new cluster

While the clusters are changing

Make each record belong to its nearest cluster center

Change the cluster centers

returnKclusters and records in each cluster

改進的K-Means算法改變了傳統(tǒng)K-Means算法對初始聚類中心的選擇，不是隨機選取K個對象作為聚類中心，而是首先選擇兩個距離最遠的對象作為初始的兩個聚類中心，接著找到第3個距離這兩個對象最遠的對象作為第3個聚類中心，依此類推，直到找到K個聚類中心為止.這樣的初始聚類中心的選擇可以最大程度地保證聚類中心分配的合理性，得到整體最優(yōu)解.

2.2 特征分析方法

對于每一個聚類的特征分析方法的實現(xiàn)，利用文檔頻度的方法統(tǒng)計治療方案，得出Top 3的治療方案作為聚類的共同特征.

文檔頻度(document frequency， DF)方法[7]是用來統(tǒng)計一個特征詞在一個類別中出現(xiàn)次數(shù)的方法，該方法的實現(xiàn)簡單且算法復雜度低，所以選用此方法來進行特征分析.數(shù)據(jù)庫表中每種治療方案均為字符串表示，比如“人工關節(jié)置換”“長期青霉素注射”等，然后利用文檔頻度統(tǒng)計的方法，列出每一個聚類中出現(xiàn)的所有治療方案，對這些治療方案進行統(tǒng)計，統(tǒng)計每種治療方案出現(xiàn)的次數(shù)，見式(2)所示.

C=(〈TERM1,DF1〉,〈TERM2,DF2〉,…, 〈TERMi, DFi〉,…,〈TERMn, DFn〉)

(2)

其中：C為統(tǒng)計的集合；〈TERMi, DFi〉為第i個治療方案字符串；DFi為第i個治療方案出現(xiàn)的次數(shù). 現(xiàn)根據(jù)DFi的大小進行排列，找出前3個DFi值最大的TERMi，這3個TERM即為找到的Top 3的治療方案，可以將其作為每一個聚類的共同特征.

2.3 實例類別匹配方法

實例類別匹配利用數(shù)值聚類的結果，將一個新的記錄匹配到某一個類別中.

(1) 第一步：一個新加進來的數(shù)據(jù)庫記錄，包括了病人的基本信息以及診療信息，同樣地，抽取病人的姓名、年齡、性別、身份證號和疾病信息，形成一個新的記錄.

(2) 第二步：新記錄類別確定.利用式(1)計算這個新記錄與各個聚類中心的距離，將該記錄分配到與其距離最小的聚類中.

2.4 診療記錄補全方法

診療記錄補全階段則利用實例類別匹配結果，判斷同名病人是否為同一個人來補全診療記錄.這里利用新生成關聯(lián)表的方法來進行同一個病人的不同診療記錄的融合.這里給出如下兩個定義.

定義1 對于每一組相同病人的不同診療記錄，在不同記錄中時間屬性值最早的那條記錄定義為主記錄，這條記錄的主鍵定義為主主鍵.

定義2 對于每一組相同病人的不同診療記錄，除了時間屬性值最早的那條記錄，其余記錄均稱為從屬記錄，這些記錄的主鍵均定義為從屬主鍵.

(1) 第一步：找出相同病人的不同診療記錄.首先找出所有同名病人的診療記錄，對于這些同名的病人，若是屬于同一個類別中，則可以將其認為是相同的病人；若不屬于同一個類別中，則認為是不同的病人.

(2) 第二步：相同病人診療記錄的融合.對于在上一步中找到的相同病人的診療記錄，對于同一個病人，取出其所有的診療記錄，找到其中的主記錄和從屬記錄、主主鍵和從屬主鍵，建立主主鍵和從屬主鍵之間的關聯(lián)表.

3 案例分析和討論

3.1 案例分析

通過分析某醫(yī)院的真實診療數(shù)據(jù)，對本文提出的個人健康檔案補全方法進行了驗證.

(1)首先分析數(shù)據(jù)庫中的每一張表的含義以及表中每一個屬性的含義，得出關于病人信息方面的表有兩張，分別是病人的基本信息表和病人的診療信息表.在此數(shù)據(jù)庫中體現(xiàn)為兩個表，分別是dbo.ab表(病人基本信息表)和dbo.cb表(病人診療信息表)，如圖2和3所示.

(2) 結合本文所提出的數(shù)值聚類的方法，建立空間多維坐標系，接著利用改進的K-Means算法對數(shù)據(jù)庫中500條記錄進行聚類，最終聚類的結果為4個類別.這里用傳統(tǒng)的K-Means算法和改進后的K-Means算法進行聚類結果的比較.

傳統(tǒng)的K-Means算法首先選取前4條記錄作為初始聚類中心，經(jīng)過多次迭代，得到4個聚類和每個聚類中的記錄.

圖2 dbo.ab表Fig.2 Table of dbo.ab

圖3 dbo.cb表Fig.3 Table of dbo.cb

改進后的K-Means算法首先選取距離分別最遠的4條記錄作為初始聚類中心，這4個初始聚類中心分別為：S1(姓名：**，年齡：12，性別：男，身份證號：**，疾?。汗钦?，S2(姓名：**，年齡：35，性別：女，身份證號：**，疾?。貉趽p)，S3(姓名：**，年齡：58，性別：男，身份證號：**，疾?。簭娭毙约怪?，S4(姓名：**，年齡：74，性別：女，身份證號：**，疾病：骨質疏松).經(jīng)過多次迭代，得到4個聚類和每個聚類中的記錄.

兩種算法的結果比較如表1所示.

表1 兩種算法結果比較

由表1可以看出，兩種算法的迭代次數(shù)都比較多，但是改進后的K-Means聚類算法明顯提高了聚類的準確率.

(3) 對于聚類得到的4個類別，分析類別特征利用上述的文檔頻度的方法得出每個類別的Top 3治療方案：類別1(Top 1：手術，Top 2：儀器固定，Top 3：長期青霉素注射)，類別2(Top 1：手術，Top 2：射頻靶點熱凝術，Top 3：牽引)，類別3(Top 1：人工關節(jié)置換，Top 2：打石膏，Top 3：中醫(yī)刺穴療法)，類別4(Top 1：運動療法，Top 2：中醫(yī)刺穴療法，Top 3：手術).

(4) 通過之前的聚類和得到的聚類結果，對于新加入數(shù)據(jù)庫的診療記錄，可以利用式(1)計算該新診療記錄屬于哪一個聚類，并賦予其相應聚類的共同特征.

(5) 最后，進行診療記錄補全方法的實現(xiàn).找出所有診療記錄中的同名病人，發(fā)現(xiàn)有17組同名病人，如圖4所示.

圖4 同名病人分組結果Fig.4 Grouping result of patients with the same name

在這17組同名病人中，有16組均是兩條相同姓名的記錄，有1組是3條相同姓名的記錄，將這17組中的姓名進行標號，姓名從A到Q依次排列，共有17組相同姓名的記錄，其中A與A是相同的姓名，B與B是相同的姓名，依此類推.同時，發(fā)現(xiàn)這17組記錄中，并不是所有的記錄均提供身份證號信息，因身份證號信息缺省，無法直接利用身份證號信息識別相同的病人，所以利用上述提出的診療信息補全方法進行識別相同病人并補全診療信息.找出這17組記錄所屬的聚類，發(fā)現(xiàn)記錄A、F、O均屬于聚類1，記錄C、H、J、M、P、Q均屬于聚類2，記錄D、E、G、I、L均屬于聚類3，記錄K、N均屬于聚類4.同屬于一個聚類，并且姓名相同，可以認為這是同一個人，所以聚類1中的A、F、O分別對應的是同一個人，即兩條姓名為A的記錄為同一個人的記錄，兩條姓名為F的記錄為同一個人的記錄，兩條姓名為O的記錄為同一個人的記錄，其余3個聚類中的記錄同理可得.但是還有一個相同姓名的兩條記錄，即為姓名B，其中一條記錄在聚類3中，一條記錄在聚類4中，不在同一個聚類中，這樣可以認為這兩條記錄對應的不是同一個人，并且通過驗證姓名B的兩條診療記錄的其他信息發(fā)現(xiàn)，這兩條診療記錄對應的確實不是同一個人，說明本文的識別方法是有效的.接著利用關聯(lián)表將對應的同一個人的記錄進行融合，即實現(xiàn)相同病人診療記錄的補全.

針對查準率和查全率兩項評價指標，分別用本文方法、代碼集遷移[8]以及PRAWN[9]方法進行試驗，比較結果如表2所示.

表2 試驗結果對比

由表2可以看出，本文提出的方法在查全率和查準率指標上都要高于另外兩種方法，說明本文方法比較好.

3.2 對比與討論

有不少學者針對識別和集成不同數(shù)據(jù)源的數(shù)據(jù)做了很多努力. 文獻[8]提出了一個代碼集遷移的方法來融合某一個患者的所有歷史診療記錄.文獻[9]提出了一個叫PRAWN的方法可以集成不同時間維度的數(shù)據(jù)，可以解決數(shù)據(jù)之間的沖突問題. 本文方法與上述兩種方法之間的比較如表3所示.

表3 幾種方法的比較

由表3可以發(fā)現(xiàn)，本文方法具有高可用性、較高查準率與查全率等優(yōu)點.

4 結 語

本文針對相同病人在不同的診療機構會形成多條診療記錄，這些同一個病人的診療記錄難以融合而導致病人的個人健康檔案信息不完全的問題，在部分診療數(shù)據(jù)缺省的情況下提出了個人健康檔案補全方法，利用數(shù)值聚類、特征分析和診療記錄補全等方法，實現(xiàn)了對相同病人不同診療記錄的識別與融合，繼而實現(xiàn)了病人個人健康檔案的補全.

下一步的研究將考慮如何在復雜數(shù)據(jù)環(huán)境下增強算法的容錯性，重點研究數(shù)據(jù)缺失或數(shù)據(jù)有誤的情況下，如何進行相同病人識別和診療記錄補全問題.

[1] 李嬌，劉全，傅啟明，等.分布式數(shù)據(jù)庫中基于局部CON模型的記錄匹配方法[J].通信學報, 2011, 32(7): 196-202.

[2] 沈忱，曾衛(wèi)明，吳愛華.融合修復代價的不一致關系數(shù)據(jù)中相似重復記錄識別[J].現(xiàn)代計算機(普及版), 2015(6): 3-9.

[3] LEE J S， OLAFSSON S. Data clustering by minimizing disconnectivity[J]. Information Science, 2011, 181(4): 732-746.

[4] IENCO D，PENSA R G，MEO R. From context to distance: Learning dissimilarity for categorical data clustering[J]. ACM Transactions on Knowledge Discovery from Data, 2012, 6(1): 1-25.

[5] RONG S， NIU X, XIANG E W, et al. A machine learning app-roach for instance matching based on similarity metrics[C] //The Semantic Web-ISWC 2012. 2012: 460-475

[6] NOWAK T, NAJGEBAUER P, RYGAL J，et al. A novel graph-based descriptor for object matching[C] //Artificial Intelligence and Soft Computing. 2013: 602-612.

[7] 龔靜，曾建一.文本聚類中的特征選擇方法[J].吉首大學學報(自然科學版), 2008, 29(2): 39-41.

[8] MCGLOTHLIN J P，KHAN L. Managing evolving code sets and integration of multiple data sources in health care analytics[C] // Proceedings of the 2013 International Workshop on Data Management and Analytics for Healthcare. 2013: 9-14.

[9] ALEXE B, ROTH M, TAN W C. Preference-aware integration of temporal data[C] //Proceedings of the VLDB Endowment. 2014: 365-376.

Research and Implementation of Personal Health Records Completion Method Based on Clustering

JIJin-xin,JIANGLi-hong,CAIHong-ming

(School of Software, Shanghai Jiao Tong University, Shanghai 200240, China)

Medical records are useful to both patients and doctors. However, the same patient may go to hospital for treatment at different times with different identification information and the patient’s medical information will be distributed in different records. So doctors can not determine whether the medical records are from the same patient. In order to solve this problem, a novel personal health records completion method is proposed. Numerical clustering, feature analyzing, instance matching and medical records fusion methods are used to identify different records of the same patient and realize the completion of personal health records. Finally, an experiment is taken in the database of a specific hospital to verify the usability of the proposed method.

medical records; personal health records completion; numerical clustering; feature analyz-ing; instance matching; records fusion

2015-11-27

國家自然科學基金資助項目(71171132,61373030)；上海市自然科學基金資助項目(13ZR1419800)

季金鑫(1991—)，男，江蘇啟東人，碩士研究生，研究方向為數(shù)據(jù)分析. E-mail: jijinxin@sjtu.edu.cn 蔡鴻明(聯(lián)系人)，男，副教授，E-mail: hmcai@sjtu.edu.cn

TP 391

A