×

Foraging theory for dimensionality reduction of clustered data. (English) Zbl 1470.68215

Summary: We present a bioinspired algorithm which performs dimensionality reduction on datasets for visual exploration, under the assumption that they have a clustered structure. We formulate a decision-making strategy based on foraging theory, where a software agent is viewed as an animal, a discrete space as the foraging landscape, and objects representing points from the dataset as nutrients or prey items. We apply this algorithm to artificial and real databases, and show how a multi-agent system addresses the problem of mapping high-dimensional data into a two-dimensional space.

MSC:

68T09 Computational aspects of data analysis and big data
68Q07 Biologically inspired models of computation (DNA computing, membrane computing, etc.)
68T42 Agent technology and artificial intelligence
92D40 Ecology

Software:

Biomimicry; t-SNE
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andrews, B. W., Passino, K. M., & Waite, T. A. (2007a). Social foraging theory for robust multiagent system design. IEEE Transactions on Automation Science and Engineering, 4(1), 74-86. · doi:10.1109/TASE.2006.872124
[2] Andrews, B. W., Passino, K. M., & Waite, T. A. (2007b). Foraging theory for autonomous vehicle decision-making system design. Journal of Intelligent and Robotic Systems, 49(1), 39-65. · doi:10.1007/s10846-007-9138-9
[3] Bishop, C. M., Svensén, M., & Williams, C. K. (1998). Generative topographic mapping. Neural Computation, 10(1), 215-234. · Zbl 0936.68091 · doi:10.1162/089976698300017953
[4] Bonabeau, E., Dorigo, M., & Theraulaz, G. (1999). Swarm intelligence: From natural to artificial swarm intelligence. Oxford: Oxford University Press. · Zbl 1003.68123
[5] Carreira-Perpiñán, M. Á., & Renals, S. (1998). Dimensionality reduction of electropalatographic data using latent variable models. Speech Communication, 26(4), 259-282. · doi:10.1016/S0167-6393(98)00059-4
[6] Chanda, P., Zhang, A., Brezeau, D., Sucheston, L., Freudenheim, J. L., Ambrosone, C., & Ramanathan, M. (2007). Information-theoretic metrics for visualizing gene-environment interactions. American Journal of Human Genetics, 81(5), 939-963. · doi:10.1086/521878
[7] Deneubourg, J.-L.; Goss, S.; Franks, N.; Sendova-Franks, A.; Detrain, C.; Chrétien, L., The dynamics of collective sorting robot-like ants and ant-like robots, 356-363 (1990), Cambridge
[8] Dukas, R. (1998). Cognitive ecology: The evolutionary ecology of information processing and decision making. Chicago: University of Chicago Press.
[9] Giraldeau, L.-A., & Caraco, T. (2000). Monographs in behavior and ecology. Social foraging theory. Princeton: Princeton University Press.
[10] Handl, J., Knowles, J. D., & Dorigo, M. (2006). Ant-based clustering and topographic mapping. Artificial Life, 12(1), 35-61. · doi:10.1162/106454606775186400
[11] Hinton, G.; Roweis, S., Stochastic neighbor embedding, 833-840 (2002), Cambridge
[12] Jain, A. K., Narasimha Murty Murty, M., & Flynn, P. J. (1999). Data clustering: A review. ACM Computing Surveys, 31(3), 264-323. · doi:10.1145/331499.331504
[13] Jain, A. K., Duin, R. P. W., & Mao, J. (2000). Statistical pattern recognition: A review. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(1), 4-37. · doi:10.1109/34.824819
[14] King, B. (1967). Setp-wise clustering procedures. Journal of the American Statistical Association, 69, 86-101. · doi:10.2307/2282912
[15] Kivinen, J., & Warmuth, M. K. (1997). Exponentiated gradient versus gradient descent for linear predictors. Information and Computation, 132(1). · Zbl 0872.68158
[16] Kivinen, J., Smola, A. J., & Williamson, R. C. (2004). Online learning with kernels. IEEE Transactions on Signal Processing, 52(8), 2165-2176. · Zbl 1369.68281 · doi:10.1109/TSP.2004.830991
[17] Kohonen, T. (2000). Self-organizing maps (3rd ed.). Heidelberg: Springer. · Zbl 0957.68097
[18] Kuntz, P., Snyers, D., & Layzell, P. (1999). A stochastic heuristic for visualising graph clusters in bi-dimensional space prior to partitioning. Journal of Heuristics, 5(3), 327-351. · Zbl 1064.90575 · doi:10.1023/A:1009665701840
[19] Lisboa, P. J., Ellis, I. O., Green, A. R., Ambrogi, F., & Dias, B. (2008). Cluster-based visualization with scatter matrices. Pattern Recognition Letters, 29(13), 1814-1823. · Zbl 1140.68482 · doi:10.1016/j.patrec.2008.05.021
[20] Littlestone, N., & Warmuth, M. K. (1994). The weighted majority algorithm. Information and Computation, 108(2), 212-261. · Zbl 0804.68121 · doi:10.1006/inco.1994.1009
[21] Lumer, E. D.; Faieta, B., Diversity and adaptation in populations of clustering ants, 501-508 (1994), Cambridge
[22] Martens, D., De Backer, M., Haesen, R., Vanthienen, J., Snoeck, M., & Baesens, B. (2007). Classification with ant colony optimization. IEEE Transactions on Evolutionary Computation, 11(5), 651-665. · doi:10.1109/TEVC.2006.890229
[23] McClurkin, J. W., Optican, L. M., Richmond, B. J., & Gawne, T. J. (1991). Concurrent processing and complexity of temporally encoded neuronal messages in visual perception. Science, 253(5020), 675-677. · doi:10.1126/science.1908118
[24] Ngenkaew, W., Ono, S., & Nakayama, S. (2008). The deposition of multiple pheromones in ant-based clustering. International Journal of Innovative Computing Information and Control, 4(7), 1583-1593.
[25] Passino, K. M. (2005). Biomimicry for optimization, control and automation. London: Springer. · Zbl 1080.93002
[26] Pearson, K. (1901). On lines and planes of closest fit to systems of points in space. Philosophical Magazine, 2(6), 559-572. · JFM 32.0246.07
[27] Pirolli, P. (2007). Information foraging theory. Oxford: Oxford University Press. · doi:10.1093/acprof:oso/9780195173321.001.0001
[28] Quijano, N., & Passino, K. M. (2007). Honey bee social foraging algorithms for resource allocation, Part ii: application. In Proceedings of the American control conference (pp. 3389-3394), New York, USA, July 2007.
[29] Quijano, N., Andrews, B. W., & Passino, K. M. (2006). Foraging theory for multizone temperature control. IEEE Computational Intelligence Magazine, 1(4), 18-27.
[30] Roweis, S. T., & Saul, L. K. (2000). Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500), 2323-2326. · doi:10.1126/science.290.5500.2323
[31] Sanguinetti, G. (2008). Dimensionality reduction of clustered data sets. IEEE Transactions on Pattern Analysis and Machine Intelligence, 30(3), 535-540. · doi:10.1109/TPAMI.2007.70819
[32] Stephens, D. W., & Krebs, J. R. (1986). Monographs in behavior and ecology. Foraging theory. Princeton: Princeton University Press.
[33] Sutton, R. S., & Barto, A. G. (1998). Reinforcement learning: An introduction. Cambridge: MIT Press.
[34] Tenenbaum, J. B., de Silva, V., & Langford, J. C. (2000). A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500), 2319-2323. · Zbl 0955.37025 · doi:10.1126/science.290.5500.2319
[35] Torgerson, W. S. (1958). Theory and methods of scaling. New York: Wiley.
[36] Ulam, P., & Balch, T. (2003). Niche selection in foraging tasks in multi-robot teams using reinforcement learning. In Second international workshop on the mathematics and algorithms of social insects, 2003.
[37] Van der Maaten, L., & Hinton, G. (2008). Visualizing data using t-SNE. Journal of Machine Learning Research, 9, 2579-2605. · Zbl 1225.68219
[38] Wen, G., Jiang, L., Wen, J., & Shadbolt, N. R. (2006). Clustering-based nonlinear dimensionality reduction on manifold. In Q. Yang & G. Webb (Eds.), PRICAI 2006: Trends in artificial intelligence (pp. 444-453).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.