# МНОГОПАРАМЕТРИЧЕСКАЯ КЛАССИФИКАЦИЯ АВТОМАТНЫХ МАРКОВСКИХ МОДЕЛЕЙ НА ОСНОВЕ ГЕНЕРИРУЕМЫХ ИМИ ПОСЛЕДОВАТЕЛЬНОСТЕЙ СОСТОЯНИЙ

• Published on
04-Apr-2017

• View
218

3

Embed Size (px)

Transcript

• 2010

4(10)

519.217

.. , ..

. .. ,. ,

E-mail: sshalagin@mail.ru, Alsu124@mail.ru

- () - . , -. (), - , . - , , .

: , , -, , -, , , , .

() -

, , , . . , [1 3]. , - (), , [4, 5].

, m-, m = 2, 3, . . . [6, 7].

, -, Statistica 6.0 [8], [9, 10]. , .

[9, 10] - () , . , [11] , - , [11 13]. , - [11]. - .

• 42 . . , . .

, , .

, [14 16], - , , - . () -, , . , , - N , , . - ().

1. 1. [1]

(S, P, 0) , (1)

S = {s0, s1, . . . , sn1} ; P [1] - P = (pij), i, j = 0, n 1; 0 n- - .

2. - [4] (

U , S, P, (u, s)), (2)

U [4], u0, u1, . . . , ul1 p = (p0, p1, . . . , pl1); l -

[4];l1i=0

pi = 1, 0 6 pi 6 1; (u, s) ,

(u, s) s S. P =l1i=0

piAi, Ai

( [5]). Ai, akj(i), k, j = 0, n 1, :

akj(i) =

{1, (ui, sk) = sj,0, (ui, sk) 6= sj.

3. (1) , , . . - [1].

4. C P , -, .

, (1) (2), . : D, - . , P , (P ).

, . , : ()

• 43

- (). () - (). () (). :

1) pij, i = 0, n 1, j = 0, i, p0(n1);2) pij, i = 0, n 1, j = i, n 1, p(n1)0;3) pij, i, j = 0, k 1, k = [n/2], pij, i, j =

= k, n 1, p(k1)k pk(k1);4) pij, i = 0, k 1, j = k, n 1, k = [n/2], pij,

i = k, n 1, j = 0, k 1. -

. -

, , ?

2. (P ) ,

P , . fk, k = 1 n, n 1,

si sj (si, sj S, i, j == 0, n 1) , i j = k. fk , [7].

N Y (N1),, yz = k i j = k (yz Y , z = 1, N 1), z- si sj.

si sj , i j = k,

fk =1

N 1N1z=1

yz, yz =

