More Web Proxy on the site http://driver.im/

article

Multi-instance clustering with applications to multi-instance prediction

Authors:

Min-Ling Zhang,

Zhi-Hua ZhouAuthors Info & Claims

Applied Intelligence, Volume 31, Issue 1

Pages 47 - 68

https://doi.org/10.1007/s10489-007-0111-x

Published: 01 August 2009 Publication History

Abstract

In the setting of multi-instance learning, each object is represented by a bag composed of multiple instances instead of by a single instance in a traditional learning setting. Previous works in this area only concern multi-instance prediction problems where each bag is associated with a binary (classification) or real-valued (regression) label. However, unsupervised multi-instance learning where bags are without labels has not been studied. In this paper, the problem of unsupervised multi-instance learning is addressed where a multi-instance clustering algorithm named Bamic is proposed. Briefly, by regarding bags as atomic data items and using some form of distance metric to measure distances between bags, Bamic adapts the popular k -Medoids algorithm to partition the unlabeled training bags into k disjoint groups of bags. Furthermore, based on the clustering results, a novel multi-instance prediction algorithm named Bartmip is developed. Firstly, each bag is re-represented by a k-dimensional feature vector, where the value of the i-th feature is set to be the distance between the bag and the medoid of the i-th group. After that, bags are transformed into feature vectors so that common supervised learners are used to learn from the transformed feature vectors each associated with the original bag's label. Extensive experiments show that Bamic could effectively discover the underlying structure of the data set and Bartmip works quite well on various kinds of multi-instance prediction problems.

References

[1]

Dietterich TG, Lathrop RH, Lozano-Pérez T (1997) Solving the multiple-instance problem with axis-parallel rectangles. Artif Intell 39(1-2):31-71.

Digital Library

[2]

Weidmann N, Frank E, Pfahringer B (2003) A two-level learning method for generalized multi-instance problem. In: Lavra¿ N, Gamberger D, Blockeel H, Todorovski L (eds) Lecture notes in artificial intelligence, vol 2837. Springer, Berlin, pp 468-579.

[3]

Scott S, Zhang J, Brown J (2003) On generalized multiple-instance learning. Technical report UNL-CSE-2003-5, Department of Computer Science and Engineering, University of Nebraska, Lincoln, NE.

[4]

Amar RA, Dooly DR, Goldman SA, Zhang Q (2001) Multiple-instance learning of real-valued data. In: Proceedings of the 18th international conference on machine learning, Williamstown, MA, 2001, pp 3-10.

Digital Library

[5]

Ray S, Page D (2001) Multiple instance regression. In: Proceedings of the 18th international conference on machine learning, Williamstown, MA, 2001, pp 425-432.

Digital Library

[6]

Dooly DR, Zhang Q, Goldman SA, Amar RA (2002) Multiple-instance learning of real-valued data. J Mach Learn Res 3:651- 678.

Digital Library

[7]

Han J, Kamber M (2001) Data mining: concepts and techniques. Morgan Kaufmann, San Francisco.

Digital Library

[8]

Edgar GA (1995) Measure, Topology, and Fractal Geometry, 3rd edn. Springer, Berlin.

[9]

Long PM, Tan L (1998) PAC learning axis-aligned rectangles with respect to product distribution from multiple-instance examples. Mach Learn 20(1):7-21.

Digital Library

[10]

Auer P, Long PM, Srinivasan A (1998) Approximating hyperrectangles: learning and pseudo-random sets. J Comput Syst Sci 57(3):376-388.

Digital Library

[11]

Auer P (1997) On learning from multi-instance examples: empirical evaluation of a theoretical approach. In: Proceedings of the 14th international conference on machine learning, Nashville, TN, 1997, pp 21-29.

Digital Library

[12]

Blum A, Kalai A (1998) A note on learning from multiple-instance examples. Mach Learn 30(1):23-29.

Digital Library

[13]

