Industrial Applications of Genetic Algorithms:Data Mining Using Genetic Algorithms

Previous | Table of Contents | Next

## Chapter 9
Data Mining Using Genetic Algorithms

Darrin J. Marshall

NCR Corporation
17095 Via Del Campo
San Diego, CA 92127
email: darrin.marshall@sandiegoca.ncr.com

ABSTRACT

Data mining involves sifting through very large databases in search of frequently occurring patterns to detect trends and produce generalizations about the data content. This chapter describes an approach, using genetic algorithms, to search through, or “mine,” a large set of database transactions in order to determine a relationship between the transactions. Consider an example database consisting of transactions representing products purchased at a retail store. This genetic algorithm implementation focuses on determining, out of 100 possible items, the four items that are most often purchased together. Information of this sort can be used by businesses to aid in inventory, sales, and marketing strategy planning. For example, such information can allow a business to focus on marketing opportunities that encompass sets or groups of products and thus maximize their advertising dollars.

INTRODUCTION

With the widespread proliferation of powerful and affordable computing and information gathering devices, we have seen a dramatic increase in the amount of electronic data that is being obtained and stored. It has been estimated that the amount of electronic information in the world doubles every 20 months, and the size and number of databases that store this information are increasing even faster [1].

Given that we have vast amounts of data stored and available to us, and new mountains of information are being gathered each day with every credit card and point-of-sale bar code transaction, businesses are now faced with the task of making use of all this information. For instance, one of the countries largest retailers, Wal-Mart, as of 1995, had 65 weeks of point-of-sale transaction data on-line, taking up more than 3.5 terabytes of storage [2]. Considering that one terabyte of data is equivalent to approximately two million books, it is obvious that new and powerful techniques will be required to make effective use of this much information.

It is generally recognized within the business community that there is untapped value in large databases [3]. It is also recognized that this information is vital to business operations, and that decision-makers need to make use of the stored data in order to be competitive. To accomplish this, the large businesses that own these terabytes of data have turned to what is being called “data mining.” Data mining employs methodologies to sift through huge databases in search of frequently occurring patterns to detect trends and produce generalizations about the data content. As one might suspect, this type of analysis not only requires the use of very sophisticated and powerful computers, designed specifically for the purpose of managing large amounts of data, but it also requires data mining application software that can efficiently and effectively search through vast amounts of data in order to recognize the possible relationships that exist.

Data mining encompasses many technologies and techniques which are used to identify “hidden” pieces of information within a database. Current technologies and techniques employed in many data mining environments include parallel computer architectures, relational database management systems (RDMS), data warehouses (which organize data in such a way that retrieval and analysis is greatly facilitated), and often, artificial intelligence and neural networks. These technologies, although important in the overall implementation of a data mining environment, are beyond the scope of the application examined in this chapter.

This chapter focuses solely on a genetic algorithm-based search technique that can be used in data mining to aid in determining relationships that may exist within a data set. In order to determine what relationships exist, many combinations of transaction comparisons and database queries must take place. Depending on the nature of the data and the relationships that are being sought, millions of data attribute combinations may have to be investigated.

For example, consider a database that contains N transactions, where each transaction consists of a list of items purchased. Also, assume that there are 100 different items that can appear in a transaction. Now, consider an effort to determine the four items that are most often purchased together. This implies that there are 100 items chosen 4 at a time, or 3,921,225 combinations of items available for investigation. If any useful output from the data mining tool is expected within a reasonable amount of time, an exhaustive comparison of all possible combinations is probably not feasible. Instead, an efficient and effective search technique is required for relationship discovery. This is where a genetic algorithm comes into play, and it is this problem that is addressed in this chapter.

The remainder of this chapter will review current data mining search techniques, describe the problem that was solved using a genetic algorithm, present the specifics of the genetic algorithm that was developed, and present the results of simulations that were run to test and analyze different aspects of the genetic algorithm in the data mining problem domain.

Previous | Table of Contents | Next

Copyright © CRC Press LLC