lookups in the data, and using algorithms such as nearest neighbor classifiers ( Margineantu & Dietterich, 1997) ?

After some of the most remarkable recent studies in voting classification algorithms, some authors have pointed out the interest to bring this classification power to data mining, and more precisely to make interpretability a clear issue in voting classification algorithms (Bauer & Kohavi, 1999; Ridgeway, Madigan, Richardson, & O'Kane, 1998). Some authors go even further, and argue that the importance of interpretability has been marginalized in the design of these algorithms, and put behind the need to devise classifiers with strong classification power (Ridgeway et al., 1998). But interpretability also governs the quality of a model by providing answers to how it is working, and, most importantly, why. According to Bauer & Kohavi (1999), striving for comprehensibility in voting models is one of the principal problems requiring future investigations.  They also remark that "voting techniques usually result in incomprehensible classifiers that cannot easily be shown to users".

Comprehensibility is, on the other hand, a hard mining issue (Buja & Lee, 2001) :
it depends on parameters such as the type of classifiers used, the algorithm inducing the classifiers, the user mining the outputs, etc. . Though the quantification of interpretability is still opened in the general case (Buja & Lee, 2001), there are some clues coming from theory and practice of machine learning/data mining indicating some potentially interesting requirements and compromises to devise an efficient learning/mining algorithm.

A first requirement for the algorithm is obviously its generalization abilities: without classification strength, it is pointless to search for interesting models of the data. A second requirement, more related to mining, is the size of the classifiers (Nock & Gascuel, 1995; Nock & Jappy, 1998). If accurate, a classifier with restricted size can lead to faster and deeper understanding. This is obviously not an absolute rule, rather an approximate proxy for interpretability : pathologic cases exist in which, for example, a large and unbalanced tree can be very simple to understand (Buja & Lee, 2001). Note that in this example, the authors explain that the tree is simple because all its nodes can be described using few clauses. Therefore, simplicity is also associated to a short description, but using a particular class of concept representation.

A third parameter influencing comprehensibility is the nature of the algorithm's output.

Inside the broad scope of symbolic classifiers, some classes of concept representations appear to offer a greater comfort for interpretation. Decision trees belong to this set (Breiman, Freidman, Olshen, & Stone, 1984), though they also raise some interpretability problems : Kohavi & Sommerfield (1998) quote that
"the clients [business users] found some interesting patterns in the decision trees, but they did not feel the structure was natural for them. They were looking for those two or three attributes and values ( e.g. a combination of geographic and industries) where something "interesting" was happening. In addition, they felt it was too limiting that the nodes in a decision tree represent rules that all start with the same attributes."
Although not limiting from a classification viewpoint, the ordering of nodes prior to classification can therefore make it uncomfortable to mine a decision tree. Notice that this problem might hold for any class of concept representation integrating an ordering prior to classification: decision lists (Rivest, 1987), alternating decision trees (Freund & Mason,