日本データベース学会データドリブンスタディーズ
一般論文

Vol. 1, Article No. 5, 2023年 3月

だ半順序集合の束となるため，普通のシーケンスで表現不可になシーケンスバリアントの比較とり，比較するためにはLCSの概念を拡張する必要がある．

電子カルテの分析への応用
李玉清1

Le Hieu Hanh2

山崎友義4

荒木賢二5

そのような分岐を含む医療指示シーケンスの比較が求められる背景としては，国として医療情報の二次利用の必要性が認識され，電子カルテなどの医療・健康に関する記録を全国規模で一元

松尾亮輔3

的に集める「千年カルテプロジェクト」 [18]等が始動しているこ

横田治夫6とが挙げられる．「千年カルテプロジェクト」に参加する医療機
関のデータがまとめに保存・管理されているため，複数の医療機関を跨いだ比較を行う研究が期待されている．医療記録のより効

シーケンスバリアント(SV)はシーケンス中に分岐を含む半順序

率的な利用の一環として医療機関が異なることによる複数クリニ集合の束で，シーケンス中の変化を扱うようなアプリケーション

カルパスのの比較によって治療パターンの多様性を知ることに非ではSV間の比較は重要な課題である．比較の際に，共通なサブ常に有用であり，医療の質と効率の向上が期待される．

シーケンスと共通でない差異となるサブシーケンスを検出するこ

本論文では半順序集合の束をシーケンスバリアント（Sequenceとが必要である．本論文では，SV間の比較に必要な定義を行い，

Variant, 以下SV）と定義し，複数SVの共通・差異部分を導出す

比較アルゴリズムを提案する．まず，最長共通サブシーケンス

るアルゴリズムを提案する． SVを有効グラフと考えた場合に，に基づき最長共通サブシーケンスバリアント（LCSV）と，複数

グラフ編集距離 [5]に基づいたグラフ比較手法を適用することで，のSVの共通・差異部分を示す併合シーケンスバリアント（MSV）

複数SV間の違いの定量化が可能ではあるが，共通・差異の部分を新たに定義する．次に， LSCVとMSVを生成するためのアルゴ

まで示すことができない．そこで，複数SVの比較のために，本リズムを示す．提案したアルゴリズムの効果を検証するために，論文ではLCSの概念を拡張した最長共通サブシーケンスバリア

実際の複数医療機関の電子カルテの医療シーケンスに適用し，医ント（Longest Common Subsequence Variant, 以下LCSV）と併

療機関間の医療指示シーケンスパターンの比較を実施する．比較合シーケンスバリアント（Merged Sequence Variant, 以下MSV）

結果は医療関係者に有益な情報であると評価された．

1を定義し，それらを生成するアルゴリズムを提案する．具体的に，シーケンスデータベースからシーケンスパターンマイニン

序論

グ（Sequence Pattern Mining, 以下SPM）を適用し，出現頻度のシーケンスは順序性を持つ要素の集合やリストとして多くの場

高い頻出シーケンスを抽出し，頻出シーケンス間の共通部分を面で出現する．例えば，書籍の購入履歴や人間の日中に行動した

まとめることで， SVを生成する [9]． 次に，２SVを入力とし，イベントの履歴などはシーケンスとして表現され，複数シーケン

LCSの生成方法に基づいてLCSVを抽出する．最後に， LCSVとスを比較することで，次商品の購入や次行動に合わせた推薦に利元々のSVと比較しながら，共通部分と差異部分を表すMSVを作用される．複数シーケンスの比較のために，シーケンス間の最長っていく．
本研究の有効性を検証するために，2医療機関の電子カルテの共通部分列（Longest Common Sequence, 以下LCS）を求めて活データを用い，同一疾病に対するクリニカルパスを抽出し，それ用する手法が多く提案されてきた [20]．
しかし，LCSはシーケンス中の分岐を扱うアプリケーションにらのパスの共通・差異部分を示すLCSVとMSVを生成する．最後

対応できていない．シーケンス中に分岐を含む半順序集合の束のに生成された実験結果に関する医療関係者の解析と評価を得る．

場合には，単純な一列のシーケンスとして表現しただけでは不十分である． 1つ例としては，検査オーダー，処方，手術などの医本 論 文 は 以 下 の 通 り 構 成 さ れ る． 2節 で は 本 研 究 に 関 連 す

療指示が含まれている電子カルテの解析で抽出される典型的な医る 概 念 を 背 景 知 識 と し て 説 明 す る． 3節 で は 提 案 概 念 で あ療指示の流れ「クリニカルパス」が挙げられる．このようなクリ

るLCSVとMSVを求めるアルゴリズムについて述べる． 4節でニカルパスに対して，患者の状態等で医療従事者が医療指示を変は，3節の手法を用いて実際の医療指示データを解析することと更する医療オプションをシーケンス中に含む場合がある [9, 12]．

治療パターンのMSVの作成を行う． 5節では，提案手法に関する

すなわち，クリニカルパスは医療指示シーケンス中に分岐を含ん考察結果を報告する．最後に6節でまとめと今後の課題について述べる．

1 学生会員2

東京工業大学情報理工学院

li@de.cs.titech.ac.jp
2 正会員

本節では，本研究に関連するシーケンシャルバリアント（SV）

東京工業大学情報理工学院

hanhlh@de.cs.titech.ac.jp
3 非会員とシーケンシャルパターンマイニング（SPM）について説明す

一般社団法人ライフデータイニシアティブ

る．

matsuo@ldi.or.jp
4 非会員

東京工業大学情報理工学院

2.1 背景知識

yamazaki.cp@gmail.com
5 非会員

2.1.1 シーケンス

宮崎大学医学部附属病院医療情報部

定義 1（アイテムセット） アイテムセット 𝐼 を以下のように定taichan@med.miyazaki-u.ac.jp
6 正会員

背景知識と関連研究

東京工業大学情報理工学院

yokota@cs.titech.ac.jp

1

日本データベース学会データドリブンスタディーズ
一般論文

