ENTROPY BASED TECHNIQUES WITH APPLICATIONS IN DATA MINING By ANTHONY OKAFOR A DISSERTATION PRESENTED TO THE GRADUATE SCHOOL OF THE UNIVERSITY OF FLORIDA IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY UNIVERSITY OF FLORIDA 2005 Copyright 2005 by Anthony Okafor This work is dedicated to my family. ACKNOWLEDGMENTS I want to thank Professor Panos M. Pardalos for his help and patience in guiding me through the preparation and completion of my Ph.D. I also want to thank Drs. JosephP.Geunes,StanislavUraysevandWilliamHagerfortheirinsightfulcomments, valuable suggestions, constant encouragement and for serving on my supervisory committee. I also would to thank my colleagues in the graduate school of the Industrial and Systems Engineering Department especially, Don Grundel. Finally, I am especially grateful to my wife, my parents, and sister for their support and encouragement as I complete the Ph.D. program. iv TABLE OF CONTENTS page ACKNOWLEDGMENTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi CHAPTERS 1 INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Data Mining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.1 Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.2 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.3 Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.4 Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.5 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 ENTROPY OPTIMIZATION . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 A Background on Entropy Optimization . . . . . . . . . . . . . . . 4 2.2.1 Definition of Entropy . . . . . . . . . . . . . . . . . . . . . . 5 2.2.2 Choosing A Probability Distribution . . . . . . . . . . . . . . 6 2.2.3 Prior Information . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.4 Minimum Cross Entropy Principle . . . . . . . . . . . . . . . 9 2.3 Applications of Entropy Optimization . . . . . . . . . . . . . . . . . 10 3 DATA MINING USING ENTROPY . . . . . . . . . . . . . . . . . . . . 12 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2 K-Means Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.3 An Overview of Entropy Optimization . . . . . . . . . . . . . . . . 15 3.3.1 Minimum Entropy and Its Properties . . . . . . . . . . . . . 16 3.3.2 The Entropy Decomposition Theorem . . . . . . . . . . . . . 18 3.4 The K-Means via Entropy Model . . . . . . . . . . . . . . . . . . . 19 3.4.1 Entropy as a Prior Via Bayesian Inference . . . . . . . . . . 19 3.4.2 Defining the Prior Probability . . . . . . . . . . . . . . . . . 20 3.4.3 Determining Number of Clusters . . . . . . . . . . . . . . . . 20 v 3.5 Graph Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.6 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.6.1 Image Clustering . . . . . . . . . . . . . . . . . . . . . . . . 26 3.6.2 Iris Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4 DIMENSION REDUCTION . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.1.1 Entropy Dimension Reduction . . . . . . . . . . . . . . . . . 30 4.1.2 Entropy Criteria For Dimension Reduction . . . . . . . . . . 31 4.1.3 Entropy Calculations . . . . . . . . . . . . . . . . . . . . . . 31 4.1.4 Entropy and the Clustering Criteria . . . . . . . . . . . . . . 32 4.1.5 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5 PATH PLANNING PROBLEM FOR MOVING TARGET . . . . . . . . 34 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 5.1.1 Problem Parameters . . . . . . . . . . . . . . . . . . . . . . . 35 5.1.2 Entropy Solution . . . . . . . . . . . . . . . . . . . . . . . . 36 5.2 Mode 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.3 Mode 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.4 Mode 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.5 Maximizing the Probability of Detecting a Target . . . . . . . . . . 42 5.5.1 Cost Function. Alternative 1 . . . . . . . . . . . . . . . . . . 43 5.5.2 Generalization . . . . . . . . . . . . . . . . . . . . . . . . . . 44 5.5.3 Cost function. Alternative 2 and Markov Chain Model . . . 46 5.5.4 The Second Order Estimated Cost Function with Markov Chain 47 5.5.5 Connection of Multistage Graphs and the Problem . . . . . . 48 5.6 More General Model . . . . . . . . . . . . . . . . . . . . . . . . . . 51 5.6.1 The Agent is Faster Than Target . . . . . . . . . . . . . . . 51 5.6.2 Obstacles in Path . . . . . . . . . . . . . . . . . . . . . . . . 51 5.6.3 Target Direction . . . . . . . . . . . . . . . . . . . . . . . . . 52 5.7 Conclusion and Future Direction . . . . . . . . . . . . . . . . . . . 52 6 BEST TARGET SELECTION . . . . . . . . . . . . . . . . . . . . . . . 53 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 6.2 Maximize Probability of Attacking the Most Valuable Target . . . . 54 6.2.1 Best Target Strategy . . . . . . . . . . . . . . . . . . . . . . 55 6.2.1.1 Probability of Attacking jth Most Valuable Target . 56 6.2.1.2 Mean Rank of the Attacked Target . . . . . . . . . 58 6.2.1.3 Mean Number of Examined Targets . . . . . . . . . 58 6.2.2 Results of Best Target Strategy . . . . . . . . . . . . . . . . 59 6.2.3 Best Target Strategy with Threshold . . . . . . . . . . . . . 59 vi 6.3 Maximize Mean Rank of the Attacked Target . . . . . . . . . . . . 61 6.3.1 Mean Value Strategy . . . . . . . . . . . . . . . . . . . . . . 61 6.3.2 Results of Mean Value Strategy . . . . . . . . . . . . . . . . 63 6.4 Number of Targets is a Random Variable . . . . . . . . . . . . . . . 63 6.5 Target Strategy with Sampling-The Learning Agent . . . . . . . . . 66 6.6 Multiple Agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 6.6.1 Agents as a Pack . . . . . . . . . . . . . . . . . . . . . . . . 70 6.6.2 Separate Agents . . . . . . . . . . . . . . . . . . . . . . . . . 73 6.6.2.1 Separate Agents without Communication . . . . . . 74 6.6.2.2 Separate Agents with Communication . . . . . . . 75 6.6.2.3 Separate Agents Comparison . . . . . . . . . . . . 76 6.6.3 Multiple Agent Strategy-Discussion . . . . . . . . . . . . . . 77 6.7 Dynamic Threshold . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 6.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 7 CONCLUDING REMARKS AND FUTURE RESEARCH . . . . . . . . 79 7.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 7.2 Future Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 REFERENCES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 BIOGRAPHICAL SKETCH . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 vii LIST OF TABLES Table page 3–1 The number of clusters for different values of β . . . . . . . . . . . . . . 26 3–2 The number of clusters as a function of β for the iris data . . . . . . . . 28 3–3 Percentage of correct classification of iris data . . . . . . . . . . . . . . . 28 3–4 The average number of clusters for various k using a fixed β = 2.5 for the iris data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3–5 The average number of clusters for various k using a fixed β = 5.0 for the iris data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3–6 The average number of clusters for various k using a fixed β = 10.5 for the Iris Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 6–1 Significant results of the basic best target strategy . . . . . . . . . . . . . 59 6–2 Empirical results of the best target strategy with threshold at upper 1-percent tail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 6–3 Empirical results of the best target strategy with threshold at upper 2.5-percent tail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 6–4 Empirical results of the best target strategy with threshold at upper 30-percent tail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 6–5 k values to minimize mean rank of attacked targets . . . . . . . . . . . . 62 6–6 Simulation results of the best target strategy . . . . . . . . . . . . . . . . 63 6–7 Simulation results of the mean target strategy . . . . . . . . . . . . . . . 63 6–8 Simulation results with number of targets poisson distributed, mean n . 65 6–9 Simulation results with number of targets normally distributed, mean n and standard deviation 0.2n . . . . . . . . . . . . . . . . . . . . . . . . . 65 6–10 Simulation results with number of targets uniformly distributed in [0.5n,1.5n] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 6–11 Performance summary of best target strategy and mean value strategy when n varies; values are in percentage drop compared to when n is fixed 66 viii 6–12 Simulationresultswithexpectednumberoftargets, n, updated90-percent into the mission . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 6–13 Simulation results with expected number of targets, n, updated near the end of the mission. n may be updated downward, but not upward. . . . 67 6–14 Simulation results of the target strategy with sampling . . . . . . . . . . 69 6–15 Simulation results of the target strategy with m agents in a pack. Target values are uniform on [0,1000]. . . . . . . . . . . . . . . . . . . . . . . . . 73 6–16 Simulation results of the target strategy with m agents on separate missionswithnocommunicationbetweenthem. Targetvaluesareuniform on [0,1000]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 6–17 Simulation results of the target strategy with m agents on separate missions with communication between them. Target values are uniform on [0,1000]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 6–18 Simulation results of the target strategy with m agents on separate missions with communication between them. Uncommitted agents are allowed to evaluate targets in other unsearched partitions. . . . . . . . . 76 6–19 Simulation results using the dynamic threshold strategy . . . . . . . . . . 78 ix LIST OF FIGURES Figure page 3–1 K-Means algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3–2 Entropy K-means algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 22 3–3 Generic MST algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3–4 Kruskal MST algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3–5 Graph clustering algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . 25 4–1 Algorithm for dimension reduction. . . . . . . . . . . . . . . . . . . . . . 33 5–1 Target and agent boundaries . . . . . . . . . . . . . . . . . . . . . . . . . 40 5–2 Region . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5–3 Multistage graph representation 1 . . . . . . . . . . . . . . . . . . . . . . 49 5–4 Multistage graph representation 2 . . . . . . . . . . . . . . . . . . . . . . 51 5–5 Region with obstacles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 5–6 Using the 8 zimuths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 6–1 Racetrack search of battlespace with n targets . . . . . . . . . . . . . . . 55 6–2 Plots of probabilities of attacking the jth best target for two proposed strategies, n=100 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 6–3 m agents performing racetrack search of battlespace with n targets . . . 70 6–4 m agents on separate missions of a equally partitioned battlespace performing racetrack search for n targets . . . . . . . . . . . . . . . . . . 74 x