Clustering Algorithms for Web-Based Data Mining Searches

Introduction and Significance of the Study

Clustering in algorithms employs abstract categories for pattern matching and pattern recognition procedures used in data mining searches of web documents. With the rapid advances in data mining software technology now taking place, website managers and search engine designers have begun to struggle to maintain efficiency in "mining" for patterns of information and user behavior. Part of the problem is the enormous amount of data being generated, making real-time search of web document databases difficult. Real-time searching is critical for real-time problem solving, high-level document searches, and prevention of database security breaches.

The analysis of this problem will be followed by a detailed description of weaknesses in data mining methods, with suggestions for a reduction of preprocessing to improve performance of search engine algorithms, and a recommendation of an optimum algorithm for this task.

The first investigators who gave serious thought to the problem of algorithm speed were researchers in the area of database searches. The field is still in its infancy; most of the tools and techniques used for data mining today come from related fields such as pattern recognition, statistics, and complexity theory. Only recently have researchers from these various fields been interacting to solve mining and timing issues.

Significance of the Study

Data mining is a knowledge discovery process that uses algorithms and advanced statistical models to analyze data in accordance with a set or sets of rules, as determined by the particular current application. Data mining methods may be classified according to the functions they perform, the class of application they are used in, or the domain of the search (e.g., the Internet is now a common domain for data mining searches). On the whole, data mining models fall into three basic categories: classification, associations and sequencing, and data clustering. "Clustering" assembles documents into related groups, or clusters, without relying on predefined categories. It essentially provides a visual map of the documents, with links between related documents, making it easy to browse through a collection, extracting multiple documents or a particular topic. The principal scholarly contribution of this study will be a refinement of the testing procedures for clustering algorithms, and a conclusion regarding the optimum algorithm for online real-time searches of web document databases.

The data mining process is inherently iterative: the output of one step may be sent as feedback to a previous step, as well as to the next step in the process. These steps are categorized into data pre-processing and discovered knowledge post-processing groupings. There are various techniques available to perform these tasks—classification, association, and clustering—the last of which is the focus of the present study. Data classification and association are appropriate to many data mining projects where pre-defined rules or concept categories exist, but many abstract problems require the creation of new abstract categories in order to provide the substructure for a more focused search. If the rule set is derived directly from the audit data, any slight deviations from the pattern scheme may go undetected; conversely, minor deviations from "normal behavior" can trigger false alarms. Abstract categories can mitigate this problem.

Project Design

For this project design, the procedure calls for algorithms to be selected on the basis of the common feature of abstract categories for clustering data, for the purpose of classifying data according to a generic category scheme.

The principal components of the research design are the following:

The operating system (Windows XP); the laboratory computer (a generic PC of 2.0 gigahertz processing speed); the data structures (data clustering algorithms identifying abstract categories, where data is parsed by the algorithm to yield search results); the experimental procedure (testing of the algorithms for elapsed time); evaluation of results of the speed trials (time series analysis); and conclusions (analysis of the optimum algorithm designs and recommendations for research applications).

Definitions

Class Description (Classification) — Summarization of a collection of data (class characterization). Class description includes summary properties such as count, sum, and average, as well as data dispersion measures such as variance and quartiles.

Association (Detection of Relations) — Association relationships or correlations among a set of items, expressed in rule form showing frequently occurring attribute-value conditions within a given data set. Association analysis is researched with efficient algorithms, including level-wise a priori search, mining multiple-level and multi-dimensional associations, mining associations for numerical, categorical, and interval data, meta-pattern directed or constraint-based mining, and mining correlations.

Clustering — Identifies embedded clusters in data, where a cluster is a collection of "similar" data objects as expressed by distance functions. Data mining research has focused on high-quality and scalable clustering methods for large databases and multi-dimensional data warehouses.

Time-Series Analysis — Analyzes large sets of time-series data, searching for similar sequences or sub-sequences and mining sequential patterns, periodicities, trends, and deviations.

Overview of the Methodology

The methodology employed in this project is experimental analysis, with the objective of testing the feasibility of abstract category data clustering algorithms for a real-world web application. In order to perform this test, a group of five linear-time clustering algorithms will be applied to a sample group of online web documents, simulating the activities of a web search engine looking for similar words, phrases, or sequences in a large database of web articles, publications, and records. The five techniques compared are K-Means, Single Pass, Fractionation, Buckshot, and Suffix Tree clustering algorithms.

The procedure is to measure the execution time of the test algorithms in clustering data sets consisting of whole documents, excerpts, and keywords of a fixed quantity and size. The tests are performed on a standard desktop personal computer running Microsoft Windows XP at a processing speed of at least 1 gigahertz, to simulate the real-world activities of a conventional office worker or librarian doing a document search. Times are recorded for a series of 10 tests repeated for the same group size and number of files, in order to determine the optimum clustering algorithm for real-time online web document searches.

Organisation of the Study

The proposed design method is to conduct a speed trial analysis of the various designs currently used in search engine algorithms. The initial evaluation will be followed by an analysis of the weaknesses in current algorithms and suggestions for improvement. The study comprises five chapters: Introduction/Statement of Problem, Review of Literature, Alternative Solutions, Feasibility Tests, and Evaluation and Implementation. Future testing will be performed through the implementation of the selected algorithm in a regular application of web-based document searches by a librarian's search engine.

Purpose of the Study

The purpose of this study is to conduct research that will analyze and improve the use of data clustering techniques in creating abstract categories in algorithms, allowing data analysts to conduct more efficient execution of large-scale searches. Increasing the efficiency of the search process requires detailed knowledge of abstract categories, pattern matching techniques, and their relationship to search engine speed.

Data mining involves the use of search engine algorithms looking for hidden predictive information, patterns, and correlations within large databases. The technique of data clustering divides datasets into mutually exclusive groups. The distance between groups is measured with respect to all available variables, versus variables that are specific predictors, to produce "abstract categories" for analysis. Search engine algorithms and user audit trails are complex, leading to time-consuming quests for specific information. It is anticipated that the proposed study will identify the most efficient and effective data clustering algorithms for this purpose.

Statement of Deliverables

The methodology employed is an empirical analysis of speed tests conducted on groups of similar algorithms. The execution time of the algorithms will be measured for clustering sets consisting of whole documents, excerpts, and keywords of a fixed number.

The distribution of all activity types in the search will be determined. Common features are identified within the system, and categories for clustering and classification are developed. At this stage, an abstract format or generic classification for the data can be developed, revealing how data are organized and where improvements are possible. Structural relationships within data can be revealed by such detailed analysis.

The final deliverable will be the search time trial results and the conclusions drawn with respect to the optimum algorithm designs. A definitive direction for the development of future design work is considered a desirable outcome.

Quality assurance will be implemented through systematic review of the experimental procedures and analysis of the test results. Achieving the goals stated at the delivery dates, performance of the tests, and successful completion of the project as determined by the committee members will provide quality assurance to the research outcomes.