Vol. 1, Article No. 5, 2023年 3月

義する．

𝐼 = {𝑖 1 , 𝑖2 , . . . , 𝑖 𝑛 }𝑖 𝑗 ∈ 𝐼 がアイテムとなる．
アイテムを解釈するとき，𝑖 をアイテム𝑖 の「name」とも呼ぶ．
定義 2（シーケンス） アイテムセット 𝐼 に対し，シーケンス𝑆 を
図1

以下のように定義する．

𝑆 = ({𝑠1 , 𝑠2 , . . . , 𝑠 𝑚 }, ≺𝑆 )

2.1.3

LCS

定義 5（共通部分列(CS)） シーケンス𝑆 𝛼 と𝑆 𝛽 に対し，共通部

𝑠 𝑗 = (𝑖𝑑, 𝑖), 𝑖 ∈ 𝐼． 𝑖𝑑 は𝑆 の中でユニークなインデックスとなる．

分 列𝐶𝑆 を 下 記 の 条 件 を 満 た す シ ー ケ ン ス と 定 義 す る．

≺𝑆 は𝑆 上の全順序関係である．∀𝑠𝑖 , 𝑠 𝑗 ∈ 𝑆, 𝑠𝑖 ≺𝑆 𝑠 𝑗 ∨ 𝑠𝑖 ≺𝑆 𝑠 𝑗 ．
2.1.2

𝑆𝑉 のシーケンスバリアントグラフ∀𝑐𝑠𝑖 , 𝑐𝑠 𝑗 ∈ 𝐶𝑆, 𝑐𝑠𝑖 , 𝑐𝑠 𝑗 ∈ 𝑆 𝛼 ∩ 𝑆 𝛽 かつ𝑐𝑠𝑖 ≺𝐶𝑆 𝑐𝑠 𝑗 ⇐⇒ 𝑐𝑠𝑖 ≺ 𝛼SV𝑐𝑠 𝑗 ∧ 𝑐𝑠𝑖 ≺𝛽 𝑐𝑠 𝑗 ．

定義 3（シーケンスバリアント） ア イ テ ム セ ッ ト 𝐼 に 対 し，CSの部分列もCSとなるので，CSは複数存在する．そのため，最束𝑆𝑉 をシーケンスバリアントと定義し，以下のように表す．

長共通部分列を定義する．

𝑆𝑉 = ({𝑠𝑣 1 , 𝑠𝑣 2 , . . . , 𝑠𝑣 𝑙 }, ≺𝑆𝑉 )定義 6（最長共通部分列(LCS)） シーケンス𝑆 𝛼 と𝑆 𝛽 に対し，最𝑠𝑣 𝑗 = (𝑖𝑑, 𝑖), 𝑖 ∈ 𝐼． 𝑖𝑑 は𝑆𝑉 の中でユニークなインデックスとな

長共通部分列 𝐿𝐶𝑆 を下記の条件を満たす共通部分列と定義する．

る． ≺𝑆𝑉 は𝑆𝑉 上の半順序関係である．また， 𝑆𝑉 が上限および下𝑆 𝛼 と𝑆 𝛽 に対する任意の共通部分列𝐶𝑆 に対し， |𝐶𝑆| ≤ |𝐿𝐶𝑆|．

限を持っている．

|𝐶𝑆| は𝐶𝑆 のノード数を表す．

例として，医療指示列において分岐が発生した場合，シーケン

例として，シーケンス< 𝐴, 𝐵, 𝐶, 𝐷 >と< 𝐴, 𝐶, 𝐵, 𝐴, 𝐷 >を考え

スバリアントになる．シーケンス（入院→検体検査→手術→注る．長さ２の共通部分列が５つ存在する： < 𝐴, 𝐵 >, < 𝐴, 𝐶 >, <射→退院）と（入院→看護タスク→手術→処方→退院）に対し𝐴, 𝐷 >, < 𝐵, 𝐷 >, < 𝐶, 𝐷 >．長さ３の共通部分列が２つ存在すて，注射と処方がバリアントと呼ばれ，この二つのシーケンスをる： < 𝐴, 𝐵, 𝐷 >, < 𝐴, 𝐶, 𝐷 >．それ以上長い共通部分列が存在

まとめてシーケンスバリアントと考える． SVのバリアントに対しない．従って，最長共通部分列が< 𝐴, 𝐵, 𝐷 >と< 𝐴, 𝐶, 𝐷 >でする安全性と効率性を定量的に比較できるため， SVを抽出するある．

ことは非常に有用である．また，バリアントが現れる要因を調査

入力列の個数が任意である一般の場合については，この問題することで，特定の患者に対する治療のような医療指示の改善支はNP困難である [13]．入力列の個数が一定のときには，この問援が可能となる．

題は動的計画法によって多項式時間で解く事ができる．

以下， 𝐴, 𝐵, 𝐶 のような大文字をアイテムとして説明する場合，𝐴, 𝐵, 𝐶 はid付きアイテムの「name」を指す．また， 𝐴 ≺ 𝐵, 𝐵 ≺

2.2

関連研究

2.2.1

SPM

Agrawalらによって提案されたSPMはシーケンシャルデータベ

𝐶, 𝐵 ≺ 𝐷, 𝐶 ≺ 𝐸, 𝐷 ≺ 𝐸 を， < 𝐴, 𝐵, (𝐶, 𝐷), 𝐸 >と表す．

ース(以下，SDB)から頻出シーケンスを抽出する手法であり [2]，SVを可視化する方法として，シーケンスバリアントグラフを

医療・Eコマース・インターネットなどの領域で注目されてい定義する．
定義 4（シーケンスバリアントグラフ）

る [4]．アイテムの順列をシーケンスと呼び，SDBはあるシーケ

シーケンスバリアン

ンス集合に属するシーケンスと，シーケンスの識別子であるシー

ト𝑆𝑉 に対し，有向非巡回グラフ𝐺 をシーケンスバリアントグ

