Abstract
The concept of Quantitative Structure-Activity Relationship (QSAR), introduced by Hansch and co-workers in the 1960s, attempts to discover the relationship between the structure and the activity of chemical compounds (SAR), in order to allow the prediction of the activity of new compounds based on knowledge of their chemical structure alone. These predictions can be achieved by quantifying the SAR. Initially, statistical methods have been applied to solve the QSAR problem. For example, pattern recognition techniques facilitate data dimension reduction and transformation techniques from multiple experiments to the underlying patterns of information. Partial least squares (PLS) is used for performing the same operations on the target properties. The predictive ability of this method can be tested using cross-validation on the test set of compounds. Later, data mining techniques have been considered for this prediction problem. Among data mining techniques, the most popular ones are based on neural networks (Wang, Durst, Eberhart, Boyd, & Ben-Miled, 2004) or on neuro-fuzzy approaches (Neagu, Benfenati, Gini, Mazzatorta, & Roncaglioni, 2002) or on genetic programming (Langdon, &Barrett, 2004). All these approaches predict the activity of a chemical compound, without being able to explain the predicted value. In order to increase the understanding on the prediction process, descriptive data mining techniques have started to be used related to the QSAR problem. These techniques are based on association rule mining. In this chapter, we describe the use of association rule-based approaches related to the QSAR problem.
TopBackground
Association rule mining, introduced by (Agrawal, Imielinski & Swami, 1993), is defined as finding all the association rules between sets of items in a database that hold with more that a user-given minimum support threshold and a user-given minimum confidence threshold. According to (Agrawal, Imielinski & Swami, 1993) this problem is solved in two steps:
- 1.
Finding all frequent itemsets in the database.
- 2.
For each frequent itemset I, generating all association rules I’⇒I\I', where I'⊂I.
The second problem can be solved in a straightforward manner after the first step is completed. Hence, the problem of mining association rules is reduced to the problem of finding all frequent itemsets. This is not a trivial problem, since the number of possible frequent itemsets is equal to the size of the power set of I, 2|I|.
There are many algorithms proposed in the literature, most of them based on the Apriori mining method (Agrawal & Srikant, 1994) that relies on a basic property of frequent itemsets: all subsets of a frequent itemset are frequent. This property can also be stated as all supersets of an infrequent itemset are infrequent. There are other approaches, namely the closed-itemset approaches, as Close (Pasquier, Bastide, Taouil & Lakhal, 1999), CHARM (Zaki & Hsiao, 1999) and Closet (Pei, Han & Mao, 2000). The closed-itemset approaches rely on the application of Formal Concept Analysis to association rule problem that was first mentioned in (Zaki & Ogihara, 1998). For more details on lattice theory see (Ganter & Wille, 1999). Another approach leading to a small number of results is finding representative association rules (Kryszkiewicz, 1998).
The difference between Apriori-based and closed itemset-based approaches consists in the treatment of sub-unitary confidence and unitary confidence association rules, namely Apriori makes no distinction between them, while FCA-based approaches report sub-unitary association rules (also named partial implication rules) structured in a concept lattice and, eventually, the pseudo-intents, a base on the unitary association rules (also named global implications, exhibiting a logical implication behavior). The advantage of a closed itemset approach is the smaller size of the resulting concept lattice versus the number of frequent itemsets, i.e. search space reduction.