Search techniques
Weixiong Zhang · 2002
Search plays an important role in knowledge discovery in databases (KDD) and data mining. Given hypothesis representation schemas and hypothesis evaluation criteria, a search process explores a hypothesis space to find useful knowledge from given data. The effectiveness and efficiency of the underlying search methods determine the success and performance of the overall KDD process. In this chapter, we briefly describe the basic concepts of hypothesis space and hypothesis evaluation, discuss in detail the basic search techniques, and highlight their performance and complexity. Particularly, we consider systematic enumerative search methods, including best-first search, depth-first branch-and-bound and iterative deepening, and neighborhood search methods, including gradient descent, artificial neural networks, tabu search, and simulated annealing. We also describe beam search, complete beam search, and genetic algorithms.