。
( a ) Signed D i r e c t e d Graph
(ー)
①
(‑) (‑)
( b ) C o n s i s t e n t Rooted Tree
F i g . A‑9 C o n s i s t e n t Rooted Tree w i t h Amplify 8ranch f o r Improved 5‑Range Method
‑A ‑ 1 6 ‑
A p p e n d i x B 異 常 診 断 法 の 具 体 的 ア ル ゴ リ ズ ム
本章では、
A p p e n d i xA
で 示 し た 各 種 診 断 法 の 具 体 的 な ア ル ゴ リ ズ ム 、 お よ び 第 3章 第 6章で 提 案 し た 診 断 法 の 具 体 的 な ア ル ゴ リ ズ ム を 示 す 。 こ れ ら は 、3
段 階 法5)のアルゴリズムを基本と し 、 そ れ を 改 良 す る こ と で 実 現 さ れ て い る。
そこで、3
段 階 法5
)のアルゴリズムを最初に示し、異 常 発 現 時 刻 法2
・
3・
18)、 改 良5
段 階 法25)
、 改 良 遅 れ 法 、 確 率 遅 れ 法 、 フ ァ ジ ィ 遅 れ 法2 2 ¥ 条 件 法のアルゴリズムを順に示す。8 ‑ 1 3
段 階 法 の 有 効 根 付 木 探 索 ア ル ゴ リ ズ ムこ の ア ル ゴ リ ズ ム は 、 あ る 枝 が 異 常 の 情 報 を 伝 搬 し て い る か ( 有 効 枝 か ) 、 し て い な い か ( 非 有 効 枝 か ) を 仮 定 す る こ と を 基 本 操 作 と し て い る 。
B ‑ 1 ‑ 1
候 補 対 探 索 ア ル ゴ リ ズ ム有 効 測 定 点 を 含 む 有 効 根 付 木 で は 、 有 効 根 付 木 の 根 ( 候 補 対 ) か ら 各 測 定 点 へ 、 有 効 枝 だ け で 構 成 さ れ る 有 効 道 が 存 在 す る 。 し た が っ て 、 ま ず あ る 点
D a
を異常の原因と仮定し、D a
から各有 効 測 定 点 ヘ 有 効 道 だ け で 構 成 さ れ る 有 効 道 が 存 在 す る か ど う か を 調 査 す れ ば よ い 。B ‑ 1 ‑ 1 ‑ 1
候 補 対 探 索 ア ル ゴ リ ズ ム 概 略s t e p 1 :
[準備]す べ て の 有 効 測 定 点 を
mdi=1 ， 2 ， … ， i m a x )
とし、i ← 1
と し 、 す べ て の 有 効 路 フ ラ グ をO
とする。s t e p 2 :
[候補対探索]mlか ら 枝 の 向 き と は 逆 の 方 向 ヘ 、 次 の条 件 を 満 足 す る 点
r
を 重 複 を 許 さ な い 方 法 で 探 索 する。( i ) rからmlヘ 有 効 道 が 存 在 す る。
( i i ) r
は 未 だ 候 補 対 と し て 検 出 さ れ て い な い。i f
(該当するr
が存在 しない)t h e n
探 索 終 了
e l s e
点
r
を候補対と仮定する。有 効 道 上 (
r → m 1 )
の す べ て の 点 に 番 号1
をつけるo e n d i f
s t e p 3 :
[前進]i f (i > i m a x ) t h e n
[格納]ヘe l s e
mi
か ら 枝 の 向 き と は 反 対 方 向 ヘ 、 始 点 に 番 号 が つ い て お り 終 点 がmi
の有効道を重 複を許さない方法で探索する。i f
(そのような有効道が存在する)t h e n
そ の 有 効 道 の 始 点 を 除 く す べ て の 点 に 番 号
i
をつける。i ← i + 1
と し て [ 前 進 ] ヘe n d i f
e n d i f
‑A ‑ 1 7 ‑
s t e p 4 :
[後退]1 ← i ‑ 1
i f ( i
=1 ) t h e n
[候補対探索]ヘ
e l s e
[前進]ヘ
e n d i f
s t e p 5 :
[格納]仮定した候補対を候補対として格納し、
1
以 外 の 有 効 路 フ ラ グ を 消 去 し て [ 候 補 対 探 索 ]' ^ ‑ .
s t e p 6 :
[終了]格 納 し て い た 候 補 対 を 出 力 し て 終 了 す る
本 ア ル ゴ リ ズ ム で 、 最 も 重 要 な こ と は 有 効 道 を 探 索 す る (有 効 な 枝 を 遡 る ) と き に 、 重 複 し な い よ う に す る こ と で あ る 。 探 索 の 方 法 と し て 深 さ 優 先 探 索
(D φ
幼F i r s t S e a r c h
，DFS )
の手法を用 いる。B ‑ 1 ‑ 2
有 効 路 フ ラ グ ・入次数フラグ上 述 し た ア ル ゴ リ ズ ム を 具 体 的 に 示 す た め に 有 効 路 フ ラ グ 、 入 次 数 フ ラ グ の 概 念 を 導 入 す る 。
B ‑
ト2 ‑ 1
有 効 路 フ ラ グ[定義B.
1 J
有 効 路 フ ラ グ と は 、 現 在 仮定 し て い る 候 補 点 を 根 と し て で き る 有 効 根 付 木 の一部になり千 る 点 に 立 つ フ ラ グ で あ る 。 そ の 値 は 、 あ る 有 効 道 を 作 成 し よ う と し た と き に 最 初 に 着 目 ( 探 索 を 開 始 ) し た 点 の 番 号 に 等 し い 。 ( 定 義 終 わ り )
有 効 路 フ ラ グ は 、 当 然 す べ て の 点 に 存 在 し 、 探 索 開 始 時 は す べ て の 点 に お い て
O
である。B ‑ 1 ‑ 2 ‑ 2
入 次 数 フ ラ グ[定義
B . 2 J
入 次 数 フ ラ グ と は 、 そ の 点 に 内 向 き に 接 続 す る ( 入 っ て く る ) 枝 の 内 、 既 に 捜査 し た 枝 の 数 を 示 す 。 ( 定 義 終 わ り )
入 次 数 フ ラ グ は 、 当 然 す べ て の 点 に 存 在 し 、 探 索 開 始 時 は す べ て の 点 に お い て
O
で あ る 。 有 効 道 探 索 時 に 、 そ の 点 に 内 向 き に 接 続 す る 枝 ( 入 っ て く る 枝 、 す な わ ち そ の 点 を 終 点 と し て い る 枝 ) の 内 の ひ と つ を 遡 ろ う と し た と き 入 次 数 フ ラ グ は ひ と つ 増 加 す る 。 そ の 枝 が 有 効 枝 と な れ ば 、 そ の 始 点 に つ い て も 同 じ こ と を 考 え る 。 入 次 数 フ ラ グ の 最 大 値 は そ の 点 の 入 次 数 と い う こ と に な る 。入 次 数 フ ラ グ が 入 次 数 と 等 し く な っ た と き 、 そ の 点 に 内 向 き に 接 続 す る 枝 は す べ て 走 査 し た こ と に な り 、 そ れ 以 上 の 走 査 が 必 要 で な く な る 。 こ れ に よ り 、 重 複 し て 枝 を 遡 る こ と を 防 ぐ こ と が できる。
‑A ‑ 1 8 ‑
B‑1‑3
有 効 根 付 木 探 索 ア ル ゴ リ ズ ムB‑1‑3‑1
有 効 根 付 木 探 索仮 定 し た 候 補 点 を 根 と し た 有 効 根 付 木 が で き な い と い う こ と は 、 あ る 点 か ら 有 効 枝 を ど の よ う に 遡 っ て も 有 効 路 フ ラ グ が
O
、 ま た は そ の 点 に 立 っ て い る 有 効 路 フ ラ グ 以 外 の フ ラ グ が 立 っ て い る 点 に 到 達 で き な い と い う こ と で あ る ( も し 、 そ の 点 に 立 っ て い る 有 効 路 フ ラ グ と 同 じ フ ラ グ の 点 に 到 達 す る と ル ー プ を 形 成 す る )。このことは、 『 も し 、 有 効 根 付 木 が 存 在 す る な ら ば 、 少 なくとも一本 の 有 効 道 が 存 在 す る は ず で あ る 』 と い う こ と か ら 明 か で あ る 。
つ ま り 、 上 述 の よ う な 点 が ひ と つ で も 存 在 す る と 、 仮 定 し た 候 補 点 を 根 と し た 有 効 根 付 木 は 存 在 し な い こ と に な る 。 ま た 逆 に 、 上 述 の よ う な 点 が 存 在 し な け れ ば 、 仮 定 し た 候 補 点 は 正 し い と いうことになる。
B ‑ 1 ‑3‑2
重 複 せ ず に 枝 を 遡 る 方 法次 に 、 あ る 点 か ら 既 に 走 査 し た 枝 と 重 複 し な い 方 法 で 枝 を 遡 る 方 法 を 述 べ る 。 こ の と き に 必 要 と な る 概 念 が 定 義
B.2
に定義した入次数フラグである。仮 に 、 あ る 点 に 内 向 き に 接 続 す る 枝 が
3
本 あ る 場 合 を 考 え る 。 そ れ ぞ れbl
、b 2
、b 3
とすると、入 次 数 は
3
である。まず、
bl
を 考 え る 。 そ の と き 、 入 次 数 フ ラ グ を1
とし、枝1
が有効枝となるかどうかを考え、な ら な け れ ば 入 次 数 フ ラ グ に
1
を加えて2
とし、b 2
に着目する。b
2も 有 効 枝とならなければ、b
3に 着 目 し て 入 次 数 フ ラ グ に1
を加えて3
とし、b
3に着目するob
3も 有 効 枝 と な ら な け れ ば 、 入 次 数 フ ラ グ は 入 次 数 と 等 し く な っ て い る の で も う そ の 点 か ら は 遡れないことになる。C
Fig. 8‑1 Inner Demi‑degree Flag
‑A ‑ 1 9 ‑
B ‑ 1 ‑ 4
ア ル ゴ リ ズ ム の 加 速以 下 の
3
点 を 考 慮 、 す る こ と に よ り 、 計 算 速 度 お よ び 診 断 精 度 の 向 上 を 図 る こ と が で き る 。B ‑ 1 ‑ 4 ‑ 1
原 因 点 の 制 約( I
) あ る 点 が 原 因 点 で な い ([j"異常の原因となり得ない』、または『異常の原因として検出 す る 必 要 が な い 』 こ と が 明 確 で あ る: 0
士に 含 ま れ な い ) 場 合 、 候 補 点 し て 仮 定 し な い。 ( I I
) あ る 点 が 『異 常 の 原 因 と し て + ま た は ー の 一 方 し か と り 得 な い 』 こ と が 明 確 で あ る 場 合 、( 0 +
またはO
ーに 含 ま れ る ) 候 補 と し て は 、 そ の 符 号 の み を 仮 定 す る 。B ‑ 1 ‑ 4 ‑ 2
非 測 定 点 の と り 得 る 符 号非 測 定 点 の 符 号 は 、 当 然 わ か ら な い の で あ る が 、 と り 得 る 符 号 は わ か る 場 合 が あ る 。 例 え ば 、 原 因 と し て バ ル ブ の 誤 操 作 だ け を 考 え て い た と す る 。 バ ル ブ を 開 く と 抵 抗 が 小 さ く な る の で 、 そ の と き の 符 号 を 一 、 逆 に バ ル ブ を 閉 め る と 抵 抗 が 大 き く な る の で 、 そ の と き の 符 号 を + と す る
。
定 常 状 態 で 、 あ る バ ル ブ を 全 開 に し て い た と す れ ば 、 そ れ 以 上 開 く こ と は な い の で 、 そ の バ ル ブ に 対 応 す る 非 測 定 点 の と り 得 る 符 号 はO
、または+ということになる。B ‑ 1 ‑ 4 ‑ 3 D G C u t
符 号 付 有 向 グ ラ フ に よ る 異 常 診 断 ア ル ゴ リ ズ ム で は 、 有 効 測 定 点 か ら 深 さ 優 先 探 索 に よ っ て 枝 を 遡 る こ と の 可 能 な す べ て の 原 因 対 お よ び そ の と き の 符 号 ( 原 因 対 ) に つ い て 、 候 補 対 の 可 能 性 を追求する。
し か し 、 全 原 因 対 の 集 合 を 候 補 対 と し て 出 力 し た 場 合 は 、 そ れ 以 上 枝 を 遡 る こ と な く 診 断 を 終 了 し て よ い は ず で あ る ( そ れ 以 上 候 補 対 を 得 る こ と は で き な い た め ) 。 こ れ を
o
G C ut
と呼ぶ。8 ‑ 2
異 常 発 現 時 刻 法 の 第1
種 の 有 効 根 付 木 探 索 ア ル ゴ リ ズ ム5
段 階 法20)
に 対 す る ア ル ゴ リ ズ ム に お い て 、 有 効 道 の 定 義 を 、 定 義A . 9
に 示 し た 第1
種 の 有 効 道 の 定 義 に 変 更 す る こ と に よ り 、 第1
種 の 有 効 根 付 木 を 列 挙 す る こ と が で き る 。 得 ら れ た 第1
種 の 有 効 根 付 木 の 内 、 第2
種 の 有 効 道 だ け で 構 成 さ れ て い る も の を 第2
種 の有効根付木とする。た だ し 、 異 常 発 現 時 刻 を 実 時 刻 で 表 現 し て も 測 定 点 聞 の 符 号 が 変 化 し た 順 序 と し て 表 現 し て も 異 常 診 断 結 果 は 同 じ で あ り 、 ま た 、 後 者 の 表 現 法 は 前 者 に 比 べ て 処 理 速 度 が 速 い た め 、 後 者 の 表 現法を用いるのがよい。
さ ら に 、 初 め て 有 効 測 定 点 に な っ た 時 刻 が早 い 順 に 有 効 道 を 探 索 す れ ば 、 探 索 中 の 有 効 測 定 点 に 対 し て 第
1
種 の 有 効 道 も し く は 第2
種 の 有 効 道 で あ る か の 判 定 対 象 と な る 有 効 道 は 既 に 成 立 し ているはずである。‑A‑20
‑s t e p 1 :
[準備]診 断 対 象 と す る 時 間 内 の 測 定 変 数 の 経 時 変 化 を 測 定 点 上 の
5
段 階 パ タ ー ン 系 列 に 変 換 化 し 、 早 く 有 効 測 定 点 と な っ た 順 番 に 番 号i
を つ け る 。 有 効 測 定 点 は 全 部 でi m a x
個 あ る も の と す る 。 す べ て の 有 効 路 フ ラ グ をO
とする。 す べてのk i n d ( i )
をO
とする。s t e p 2 :
[候補対探索]1
番 目 の 有 効 測 定 点I D l
の上流に存在する原因対で、皿1と 有 向 道 で 結 ぶ こ と の で き る も の を 探 索 す る 。 こ の と き 、 同 じ 道 を 重 複 し て 探 索 し な い よ う に 、 探 索 中 の 道 上 の 有 効 路 フ ラグに1
を た て 、 そ れ 以 外 の 点 の 有 効 路 フ ラ グ をO
とする。i f
(過去に候補対として探索されているa n dk i n d ( i )
=2 ) t h e n
[候補対探索]ヘe l s e
候補対として仮定し、
k i n d ( i ) ← k i n d ( i ) + l
、i ← 2
と し て [ 前 進 ] ヘe n d i f
i f
(すべての道を探索した)t h e n
[終了]ヘe n d i f s t e p 3 :
[前進〕i f ( i > i m a x ) t h e n
[格納]ヘe l s e
i
か ら 枝 の 向 き と は 反 対 方 向 ヘ 、 始 点 に 番 号 が つ い て お り 終 点 がi
の第k i n d ( i )
種 の 有 効 道 を 重 複 を 許 さ な い 方 法 で 探 索 す る。i f
(そのような有効道が存在する)t h e n i ← i + 1
e l s e
[後退]ヘ
e n d i f
e n d i f s t e p 4 :
[後退]i ← i ‑ 1
i f ( i
=1 ) t h e n
[候補対探索]ヘe l s e
[前進]ヘ
e n d i f
s t e p 5 :
[格納]仮 定 し た 候 補 対 を 第
k i n d ( i )
種の候補対として格納し、1
以 外 の 有 効 路 フ ラ グ を 消 去 し て [候補対探索]ヘs t e p 6 :
[終了]第
1
種 の 候 補 対 と 第2
種 の 候 補 対 を 区 別 し て 出 力 し 、 終 了 す る‑A ‑ 2 1 ‑
B ‑ 3
改良5
段 階 法 の 有 効 根 付 木 探 索 ア ル ゴ リ ズ ム改良
5
段 階 法25 )の有効根付木探索アルゴリズムは、5
段 階 法20)の ア ル ゴ リ ズ ム に 改 良5
段 階 法25)に お け る 有 効 道 を 評 価 す る 部 分 を 追 加 す る こ と に よ っ て 容 易 に 構 成 す る こ と が で き る 。s t e p 1 : [準備]
有 効 な 確 定 測 定 点 を 数 え 上 げ 、 番 号 を つ け る
(
全 部 で k個 あ る も の と す る)
0s t e p 2 : [候補点の探索]
1
番R
の 有 効 な 確 定 測 定 点m
の 上 流 で 、 ま だ 候 補 点 と さ れ た こ と が な く 、f f i ，と改
良5
段 階法~o)に お け る 有 効 道 で 結 ぶ こ と の で き る 最 も 近 い 点 を 探 索 す る 。i f (そのよ
う な 点 が あ る と き )t h e n
候補点として選び，
f f i
，とその点とを結ぶ改良5
段 階 法25 )に お け る 有 効 道 上 の す べ て の 点 に 有 効 道 フ ラ グ1
を立て、i← 2
と し て [ 出 力 ] ヘe l s e
そ の よ う な 点 が な い と き に は [ 終 了 ] ヘ
e n d i f s t e p 3 : [出力]
i f ( i > k ) t h e n
候 補 点 を 改 良
5
段 階 法25)における候補集合の要素とし、1
以 外 の 有 効 路 フ ラ グ を 消 去して[
候 補 点 の 探 索]ヘ
e l s e
[前進]ヘ
e n d i f s t e p 4 : [前進]
i f ( i
番目の有効な確定測定点、I D i
に 既 に 有 効 道 フ ラ グ が 立 っ て い る )t h e n i ← i + l と し て [ 出 力 ] ヘ
e l s e
既 に 有 効 路 フ ラ グ の 立 っ て い る 点 か ら
f f i i
へ の 改 良5
段 階 法25)
における
有 効 道 を 探 索する。i f (そのような改
良5
段 階 法25
)における有効道が存在する) t h e n
そ の 改 良
5
段 階 法25
) に お け る 有 効 道 上 の 有 効 道 フ ラ グ が 立 っ て い な い 点 す べ て に有効道フラグを与え、i← i + l
と し て [ 出 力 ] ヘe l s e
[後退]ヘ e n d i f
e n d i f s t e p 5 : [後退]
i
f( i = 1 ) t h e n
[候補
点の 探 索 ] ヘ
e l s e
f f i i を終
点とする改良 5 段 階
法25)に お け る 有 効 道 の 変 更 の 可 能 性 を 調 べ る 。i f (可能性がある) t h e n
変更を行い、
i = i + l
と し て [ 前 進 ] ヘe l s e
[後退]ヘ e n d i f
e n d i f s t e p 6 : [終了]
終 了 処 理 を し て 作 業 を 終 了 す る。