Goldman SA, Kwek SS, Scott SD (2001) Agnostic learning of geometric patterns. J Comput Syst Sci 62(1):123-151.

Digital Library

[14]

Goldman SA, Scott SD (2003) Multiple-instance learning of real-valued geometric patterns. Ann Math Artif Intell 39(3):259-290.

Digital Library

[15]

Maron O, Lozano-Pérez T (1998) A framework for multiple-instance learning. In: Jordan MI, Kearns MJ, Solla SA (eds) Advances in neural information processing systems, vol 10. MIT Press, Cambridge, pp 570-576.

Digital Library

[16]

Zhang Q, Goldman SA (2002) EM-DD: an improved multiple-instance learning technique. In: Dietterich TG, Becker S, Ghahramani Z (eds) Advances in neural information processing systems, vol 14. MIT Press, Cambridge, pp 1073-1080.

[17]

Chen Y, Wang JZ (2004) Image categorization by learning and reasoning with regions. J Mach Learn Res 5:913-939.

Digital Library

[18]

Wang J, Zucker J-D (2000) Solving the multiple-instance problem: a lazy learning approach. In: Proceedings of the 17th international conference on machine learning, San Francisco, CA, 2000, pp 1119-1125.

Digital Library

[19]

Ruffo G (2000) Learning single and multiple decision trees for security applications. Ph.D. thesis, Department of Computer Science, University of Turin, Italy, 2000.

[20]

Chevaleyre Y, Zucker J-D (2001) Solving multiple-instance and multiple-part learning problems with decision trees and decision rules. Application to the mutagenesis problem. In: Stroulia E, Matwin S (eds) Lecture notes in artificial intelligence, vol 2056. Springer, Berlin, pp 204-214.

Digital Library

[21]

Blockeel H, Page D, Srinivasan A (2005) Multi-instance tree learning. In: Proceedings of the 22nd international conference on machine learning, Bonn, Germany, 2005, pp 57-64.

Digital Library

[22]

Xu X, Frank E (2004) Logistic regression and boosting for labeled bags of instances. In: Dai H, Srikant R, Zhang C-Q (eds) Lecture notes in computer science, vol 3056. Springer, Berlin, pp 272-281.

[23]

Ramon J, De Raedt L (2000) Multi instance neural networks. In: Proceedings of ICML-2000, workshop on attribute-value and relational learning, San Francisco, CA, 2000.

[24]

Zhou Z-H, Zhang M-L (2002) Neural networks for multiinstance learning. Technical report, AI Lab, Computer Science and Technology Department, Nanjing University, Nanjing, China.

[25]

Zhang M-L, Zhou Z-H (2004) Improve multi-instance neural networks through feature selection. Neural Process Lett 19(1):1-10.

Digital Library

[26]

Bouchachia A (2004) Multiple instance learning with radial basis function neural networks. In: Pal NR, Kasabov N, Mudi RK (eds) Lecture notes in computer science, vol 3316. Springer, Berlin, pp 440-445.

[27]

Zhang M-L, Zhou Z-H (2006) Adapting RBF neural networks to multi-instance learning. Neural Process Lett 23(1):1-26.

Digital Library

[28]

Gärtner T, Flach PA, Kowalczyk A, Smola AJ (2002) Multiinstance kernels. In: Proceedings of the 19th international conference on machine learning, Sydney, Australia, 2002, pp 179-186.

Digital Library

[29]

Andrews S, Tsochantaridis I, Hofmann T (2003) Support vector machines for multiple-instance learning. In: Becker S, Thrun S, Obermayer K (eds) Advances in neural information processing systems, vol 15. MIT Press, Cambridge, pp 561-568.

[30]

Cheung P-M, Kwok JT (2006) A regularization framework for multiple-instance learning. In: Proceedings of the 23th international conference on machine learning, Pittsburgh, PE, 2006, pp 193-200.

Digital Library

[31]

