.
: , , , , .
: , , , , .
, ( ).
. . .
.
, , .
() , .
, , , .
, , () .
, , / ( /), , ( /).
, , .
, , .
, , , , .
:
1) , , .
2) .
3) .
|
|
, , , , .
, :
1) .
2) .
3) .
, .
, .
E=S+n
, .
, ,
E(t1) , t1
E(t2) t2
() . : , , .
, , .
. .
, , ( ), ( ), ( ).
, .
, , , , , .
1. , , (), ?
2. ?
|
|
1. ?
2. ?
3. ?
1. . .- .: , 2002.- 120 .
2. .. : . . / .. .- .: , 2007.- 192 .
3. .. . ¾ .: , 2003.
4. . . ¾ .: , 1998
:
. . .
. .
. .
:
, - , .
, , , :
- ( ). - - : 1 - , ( , ..), (- , ). 2 , , , (- , , ). 3 , . . . (, , , ). |
.
, , . .
, , , . . . :
,
,
,
,
,
.
|
|
-
n , .
- .
t - .
d .
v ( , ).
, . . , . f. , .
, , .
1. ?
2. ?
1. ?
2. ?
5. . .- .: , 2002.- 120 .
6. .. : . . / .. .- .: , 2007.- 192 .
7. .. . ¾ .: , 2003.
8. . . ¾ .: , 1998
:
.
. .
. . . , , .
( ) . , , . , , , , .
:
1) (n);
2) (S);
3) (E(t)=S+n);
4) (I=E(t2)-E(t1)/t2-t1);
5) ( );
6) (gi);
7) (ij=f(gi,gj);
8) ( );
9) (T);
|
|
10) (H);
11) (V).
:
A: {a1(ai,aj,ak,),a2(),a3(),an()}
a1 , , - ;
ai , i- , - , ;
an n , - , ;
n ;
, , .
:
1) {1(2,3),2(1,3),3(1,2)}
2) {1(2,5),2(1,3)3(2,4),4(3,5),5(4,1)}
3) {1(3),2(3),3(1,2,4,5),4(3),5(3)}
4) {1(3),2(3),3(1,2,5),4(5),5(3,4)}
5) {1(2,4),2(1,3),3(2,4),4(1,3)}
, :
{11(2,3),22(1,3),3200(1,2)}
, . :
{11(+2,-3),22(+1,+3),3200(-1,+2)}
1 2, 3. 2 . 3 1 2.
, . . .
. , . . , , . . . .
. , ( ).
, :
: {1(2),2(1,3),3(2,4),4(3)}
B: {2(3),3(2,4),4(3,1),1(4)}
B :
2 1, 3 2, 1 4, 4 3,
. , .
, , .
, , , , - .
, , . , :
1) ,
2) .
. , , , , , ..
1. ai(gi) aj(gj)
Zij=Gij(gi+gj)/2
2. ai(gi) aj(gj)
Zij=Gij(gi/si+gj/sj)/2
Gij , 1 i j 1, i=j
gi i
si i c .
.
|
|
, , , . () , . , , .
:
A:{11(2,3,5),22(1,4),32(1,4,5),43(2,3,5),51(1,3,4)}
.
, 1, : Zij=(gi+gj)/2
. , , :
:{11(2,3,),22(1,4),32(1,4,5),43(2,3,5),51(3,4)}
, ( )
: {22(4),32(4),43(2,3)}
, , , .
, :
1) ,
2) , ,
3)
4) .
, .
, , .
, , . : , ( ). . .
.
:
1) ?
2) ?
3) ?
:
1) ? ?
2) ?
:
. .
.
: , .
, , .
, , ..
, n , , , .
1
(), .
2
, .
, . , .
, , , , .. - .
, t . :
., , . , , . , , .
n-1 ( )
t.
(n-1)*(n-1)
, p t. T=p*t.
. n k . , . , n k , k*log2(n) , . , k*log2(n)*t , log2(n)*t.
n k , . k .( , )
. , . , , .
, , :
1) , , ,.. , ., . . , , , . , .
, . :
H=k*log2(W)-B
W- , .
B- , , . , .
- .
k- , , . k . k=1.
B (log2(n-1)).
:
H=log2()-log() H=log2(S/(n-1)), S- , n .
S=(n*(n-1))/2 H=log2(n/2).
2) , , . .
3) ,
.
, .
H1=log2(7/4)=0.8
H2=log2(6/4)=0.58
H3=log2(2/2)=0
4) .
, . , .
, , .
:
, . 1, 3.
, 8:
1-3
3-2, 3-4, 3-5
2-3, 4-3, 5-3
3-1
. 4t, t .
:
3-1, 3-2, 3-4, 3-5
1-3, 2-3, 4-3, 5-3
2t.
5) 2,9. . - .
, , .
:
1) ?
2) ?
3) , ?
1. . .- .: , 2002.- 120 .
2. .. : . . / .. .- .: , 2007.- 192 .
3. .. . ¾ .: , 2003.
4. . . ¾ .: , 1998
:
. . .
, .
? , .
, , .
, , , .
.
: {1(2,3,4,),2(1,3,4),3(1,2,4),4(1,2,3,5),5(4,6,7),6(6,7),7(5,6)}
4, . . , , . , .
.
Uik , i- k , n .
k- ( k )
Vk=k*Cnk/(∑Uik)
, , . 1 2 , .
:
, , , , .
, . , . .
, , . , .
, . , .
V=1.
, ().
:
1) ?
2) ?
3) ?
1. . .- .: , 2002.- 120 .
2. .. : . . / .. .- .: , 2007.- 192 .
3. .. . ¾ .: , 2003.
4. . . ¾ .: , 1998
: .
.
, , .
. . . , ( ) : +, - , *, /, . . , . , ( ) . , . . , 3 =3. =5. z=20. : , - , z- . d- +, -, *, /, . , . . d, (z-d(,))2. , , , :
Min(z-(d1(x,y,A1))2
Min((z-d2(d1(,y),A1))2, (z-d2(d1(x,A1),))2,(z-d2(d1(A1,y),x)))2
, , , . , , . . , , . , , .
, . , .
, . ( ) . .
, . . .
, . .
: , ... .
:
1) ( )
2) , . : , , .
3) . .
4) , . . ,
5) , , . , . , , .
:
1) ?
2) ?
3) ?
:
1) ?
2) ?
1. . .- .: , 2002.- 120 .
2. .. : . . / .. .- .: , 2007.- 192 .
3. .. . ¾ .: , 2003.
4. . . ¾ .: , 1998
: .
.
.
. , , , , . , . , , .
i- :
Li={(ai,k, bi,k)}., <=k<=n
n - I,
ai,k , I,
bi,k - , I ai,k
: , , .. aik=(di,k,fi,k,ti, k),
di,k ,fi,k ,
ti,k .
, aj,k=aj,l,
ci,k dj,l < Ad
fi,k fj,l < Af
ti,k tj,l < At
:
li,k = (aj,k, bj,k),
Ai = {ai,k},
Bi = {bi,k},
S1() - . I j ( ):
Mi,j = S1(Li ∩᷅ Lj) / max (S1(Li),S1(Lj)).
j I
mi,j=S1(Li ∩ Lj) / S1(Li)
. , , I Ai,l Bi,l, j Bj,l. , , I j :
pi,j = S1(Ai ∩ Aj) / S1(Aj)
, , , , , . , ui,j.
: , I j = 0, ui,j = 0; 2) ui,j ( ) I j . ( ), , . : , , ( ).
, . , , . , , . +/- , , . , , .
.
1) i- ?
2)
?
3) . ?
5. . .- .: , 2002.- 120 .
6. .. : . . / .. .- .: , 2007.- 192 .
7. .. . ¾ .: , 2003.
8. . . ¾ .: , 1998
:
.
.
. , , :
1) . , . I.
I(x+y)=x+y
2) () , .. -. (I+x)
(I+x)(y+z)=y+z+xy+xz
3) , , , y: (I+x+xy)
(I+x+xy)(y+z)=y+z+xy+xz+xyy+xyz
4) , , , - .
(I+x+xy+xyx)
, . , , , , - . , , , , , .. . . , , . . . . Y . X Y. , Y , Y . , :
S1)
S2)
Y , , S1, S2 .
: W1=x+y+M+M1+M2++Mn+x(x+y+M+M1+M2++Mn)
: W2=W1+Si, i=1 2
, , , , .. . . Si, , . , , . . I+x Si , .
. . , , (, , ) . , - , ( ) (I+x+xy)
W3=(I+x+xy)W2=(I+x+xy)W1+Si+xSi+xySi
Si xySi , , ?
. . , . , Y 0 X I+x+xy. Y , . , , .
:
1) , .. .
2) , , , . , , .. .
:
1. ?
2. ?
9. . .- .: , 2002.- 120 .
10. .. : . . / .. .- .: , 2007.- 192 .
11. .. . ¾ .: , 2003.
12. . . ¾ .: , 1998
: .
.
.
. , , .
, . . , , , :
=666 |
= |
( )
, , . , 5 :
.
3 , 1. 3 1.
. , . , , , , . . , , . .
, , , . . , .
, . , : , ... , . , .
, , , . , (k ).
. t; . ki ti, .
- (- ), Si- , . , .
Wi,Wi+1Wn. , , , , .
, , . , . , , .
1. ?
2. ?
3.. ?
1. .