{1, yz = k,0, yz 6= k,

k = 1 n, n 1. (3)

fk (k = 1 n, n 1) si sj , i j = k, fk, - (P ), (P ),

fk =1

n

n|k|i=1

m(i, k), (4)

m(i, k) = pi(ik) k = 1 n, 0 m(i, k) = p(i+k)i k = 1, n 1. (3) (4) . - N . k = |fk fk|(k = 1 n, n 1) , fk - si sj i j = k, i, j = 0, n 1. , fk, k = 1 n, n 1, . - , k [17]. - N > 5 [17]. , fk Y (N 1), -

• 44 . . , . .

[17]

k =fk fk = t

fk (1 fk)N 1

, k = 1 n, n 1, (5)

t , - , , . fk - [17]

fk [

5

N 1,N 6N 1

]. (6)

1. (6) , (3), N1z=1

yz

[5, N 6], yz Y , z = 1, N 1. (6) fk -

, . k

k = max(|fk p1k|, |p2k fk|), (7)

p1k p2k , :

N1m=l

CmN1pm1k (1 p1k)

Nm1 =

2;

lm=0

CmN1pm2k (1 p2k)

Nm1 =

2,

l si sj , i j = k, k = 1 n, n 1 [16]. (5)

N =fk

(1 fk

)f fk2 t2 + 1 6 maxfk

fk(

1 fk)

2t2

= 142

t2, k = 1 n, n 1. (8)

1. N , -

f , (P1) (P2), P1 P2 - , (8).

1, , - ,

= maxk=1n,n1

(min fk(P1)min fk(P2)) , (9)

fk(P1), fk(P2) k- , P1 P2 -, N , - , , - , (8).

1 (P ) -, P .

• 45

3. ()

pij > 0 P D pij [D, 1 D],i, j = 0, n 1. (4) fk, k = 1 n, n 1.

(P ), P {,,,}, - , P , (P ), .

1. (4). 2. , fk

P , (P ) ( ). 3. fk -

(3) . N, , k, (5).

4. , (P ), , , , , , - .

1 4 (3).

1 . 2. fk, k = 1 n, n 1,

Vk P (4), , min fk, , h = D h Vk, , max fk, , h = 1D h Vk.

(min fk,max fk) - .

f1n = (D, 1D) , fk = (0, 0), k = 2 n,1,f0 =

(D, 1 (2 + n(n 1))0,5Dn1

), (10)

fk =((1 kn1)D, 1 (n+ k 1)(n k)0,5Dn1

), k = 1, n 1.

:

fk =((1 kn1)D, 1 (n+ k 1)(n k)0,5Dn1

), k = 1 n,1,

f0 =(D, 1 (2 + n(n 1))0,5Dn1

), (11)

fk = (0, 0), k = 1, n 2, fn1 = (D, 1D).

, w = 0,5n v = [w] + 1, n > 4:

fk = (0, 0) k = 1 n,v k = v, n 1,f0 =

(D, 1 2Dn1((v 1)2 1)

). (12)

• 46 . . , . .

n:

f1 =

((n 1)Dn1, 1 2Dn1

((v 1,25)2 + 23

16

)),

f1 =((n 1)Dn1, 1 2Dn1(v 1,5)2 + 0,25

),

fk =((1 + 2k)Dn1, 1 (v 1) (v + k) +D (v 2) (n+ k v)

), k = 1 v,2.

n:

f1 = f1 =((n 1)Dn1, 1 2Dn1((w 1,5)2 0,75)

),

fk =((1 2|k|)Dn1, 1Dn1(2w2 n(1 + |k|) + 2|k|+ 1)

), k = w,2, k = 2, w.

: f0 = (0, 0); - n:

fk =(kDn1, 1 k[w]D

), k = 1, [w],

fk =(kDn1, 1 k[w]D

), k = [w],1, (13)

fk =([w]Dn1, 1 2[w]D

), k = [w] + 1,

fk =((1 k)Dn1, 1 (n k)[w]D

), k = 1 n,[w] 2, k = [w] + 2, n 1;

n:

fk =(|k|Dn1, 1 + |k| (1 w)D

), k = w + 1,1, k = 1, w 1,

fk =((1 |k|n1)D, 1 (n |k|) (w 1)D

), k = 1 n,w, k = w, n 1.

, (10)(13), . 1 2 . Q-

, , - , , ; JQ fk, fk(Q) = 0.

3. fk (4), RQ, - (P Q) , : fk(Q) = 0, min fk (Q) > 0, k JQ.

4. RQ(1) RQ(2) fk (4), - (P1 Q(1)) (P2 Q(2)), Q(1) Q(2) = , .

(10)(13), fk 0 :

fk(T) = 0, k JT = {2 n, 3 n, . . . ,1},fk(T) = 0, k JT = {1, 2, . . . , n 2} ,

fk() = 0, k J = J1 J2 = {1 n, 2 n, . . . ,v} {v, v + 1, . . . , n 1},f0() = 0.

• 47

1 fk, k = 1 n, n 1

P min fk max fkD, k = 1 n 1D, k = 1 n

D, k = 0 1 (2 + n(n 1))0,5Dn1,k = 0

(1 kn1)D, 1 (n+ k 1)(n k)0,5Dn1,k = 1, n 1 k = 1, n 1

0, k = 2 n,1 0, k = 2 n,1(1 kn1)D, 1 (n+ k 1)(n k)0,5Dn1,k = 1 n,1 k = 1 n,1

D, k = 0 1 (n+ k 1)(n k)0,5Dn1,k = 0

D, k = n 1 1D, k = n 10, k = 1, n 2 0, k = 1, n 2

n mod 2 = 1

min fk max fk

kn1D, k = 1, [w] 1 k[w]D,k = 1, [w], k = [w],1

[w]Dn1, 1 2[w]D,k = [w] 1, k = [w] + 1 k = [w] 1, k = [w] + 1

(1 k)n1D, 1 (n k)[w]D,k = 1 n,[w] 2, k = 1 n,[w] 2,k = [w] + 2, n 1 k = [w] + 2, n 1

kn1D, k = [w],1n mod 2 = 0

min |fk| max |fk| |k|n1D, 1 |k| (w 1)D,

k = w + 1,1, k = w + 1,1,k = 1, w 1 k = 1, w 1

(1 |k|n1), 1 (n |k|) (w 1),k = 1 n,w, k = 1 n,w,k = w, n 1 k = w, n 1

3 4 - () (P ), P {,,,}, ( ).

• 48 . . , . .

1. , , - (P), , (M), M{,,}.

2. , -, (P), , (M).

3. , , - (P), , (P).

1 , {, , , }. , . :

A1 = maxkJ

|min fk()min fk()| = maxkJ

(min fk()) = (n 1)Dn1 k = 1,

B1 = maxkJ

|min fk()min fk()| = maxkJ

(min fk()) = (n 1)Dn1 k = 1. , ,

C1 = max

k(J\J1 )J2|min fk()min fk()| =

= max

(max

k(J\J1 )(min fk()), max

kJ2(min fk())

).

(14)

J\J1 = {[w],[w]+1, . . . ,1}. maxk (min fk()) == (n 1)Dn1 k = 1, k J2 maxk (min fk()) = (n 1)Dn

1

k = 1. C1 = (n 1)Dn1. , , , (14),

E1 = maxkJ{0}

|min fk()min fk()|. J{0} = {2n, 3n, . . . , 0},

maxkJ

(min fk()) = [w]Dn1, min f0 () = D. E1 = D.

1 : {,,,}, , min (A1, B1, C1, E1) = (n1)Dn1. fk, fk - : |min fk()min fk(Q)| > (n1)Dn1, Q {,,,}. R .

2 , = {,}.

, , - (13), A2 = max

kJ\J2|min fk()min fk()| = (n 1)Dn1, k = 1.

, , , - (14), B2 = max

k{0}J|min fk()min fk()| = D. {0} J = {0, 1, . . . ,

n 2}, min f0 () = D, maxkJ

(min fk()) = [w]Dn1.

, 2, , - , min(A2, B2) = (n 1)Dn1. , - R , fk, fk |min fk()min fk()| > (n 1)Dn1.

, . - , (14), A3 = max

k{0}J|min fk()min fk()|.

• 49

{0} J = {1 n, 2 n, . . . ,v, 0, v, v + 1, . . . , n 1}, min fk () = D k = 0, max

kJ(min fk()) = [w]Dn1.

, R , fk, fk - : |min fk()min fk()| > D.

, , 1 3, 2. (P ), P {,,,},

R = R R R . , (9), (n 1)Dn1.

3. (3), R, , (P ), - , P . , , (P ), (5) ( (6) )

N = maxfkR

(fk

(1 fk

)t22k + 1

)6

n2t24(n 1)2D2

+ 1, (15)

k fk R fk, - (n 1)Dn1. k, - , (15). = 0,95, -, t = 1,96 [17], D = 5 102. , (15) -: N = max

fkR

(1536,64 n2 (n 1)2 fk

(1 fk

)+ 1). , (15),

fk = 0,5 N 6 384,16 n2 (n 1)2 + 1. 3. , (6) R

J , fk, k J , (7) Nk:{

(n 1)Dn1 > fk p1k,(n 1)Dn1 > p2k fk,

{p1k > fk (n 1)Dn1,p2k 6 (n 1)Dn1 + fk,

(16)

p1k p2k , (7), = 0,95:

Nk1m=l

CmNk1pm1k (1 p1k)

Nkm1 = 0,475,l

m=0

CmNk1pm2k (1 p2k)

Nkm1 = 0,475.

l si sj , i j = k, k = 1 n, n 1.

5. , - , (P ), N = max(Nk, Nz), Nk, k J , (16), Nz -, (15), z = 1 n, n 1.

2 3 , P{,,,}, n = 5. - fk . 2; .

• 50 . . , . .

2 n = 5

f4 (D, 1D)/5 (D, 1 4D)/5 (0, 0) (D, 1D)/5f3 (0, 0) (2D, 1 7D)/5 (0, 0) (2D, 1 2D)/5f2 (0, 0) (3D, 1 9D)/5 (D, 1 2D)/5 (2D, 1 2D)/5f1 (0, 0) (4D, 1 10D)/5 (4D, 1 9D)/5 (D, 1D)/5f0 (5D, 1 11D)/5 (5D, 1 11D)/5 (5D, 1 10D)/5 (0, 0)f1 (4D, 1 10D)/5 (0, 0) (4D, 1 8D)/5 (D, 1 2D)/5f2 (3D, 1 9D)/5 (0, 0) (D, 1 3D)/5 (2D, 1 4D)/5f3 (2D, 1 7D)/5 (0, 0) (0, 0) (2D, 1 4D)/5f4 (D, 1 4D)/5 (D, 1D)/5 (0, 0) (D, 1 3D)/5

1 . 3, , - . {,,,} fk, k = 1, 1, k 6 D.

3 , {,,,}

f4 f3 f2 f1 f0 f1 f2 f3 f4 Ma. .

0,4D 0,6D 0,8D 0,8D 0,6D 0,4D 0,8D

0,2D 0,2D 0,8D 0,4D 0,4D 0,2D 0,8D

0,4D 0,4D 0,2D D D

, 2, . 4 {,,} fk, k = 0, 1, D.

4 , {,,}

f4 f3 f2 f1 f0 f1 f2 f3 f4 Ma. .

0,2D 0,4D 0,4D 0,8D 0,2D 0,2D 0,8D

D 0,2D 0,4D 0,4D D

. 5 3, f0 D.

• 51

5 ,

f4 f3 f2 f1 f0 f1 f2 f3 f4 Ma. .

0,2D 0,4D D 0,4D 0,2D D

. 24 , (P ), P {,,,}. k = D, k = 1, 1.

(3), fk, k = 1, 1, , (P ), - , P . -, , (P ), (5) (14):

N = maxfkR

(2401 fk

(1 fk

)+ 1)6 602,

k fk fk, k = 1, 1, - 2 n = 5. , , (15); = 0,95, t = 1,96;D = 5 102.

4. 4 , -

(P ), P {,,,}. (15) (5) , (16) .

, (P ). P , , , n = 5. ,, , MS Excel. D = 5 102.

5 (P ), 20 , , , 400 . (15) 602, , - , (5). - N , , (P ), 94% NM = 602.

N , , . 6.

, - ( = 0,95), (), - 509 , 85% NM . , , 473 . - 79% NM . . , (),

• 52 . . , . .

, , ().

6 N ,

N % % NM 380 564 87 63 94

86 233 13 14 39

380 564 99 63 94

417 564 97 69 94

343 564 90 57 94

, , - . - . 7. (F -) 221,8 p < 5 105. - 1,622 102. -.

7

- F - (3,291) .

f1 0,073929 409,5078 0,718518

f0 0,074529 413,8994 0,619251

f1 0,094515 560,1085 0,668676

. 7 - : - , F - - . , [11, 12], - 409 [4, 7], - 0,1. .

, - , 100%, .

5.

, si sj i j = k (si, sj S, i, j = 0, n 1), , - (P ). P , , ,

• 53

, (P ). -, (P ) .

, . .

, 3 n = 5 , , 602 0,5. - , n . , (2n 2), - . , n . .

N , (11), (

maxkJ

k

)1.

k, , D , 22 0,5D. , , 621% .

(P ) -

, P . , - .

, - (P ). 0,5 - . - , .

, - , - .

1. ., . . .: , 1970. 272 .2. .. . .; .: , 1949. 436 .3. . . -

. .: . , 1976. 344 .4. . . . .: , 1985. 287 .

• 54 . . , . .

5. .. . .: , 1970. 88 .6. .., .., .., .. .

.: , 2002. 480 .7. Friedman W.F., Callimahos D. Military crypto analyze. Part I. V. Z. Aegean Park Press,

Laguna Hills CA, 1985. 356 p.8. .. Statistica: . 2- . .: -

, 2003. 700 .9. .., .., .. .

// . .. . 2001. . 1. 3.. 3739.

10. .., .., .., .. - // - . : , 2000. . 91106.

11. ., ., .M. - . .: , 1977. 221 .

12. . . .: , 1982. 272 .13. .. // . . 1953.

3(55). . 320.14. .., .. -

// . . : . . . : - , 2007. . 9092.

15. .., .. - // XV : . . .: - . .. , 2007. C. 7879.

16. .., .. - // . .. . 2010. 1. . 9499.

17. .. . IV ., . .: , 1969. 576 .