ケンスIDを組みとする要素からなる． SDBから出現頻度が設定

ラフと定義し，以下のように表す．

された最小支持度（minsup）より大きいシーケンスを抽出することとなる．

𝐺 = (𝑉, 𝐸)
頂 点 集 合𝑉 が𝑆𝑉 の ア イ テ ム 集 合 と な る． ま た， ∀𝑒

アプリオリに基づいたアルゴリズム [2]はよく知られているが，抽出するとき，冗長なパターンを大量に生成するところと大規模=

データセットの場合，データセットをスキャンする時間が大量に(𝑠𝑣 𝑜𝑢𝑡 , 𝑠𝑣 𝑖𝑛 ) ∈ 𝐸, 𝑠𝑣 𝑜𝑢𝑡 ≺𝑆𝑉 𝑠𝑣 𝑖𝑛．

要求されるところが問題点であった．データセットのスキャンを

シ ー ケ ン ス バ リ ア ン ト グ ラ フ を 可 視 化 す る こ と で， 簡 単減らすために，PrefixSpan [14]が提案されている． PrefixSpanは，に シ ー ケ ン ス バ リ ア ン ト を 示 す こ と が で き る． 例 と し て，

末端アイテムを除いた頻出パターンであるprefixへの射影を繰り𝐴, 𝐵, 𝐶, 𝐷, 𝐸 がアイテムで， 𝑆𝑉 =< 𝐴, 𝐵, (𝐶, 𝐷), 𝐸 >のシーケ返すことで，探索対象のデータセットを徐々に縮小するため，効

ンスバリアントグラフが図1に示す．

率的な探索ができる．さらに効率的に抽出を行うために，飽和オシーケンスバリアントとシーケンスバリアントグラフは互いにーダー列を抽出するCSpan [15]等も提案されている．

変換可能であるため，以下両者を同じものと扱う．

2

日本データベース学会データドリブンスタディーズ
一般論文

2.2.2

Vol. 1, Article No. 5, 2023年 3月

SPMによる医療情報の解析

Input: 𝑆𝑉1 , 𝑆𝑉2

佐々木ら [16]は，実際の電子カルテデータに、タイムインター

Output: 𝐿𝐶𝑆𝑉バルSPM [3]（以下 TI-SPM）を適用して，時間間隔を考慮した

1

number 𝑆𝑉1 from 1 to 𝑠;

頻出シーケンシャルパターンの抽出を行った． Leら [10]は，効

2number 𝑆𝑉2 from 𝑠 + 1 to 𝑡;

率的なSPMであるCSpan [15]を拡張して，タイムインターバル

3 𝑟 1 ← the number of routes of 𝑆𝑉1 ;の統計情報を収集するT-CSpanを提案し，実電子カルテに適用し4 𝑟 2 ← the number of routes of 𝑆𝑉2 ;た．山田ら [6]は，頻出シーケンスがどのシーケンスと対応関係

5にあるのかという情報を，シーケンスの識別子であるシーケン

6

スIDを保持しながらマイニングすることによって，頻出シーケ

for 𝑖 = 1, 2, . . . , 𝑟 1 dofor 𝑗 = 1, 2, . . . , 𝑟 2 do
𝐿𝐶𝑆(𝑖, 𝑗) ← the LCS of route 𝑖 of 𝑆𝑉1 and route 𝑗 of

7

ンス抽出と同時に取得し，頻出シーケンスごとの安全性や効率性

𝑆𝑉2 ;の指標を算出し， SV評価が円滑かつ正確に行える可視化手法を提案し，実電子カルテを用いて推薦結果の評価を行った．坂本ら [8]は，分岐先頻度と実施時刻情報を用いたグループ化による

8

end

9

𝐿𝐶𝑆(𝑖) ← the longest one in

適正分岐候補選択を行い，頻出シーケンス分岐先の適正候補選択

𝐿𝐶𝑆(𝑖, 1), 𝐿𝐶𝑆(𝑖, 2), . . . , 𝐿𝐶𝑆(𝑖, 𝑟 2 )による併合シーケンスの生成を行った．また，分岐要因である患;者情報を拡充し，併合シーケンスの分岐への要因適用による医療

end

指示推薦を提案した． Leら [11]は，電子カルテ解析におけるプ

10

ライバシー保護に関して差分プライバシーの概念を適用する手法

11

𝐿𝐶𝑆𝑉 ← combination of 𝐿𝐶𝑆(1), 𝐿𝐶𝑆(2), . . . , 𝐿𝐶𝑆(𝑟 1 );を提案している．

12

re-number nodes in 𝐿𝐶𝑆𝑉 from 𝑡 + 1, also re-number them

2.2.3

in 𝑆𝑉1 and 𝑆𝑉2 ;Algorithm 1: LCSVを導出するアルゴリズム

SVの解析

本田ら [9]は，実電子カルテの医療指示のSVを抽出し，グラフで表現して医療従事者への視認性の高い可視化ツールの提供を行った．さらに本田ら [7]は，SVに関する医療関係者の解析と評価

CSVのサブシーケンスバリアントもCSVとなるので， CSVは複を得るに対して，患者の性別や年齢といった静的情報と，血圧や数存在する．そのため，最長共通サブシーケンスバリアントを定検査結果といった動的情報に対する多変量解析を行うことでバリ義する．

アントの要因分析を行う手法を提案し，実電子カルテを用いて効
定義 8（最長共通サブシーケンスバリアント(LCSV)）果を示した．

ス𝑆𝑉 𝛼 と𝑆𝑉𝛽 に 対 し， 最 長 共 通 サ ブ シ ー ケ ン ス バ リ ア ン

提案手法

3

ト 𝐿𝐶𝑆𝑉 を下記の条件を満たす共通サブシーケンスバリアントと定義する． 𝑆𝑉 𝛼 と𝑆𝑉𝛽 に対する任意の共通サブシーケンスバリ

本節では， LCSVとMSVの定義とそれらを算出するアルゴリ

