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

An impurity measures $I:{R}^k \to {R}^+$ maps a $k$-dimensional vector ${\bfv}$ to a non-negative value $I({\bf v})$ so that the more homogeneous ${\bfv}$, the larger its impurity. We study clustering based on impurity measures:given a collection $V$ of $n$ many $k$-dimensional vectors and an impuritymeasure $I$, the goal is to find a partition ${\cal P}$ of $V$ into $L$ groups$V_1,\ldots,V_L$ that minimizes the total impurities of the groups in ${\calP}$, i.e., $I({\cal P})= \sum_{m=1}^{L} I(\sum_{{\bf v} \in V_m}{\bf v}).$  Impurity minimization is widely used as quality assessment measure inprobability distribution clustering and in categorical clustering where it isnot possible to rely on geometric properties of the data set. However, incontrast to the case of metric based clustering, the current knowledge ofimpurity measure based clustering in terms of approximation andinapproximability results is very limited.  Our research contributes to fill this gap. We first present a simple lineartime algorithm that simultaneously achieves $3$-approximation for the Giniimpurity measure and $O(\log(\sum_{{\bf v} \in V} \| {\bf v}\|_1))$-approximation for the Entropy impurity measure. Then, for the Entropyimpurity measure---where we also show that finding the optimal clustering isstrongly NP-hard---we are able to design a polynomial time$O(\log^2(\min\{k,L\}))$-approximation algorithm. Our algorithm relies on anontrivial characterization of a class of clusterings that necessarily includesa partition achieving $O(\log^2(\min\{k,L\}))$--approximation of the impurityof the optimal partition. Remarkably, this is the first polynomial timealgorithm with approximation guarantee independent of the number ofpoints/vector and not relying on any restriction on the components of thevectors for producing clusterings with minimum entropy.

Approximation Algorithms for Clustering via Weighted Impurity Measures