The mixture of K-Optimal-Spanning-Trees based probability approximation: Application to skin detection

This paper presents a new approach for machine learning to deal with the problem of classification and/or probability approximation. Our contribution is based on the Optimal-Spanning-Tree distributions that are widely used in many optimization areas. The rationale behind this study is that in some cases the approximation of true class probability given by an Optimal-Spanning-Tree is not unique and might be chosen randomly. Furthermore, the user can specify the error tolerance between the tree weights that he/she can accept to manage the information of these kinds of trees. Therefore, the main idea of this work consists in focusing and highlighting the performance of each possible K  (K∈N)(K∈N) Optimal-Spanning-Tree and making some assumptions, to propose the mixture of the K-Optimal-Spanning-Trees approximating the true class probability in a supervised algorithm.The theoretical proof of the K-Optimal-Spanning-Trees’ mixture is given. Furthermore, the performance of our method is assessed for Skin/Non-Skin classification in the Compaq database by measuring the Receiver Operating Characteristic curve and its under area. These measures have proved better results of the proposed model compared with a random Optimal-Spanning-Tree model and the baseline one.