アント𝐶𝑆𝑉 に対し， |𝐶𝑆𝑉 | ≤ |𝐿𝐶𝑆𝑉 |． |𝐶𝑆𝑉 | は𝐶𝑆𝑉 のノード数

ズムについて述べる． また， MSVの算出によるSV比較方法をを表す．

提案する． 前提として [6]で用いられたシーケンスIDを保持す
るSPMを行い，頻出シーケンスを抽出し， SVを生成しているも

LCSVを導出するアルゴリズムと具体的な例を説明する．

のとする．

図2が示しているように， 𝑆𝑉1 にパスが2つあり， 𝑆𝑉2 にパスが

本節からアイテムをノードとも呼ぶ． ノードには四つの属４つある． LCSVはアルゴリズム 12により算出され，中のノード性があり，それぞれ𝑛𝑎𝑚𝑒，ノードの名称を指す； 𝑛𝑒𝑥𝑡 𝐿𝑖𝑠𝑡 ，ノがリナンバーされた．

ードの次に来るノードのリストを指す；𝑖𝑑 ，ノードの唯一の番

3.2 MSV号を指す； 𝑙𝑎𝑏𝑒𝑙 ，ノードの属しているSVを指す．具体的には，複数のSVを比較するために，MSVを導入する．

𝑠𝑣.nextList = {𝑠𝑣 0 ∈ 𝑆𝑉 |(𝑠𝑣, 𝑠𝑣 0) ∈ 𝐸 }．
3.1

シーケン

定義 9（併合シーケンスバリアント(MSV)） シーケンスバリア

LCSV

ン ト𝑆𝑉 𝛼 , 𝑆𝑉𝛽 と そ の 𝐿𝐶𝑆𝑉 に 対 し， 併 合 シ ー ケ ン ス バ リ ア ン

SV間の差異を示すために，まずSV間の共通部分を抽出する．

ト 𝑀𝑆𝑉 を下記の条件を満たすシーケンスバリアントと定義する．

従来のLCSでは，SVに適用できないため，CSとLCS を拡張した∀𝑠𝑣 𝑖 , 𝑠𝑣 𝑗 ∈ 𝑆𝑉 𝛼 ∪ 𝑆𝑉𝛽 , 𝑠𝑣 𝑖 , 𝑠𝑣 𝑗 ∈ 𝑀𝑆𝑉 かつ𝑠𝑣 𝑖 ≺ 𝑀 𝑆𝑉 𝑠𝑣 𝑗 ⇐⇒概念とした共通サブシーケンスバリアント(CSV)と最長共通サブ

𝑠𝑣 𝑖 ≺ 𝛼 𝑠𝑣 𝑗 ∧ 𝑠𝑣 𝑖 ≺𝛽 𝑠𝑣 𝑗 ． ∀𝑚𝑠𝑣 𝑖 , 𝑚𝑠𝑣 𝑗 ∈ 𝑀𝑆𝑉, 𝑚𝑠𝑣 𝑖 ≺ 𝑀 𝑆𝑉

シーケンスバリアント(LCSV)を提案する．

𝑚𝑠𝑣 𝑗 =⇒ (𝑚𝑠𝑣 𝑖 , 𝑚𝑠𝑣 𝑗 ∈ 𝑆𝑉 𝛼 ∧ 𝑚𝑠𝑣 𝑖 ≺ 𝛼 𝑚𝑠𝑣 𝑗 ) ∨ (𝑚𝑠𝑣 𝑖 , 𝑚𝑠𝑣 𝑗 ∈定義 7（共通サブシーケンスバリアント(CSV)） シ ー ケ ン ス バ

𝑆𝑉𝛽 ∧ 𝑚𝑠𝑣 𝑖 ≺𝛽 𝑚𝑠𝑣 𝑗 )． また， 𝐿𝐶𝑆𝑉 に出現したノードにlabel

リ ア ン ト𝑆𝑉 𝛼 と𝑆𝑉𝛽 に 対 し， 共 通 サ ブ シ ー ケ ン ス バ リ ア ン{𝛼, 𝛽}を与え，出現していないノードに属しているSVにより，ト𝐶𝑆𝑉 を下記の条件を満たすシーケンスバリアントと定義すlabel 𝛼か 𝛽を与える．

る． ∀𝑐𝑠𝑣 𝑖 , 𝑐𝑠𝑣 𝑗 ∈ 𝐶𝑆𝑉, 𝑐𝑠𝑣 𝑖 , 𝑐𝑠𝑣 𝑗 ∈ 𝑆𝑉 𝛼 ∩ 𝑆𝑉𝛽 かつ𝑐𝑠𝑣 𝑖 ≺𝐶𝑆𝑉

SV間のMSVを導出するためのアルゴリズムを以下に述べる．

𝑐𝑠𝑣 𝑗 ⇐⇒ 𝑐𝑠𝑣 𝑖 ≺ 𝛼 𝑐𝑠𝑣 𝑗 ∧ 𝑐𝑠𝑣 𝑖 ≺𝛽 𝑐𝑠𝑣 𝑗 ．

3日本データベース学会データドリブンスタディーズ
一般論文

Vol. 1, Article No. 5, 2023年 3月

Input: 𝑆𝑉1 , 𝑆𝑉2 , 𝐿𝐶𝑆𝑉
Output: a mapping 𝑚𝑎 𝑝

図2

𝑆𝑉1 と𝑆𝑉2 のLCSVを計算する

1

𝑚𝑎 𝑝 1 ← ∅;2

𝑚𝑎 𝑝 2 ← ∅;3𝑙𝑖𝑠𝑡 ← 𝑛𝑜𝑑𝑒(𝐿𝐶𝑆𝑉);

4𝑛 ← the maximum number of nodes in 𝐿𝐶𝑆𝑉;

5

while 𝑙𝑖𝑠𝑡 ≠ ∅ do

6

𝐶𝑁 𝑐 ← the node with smallest number in 𝑙𝑖𝑠𝑡;

7

