English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Partitioning algorithms play a key role in many scientific and engineeringdisciplines. A partitioning algorithm divides a set into a number of disjointsubsets or partitions. Often, the quality of the resulted partitions ismeasured by the amount of impurity in each partition, the smaller impurity thehigher quality of the partitions. In general, for a given impurity measurespecified by a function of the partitions, finding the minimum impuritypartitions is an NP-hard problem. Let $M$ be the number of $N$-dimensionalelements in a set and $K$ be the number of desired partitions, then anexhaustive search over all the possible partitions to find a minimum partitionhas the complexity of $O(K^M)$ which quickly becomes impractical for manyapplications with modest values of $K$ and $M$. Thus, many approximatealgorithms with polynomial time complexity have been proposed, but few providebounded guarantee. In this paper, an upper bound and a lower bound for a classof impurity functions are constructed. Based on these bounds, we propose alow-complexity partitioning algorithm with bounded guarantee based on themaximum likelihood principle. The theoretical analyses on the bounded guaranteeof the algorithms are given for two well-known impurity functions Gini indexand entropy. When $K \geq N$, the proposed algorithm achieves state-of-the-artresults in terms of lowest approximations and polynomial time complexity$O(NM)$. In addition, a heuristic greedy-merge algorithm having the timecomplexity of $O((N-K)N^2+NM)$ is proposed for $K<N$. Although the greedy-mergealgorithm does not provide a bounded guarantee, its performance is comparableto that of the state-of-the-art methods. Our results also generalize somewell-known information-theoretic bounds such as Fano's inequality andBoyd-Chiang's bound.

Bounded Guaranteed Algorithms for Concave Impurity Minimization Via Maximum Likelihood