Диссертация (1137435), страница 21
Текст из файла (страница 21)
b e g i n ( ) , x . end ( ) ) ;int s z = 1 ;f o r ( int i = 1 ; i < x . s i z e ( ) ; ++i ) {i f ( x [ i ] != x [ i − 1 ] ) {x [ sz ] = x [ i ] ;++s z ;}}x . r e s i z e ( sz ) ;sz = 0;f o r ( int i = 0 ; i < x . s i z e ( ) ; ++i ) {bool ok = true ;f o r ( int j = 0 ; j < x . s i z e ( ) ; ++j ) {i f ( ! minimize ) {i f ( j != i && i s _ s u b s e t ( x [ j ] , x [ i ] ) ) {184ok = f a l s e ;break ;}} else {i f ( j != i && i s _ s u b s e t ( x [ i ] , x [ j ] ) ) {ok = f a l s e ;break ;}}}i f ( ok ) {x [ sz ] = x [ i ] ;++s z ;}}x .
r e s i z e ( sz ) ;}v e c t o r <mset> f i n d _ s h a r e d _ h y p o t h e s e s ( const v e c t o r <Context>& pK, constv e c t o r <Context>& nK) {v e c t o r <mset> r e t ;v e c t o r <mset> neg ;f o r ( int i = 0 ; i < nK . s i z e ( ) ; ++i ) {f o r ( int j = 0 ; j < nK [ i ] .
o b j e c t s . s i z e ( ) ; ++j ) {neg . push_back (nK [ i ] . o b j e c t s [ j ] ) ;185}}maximize ( neg ) ;mset X, nX ;while ( ( nX = n e x t _ c l o s u r e (X, pK) ) != X) {X = nX ;bool ok = true ;f o r ( int j = 0 ; j < neg . s i z e ( ) ; ++j ) {i f ( i s _ s u b s e t ( neg [ j ] , X) ) {ok = f a l s e ;break ;}}i f ( ok ) {r e t . push_back (X) ;i f ( r e t . s i z e ( ) % 50 == 0 )c o u t << " . " ;}}c o u t << e n d l ;return r e t ;}mset next_closure_JSM ( const mset& X, const Context& K) {int m = K.M;186f o r ( int i = m − 1 ; i >=0 ; −−i ) {mset Y;bool ok = true ;f o r ( int j = 0 ; j < X.
s i z e ( ) ; ++j ) {i f (X[ j ] == i ) {ok = f a l s e ;break ;} e l s e i f (X[ j ] < i )Y. push_back (X[ j ] ) ;elsebreak ;}i f ( ok ) {Y. push_back ( i ) ;Y = K. c l o s u r e (Y) ;ok = true ;int j = 0 , k = 0 ;while ( j < X. s i z e ( ) && k < Y. s i z e ( ) ) {i f (X[ j ] >= i | | Y[ k ] >= i )break ;i f (X[ j ] != Y[ k ] ) {ok = f a l s e ;break ;}++j ;++k ;187}i f ( j < X. s i z e ( ) )i f (X[ j ] < i )ok = f a l s e ;i f ( k < Y.
s i z e ( ) )i f (Y[ k ] < i )ok = f a l s e ;i f ( ok )return Y;}}return X;}v e c t o r <mset> f i n d _ h y p o t h e s e s ( const Context& pK, const Context& nK,double stab_thr ) {v e c t o r <mset> r e t ;v e c t o r <mset> neg ;f o r ( int j = 0 ; j < nK .
o b j e c t s . s i z e ( ) ; ++j ) {neg . push_back (nK . o b j e c t s [ j ] ) ;}maximize ( neg ) ;Context K, Kt ;f o r ( int i = 0 ; i < neg . s i z e ( ) ; ++i )K. o b j e c t s . push_back ( neg [ i ] ) ;188f o r ( int i = 0 ; i < pK . o b j e c t s . s i z e ( ) ; ++i )K. o b j e c t s . push_back (pK . o b j e c t s [ i ] ) ;K.M = pK .M;int M = K.M;Kt .M = K. o b j e c t s . s i z e ( ) ;f o r ( int j = 0 ; j < M; ++j ) {Kt . o b j e c t s . push_back ( mset ( ) ) ;}f o r ( int i = 0 ; i < K. o b j e c t s .
s i z e ( ) ; ++i ) {f o r ( int j = 0 ; j < K. o b j e c t s [ i ] . s i z e ( ) ; ++j ) {int a = K. o b j e c t s [ i ] [ j ] ;Kt . o b j e c t s [ a ] . push_back ( i ) ;}}mset X, nX ;while ( ( nX = next_closure_JSM (X, Kt ) ) != X) {X = nX ;bool done = f a l s e ;f o r ( int i = 0 ; i < X. s i z e ( ) ; ++i )i f (X[ i ] < neg . s i z e ( ) )done = true ;i f ( done )break ;mset Z ;189i f (X.
s i z e ( ) > 0 ) {Z = K. o b j e c t s [X [ 0 ] ] ;f o r ( int i = 1 ; i < X. s i z e ( ) ; ++i )Z = g e t _ i n t e r s e c t i o n ( Z , K. o b j e c t s [X[ i]]) ;}i f ( stab_thr < 1 e−5 | | s t a b i l i t y ( Z , K) > stab_thr )r e t . push_back (Z) ;i f ( r e t . s i z e ( ) % 50 == 0 )c o u t << " .
" ;}c o u t << e n d l ;return r e t ;}int c l a s s i f y ( const v e c t o r <mset>& pH , const v e c t o r <mset>& nH , const mset& X) {int pos = 0 ;f o r ( int i = 0 ; i < pH . s i z e ( ) ; ++i )i f ( i s _ s u b s e t (X, pH [ i ] ) )++pos ;int neg = 0 ;f o r ( int i = 0 ; i < nH . s i z e ( ) ; ++i )i f ( i s _ s u b s e t (X, nH [ i ] ) )190++neg ;i f ( pos > 0 && neg == 0 )return 1 ;i f ( neg > 0 && pos == 0 )return −1;return 0 ;}int main ( ) {// f r e o p e n (" o u t p u t .
t x t " , "w" , s t d o u t ) ;const double s t a b i l i t y _ t h r e s h o l d = 0 . 6 5 ;const int s u p p o r t = 2 0 ;v e c t o r <Context> pK, nK ;r e a d _ a l l (pK, nK, true , s u p p o r t ) ;v e c t o r <mset> pH , nH ;pH = f i n d _ s h a r e d _ h y p o t h e s e s (pK, nK) ;maximize (pH , true ) ;nH = f i n d _ s h a r e d _ h y p o t h e s e s (nK, pK) ;maximize (nH , true ) ;c o u t << "no␣ n e g a t i v e ␣ h y p o t h e s e ␣=␣" << nH .
s i z e ( ) << e n d l ;c o u t << "no␣ p o s i t i v e ␣ h y p o t h e s e ␣=␣" << pH . s i z e ( ) << e n d l ;191v e c t o r <Context> tpK , tnK ;r e a d _ a l l ( tpK , tnK , f a l s e , s u p p o r t ) ;int t o t a l = 0 ;int e r r o r = 0 ;int mis = 0 ;f o r ( int i = 0 ; i < tpK . s i z e ( ) ; ++i ) {f o r ( int j = 0 ; j < tpK [ i ] . o b j e c t s . s i z e ( ) ; ++j ) {int r e s = c l a s s i f y (pH , nH , tpK [ i ] . o b j e c t s [ j ] ) ;i f ( r e s == 0 )++mis ;i f ( r e s == −1)++e r r o r ;++t o t a l ;}f o r ( int j = 0 ; j < tnK [ i ] . o b j e c t s . s i z e ( ) ; ++j ) {int r e s = c l a s s i f y (pH , nH , tnK [ i ] .
o b j e c t s [ j ] ) ;i f ( r e s == 0 )++mis ;i f ( r e s == 1 )++e r r o r ;++t o t a l ;}}192c o u t << " t o t a l ␣ " << t o t a l << "␣ e r r o r s ␣=␣" << e r r o r << "␣ mis se d ␣=␣ " << mis << e n d l ;c o u t << " c l a s s i c ␣JSM␣==================\n" ;total = 0;error = 0;mis = 0 ;f o r ( int i = 0 ; i < pK .
s i z e ( ) ; ++i ) {pH = f i n d _ h y p o t h e s e s (pK [ i ] , nK [ i ] , s t a b i l i t y _ t h r e s h o l d );maximize (pH , true ) ;c o u t << "no␣ p o s i t i v e ␣ h y p o t h e s e ␣ [ "<< i <<" ] ␣=␣" << pH .s i z e ( ) << e n d l ;nH = f i n d _ h y p o t h e s e s (nK [ i ] , pK [ i ] , s t a b i l i t y _ t h r e s h o l d );maximize (nH , true ) ;c o u t << "no␣ n e g a t i v e ␣ h y p o t h e s e ␣ [ " << i << " ] ␣=␣" << nH .s i z e ( ) << e n d l ;int c t o t a l = 0 ;int c e r r o r = 0 ;int cmis = 0 ;f o r ( int j = 0 ; j < tpK [ i ] .
o b j e c t s . s i z e ( ) ; ++j ) {int r e s = c l a s s i f y (pH , nH , tpK [ i ] . o b j e c t s [ j ] ) ;i f ( r e s == 0 )193++cmis ;i f ( r e s == −1)++c e r r o r ;++c t o t a l ;}f o r ( int j = 0 ; j < tnK [ i ] . o b j e c t s . s i z e ( ) ; ++j ) {int r e s = c l a s s i f y (pH , nH , tnK [ i ] . o b j e c t s [ j ] ) ;i f ( r e s == 0 )++cmis ;i f ( r e s == 1 )++c e r r o r ;++c t o t a l ;}c o u t << " t o t a l ␣" << c t o t a l << "␣ e r r o r s ␣=␣" << c e r r o r <<"␣ m is sed ␣=␣" << cmis << "===\n" ;t o t a l += c t o t a l ;mis += cmis ;e r r o r += c e r r o r ;}c o u t << " t o t a l ␣ " << t o t a l << "␣ e r r o r s ␣=␣" << e r r o r << "␣ mis se d ␣=␣ " << mis << e n d l ;194return 0 ;}.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