𝐶𝑁1 ← the node in 𝑆𝑉1 with the same number as 𝐶𝑁 𝑐 ;8

𝐶𝑁2 ← the node in 𝑆𝑉2 with the same number as 𝐶𝑁 𝑐 ;9

𝑛𝑒𝑤𝐶𝑁 𝑐 ← 𝐶𝑁 𝑐 ;10

𝑛𝑒𝑤𝐶𝑁 𝑐 .next ← 𝐶𝑁1 .next ∪ 𝐶𝑁2 .next;11

put {𝑛𝑒𝑤𝐶𝑁 𝑐 .id : 𝑛𝑒𝑤𝐶𝑁 𝑐 } into 𝑚𝑎 𝑝 1 and 𝑚𝑎 𝑝 2 ;12𝑛𝑒𝑥𝑡 𝐿𝑖𝑠𝑡 ← 𝐶𝑁 𝑐 .next;13

𝑚𝑎 𝑝 1 ← 𝑆𝑒𝑎𝑟𝑐ℎ𝑁𝑒𝑥𝑡 (𝐶𝑁1 , 𝑛𝑒𝑥𝑡 𝐿𝑖𝑠𝑡, 𝐶𝑁 𝑐 , 𝑛, 𝑚𝑎 𝑝 1 );14

𝑛𝑒𝑥𝑡 𝐿𝑖𝑠𝑡 ← 𝐶𝑁 𝑐 .next;

15

𝑚𝑎 𝑝 2 ← 𝑆𝑒𝑎𝑟𝑐ℎ𝑁𝑒𝑥𝑡 (𝐶𝑁2 , 𝑛𝑒𝑥𝑡 𝐿𝑖𝑠𝑡, 𝐶𝑁 𝑐 , 𝑛, 𝑚𝑎 𝑝 2 );16

𝑙𝑖𝑠𝑡.remove(𝐶𝑁 𝑐 );

17

end

18

combine 𝑚𝑎 𝑝 1 and 𝑚𝑎 𝑝 2 as 𝑚𝑎 𝑝;
Algorithm 3: NodeMappingGeneration 関数

Input: 𝑆𝑉1 , 𝑆𝑉2
Output: 𝑀𝑆𝑉
1

𝐿𝐶𝑆𝑉 ← 𝐿𝐶𝑆𝑉 (𝑆𝑉1 , 𝑆𝑉2 );2

𝑚𝑎 𝑝 ← 𝑁𝑜𝑑𝑒𝑀𝑎 𝑝 𝑝𝑖𝑛𝑔𝐺𝑒𝑛𝑒𝑟𝑎𝑡𝑖𝑜𝑛(𝑆𝑉1 , 𝑆𝑉2 , 𝐿𝐶𝑆𝑉);

3

restore the MSV from 𝑚𝑎 𝑝 (𝑚𝑎 𝑝 contains label and orderinformation);
Algorithm 2: MSVを導出するアルゴリズム
𝑚𝑎 𝑝 はkey-value型 の デ ー タ 構 造 で， keyが ノ ー ド のidで，valueがノードとなる．最後のステップで， 𝑚𝑎 𝑝 1 と𝑚𝑎 𝑝 2 を併合するとき，同時に両者に存在するノードのnextListを併合してから𝑚𝑎 𝑝 の中に入れる．他のノードはそのまま入れる．
図2の例に対してMSVを求めるアルゴリズムを適用したものを図3に示す．図では，ノードのlabelを表すために色を用い，𝑆𝑉1 を
青で， 𝑆𝑉2 を赤で，共通部分である 𝐿𝐶𝑆𝑉 を黄で示している．

図3

MSVの作成において，同じ名前を持つノードがSV中に複数出

𝑆𝑉1 と𝑆𝑉2 のMSV現する場合，それを区別するためにノードに対するidの番号によって区別する．

を持つノードを入れることが可能になった．

さらに，それぞれのSVにおいて，共通の名前のノード間の順

実験

4

序関係が変わる場合には，元のシーケンスの順序を保つため，

MSV中に新たなノードを作成する．例として，図2のノードCと

本節では，医療機関Aと医療機関Bから提供された実際の電子

ノードFの順序関係が２パターンある．このため，図3のMSVにカルテデータに対して提案手法を適用し，有効性を確認する．

は，ラベル1+2のノードCとラベル2のノードCが同時に出現した．

4.1

この点を正確に示すことは非常に重要である．

実験方法と環境

有 効 なLCSVとMSVを 得 る た め に は， そ れ ぞ れ の 最 小 支 持

このため，アルゴリズム20でサーチをするとき，一度出現し度(minsup)をどのように設定するかが問題で，そのためにまずた 𝐿𝐶𝑆𝑉 に属しているノードがまた見つかると，新しいノードをはminsupを変化させたSV同士のLCSVとMSVを求めてみること作り，新しいidを与える．この操作により，mapに異なるラベルから始める．「調剤料計算」，「食事療養」など治療行為とは関4

日本データベース学会データドリブンスタディーズ
一般論文

Vol. 1, Article No. 5, 2023年 3月

Input: 𝐶𝑁, 𝑛𝑒𝑥𝑡 𝐿𝑖𝑠𝑡, 𝐶𝑁 𝑐 , 𝑛, 𝑚𝑎 𝑝

表2 実験に関する情報

Output: 𝑚𝑎 𝑝
1

if 𝑛𝑒𝑥𝑡 𝐿𝑖𝑠𝑡 = ∅ or 𝐶𝑁.next=∅ thenreturn

2
3

end

4

for 𝑛𝑜𝑑𝑒 in 𝐶𝑁.next do

5

if 𝑚𝑎 𝑝.keySet().contains(𝑛𝑜𝑑𝑒.id) and6

𝐶𝑁 𝑐 .next.contains(𝑛𝑜𝑑𝑒) then7

𝑛𝑒𝑤𝑁𝑜𝑑𝑒 ← 𝑛𝑜𝑑𝑒;8

