Диссертация (1137435), страница 17
Текст из файла (страница 17)
4th Inernational Conference on FormalConcept Analysis (ICFCA’2006), Lecture Notes in Artificial Intelligence(LNAI), vol. 3874, p.89–104, Springer 2006.80. Loshin D. Master Data Management // Morgan Kaufmann Publishers,2009.81. Mannila H., Räihä K. The design of relational databases // AddisonWesley, 1992.13182. Mohammed Z.J. Scalable algorithms for association mining // IEEETransactions on Knowledge and Data Engineering, vol. 12(3), p.372–390,2000.83. Motwani R., Raghavan P.
Randomized Algorithms // CambridgeUniversity Press, 1995.84. Nienhuys-Cheng S.-H., Wolf R. Foundations of Inductive LogicProgramming, // Lecture Notes in Artificial Intelligence, vol. 1228, 1997.85. Obiedkov S.A., Roth C., Kourie D.G. On Succinct Representation ofKnowledge Community Taxonomies with Formal Concept Analysis // Int.J. Found.
Comput. Sci., 19(2), p.383–404, 2008.86. Obiedkov S.A., Roth C., Kourie D.G. Towards Concise Representationfor Taxonomies of Epistemic Communities // Proc. 4th InternationalConference Concept Lattices and Their Applications (CLA’2006), p.240–255, 2008.87.
Piatetsky-Shapiro G. Discovery, Analysis, and Presentation of StrongRules // Knowledge Discovery in Databases, p.229–248, 1991.88. Poelmans J., Elzinga P., Neznanov A., Dedene G., Viaene S., KuznetsovS.O. Human-Centered Text Mining: A New Software System // ICDM2012, p.258–272, 2012.89. Priss U.
Some open problems in Formal Concept Analysis // Proc. ICFCA2006, 2006.90. Rudolph S. Some notes on pseudo-closed sets // Proc. ICFCA 2007,Lecture Notes in Computer Science, vol. 4390, p.151–165, Springer, 2007.13291. Sertkaya B. Towards the complexity of recognizing pseudo-intents // Proc.ICCS 2009, Lecture Notes in Computer Science, vol. 5662, p.284–292,Springer, 2009.92. Sertkaya B. Some computational problems related to pseudo-intents //Proc.
ICFCA 2009, Lecture Notes in Computer Science, vol. 5662, p.284–292, Springer, 2009.93. Singh K., Singh R. A Descriptive Classification of Causes of Data QualityProblems in Data Warehousing // International Journal of ComputerScience Issue, vol. 7, Issue 3, No. 2, 2010.94. Solomonoff R.J. A formal theory of inductive inference // Information andControl, vol. 7, p.
224–254, 1964.95. Valiant L.G. The complexity of computing the permanent // TheoreticalComputer Science, 8, No. 2, p.189–201, 1979.96. Valiant L.G. The Complexity of Enumeration and Reliability Problems //SIAM J. Comput., 8, no. 3, p.410–421, 1979.97. Valiant L.G. A theory of the learnable // Commun. ACM, 27, no. 11,p.1134–1142, 1984.98. Wille R.
Restructuring Lattice Theory: an Approach Based on Hierarchiesof Concepts // Ordered Sets, Reidel, p.445–470, Dordrecht–Boston, 1982.99. Wille R. Conceptual Structure of Multicontexts // Proc. 4th InternationalConference on Conceptual Structures, Lecture Notes in ArtificialIntelligence (LNAI), vol. 1115, p.23–39, Springer, 1996.133100. Сайт репозитория машинного обучения UCIhttp://archive.ics.uci.edu/ml/134Приложения5.5.Приложение 1.1Файл mset.h:#i f n d e f MSET_H#define MSDET_H#include <v e c t o r >#include <a l g o r i t h m >typedef s t d : : v e c t o r <int> mset ;mset rand_set ( int M, double p ) ;mset get_union ( const mset& A, const mset& B) ;mset g e t _ i n t e r s e c t i o n ( const mset& A, const mset& B) ;bool i s _ s u b s e t ( const mset& s u p e r s e t , const mset& s u b s e t ) ;void p r i n t ( const mset& s , int M) ;135#endifФайл mset.cpp:#include " mset .
h"#include < s t d l i b . h>mset get_union ( const mset& A, const mset& B) {mset r e t ;bool ok = true ;f o r ( int i = 1 ; i < A. s i z e ( ) ; ++i ) {i f (A[ i ] < A[ i − 1 ] ) {ok = f a l s e ;break ;}}i f ( ok ) {f o r ( int i = 1 ; i < B . s i z e ( ) ; ++i ) {i f (B [ i ] < B [ i − 1 ] ) {ok = f a l s e ;break ;}}}i f ( ok ) {int i = 0 ;136int j = 0 ;while ( i < A.
s i z e ( ) && j < B . s i z e ( ) ) {i f (A[ i ] < B [ j ] ) {r e t . push_back (A[ i ] ) ;++i ;} e l s e i f (A[ i ] > B [ j ] ) {r e t . push_back (B [ j ] ) ;++j ;} else {r e t . push_back (A[ i ] ) ;++i ;++j ;}}f o r ( ; i < A. s i z e ( ) ; ++i )r e t . push_back (A[ i ] ) ;f o r ( ; j < B . s i z e ( ) ; ++j )r e t . push_back (B [ j ] ) ;} else {int n = 0 ;f o r ( int i = 0 ; i < A. s i z e ( ) ; ++i )n = s t d : : max( n , A[ i ] + 1 ) ;f o r ( int i = 0 ; i < B . s i z e ( ) ; ++i )n = s t d : : max( n , B [ i ] + 1 ) ;s t d : : v e c t o r <bool> used ( n , f a l s e ) ;137f o r ( int i = 0 ; i < A. s i z e ( ) ; ++i )used [A[ i ] ] = true ;f o r ( int i = 0 ; i < B .
s i z e ( ) ; ++i )used [ B [ i ] ] = true ;f o r ( int i = 0 ; i < n ; ++i )i f ( used [ i ] )r e t . push_back ( i ) ;}return r e t ;}mset g e t _ i n t e r s e c t i o n ( const mset& A, const mset& B){mset r e t ;bool ok = true ;f o r ( int i = 1 ; i < A. s i z e ( ) ; ++i ) {i f (A[ i ] < A[ i − 1 ] ) {ok = f a l s e ;break ;}}i f ( ok ) {f o r ( int i = 1 ; i < B . s i z e ( ) ; ++i ) {i f (B [ i ] < B [ i − 1 ] ) {ok = f a l s e ;break ;138}}}i f ( ok ) {int i = 0 ;int j = 0 ;while ( i < A.
s i z e ( ) && j < B . s i z e ( ) ) {i f (A[ i ] < B [ j ] )++i ;e l s e i f (A[ i ] > B [ j ] )++j ;else {r e t . push_back (A[ i ] ) ;++i ;++j ;}}} else {int n = 0 ;f o r ( int i = 0 ; i < A. s i z e ( ) ; ++i )n = s t d : : max( n , A[ i ] + 1 ) ;f o r ( int i = 0 ; i < B . s i z e ( ) ; ++i )n = s t d : : max( n , B [ i ] + 1 ) ;s t d : : v e c t o r <unsigned char> used ( n , 0 ) ;f o r ( int i = 0 ; i < A. s i z e ( ) ; ++i )++used [A[ i ] ] ;139f o r ( int i = 0 ; i < B . s i z e ( ) ; ++i )++used [ B [ i ] ] ;f o r ( int i = 0 ; i < n ; ++i )i f ( used [ i ] == 2 )r e t .
push_back ( i ) ;}return r e t ;}bool i s _ s u b s e t ( const mset& s u p e r s e t , const mset& s u b s e t ) {i f ( superset . s i z e () < subset . s i z e () )return f a l s e ;int i = 0 , j = 0 ;bool r e t = true ;while ( i < s u b s e t . s i z e ( ) && j < s u p e r s e t . s i z e ( ) ) {i f ( subset [ i ] < superset [ j ] )return f a l s e ;i f ( s u b s e t [ i ] == s u p e r s e t [ j ] ) {++i ; ++j ;}else++j ;}return i >= s u b s e t .
s i z e ( ) ;}140void p r i n t ( const mset& s , int M) {s t d : : v e c t o r <bool> a (M, f a l s e ) ;f o r ( int i = 0 ; i < s . s i z e ( ) ; ++i )a [ s [ i ] ] = true ;f o r ( int i = 0 ; i < M; ++i ) {if (a [ i ])p r i n t f ( "1" ) ;elsep r i n t f ( "0" ) ;}}mset rand_set ( int M, double p ) {mset r e t ;// d o u b l e p = 0 . 5 ;f o r ( int i = 0 ; i < M; ++i )i f ( ( double ) rand ( ) / RAND_MAX >= p )r e t . push_back ( i ) ;return r e t ;}5.6.Приложение 1.2Файл implications.h:#i f n d e f IMPLICATIONS_H#define IMPLICATIONS_H141#include <v e c t o r >#include <a l g o r i t h m >#include " mset .
h"namespace i m p l i c a t i o n s {struct I m p l i c a t i o n {int n u m b e r _ o f _ a t t r i i b u t e s ;mset l e f t ;mset r i g h t ;bool operator < ( const I m p l i c a t i o n& I ) const{i f ( n u m b e r _ o f _ a t t r i i b u t e s != I .number_of_attriibutes )return n u m b e r _ o f _ a t t r i i b u t e s < I .number_of_attriibutes ;i f ( l e f t != I . l e f t )return l e f t < I .
l e f t ;return r i g h t < I . r i g h t ;}bool operator != ( const I m p l i c a t i o n& I ) const{i f ( n u m b e r _ o f _ a t t r i i b u t e s != I .number_of_attriibutes )return true ;142return l e f t != I . l e f t| | r i g h t != I . r i g h t ;}bool operator == ( const I m p l i c a t i o n& I ) const{i f ( n u m b e r _ o f _ a t t r i i b u t e s != I .number_of_attriibutes )return f a l s e ;return l e f t == I . l e f t && r i g h t == I . r i g h t ;}};mset l i n _ c l o s u r e ( const s t d : : v e c t o r <I m p l i c a t i o n >& i m p l i c a t i o n s ,const mset& X) ;s t d : : v e c t o r <I m p l i c a t i o n > find_min_base ( const s t d : : v e c t o r <I m p l i c a t i o n >& i m p l i c a t i o n s ) ;mset get_rand_closed1 ( const s t d : : v e c t o r <I m p l i c a t i o n >&i m p l i c a t i o n s , int M, double p = 0 .
5 ) ;mset get_rand_closed2 ( const s t d : : v e c t o r <I m p l i c a t i o n >&i m p l i c a t i o n s , int M, double p = 0 . 5 ) ;}#endifФайл implications.cpp:#include " i m p l i c a t i o n s . h"143namespace i m p l i c a t i o n s {mset get_rand_closed1 ( const s t d : : v e c t o r <I m p l i c a t i o n >&i m p l i c a t i o n s , int M, double p ) {mset X = rand_set (M, p ) ;// r e t u r n l i n _ c l o s u r e ( i m p l i c a t i o n s , X) ;while ( 1 ) {X = rand_set (M, p ) ;i f (X == l i n _ c l o s u r e ( i m p l i c a t i o n s , X) )break ;}return X;}mset get_rand_closed2 ( const s t d : : v e c t o r <I m p l i c a t i o n >&i m p l i c a t i o n s , int M, double p ) {mset X = rand_set (M, p ) ;return l i n _ c l o s u r e ( i m p l i c a t i o n s , X) ;}mset l i n _ c l o s u r e ( const s t d : : v e c t o r <I m p l i c a t i o n >& i m p l i c a t i o n s ,const mset& X) {i f ( i m p l i c a t i o n s .
s i z e ( ) == 0 )return X;int n = i m p l i c a t i o n s [ 0 ] . n u m b e r _ o f _ a t t r i i b u t e s ;s t d : : v e c t o r <bool> used ( n , f a l s e ) ;144s t d : : v e c t o r <int> r e q u i r e d ( i m p l i c a t i o n s . s i z e ( ) , 0 ) ;s t d : : v e c t o r <s t d : : v e c t o r <int> > a t t r _ i m p l i c a t i o n s ( n ) ;f o r ( int i = 0 ; i < i m p l i c a t i o n s . s i z e ( ) ; ++i ) {const mset& A = i m p l i c a t i o n s [ i ] .
l e f t ;r e q u i r e d [ i ] = A. s i z e ( ) ;f o r ( int j = 0 ; j < A. s i z e ( ) ; ++j ) {int a t r = A[ j ] ;a t t r _ i m p l i c a t i o n s [ a t r ] . push_back ( i ) ;}}s t d : : v e c t o r <int> add_right ;f o r ( int j = 0 ; j < X. s i z e ( ) ; ++j ) {int x = X[ j ] ;used [ x ] = true ;f o r ( int i = 0 ; i < a t t r _ i m p l i c a t i o n s [ x ] .
s i z e ( ); ++i ) {int impl_ind = a t t r _ i m p l i c a t i o n s [ x ] [ i ] ;−−r e q u i r e d [ impl_ind ] ;i f ( r e q u i r e d [ impl_ind ] == 0 )add_right . push_back ( impl_ind ) ;}}while ( ! add_right . empty ( ) ) {int i n d = add_right . back ( ) ;145add_right . pop_back ( ) ;const mset& A = i m p l i c a t i o n s [ i n d ] .