Zhou Z-H, Zhang M-L (2003) Ensembles of multi-instance learners. In: Lavra¿ N, Gamberger D, Blockeel H, Todorovski L (eds) Lecture notes in artificial intelligence, vol 2837. Springer, Berlin, pp 492-502.

[32]

Andrews S, Hofmann T (2004) Multiple-instance learning via disjunctive programming boosting. In: Thrun S, Saul LK, Schölkopf B (eds) Advances in neural information processing systems, vol 16. MIT Press, Cambridge.

[33]

Auer P, Ortner R (2004) A boosting approach to multiple instance learning. In: Boulicaut J-F, Esposito F, Giannotti F, Pedreschi D (eds) Lecture notes in artificial intelligence, vol 3201. Springer, Berlin, pp 63-74.

[34]

Viola P, Platt J, Zhang C (2006) Multiple instance boosting for object detection. In: Weiss Y, Schölkopf B, Platt J (eds) Advances in neural information processing systems, vol 18. MIT Press, Cambridge, pp 1419-1426.

[35]

Huang X, Chen S-C, Shyu M-L, Zhang C (2002) Mining high-level user concepts with multiple instance learning and relevance feedback for content-based image retrieval. In: Zaïane OR, Simoff SJ, Djeraba C (eds) Lecture notes in artificial intelligence, vol 2797. Springer, Berlin, pp 50-67.

[36]

Yang C, Lozano-Pérez T (2000) Image database retrieval with multiple-instance learning techniques. In: Proceedings of the 16th international conference on data engineering, San Diego, CA, 2000, pp 233-243.

Digital Library

[37]

Zhang Q, YuW, Goldman SA, Fritts JE (2002) Content-based image retrieval using multiple-instance learning. In: Proceedings of the 19th international conference on machine learning, Sydney, Australia, 2002, pp 682-689.

Digital Library

[38]

Zhou Z-H, ZhangM-L, Chen K-J (2003) A novel bag generator for image database retrieval with multi-instance learning techniques. In: Proceedings of the 15th IEEE international conference on tools with artificial intelligence, Sacramento, CA, 2003, pp 565-569.

Digital Library

[39]

Rahmani R, Goldman SA (2006) Missl: multiple-instance semisupervised learning. In: Proceedings of the 23rd international conference on machine learning, Pittsburgh, PE, 2006, pp 705- 712.

Digital Library

[40]

Maron O, Ratan AL (1998) Multiple-instance learning for natural scene classification. In: Proceedings of the 15th international conference on machine learning, Madison, WI, 1998, pp 341-349.

Digital Library

[41]

McGovern A, Barto AG (2001) Automatic discovery of subgoals in reinforcement learning using diverse density. In: Proceedings of the 18th international conference on machine learning, Williamstown, MA, 2001, pp 361-368.

Digital Library

[42]

Zhou Z-H, Jiang K, Li M (2005) Multi-instance learning based web mining. Appl Intell 22(2):135-147.

Digital Library

[43]

Zhou Z-H, Zhang M-L (2007) Solving multi-instance problems with classifier ensemble based on constructive clustering. Knowl Inf Syst 11(2):155-170.

[44]

Tao Q, Scott S (2004) A faster algorithm for generalized multiple-instance learning. In: Proceedings of the 17th international Florida artificial intelligence research society conference, Miami Beach, FL, 2004, pp 550-555.

[45]

Tao Q, Scott S, Vinodchandran NV, Osugi TT (2004) Svm-based generalized multiple-instance learning via approximate box counting. In: Proceedings of the 21st international conference on machine learning, Banff, Canada, 2004, pp 799-806.

Digital Library

[46]

Tao Q, Scott S, Vinodchandran NV, Osugi TT, Mueller B (2004) An extended kernel for generalized multiple-instance learning. In: Proceedings of the 16th IEEE international conference on tools with artificial intelligence, Boca Raton, FL, 2004, pp 272-277.

Digital Library

[47]