𝑛𝑒𝑤𝑁𝑜𝑑𝑒.id ← 𝑛 + 1;

9𝑛 + +;

10put {𝑛𝑒𝑤𝑁𝑜𝑑𝑒.id : 𝑛𝑒𝑤𝑁𝑜𝑑𝑒} into 𝑚𝑎 𝑝;

13

end

14

if 𝑛𝑜𝑑𝑒 ∈ 𝑛𝑒𝑥𝑡 𝐿𝑖𝑠𝑡 then16

𝑛𝑒𝑥𝑡 𝐿𝑖𝑠𝑡.remove(𝑛𝑜𝑑𝑒);20

1, 100

平均医療指示数

85.61

69.51

最長在院日数48

50

平均在院日数

11.52

6.87

を基に解析を予定していたが，複数病院の比較をするために，臨床研究情報基盤の電子カルテデータを使うことにした．臨床研究
情報基盤の電子カルテデータに処置の日付情報はあるが，詳しい
時刻情報はない．千年カルテプロジェクトのデータにも同じく，

みに基づく実験を行う．
本実験ではカテールを用いた狭心症・筋梗塞の治療法である経else

皮的冠動脈インターベンション(Percutaneous Coronary Interven-

𝑆𝑒𝑎𝑟𝑐ℎ𝑁𝑒𝑥𝑡 (𝑛𝑜𝑑𝑒, 𝑛𝑒𝑥𝑡 𝐿𝑖𝑠𝑡, 𝐶𝑁 𝑐 , 𝑛, 𝑚𝑎 𝑝);tion, PCI)を受けた患者の入院期間中に行われた医療指示履歴を

end

19

4, 265816

たが，一日内の処置の順番は必ずしも正確ではない．今後日付の𝑚𝑎 𝑝.get(𝑛𝑜𝑑𝑒.id).label ← {1, 2};

18

438

最大医療指示数

時刻情報がない．データベースに入っている順番を使うことにし

15

17

延患者数

報が入っており，時刻を使っていた．本研究もそれに準じて時刻

put {𝑛𝑜𝑑𝑒.id : 𝑛𝑜𝑑𝑒} into 𝑚𝑎 𝑝;

12

医療機関B

先行研究で使っていた医療機関Aの電子カルテデータは時刻情

else

11

医療機関A

対象とする．両医療機関で共通しているため，PCIを選んだ．実験に関する情報を表2に示す．

end
Algorithm 4: SearchNext 関数

4.3
4.3.1

表1

CPU

実験環境

実験結果
シーケンスバリアントの抽出

両医療機関のデータセットが違うため，同じ処置でも用語が違

AMD Ryzen Threadripper 3960X 24-Core Processor

う場合がある．それを統一するために，レセプト電算コードを使

128 GBう．同じレセプト電算コードを持つ処置を同じ処置と見なす．処Ubuntu 18.04.1 LTS

置の名称とレセプト電算コードの対照を表3に示す．表には，処Java.verJava 11.0.11

置についての簡単な説明も加えた．特に，PCIは様々な種類があR.ver

R 3.6.3

るため，対応するレセプト電算コードも多いである．処置毎にMemoryOS

費用に関わる診療報酬点数（以下，点数と表記）が付いている．

PCIは対応する点数が多いため，平均値24, 802を使う．さらに詳係が薄い医療指示を除外し，各病院のデータベースにSPMを行しい情報を知りたい場合は， [17]で処置の名称あるいはレセプト

い，頻出シーケンスを求める．得られた頻出シーケンスをSVに

電算コードで区分番号（例えば，A000-00）を探して，区分番号

併 合 す る． 次 にLCSVの ア ル ゴ リ ズ ム を 適 用 し， 各 医 療 機 関を用いて [1]で処置の詳細内容が得られる．

のSVのLCSVを算出する．さらに， MSVを作成し，グラフとし前に説明した通り， minsupをいくつか試して，実際に医療機て可視化する．治療に直接関係する医療指示を最大限に含んでい関Aでは0.15と0.2，医療機関Bでは0.25と0.3を採用した．抽出さるため，この実験は最長の頻出シーケンスのみを考慮している．

れたシーケンスバリアントを図4，図5，図6と図7に示す．

実験の環境を表1に示す．

病院毎に総点数を算出する．医療機関Aのminsup=0.15の場合，

4.2 データセット

パスが4つある．それぞれのパスにおける点数の合計は25, 411，

本研究では宮崎大学医学部の臨床研究情報基盤に蓄積されてい25, 400， 25, 261と25, 250で，平均値は25, 330.5となる．医療機

る両医療機関で2015年4月から2020年3月までに記録された，実関Aのminsup=0.2の場合， パ スが2つ あ る． それぞれのパスの際に使用されているクリニカルパスを元に行った医療指示データ

合計の点数は25, 213と25, 099で，平均値は25, 156となる．医療を対象とする．この医療指示データは個人情報保護の観点より患機 関Bのminsup=0.25の 場 合， 総 点 数 は25, 524と な る． 医 療 機

者を一意に特定できるような情報を含まない．なお，本研究で医関Bのminsup=0.3の場合，総点数は25, 388となる． 今回の場合療機関Aならびに医療機関Bの電子カルテデータを，多施設共同は，シーケンスバリアント間および医療機関間の差は0.5%以下

研究として医療従事者支援に用いることは宮崎大学のHP [19]にで，比較的小さいである．

記載されており，宮崎大学の倫理審査委員会及び東京工業大学の医療機関BのSVにはパスが1つしかない． 患者数が多いため，人を対象とする研究倫理審査委員会の承認を得ている．

頻出パターンの抽出が困難であることが原因として考えられる．

5

日本データベース学会データドリブンスタディーズ
一般論文

Vol. 1, Article No. 5, 2023年 3月

図4 医療機関Aのminsup=0.15のSV

図5

医療機関Aのminsup=0.2のSV

図6

医療機関Bのminsup=0.25のSV

図7 医療機関Bのminsup=0.3のSV

