Explore chapters and articles related to this topic
Signature Generation Algorithms for Polymorphic Worms
Published in Mohssen Mohammed, Al-Sakib Khan Pathan, Automatic Defense Against Zero-day Polymorphic Worms in Communication Networks, 2016
Mohssen Mohammed, Al-Sakib Khan Pathan
Classification rules represent each class by disjunctive normal form (DNF). A k-DNF expression is of the form: (X1^X2^…^Xn) ∨ (Xn + 1^ Xn + 2^…X2n) ∨ … ∨ (X(k-1)n+1 ∨ X(k-1)n+2 ∨ … ∨ Xkn, where k is the number of disjunctions, n is the number of conjunctions in each disjunction, and Xn is defined over the alphabet X1, X2, ... , Xj ∪ ~ X1, ~ X2, ... ,~ Xj. The goal is to construct the smallest rule set that is consistent with the training data. A large number of learned rules is usually a sign that the learning algorithm is attempting to “remember” the training set, instead of discovering the assumptions that govern it. A separate-and-conquer algorithm (covering algorithms) search for a rule that explains a part of its training instances separates these instances and recursively conquers the remaining instances by learning more rules until no instances remain. A general pseudocode for rule learners is as follows [16]:
Medical diagnosis and treatment is NP-complete
Published in Journal of Experimental & Theoretical Artificial Intelligence, 2021
Jeffrey. E. Arle, Kristen W. Carlson
Can all MDT be put into DNF? In general, the computational cost is prohibitive. There exist automated procedures for transforming a general Boolean function, or pure CNF, into DNF. But all known algorithms that can reduce a general expression to a minimal size are either exponential, e.g., Quine-McCluskey, or NP-hard (Wolfram, 2002). If arbitrary size is allowed, the ‘blow-up’ in DNF derived from CNF is O(2(n-c(n/log(m/n)))), where |CNF| < m and c is a constant (Miltersen et al., 2005). Expressions of up to 12 variables are tractable (Wolfram, 2002); therefore, while diagnostic variables may exceed 12, which is notably the trend in GWAS studies (International Common Disease Alliance, 2019), the number of dominant factors may generally permit automated CNF-to-DNF methods.
Some fuzzy measure modeled multi-criteria formulations
Published in International Journal of General Systems, 2020
In the following discussion we shall use the term “literal” to indicate a criteria, Ck, or its negation, Ck. A logical formula is in disjunctive normal form, DNF, if it is a disjunction, sequence of ors, consisting of one or more disjuncts, where each disjunct is a conjunction, an anding, of one or more literals (Mendelson 1964). Here then Here each disjunct Dk, is of the form where each Li, literal, is an element from C or the negation of an element from C, C5. The following is an example of a statement in DNF We shall say a DNF is pure if none of the literals involve the negation, all the literals in any Dk are simply elements from C.
A Comparison of Lucene Search Queries Evolved as Text Classifiers
Published in Applied Artificial Intelligence, 2018
Laurence Hirsch, Teresa Brunsdon
A DNF (“disjunctive normal form”) formula is a disjunction of conjunctive clauses. The document is classified under a category if it satisfies the formula, i.e. if it satisfies at least one of the conjunctive clauses. An oft quoted example of this approach is the CONSTRUE system (Hayes et al. 1990), built by the Carnegie Group for the Reuters news agency. A sample rule of the type used in CONSTRUE to classify documents in the “wheat” category of the Reuters dataset is given below.