Publica
Hier finden Sie wissenschaftliche Publikationen aus den FraunhoferInstituten. Maximal Closed Set and HalfSpace Separations in Finite Closure Systems
 Brefeld, U.: Machine Learning and Knowledge Discovery in Databases. Proceedings. Pt.I : European Conference, ECML PKDD 2019, Würzburg, Germany, September 1620, 2019 Cham: Springer Nature, 2020 (Lecture Notes in Artificial Intelligence 11906) ISBN: 9783030461492 (Print) ISBN: 9783030461508 (Online) ISBN: 9783030461515 pp.2137 
 European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD) <2019, Würzburg> 
 Bundesministerium für Bildung und Forschung BMBF (Deutschland) 01/S18038C; ML2R 
 Deutsche Forschungsgemeinschaft DFG EXC 2070 390732324 

 English 
 Conference Paper 
 Fraunhofer IAIS () 
 closure systems; halfspace separation; binary classification 
Abstract
Motivated by various binary classification problems in structured data (e.g., graphs or other relational and algebraic structures), we investigate some algorithmic properties of closed set and halfspace separation in abstract closure systems. Assuming that the underlying closure system is finite and given by the corresponding closure operator, we formulate some negative and positive complexity results for these two separation problems. In particular, we prove that deciding halfspace separability in abstract closure systems is NPcomplete in general. On the other hand, for the relaxed problem of maximal closed set separation we propose a simple greedy algorithm and show that it is efficient and has the best possible lower bound on the number of closure operator calls. As a second direction to overcome the negative result above, we consider Kakutani closure systems and show first that our greedy algorithm provides an algorithmic characterization of this kind of set systems. As one of the major potential application fields, we then focus on Kakutani closure systems over graphs and generalize a fundamental characterization result based on the Pasch axiom to graph structure partitioning of finite sets. Though the primary focus of this work is on the generality of the results obtained, we experimentally demonstrate the practical usefulness of our approach on vertex classification in different graph datasets.