表3 処置の詳細
ノードネームレセプト電算コード点数

医療機関A 1

医療機関B 2

簡単な説明

CBC

160008010

21

末梢血液一般

末梢血液一般血液形態・機能検査

HR and RR

160102510

150

呼吸心拍監視(3時間超 7日以内)-

呼吸心拍監視B-CK-MB

160114710

90

CK-MB

B-CK-MB

血液化学検査BUN

160019010

11

BUN

-

血液化学検査T-BIL

160017010

11

BIL/総

-

B-Cr

160019210

11-

B-クレアチニン

血液化学検査

B-CRP

160054710

16

C反応性蛋白(CRP)

B-CRP

血漿蛋白免疫学的検査

B-BNP

160162350

136

-

B-BNP

内分泌学的検査ECG12160068410

130

心電図(四肢単極・胸部誘導含む12誘導)

ECG12

心電図

150374910

36,000150375010

22,000150375110

19,300150260350

28,280150284310

24,720150359310

24,720150375210

34,380150375310

24,380150375410

21,680160107550

17,720150318310

19,640PCI

図9 医療機関A(0.2)と医療機関B(0.25&0.3)のLCSV

血液化学検査の上部に示す．
図から簡単に処置の情報が得られる．黄色の部分は両医療機関
で共通のサブシーケンスで，赤と青の部分から両医療機関それぞ

PCI

PCI

れがどのように医療指示を行うかも分かる．赤と青の部分を比較

経皮的冠動脈インターベンション

することで，両医療機関の治療パターンの違いを知ることができる．例として，「T-BIL(総ビリルビン)」は医療機関Aでは何回か出てくるが，医療機関Bでは出なかった．また，「ECG12(12誘導
心電図)」は医療機関Bでは毎日実施されるが，医療機関Aでは一回しか実施されなかった．
得られた情報に関して，医療関係者に確認したところ，この図8 医療機関A(0.15)と医療機関B(0.25&0.3)のLCSV

ような示し方は有益であるという評価であった．具体的な違い
4.3.2

に関しては，「ECG12」の違いは発生しうる違いであり，術後はLCSVの導出

患者モニターで3点誘導の心電図情報を絶えず取っているのが一

いくつかのminsupの組み合わせを試し，LCSVを導出する．結般的で，医療機関Aでは3点に加えて12点で取るのは1回で十分果は図8と9に示す．

と判断している可能性がある．一方，医療機関Bでは， 3点では処置の名称と相対的日付を全体として扱う．例えば，「B-CK-

不十分で毎日12点を取る必要があると判断している可能性があMB day0」と「B-CK-MB day1」は異なる医療指示である．

る．「T-BIL」の違いに関しては，オリジナルデータベースを確

実際に，医療機関Bのminsup=0.25とminsup=0.3のSVには細か認した結果，医療機関Bではたまに実施されるが，頻度が低いた

い違いしかないため，導出したLCSVは同じである．
4.3.3

め抽出されなかった．医療機関Aの場合に，パッケージとして含MSVの導出まれている可能性が考えられる．

各minsupの組み合わせのMSVは図10，図11，図12と図13に示す．差異部分の処置の点数を，それぞれのSVに対応するノード

6

日本データベース学会データドリブンスタディーズ
一般論文

Vol. 1, Article No. 5, 2023年 3月

ҫྏ‫ؖؽ‬$
ҫྏ‫ؖؽ‬%/&69

図10

医療機関A(0.15)と医療機関B(0.25)のMSV

ҫྏ‫ؖؽ‬$
ҫྏ‫ؖؽ‬%/&69

図11 医療機関A(0.15)と医療機関B(0.3)のMSV

ҫྏ‫ؖؽ‬$
ҫྏ‫ؖؽ‬%/&69

図12 医療機関A(0.2)と医療機関B(0.25)のMSV

5

考察

6

結論

6.1 まとめ

1つの医療機関のデータセットから頻出パターンを抽出する場
合， minsupは抽出された情報の数と頻出パターンの読みやすさ

本論文はシーケンス中に分岐を含む半順序集合の束であるシで決めることができる．また， minsupをいくつか試し，すべてーケンスバリアント（SV）を比較するためのアルゴリズムをの結果を示すのも選択肢である．しかし，複数の医療機関のパ提案した． SV比較のために， LCSに基づき最長共通サブシーケ

ターンを比較する場合，どのような比較は医学的に意味がある

ンスバリアント（LCSV）を抽出し，LCSVと元SVを比較しながか，どのようにそれぞれのminsupを設定するかが問題になる．例

ら2SVの共通・差異を示す併合シーケンスバリアント（MSV）をとして， minsupを実験で用いた値より小さくすると， SVの長さ

生成し，可視化する．本提案の有効性を検証するために， 実際が100以上になる．実際に本研究は任意の2つのSVを比較できるに， 2種類のminsupの設定を用いて， 2医療機関の電子カルテの方法を提案したため， minsupの組み合わせをいくつか試し，そデータに提案手法を適用し，LCSVとMSVを求め，両病院間の差れを全部比較することができる．どの組み合わせが最も医学的に異を可視化した． その結果を医療関係者に提示した結果，医療意味があるかを決めるのは困難だが，全部の組み合わせを医療従

機関間の治療方針の違いと思われる差異が分かり有益である評価

事者に示し，有用な組み合わせを選んでもらうことができる．

が得られた．
6.2 今後の課題

今後の課題として，まず3医療機関以上の扱いに関しても検討7

日本データベース学会データドリブンスタディーズ
一般論文

Vol. 1, Article No. 5, 2023年 3月

ҫྏ‫ؖؽ‬$
ҫྏ‫ؖؽ‬%/&69

図13

医療機関A(0.2)と医療機関B(0.3)のMSV