De Raedt L (1998) Attribute-value learning versus inductive logic programming: the missing links. In: Page D (ed) Lecture notes in artificial intelligence, vol 1446. Springer, Berlin, pp 1-8.

Digital Library

[48]

Alphonse É, Matwin S (2004) Filtering multi-instance problems to reduce dimensionality in relational learning. J Intell Inf Syst 22(1):23-40.

Digital Library

[49]

McGovern A, Jensen D (2003) Identifying predictive structures in relational data using multiple instance learning. In: Proceedings of the 20th international conference on machine learning, Washington, DC, 2003, pp 528-535.

[50]

Günter S, Bunke H (2003) Validation indices for graph clustering. Pattern Recogn Lett 24(8):1107-1113.

Digital Library

[51]

Quinlan JR (1993) C4.5: Programs for machine learning. Morgan Kaufmann, San Mateo.

Digital Library

[52]

Blake C, Keogh E, Merz CJ (1998) UCI repository of machine learning databases {http://www.ics.uci.edu/~mlearn/mlrepository. html}. Technical report, Department of Information and Computer Science, University of California, Irvine, CA.

[53]

Berry RS, Rice SA, Ross J (1980) Physical Chemistry. Wiley, New York, Chapter 10, Intermolecular Forces.

[54]

Liu H, Motoda H (1998) Feature selection for knowledge discovery and data mining. Kluwer Academic, Norwell.

Digital Library

[55]

Wang C, Scott SD, Zhang J, Tao Q, Fomenko D, Gladyshev V (2004) A study in modeling low-conservation protein superfamilies. Technical report UNL-CSE-2004-0003, Department of Computer Science and Engineering, University of Nebraska, Lincoln, NE.

[56]

Kim J, Moriyama EN, Warr CG, Clyne PJ, Carlson JR (2000) Identification of novel multi-transmembrane proteins from genomic databases using quasi-periodic structural properties. Bioinform 16(9):767-775.

[57]

Littlestone N (1991) Redundant noisy attributes, attribute errors, and linear threshold learning using winnow. In: Proceedings of the 4th annual workshop on computational learning theory, Santa Cruz, CA, 1991, pp 147-156.

Digital Library

[58]

Bishop CM (1995) Neural networks for pattern recognition. Oxford University Press, New York.

Digital Library

[59]

Dietterich TG (2000) Ensemble methods in machine learning. In: Kittler J, Roli F (eds) Lecture notes in computer science, vol 1867. Springer, Berlin, pp 1-15.

Digital Library

[60]

Chang C-C, Lin C-J (2001) LIBSVM: a library for support vector machines. Technical report, Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan.

[61]

Ray S, Craven M (2005) Supervised versus multiple instance learning: an empirical comparison. In: Proceedings of the 22nd international conference on machine learning, Bonn, Germany, 2005, pp 697-704.

Digital Library

[62]

Tan X, Chen S, Zhou Z-H, Liu J (2006) Learning non-metric partial similarity based on maximal margin criterion. In: Proceedings of the IEEE computer society conference on computer vision and pattern recognition, New York, NY, 2006, pp 138-145.

Digital Library

Cited By

Yang MChen TWu WZeng WZhang JMin F(2025)Dual-perspective multi-instance embedding learning with adaptive density distribution miningPattern Recognition10.1016/j.patcog.2024.111063158:COnline publication date: 1-Feb-2025
https://dl.acm.org/doi/10.1016/j.patcog.2024.111063
Jiang XZhang HZhou Y(2023)Multi-Granularity Abnormal Traffic Detection Based on Multi-Instance LearningIEEE Transactions on Network and Service Management10.1109/TNSM.2023.332215221:2(1467-1477)Online publication date: 5-Oct-2023
https://dl.acm.org/doi/10.1109/TNSM.2023.3322152
Zafra AGibaja E(2023)Nearest neighbor-based approaches for multi-instance multi-label classificationExpert Systems with Applications: An International Journal10.1016/j.eswa.2023.120876232:COnline publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1016/j.eswa.2023.120876
Show More Cited By

Multi-instance clustering with applications to multi-instance prediction
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Supervised learning
      2. Unsupervised learning

Recommendations

Cost‐effective multi‐instance multilabel active learning
Abstract
Multi‐instance multi‐label (MIML) Active Learning (M2AL) aims to improve the learner while reducing the cost as much as possible by querying informative labels of complex bags composed of diverse instances. Existing M2AL solutions suffer high ...
Diversified dictionaries for multi-instance learning

Multiple-instance learning (MIL) has been a popular topic in the study of pattern recognition for years due to its usefulness for such tasks as drug activity prediction and image/text classification. In a typical MIL setting, a bag contains a bag-level ...
Multi-instance multi-label learning

In this paper, we propose the MIML (Multi-Instance Multi-Label learning) framework where an example is described by multiple instances and associated with multiple class labels. Compared to traditional learning frameworks, the MIML framework is more ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Applied Intelligence

Applied Intelligence Volume 31, Issue 1

August 2009

106 pages

ISSN:0924-669X

Issue’s Table of Contents

Copyright © Copyright © 2009 Springer Science+Business Media, LLC.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 August 2009

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

40
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yang MChen TWu WZeng WZhang JMin F(2025)Dual-perspective multi-instance embedding learning with adaptive density distribution miningPattern Recognition10.1016/j.patcog.2024.111063158:COnline publication date: 1-Feb-2025
https://dl.acm.org/doi/10.1016/j.patcog.2024.111063
Jiang XZhang HZhou Y(2023)Multi-Granularity Abnormal Traffic Detection Based on Multi-Instance LearningIEEE Transactions on Network and Service Management10.1109/TNSM.2023.332215221:2(1467-1477)Online publication date: 5-Oct-2023
https://dl.acm.org/doi/10.1109/TNSM.2023.3322152
Zafra AGibaja E(2023)Nearest neighbor-based approaches for multi-instance multi-label classificationExpert Systems with Applications: An International Journal10.1016/j.eswa.2023.120876232:COnline publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1016/j.eswa.2023.120876
Yang MZhang YZhou ZZeng WMin F(2022)Multi-embedding space set-kernel and its application to multi-instance learningNeurocomputing10.1016/j.neucom.2022.09.067512:C(339-351)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1016/j.neucom.2022.09.067
Yu LCao F(2022)Weighted matrix-object data clustering guided by matrix-object distributionsEngineering Applications of Artificial Intelligence10.1016/j.engappai.2021.104612109:COnline publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1016/j.engappai.2021.104612
Wang CLu XWang W(2022)A theoretical analysis based on causal inference and single-instance learningApplied Intelligence10.1007/s10489-022-03193-052:12(13902-13915)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1007/s10489-022-03193-0
Zhao LYuan LHao KWen X(2022)Generalized attention-based deep multi-instance learningMultimedia Systems10.1007/s00530-022-00992-w29:1(275-287)Online publication date: 7-Sep-2022
https://dl.acm.org/doi/10.1007/s00530-022-00992-w
Yang MZhang YYe MMin F(2022)Attention-to-Embedding Framework for Multi-instance LearningAdvances in Knowledge Discovery and Data Mining10.1007/978-3-031-05936-0_9(109-121)Online publication date: 16-May-2022
https://dl.acm.org/doi/10.1007/978-3-031-05936-0_9
Su CYan ZYu G(2021)Cost‐effective multi‐instance multilabel active learningInternational Journal of Intelligent Systems10.1002/int.2258536:12(7177-7203)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1002/int.22585
Esteban AZafra AVentura S(2020)A Preliminary Study on Evolutionary Clustering for Multiple Instance Learning2020 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC48606.2020.9185588(1-8)Online publication date: 19-Jul-2020
https://dl.acm.org/doi/10.1109/CEC48606.2020.9185588
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents