Search

Class imbalance is a challenging problem that demonstrates the unsatisfactory classification performance of a minority class. A trivial classifier is biased toward minority instances because of their tiny fraction. In this paper, our density function is defined as the distance along the shortest path between each majority instance and a minority-cluster pseudo-centroid in an underlying cluster graph. A short path implies highly overlapping dense minority instances. In contrast, a long path indicates a sparsity of instances. A new under-sampling algorithm is proposed to eliminate majority instances with low distances because these instances are insignificant and obscure the classification boundary in the overlapping region. The results show predictive improvements on a minority class from various classifiers on different UCI datasets.

In the p-Cluster Vertex Deletion problem, we are given a graph $$G=(V,E)$$G=(V,E) and two parameters k and p, and the goal is to determine if there exists a subset X of at most k vertices such that the removal of X results in a graph consisting of exactly p disjoint maximal cliques. Let $$r=p/k$$r=p/k. In this paper, we design a branching algorithm with time complexity $$O(\alpha ^k+|V||E|)$$O(źk+|V||E|), where $$\alpha $$ź depends on r and has a rough upper bound $$\min \{1.618^{1+r},2\}$$min{1.6181+r,2}. With a more precise analysis, we show that $$\alpha =1.28\cdot 3.57^{r}$$ź=1.28·3.57r for $$r\le 0.219$$r≤0.219; $$\alpha =(1-r)^{r-1}r^{-r}$$ź=(1-r)r-1r-r for $$0.219< r

The cluster editing problem consists of transforming an input graph $$G$$G into a cluster graph (a disjoint union of complete graphs) by performing a minimum number of edge editing operations. Each edge editing operation consists of either adding a new edge or removing an existing edge. In this paper we propose new theoretical results on data reduction and instance generation for the cluster editing problem, as well as two algorithms based on coupling an exact method to, respectively, a GRASP or ILS heuristic. Experimental results show that the proposed algorithms are able to find high-quality solutions in practical runtime.

Investigating the secondary geochemical environments, river, and stream sediments are considered as one of the geochemical exploratory methods on a primary scale, which is justifiable regarding the expenses and time of execution. Evaluating the factors related to mineralization of gold shear zones based on stream and river sediment sampling, located in the southwest of Saqqez (Kurdistan), is the main purpose of this research. Using multivariable analyses and investigating the cluster graph of the elements, controlling factors of mineralization have been investigated and effective factors are divided into two groups, one is probably related to the mineralization of gold in the region which contains the elements (Pb, Zn, Mo, Ag, Cu, Bi, etc.), and other is related to typical petrogenetic processes which contains the elements (Co, V, Cr, Ti, Ni, Mn, etc.). Based on factor analysis, seven main factors, which justify about 80% of the changes of the region, were introduced; factors 3, 1, 5, and 6 were related to mineralization and factors 2, 4, and 7 were related to the lithology of the region. For a more precise separation of the processes related to mineralization, various ratios were investigated and reagent ratios (Au/Bi and Au/Mo) were identified. It is found that the ranges of [23–100] for Au/Bi and [8–80] for Au/Mo are related to gold mineralization. Using the modeling of the reagent ratios probability graph and determining the exploratory threshold, significant parameters in gold mineralization were separated from insignificants.

Motivated by fundamental problems in chemistry and biology we study cluster graphs arising from a set of initial states $S\subseteq\Z^n_+$ and a set of transitions/reactions $M\subseteq\Z^n_+\times\Z^n_+$. The clusters are formed out of states that can be mutually transformed into each other by a sequence of reversible transitions. We provide a solution method from computational commutative algebra that allows for deciding whether two given states belong to the same cluster as well as for the reconstruction of the full cluster graph. Using the cluster graph approach we provide solutions to two fundamental questions: 1) Deciding whether two states are connected, e.g., if the initial state can be turned into the final state by a sequence of transition and 2) listing concisely all reactions processes that can accomplish that. As a computational example, we apply the framework to the permanganate/oxalic acid reaction., Revised version, to appear in Journal of Mathematical Chemistry