し，適切なminsupを選択する指針に関して検討する．更に，電子ーケンス解析に基づく医療指示推薦. In DEIM Forum 2021, C25-1,
2021.
[9] Yuichi Honda, Muneo Kushima, Tomoyoshi Yamazaki, Kenji Araki,and Haruo Yokota. Detection and visualization of variants in typical
medical treatment sequences. In Proceeding of the third VLDB workshop on data management and analytics for medicine and healthcare(DMAH 2017), pages 88–101. Springer, 2017.
[10] Hieu Hanh Le, Henrik Edman, Yuichi Honda, Muneo Kushima, Tomoyoshi Yamazaki, Kenji Araki, and Haruo Yokota. Fast generationof clinical pathways including time intervals in sequential patternmining on electronic medical record systems. In Proceeding of the
fourth International Conference on Computational Science and Computational Intelligence (CSCI 2017), pages 1726–1731, 2017.
[11] Hieu Hanh Le, Muneo Kushima, Kenji Araki, and Haruo Yokota.
Differentially private sequential pattern mining considering time interval for electronic medical record systems. In Proceedings of the
23rd International Database Engineering and Applications Symposium (IDEAS 2019), page 95–103, 2019.
[12] Hieu Hanh Le, Tatsuhiro Yamada, Yuichi Honda, Masaaki Kayahara, Muneo Kushima, Kenji Araki, and Haruo Yokota. Analyzing
sequence pattern variants in sequential pattern mining and its application to electronic medical record systems. In Proceedings ofthe 30th International Conference on Database and Expert Systems
Application (DEXA 2019) Part 2, pages 393–408, 2019.
[13] David Maier. The complexity of some problems on subsequences andsupersequences. Journal of the ACM, 25(2):322–336, 1978.
[14] Jian Pei, Jiawei Han, Behzad Mortazavi-Asl, Helen Pinto, Qiming
Chen, Umeshwar Dayal, and Mei-Chun Hsu. Prefixspan: Mining
sequential patterns efficiently by prefix-projected pattern growth. In
Proceeding of 2001 International Conference on Data Engineering(ICDE 2001), pages 215–224, 2001.
[15] Raju V Purushothama and Varma GP Saradhi. Mining closed sequential patterns in large sequence databases. International Journalof Database Management Systems, 7(1):29–39, 2015.
[16] 佐々木夢，荒堀喜貴，串間宗夫，荒木賢二，横田治夫. 電子カルテシステムのオーダログデータ解析による医療行為の支援. In DEIM
Forum 2015, G5-1, 2015.
[17] 厚 生 労 働 省 保 健 局.
医科診療行為告示・通知情報
一 覧.
https://shinryohoshu.mhlw.go.jp/shinryohoshu/
paMenu/doPaListSp. 最終アクセス：2022年11月9日.
[18] 吉原博幸. 千年カルテプロジェクト：本格的日本版ehr と医療デー
タの2 次利用に向けて. 情報管理, 60(11):767–778, 2018.
[19] 宮崎大学医学部附属病院臨床研究支援センター. 公開しなければな
らない臨床研究（公示）. http://www.med.miyazaki-u.ac.jp/
home/crsc/patient/notice/. 最終アクセス：2022年11月9日.
[20] 山元理絵，小林大，吉原朋宏，小林隆志，横田治夫. アクセスログに基づくWebページ推薦におけるLCSの利用とその解析. 情報処理学会論文誌データベース, 48(SIG11 (TOD34)):38–48, 2007.

カルテシステムの医療指示の情報には時刻情報が含まれない場合に，日単位での医療指示のシーケンスとして扱う必要があり，その場合のLCSVやMSVに関しても検討を行う．また，提案手法は様々な施術を対象にすることができるが，他の施術に対する適用も考える．最後に，シーケンスバリアントの差分をより分かりやすくするために， MSVを表示する可視化ツールを開発する予定である．

謝辞
本 研 究 の 一 部 は， 日 本 学 術 振 興 会 科 学 研 究 費 補 助
金(#20H04192, #21K17746)の助成により行われた．本研究で用いた電子カルテデータの利用に関しては，宮崎大学のHP [19]に記載されており，宮崎大学の倫理審査委員会及び東京工業大学の人を対象とする研究倫理審査委員会の承認を得ている．関係者各位の協力に感謝する．

参考文献[1] 医 科 診 療 報 酬 点 数 表. https://shirobon.net/medicalfee/latest/. 最終アクセス：2022年11月9日.
[2] Rakesh Agrawal and Ramakrishnan Srikant. Fast algorithms for mining association rules in large databases. In Proceeding of the 20th
International Conference on Very Large Data Bases (VLDB 1994),
pages 487–499, 1994.
[3] Yen-Liang Chen, Mei-Ching Chiang, and Ming-Tat Ko. Discovering time-interval sequential patterns in sequence databases. Expert
Systems with Applications, 25:343–354, 2003.
[4] Philipe Fournier-Viger, Jerry Chun-Wei Lin, Rage Uday Kiran, Yun
Sing Koh, and Rincy Thomas. A survey of sequential pattern mining.
Data Science and Pattern Recognition, 1(1):54–77, 2017.
[5] Xinbo Gao, Bing Xiao, Dacheng Tao, and Xuelong Li. A survey ofgraph edit distance. Pattern Analysis and Application, 13:113–129,
2010.
[6] 山田達大，本田祐一，萱原正彬， Le Hieu Hanh，串間宗夫，小川泰右，松尾亮輔，山崎友義，荒木賢二，横田治夫. SID を保持する
シーケンシャルパターンマイニングによるクリニカルパスバリア
ント分析. In DEIM Forum 2019, D1-1, 2019.
[7] 本田祐一，山田達大，萱原正彬， Le Hieu Hanh，串間宗夫，小川泰右，松尾亮輔，山崎友義，荒木賢二，横田治夫. 患者の固有情報
及び動的状況を考慮したクリニカルパス分岐要因推定. In DEIM

Forum 2019, D1-5, 2019.
[8] 坂本任駿，小林莉華， Le Hieu Hanh，松尾亮輔，山崎友義，荒木賢二，横田治夫. 頻度と実施時刻によるグループ化を採り入れたシ

8