More Related Content
More from harmonylab (20)
tadano b
- 1. グラフマッチングの 患者紹介システムへの適用 但野友美 复合情报学専攻调和系工学研究室
- 2. 背景 近年，医療の対象として介護?療養型施設を意識する状況となり， 地域医療システム全体を総合的に捉える重要性が高まっている 医療の機能を分化し，患者の治療の段階によって適切な病床に行くように 流れを作ることが望まれている 急性期病床 亜急性期?回復 リハビリテーション病床 介護療養型施設 現在，札幌市では急性期から介護?療養型施設などへの 転院が，隘路となっている 問題点 「札幌市医師会双方向患者紹介システム」より ※（「札幌市医師会双方向患者紹介システムの構築にむけた実態調査とその分析」より） ※ 病院側が患者に適切な紹介先の医療機関を提示できない場合が多い 理由 ※ 地域全体で情報の共有ができていない 医療機関，現在の空き病床
- 3. ①送り手側が患者を登録 ②医療機関DBでマッチング ③結果確認 ④転院先決定 患者紹介システム →現在β版が公開されている 双方向患者紹介システム 情報不足を解消するために，札幌市医師会では の構築を目指している 複数の患者のマッチングを同時にとる方法の提案 ?患者が転院する際の病床の割り当てを二部グラフの完全マッチング問題としてモデル化 ?二部グラフの完全マッチングを求めるプログラムを実装し，患者紹介システムへの適用性を検証 目的 患者A 患者B 患者C 病床1 病床2 病床3 病床4 β版 登録順に患者を一人 ずつマッチングする 患者全体のマッチングを一度にとることにより， 登録順が後の患者を考慮する 1/28 A 2/16転院 病床1，3，4 B 2/9 2/20転院 病床1，2，3 転院できない C 2/12 2/25転院 病床2，3 病床1，2，3，4があるとする
- 4. モデル化 複数の患者のマッチングを同時にとり，すべての患者に症状に合った医 療機関を割り当てることを，二部グラフG(X,Y)の完全マッチングを解く問 題としてモデル化する． ? X={1,2,‥,n} 患者集合 （転院希望の患者） ? Y={1,2,‥，m} 病床の集合 （空いている病床の集合） X,Yからなる二部グラフの行列 ? ? ? ? ? ? ? ? ? ? ? n mn m g g g g G X Y ? ? ? ? ? 1 11 1 ( , ) とする． 辺ijが存在するとは，患者i が病床j に行くことが可能 であることを表す ここで， ∈｛0,1｝ であり， 辺ijが存在する場合は1，ない場合は0が入る ij g ?0 ? i ? m,0 ? j ? n?
- 5. 求める解 すべての行に1が1つだけあり，列にはたかだか1つの1がある． そしてその他はすべて0であるという条件を満たすマッチング行列 ? ? ? ? ? ? ? ? ? ? ? n mn m m m m m M ? ? ? ? ? 1 11 1 を求める Mが存在しなければ“ない”存在した場合は 条件を満たす解を1つ求める 解があるための必要十分条件は，Xの任意の部分集合X’に対して，X’の近傍をφ（X’) とすると， |X’|≦|φ(X’)| を満たすことである． 制約条件 Hallの定理より ? ? ? n ? m ?{0,1} ij g ?{0,1} ij m ここで， であり， 辺ijがマッチングである場合は1，そうでない場合は0が入る ?{0,1} ij m ?0 ? i ? m,0 ? j ? n? （n ：患者数 m ：病床数） ? ? ? ? ? ? ? m i ij ij m i ij m m g 1 1 ? 1∧ 1 ?i ?1,?,m? ? ? ? ? ? ? ? ? n j ij ij n j ij m m g 1 1 1 ?1 0 ? ? ? ? ? ? ? ? ? ?? n j ij m 1 1 ? ? ? ? ? ? ? ? ? ?? n j ij m 1 0 ∧ ? j ? 0,?,m?
- 6. 特徴：完全マッチングが存在する場合は必ず見つけることができる 計算量： ? ? （E:辺の集合，X：患者の集合） 2 O E X システム要件 すべての患者に病床を割り当てる組み合わせが存在する場合， 必ずその組み合わせを求められるようにしたい ハンガリー法 二部グラフG(X,Y)のXにおける完全マッチングを求めるアルゴリズム ①初期マッチングを 作る a1 a2 a3 b1 b2 b3 二部グラフG(A,B)についてAにおける完全マッチングを求める場合 a1 a2 a3 b1 b2 b3 A B ②Aについて マッチング相手が 未割り当てな 点を探す ③マッチングを 置き換えられる 道を探す ④マッチングを 置き換える a1 a2 a3 b1 b2 b3 a1 a2 a3 b1 b2 b3 アルゴリズム a1 a2 a3 b1 b2 b3
- 7. 実験概要 実際にハンガリー法を患者紹介システムに適用した場合の計算時間を調べる 症状が似ている患者は行くことができる病床も似てくる 実用的な範囲の計算時間で転院先を見つける必要がある 病床数 1000 患者数 1≦|X|≦1000 各x∈Xの次数 E 計算機 オプテロン270CPU（2GHｚ） メモリ：4GB ②1000の病床が症状によって10個ずつ 100カテゴリーにカテゴライズされたグラフ ? ランダムに辺を引いた二部グラフとカテゴライズ されたグラフにおける計算時間の比較 → 実験１ ? カテゴライズされたグラフの場合，辺の本数による 計算時間の比較 → 実験２ 患者Ａ 患者Ｂ ? 札幌市の病床数約45000 ? 空き病床率8％ ? システム登録率約3割 と仮定 ×10 ×10 ×10 ??? ×10 カテゴリー1 カテゴリー2 カテゴリー3 カテゴリー 100 実験で扱うグラフ ①ランダムに辺を引いた二部グラフ カテゴライズされたグラフ
- 8. 0 2 4 6 8 10 0 200 400 600 800 1000 10*10 100 実験① |X| ? カテゴライズされたグラフの方が計算時間が多くなった ? 計算時間は，初期マッチングの段階で病床が未割り当ての患者数に比例する ? いずれの場合も|X|が|Y|の90％以下の範囲では，解を20秒以内で算出できる １，ランダムに100本辺を引いた二部グラフと，カテゴライズされたグラフの比較 時 間 （秒 ） 0 20 40 60 80 100 120 0 200 400 600 800 1000 10*10 100 |X| |X|が|Y|の90％ ランダムに100本辺を引いた 二部グラフ カテゴライズされた二部グラフ においてカテゴリーを10ずつ選ぶ （全部で100本引く） カテゴライズされたグラフ ランダム 初期マッチングの段階で 病床が未割り当ての患者数
- 9. 0 50 100 150 200 250 0 200 400 600 800 1000 10*5 10*10 10*25 実験② 時間（秒） |X| |X|が|Y|の90％ ? 辺の数が少ないほど計算時間は多くなった ? 計算時間は，初期マッチングの段階で病床が未割り当ての患者数に比例する ? いずれの場合も|X|が|Y|の90％以下の範囲では，解を20秒以内で算出できる ２，カテゴライズされたグラフについて，各x∈Xからひく辺の数による計算時間の比較 カテゴリーを5個ずつ選ぶ （次数Ｅ=５０） 10個ずつ選ぶ（Ｅ=100） 25個ずつ選ぶ（Ｅ=250） 0 5 10 15 20 25 0 200 400 600 800 1000 5*10 10*10 25*10 初期マッチングの段階で 病床が未割り当ての患者数 |X| E=50 E=100 E=250
- 10. 結果と考察 ハンガリー法は患者紹介システムのマッチングにおいて， 登録順が後の患者を考慮に入れる場合に適用可能である ? 完全マッチングが存在する場合は必ず見つけることができる ? 計算時間が少ない ? 全探索ではないので，解を1つしか求めることができない 病床数が1000以下で，患者数が病床数の90％以下の場合，グラフの形状によらず 計算時間は20秒以内に算出できることが分かった 利点 欠点 ? カテゴライズされたグラフの方が計算時間が多くなった ? 辺の数が少ない場合，初期マッチングで未割り当てとなる病床が多くなり 計算時間が多くなった
- 11. まとめ ? 登録順が後の患者を考慮したマッチング方法として，二部グラフの 完全マッチングを用いる方法を適用した ? 患者紹介システムにハンガリー法を適用した場合，計算時間は， 病床数1000以下，患者数が病床数の90％以下であれば 20秒以内に算出できる ? ハンガリー法は完全マッチングが存在する場合，必ず解を求めること はできるが，求めることのできる解は1つである 課題 ? すべての完全マッチングを求める方法の検討 ? 患者の行くことのできる病院について希望順位などを定められる完全 マッチング（辺に重みをつけるなど） の実現
- 12. 双方向患者紹介システム 登録医療機関データベース マッチングシステム コーディネートスクエア 図1：札幌市医師会入退院支援システム （「札幌市医師会双方向患者紹介システム」より） 患者を受け入れること ができる医療機関の データベース 転送側医療機関と受入側 医療機関が患者情報を入 力し，双方向からマッチン グを行うシステム マッチングの結果をもとに転送側?受入側医 療機関双方の担当者，患者本人，家族など が集まり，受入医療機関を決定する 一度に転院希望の患者数が 複数の場合，患者と病床の 集合を二部グラフとして捉え， その完全マッチングを求める 問題に置き換えることができないか
- 13. 実験② 0 0.2 0.4 0.6 0.8 1 1.2 1.4 0 100 200 300 400 500 E100 Y10.E10 |Y|=1000に固定 1≦|X|≦500 Yに偏りをもたせるためにYの要素を10ずつ100個のかたまりとし， 各x∈XからYに辺を引く場合，一度に10本ずつ引くようにした． 各x∈XからE個ｙ∈Yを選んだので，実際にはE×10本の辺を引いたこととなる． 時 間 （秒 ） |X| 1.4秒 Yに偏りをもたせ 100本の辺を引く場合 ランダムに100本の辺を 引く場合 結果：E=10 辺の引き方に偏りを持たせて計算時間を計る
- 14. 0 0.0005 0.001 0.0015 0.002 0.0025 0.003 0.0035 0.004 0.0045 0 10 20 30 40 50 60 70 80 90 100"kekka100.kanzen.txt" using 1:4
- 15. 0 20 40 60 80 100 120 140 160 180 200 0 100 200 300 400 500 600 700 800 900 1000random10010*10
- 16. 0 20 40 60 80 100 120 140 160 180 200 0 100 200 300 400 500 600 700 800 900 100010*1025*10 0 20 40 60 80 100 120 140 160 180 200 0 100 200 300 400 500 600 700 800 900 1000 random100 10*10
- 17. 0 1 2 3 4 5 6 7 0 100 200 300 400 500 600 700 800 900 1000 10*10 100 0 20 40 60 80 100 120 0 100 200 300 400 500 600 700 800 900 1000 10*10 100 0 20 40 60 80 100 120 0 100 200 300 400 500 600 700 800 900 1000 10*10 10*25 0 50 100 150 200 250 0 200 400 600 800 1000 10*10 10*25 10*5 10*3