Clustering Aware Classification for Risk Prediction & Subtyping in Clinical
Data

Shivin Srivastava1 Siddharth Bhatia1 Lingxiao Huang2 Jun Heng Lim3 Kenji
Kawaguchi1 Vaibhav Rajan1

1School of Computing, National University of Singapore, Singapore 2 Huawei TCS
Labs, Shanghai, China 3 Nanyang Institute of Technology, Singapore

###### Abstract

In data containing heterogeneous subpopulations, classification performance
benefits from incorporating the knowledge of cluster structure in the
classifier. Previous methods for such combined clustering and classification
either 1) are classifier-specific and not generic, or 2) independently perform
clustering and classifier training, which may not form clusters that can
potentially benefit classifier performance. The question of how to perform
clustering to improve the performance of classifiers trained on the clusters
has received scant attention in previous literature, despite its importance in
several real-world applications. In this paper, first, we theoretically
analyze the generalization performance of classifiers trained on clustered
data and find conditions under which clustering can potentially aid
classification. This motivates the design of a simple $k$-means-based
classification algorithm called Clustering Aware Classification (CAC) and its
neural variant DeepCAC. DeepCAC effectively leverages deep representation
learning to learn latent embeddings and finds clusters in a manner that make
the clustered data suitable for training classifiers for each underlying
subpopulation. Our experiments on synthetic and real benchmark datasets
demonstrate the efficacy of DeepCAC over previous methods for combined
clustering and classification.

##  1 Introduction

Many real datasets have complex underlying structures such as clusters and
intrinsic manifolds. For classification tasks on such data, linear classifiers
fail to learn well because of the inherent non-linear data distribution. Non-
linear classifiers such as (deep) neural networks perform well in such cases,
but often require large training data sets to achieve good generalization.
When clusters are found or suspected in the data, it is well known that
classification performance benefits from incorporating knowledge of such
cluster structure in the model, for both linear and non-linear classifiers [1,
2, 3, 4].

As an example, consider the problem of predicting the risk of disease using
patients’ clinical data. Patient populations, even for a single disease, show
significant clinical heterogeneity. As a result, subpopulations (called
subtypes) having relatively homogeneous clinical characteristics can often be
found in the data. Models that do not consider underlying subtypes may be
consistently underestimating or overestimating the risks in specific subtypes
[5], and risk models that account for subtypes are more effective [6, 7, 4,
8]. Similar examples illustrate the benefit of clustering to build classifiers
in, e.g., image processing [9, 10] and natural language processing [11].

Previous works on using clustering for classification broadly fall into two
categories. The first group of techniques modify specific classification
techniques to account for the underlying clusters, e.g., Clustered SVMs [2].
These techniques are closely tied to the modified classifier and inherit both
its modeling strengths and weaknesses. The second and more common approach is
to first cluster the data and then independently train classifiers on each
cluster. Although simple and intuitive, such a ‘cluster-then-predict’ approach
is not designed to form clusters optimized to improve the performance of
classifiers trained on those clusters. To the best of our knowledge, the
question of performing clustering to improve the performance of classifiers
trained on the clusters has not been addressed by previous literature.

Thus, in this paper, we first investigate the fundamental question of when and
how clustering can help in obtaining accurate classifiers. Our analysis yields
novel insights into the benefits of using simple classifiers trained on
clusters compared to simple or complex (in terms of Rademacher complexity
[12]) classifiers trained without clustering. It provides clues on when such a
clustering-based approach may or may not improve the subsequent
classification. This leads to the design of our first clustering-based
algorithm for classification, called Clustering Aware Classification (CAC).
CAC finds clusters that are intended to be used as training datasets by the
(base) classifiers of choice e.g., logistic regression, SVM, or neural
networks. The key idea of our approach is to induce class separability
(polarization) within each cluster, for better downstream classification, in
addition to partitioning the data. This is effected by designing a cost
function that can be used within the optimization framework of $k$-means.

Theoretical and empirical analysis of CAC demonstrates the benefits of
inducing class separability in clusters for downstream classification.
However, linear separability in CAC and clustering in the data space do not
yield good quality clusters. To address this limitation we turn to recent deep
clustering methods that have shown the efficacy of clustering on low-
dimensional embeddings obtained from deep representation learning, through
autoencoders. Adopting this approach for simultaneous clustering and
classification is not straightforward as we face two hurdles. First, the
class-separability loss in CAC cannot be optimized directly during network
training. Second, we often obtain degenerate clustering solutions with empty
clusters. We solve these two problems in our second algorithm DeepCAC, a
neural variant of CAC, that uses an additive margin softmax loss to induce
class separability in clusters and a normalization term to avoid degenerate
solutions. In summary, our contributions are:

  1. 1.

Our theoretical analysis provides insights into the fundamental question of
how clustering can aid in potentially improving the performance of classifiers
trained on the clusters.

  2. 2.

We propose the concept of class separation aware clustering and provide a
theoretical result showing how class separation bounds the log-loss of
clusters. We design a simple, proof-of-concept algorithm, Clustering Aware
Classification (CAC) based on $k$-means algorithm. We conduct extensive
empirical studies on synthetic data and real data to evaluate its efficacy and
validate our theoretical results.

  3. 3.

We propose DeepCAC, a novel model for simultaneous clustering and
classification that realizes cluster-specific class separation through
additive margin softmax loss. We introduce novel techniques to stabilize
training and prevent degenerate clusters.

  4. 4.

Our experimental results on benchmark clinical datasets show that DeepCAC
yields improved performance over the state-of-art approaches for combined
clustering and classification on large, highly imbalanced datasets while being
comparable on mid-sized datasets. We also demonstrate the practical utility of
our approach through a case study on the prediction of length of stay in
Intensive Care Units in hospitals.

REPRODUCIBILITY: Our code and datasets are publicly available at this
anonymous link.

##  2 Related Work

The idea of training multiple local classifiers on portions of the dataset has
been extensively studied for specific classifiers [13, 14, 15, 16, 17, 18, 19,
20]. For instance, [21] presents a novel locality-sensitive support vector
machine (LSSVM) for the image retrieval problem. Locally Linear SVM [22] has a
smooth decision boundary and bounded curvature. Its authors show how functions
defining the classifier can be approximated using any local coding scheme.

There are other related works, which aim to find suitable representations of
raw data such that the performance in downstream prediction tasks is better
when they use the learned embeddings. Large Margin Nearest Neighbour (LMNN)
[23] introduces the much-celebrated triplet loss. In this work, the authors
find a data-specific Mahalanobis distance embedding for the data, subject to
the constraint that $k$ similarly labeled points are mapped in the
neighborhood of every point. The transformed data is more amenable for a $k$
Nearest Neighbour classifier to work with. [24] extends LMNN to make it
parameter-free. Some Bayesian approaches have been developed for combined
classification and clustering, e.g., [1, 25] but they are computationally
expensive.

Recent neural models for combined clustering and classification, that are
closest to our work, are DMNN, GRASP and, AC-TPC. In Deep Mixture Neural
Network (DMNN) [4] neural representations, from an encoder, are clustered
using softmax gating and a mixture of experts, comprising neural networks, is
used to predict risk. However, as seen in our experiments, clustering through
softmax gating does not yield well-characterized subtypes and does not improve
risk prediction. GRASP [26] aims to boost healthcare models by incorporating
auxiliary information from similar patients. In GRASP, clustering and
prediction processes influence and enhance each other over iterations and thus
it can be viewed as an algorithm for simultaneous classification and
clustering. In [27] an Actor-Critic Approach for Temporal Predictive
Clustering (AC-TPC) is designed wherein latent representations from patient
data are clustered ensuring intra-cluster homogeneity in outcomes. A predictor
neural network is conditioned on cluster centroids, with actor-critic
training.

##  3 Background

Given a set of data samples $X=(x_{1},x_{2},\cdots,x_{N})$ with $N$ records
$x_{i}\in\mathbb{R}^{d}$ together with binary labels
$y_{i}\in\left\\{0,1\right\\}$, the task of clustering is to group the $N$
points into $K$ clusters. $K$-means is arguably the most widely adopted
algorithm due to its simplicity, speed, properties that are well studied in
literature [28, 29]. It works by optimizing the following cost function:

$\displaystyle\min_{\boldsymbol{M}\in\mathbb{R}^{M\times
K},\left\\{\boldsymbol{s}_{i}\in\mathbb{R}^{K}\right\\}}$
$\displaystyle\sum_{i=1}^{N}\left\|\boldsymbol{x}_{i}-\boldsymbol{M}\boldsymbol{s}_{i}\right\|_{2}^{2}$
$\displaystyle\text{s.t.\
}s_{j,i}\in\\{0,1\\},\mathbf{1}^{T}\boldsymbol{s}_{i}=1\quad\forall i,j$

where $\boldsymbol{s}_{i}$ is the assignment vector of data point $i$ which
has only one non-zero element, $s_{j,i}$ denotes the $j^{th}$ element of
$\boldsymbol{s}_{i}$, and the $k^{th}$ column of $M$ (the cluster assignment
matrix), i.e., $m_{k}$, denotes the centroid of the $k^{th}$ cluster.
$k$-means works well when the data points are evenly distributed about their
centroids. Real world data, however, are generally high dimensional and thus
not ‘$k$-means friendly’. The Deep Clustering Network (DCN) [30] algorithm
solves this problem by designing a deep neural network (DNN) structure and the
associated joint optimization criterion for joint dimensionality reduction
(DR) and clustering instead of using DR as a mere preprocessing technique,
also followed in other works, e.g. [31, 32]. The loss function they optimize
takes the form:

$\min_{\mathcal{U},\mathcal{W}}\ell(X,g(f(X)))+\beta\cdot\sum_{i=1}^{N}\|f(x_{i})-Ms_{i}\|^{2}+\gamma\cdot
r(f(X))$

where $X=[x_{1},\cdots,x_{N}]$, $\beta>0$ is a parameter for balancing data
fidelity and the latent cluster structure; $\ell$ is a function that measures
the reconstruction error. Popular choices for $\ell$ include the KL divergence
loss and least square loss; $r$ is a regularization imposed upon the latent
embeddings to encourage other properties (like class separability in our case)
weighted by $\gamma>0$.

##  4 Problem Statement

Let $X=(x_{1},x_{2},\cdots,x_{N})$ be a training dataset with $N$ records
$x_{i}\in\mathbb{R}^{d}$ together with binary labels
$y_{i}\in\left\\{0,1\right\\}$. Given an integer $k\geq 1$, our goal is to:

  1. 1.

Divide $X$ into $k$ non-empty, distinct clusters
$\mathcal{C}=\\{C_{1},C_{2},\cdots,C_{k}\\}$, and

  2. 2.

Obtain a collection of $k$ classifiers
$\mathcal{F}=\\{f_{1},f_{2},\cdots,f_{k}\\}$ where each
$f_{j}:C_{j}\rightarrow\left\\{0,1\right\\}^{|C_{j}|}$ is trained on all
$x_{i}\in C_{j}$ with the objective
$\mathop{\mathrm{argmin}}_{\mathcal{F},\mathcal{C}}\sum_{j=1}^{k}\sum_{i\in
C_{j}}\ell(f_{j}(x_{i}),y_{i}).$

There is no restriction on the choice of the classifier, which is determined
apriori by the user.

##  5 Can Clustering Aid Classification?

We provide a principled motivation behind our clustering approach by analyzing
when clustering can potentially help obtain accurate classifiers. Our analysis
yields crucial insights into developing the CAC framework. Fix
$j\in\\{1,\dots,k\\}$ and let $S_{j}=\\{(x_{i},y_{i})\\}_{i=1}^{m_{j}}$ be the
training dataset from the $j$-th cluster (having $m_{j}$ points) with
$x\in\mathcal{X}_{j}$ and $y\in\mathcal{Y}_{j}$ s.t.
$\mathcal{X}_{j}=\\{x:x\in C_{j}\\}$ and $\mathcal{Y}_{j}=\\{y:y\in C_{j}\\}$.
Then, the following theorem — a direct application of a previous result [33,
12] to our problem — suggests a potential benefit of clustering in terms of
the expected error $\mathbb{E}_{x,y}[\ell(f(x),y)]$ for unseen data:

######  Theorem 1 (Proof in Appendix 11.1).

Let $\mathcal{F}_{j}$ be a set of maps $x\in C_{j}\mapsto f_{j}(x)$. Let
$\mathcal{F}=\\{x\mapsto f(x):f(x)=\sum_{j=1}^{K}\mathbbm{1}\\{x\in
C_{j}\\}f_{j}(x),f_{j}\in\mathcal{F}_{j}\\}$. Suppose that
$0\leq\ell\left(q,y\right)\leq\lambda_{j}$ for any
$q\in\\{f(x):f\in\mathcal{F}_{j},x\in C_{j}\\}$ and $y\in\mathcal{Y}_{j}$.
Then, for any $\delta>0$, with probability at least $1-\delta$, the following
holds: for all maps $f\in\mathcal{F}$,

$\displaystyle\mathbb{E}_{x,y}[\ell(f(x),y)]\leq\sum_{j=1}^{K}\Pr(x\in
C_{j})\cdot\biggl{(}\frac{1}{m_{j}}\sum_{i=1}^{m_{j}}\ell(f(x_{i}^{j}),y_{i}^{j})+$
$\displaystyle
2\hat{\mathcal{R}}_{m_{j}}(\ell\circ\mathcal{F}_{j})+3\lambda_{j}\sqrt{\frac{\ln(K/\delta)}{2m_{j}}}\biggr{)},$
(1)

where
$\hat{\mathcal{R}}_{m_{j}}(\ell\circ\mathcal{F}_{j}):=\mathbb{E}_{\sigma}[\sup_{f_{j}\in\mathcal{F}_{j}}\frac{1}{m_{j}}\sum_{i=1}^{m_{j}}\sigma_{i}\ell(f_{j}(x_{i}),y_{i})]$,
$Pr(x\in C_{j})=1$ if $x\in C_{j}$ and $\sigma_{1},\dots,\sigma_{m_{j}}$ are
independent uniform random variables taking values in $\\{-1,1\\}$.

Theorem 1 shows that the expected error $\mathbb{E}_{x,y}[\ell(f(x),y)]$ for
unseen data is bounded by three terms: the training error
$\frac{1}{m_{j}}\sum_{i=1}^{m_{j}}\ell(f(x_{i}),y_{i})$, the Rademacher
complexity $\mathcal{R}_{m_{j}}(\ell\circ\mathcal{F}_{j})$ of the set of
classifiers $\mathcal{F}_{j}$ on the $j$-th cluster, and the last term
$O({\ln(K/\delta)}/{2m_{j}})$ in equation (1). To apply Theorem 1 to models
without clustering, we can set the $j$-th cluster to contain all data points
with $m_{j}=N$.

The upper bound can be used to analyze the benefit of using a simple model
(e.g., a linear model) with clustering compared to two cases of (1) a simple
model and (2) a complex model (e.g., a deep neural network), both without
clustering. For a simple model without clustering, the training error term
$\frac{1}{m_{j}}\sum_{i=1}^{m_{j}}\ell(f(x_{i}^{j}),y_{i}^{j})$ in equation
(1) can be large, because a simple model may not be able to sufficiently
separate training data points (underfitting) to minimize the training error.
In the case of a complex model without clustering, the training error can be
small but the Rademacher complexity
$\mathcal{R}_{m_{j}}(\ell\circ\mathcal{F}_{j})$ tends to be large. A simple
model with clustering can potentially trade-off these by minimizing Rademacher
complexity $\mathcal{R}_{m_{j}}(\ell\circ\mathcal{F}_{j})$ while making the
training data in the cluster linearly separable to minimize training error
$\frac{1}{m_{j}}\sum_{i=1}^{m_{j}}\ell(f(x_{i}^{j}),y_{i}^{j})$. This
observation leads us to explore ways to induce class separability in data
clusters.

##  6 CAC

The previous section discusses factors that give us hints of possible
scenarios when clustering can aid classification. Using a simple model with
clustering can be potentially advantageous when the first and second terms in
the RHS of Equation (1) are dominant. It thus motivates the formation of
clusters, each of which can be linearly separable internally with respect to
the classes for further improved performance of downstream simple classifiers.
We test our idea by designing a simple algorithm, Clustering Aware
Classification (CAC), that finds clusters to be used as training datasets by a
chosen classifier. The key idea is to induce class separability within
clusters to aid downstream cluster-specific classifiers. During clustering, we
measure the class separability by developing a metric based on class-specific
centroids within each cluster, and theoretically analyze the effect of its use
on the classification error.

#### Class Separability:

We use a simple heuristic to measure class separability within each cluster.
For each cluster $C_{j}$ ($j\in[k]$), we define: cluster centroid:
$\mu(C_{j}):=|C_{j}|^{-1}\sum_{x\in C_{j}}x_{i}$, positive centroid:
$\mu^{+}(C_{j}):=(\sum_{x_{i}\in C_{j}}y_{i})^{-1}\sum_{x_{i}\in
C_{j}}y_{i}x_{i}$, and negative centroid: $\mu^{-}(C_{j}):=({\sum_{x_{i}\in
C_{j}}(1-y_{i})})^{-1}\sum_{x_{i}\in C_{j}}(1-y_{i})x_{i}$. Class separability
is defined as the distance between positive and negative centroids within each
cluster i.e. $\|\mu^{+}-\mu^{-}\|$.

#### Bounding Log-Loss of Classifiers in terms of Class Separation:

We now show how class separation within clusters has a direct effect on the
training error of classifiers employing log-loss. The following theorem also
validates our choice of using $\|\mu^{+}-\mu^{-}\|$ as a heuristic to measure
class separability.

######  Theorem 2 (Proof in Appendix 11.3).

Let $X=(x_{1},x_{2},\cdots,x_{N})$ be a training dataset with $N$ records
$x_{i}\in\mathbb{R}^{d}$ together with binary labels
$y_{i}\in\left\\{0,1\right\\}$. Define the log-loss over the entire dataset as
: $\ell(X)=-\Sigma_{i}y_{i}\ln(p(x_{i}))+(1-y_{i})\ln(1-p(x_{i}))$, where
$p(x_{i})=[1+\exp(-\beta x_{i})]^{-1}$ and
$\beta=\mathop{\mathrm{argmin}}_{\beta}\ell(X)$. Then,

$C_{1}-(C_{3}\beta\mu^{+}-C_{4}\beta\mu^{-})\leq\ell(X)\leq
C_{2}-(C_{3}\beta\mu^{+}-C_{4}\beta\mu^{-})$

where $C_{1}=N\ln(2),\ C_{2}=N\ln(1+\exp(c))-\frac{Nc}{2},\
C_{3}=\frac{N^{+}}{2},\ C_{4}=\frac{N^{-}}{2},\ N^{+}=\sum_{x_{i}\in X}y_{i}$,
$N^{-}=\sum_{x_{i}\in X}(1-y_{i})$ and $c=\mathop{\mathrm{argmax}}_{i}\|\beta
x_{i}\|$.

#### Clusters with Class Separability:

To induce our notion of class separability within clustering we consider the
$k$-means clustering formulation that is widely used for its simplicity,
effectiveness, and speed. Clusters using $k$-means are obtained by minimizing
the size-weighted sample variance of each cluster:
$\mathcal{D}(X)=\sum_{p=1}^{k}\inf_{\mu(C_{p})\in X}\sum_{i\in
C_{p}}\|x_{i}-\mu(C_{p})\|^{2}.$ To induce class separability, a natural
formulation is to add a cost with respect to class separability for each
cluster. With our measure for class separability, and $\alpha>0$ as a class
separation hyperparameter, we get $\phi(C_{j})=\sum_{i\in
C_{j}}\left(\|x_{i}-\mu(C_{j})\|^{2}-\alpha\cdot\|\mu^{+}(C_{j})-\mu^{-}(C_{j})\|^{2}\right)$.

Defining the cost function in this manner encourages the decrease of cluster
variance term and increase of the class separability term, weighted by
$\alpha$. Consequently, the overall cost function defined as
$\phi(\\{C_{j}\\}_{1}^{k}):=\sum_{j=1}^{k}\phi(C_{j})$ and the CAC algorithm
aims to minimize that. We optimize for $\phi(\\{C_{j}\\}_{1}^{k})$ by using
the Hartigan’s method [34] instead of the more common Lloyd’s Algorithm [28].
Our approach is summarized in Algorithm 1. $\Phi(x_{i};C_{p},C_{q})$
represents the overall decrease in the cost function for the entire dataset if
the point $x_{i}$ is moved from cluster $C_{p}$ to $C_{q}$ (see Appendix 10
for more details).

In conclusion, Theorem 2 points out that under certain conditions (See Lemma 2
in Appendix 11.2), the upper and lower bounds of log-loss provably decrease.
The gap between the upper and lower bounds is a direct function of the breadth
of the cluster. Thus as clusters become tighter, the training log-loss of the
classifiers becomes more tightly bound. Classification results on real
datasets (see Table 5 in Appendix) show that CAC outperforms the simple
cluster-then-predict approach on multiple base classifiers.

We however note that CAC has several limitations. Firstly, CAC assumes linear
class separability which is not a realistic assumption in real world data.
Moreover, the restriction of working in the original data space leads to poor
quality of clusters as compared to those found by plain $k$-means (c.f. Fig. 5
in Appendix). CAC initialized with $k$-means has a good Silhouette Index which
decreases with training iterations). We thus turn to representation learning
to discover transformations that conform to requirements of class separability
and clustering while not being brittle at the same time. This motivates the
design of the neural variant of CAC, DeepCAC, which addresses these
limitations by clustering in a low-dimensional embedding space instead of the
data space, where the embeddings are obtained via non-linear dimensional
reduction algorithms like deep autoencoders.

Input: Training Data: $X\in\mathbb{R}^{N\times d}$, binary labels $y^{n\times
1}\in\\{0,1\\}^{N}$, $\\{C_{j}\\}_{1}^{k}$, $\\{f_{j}\\}_{1}^{k}$ and $\alpha$

1 $\triangleright$ Initialization

2 Compute $\mu(C_{j}),\mu^{+}(C_{j}),\mu^{-}(C_{j})\ \forall\ C_{j}\ s.t.\
j\in\\{1,\cdots,k\\}$.

3 $\triangleright$ Algorithm

4 while  _not converged_ do

5 for  _$i\in\\{1\ldots N\\}$_ do

6 if  _Removing $x_{i}\in C_{p}$ from its cluster does not lead to a $1$-class
cluster_ then

7 $\triangleright$ Assign new cluster to $x_{i}$

8

9 Let $q:=\mathop{\mathrm{argmin}}_{j}{\Phi(x_{i};C_{p},C_{j})}$ (breaking
ties arbitrarily).

10 if  _$\Phi(x_{i},C_{p},C_{q}) <0$_ then

11 Assign $x_{i}$ to $C_{q}$ from $C_{p}$ and update $\mu(C_{p})$,
$\mu(C_{q})$, $\mu^{\pm}(C_{p})$ and $\mu^{\pm}(C_{q})$.

12 Otherwise, let $x_{i}$ remain in $C_{p}$.

13

14

15$\triangleright$ Train Classifiers

16 For every cluster $C_{j}$, train a classifier $f_{j}$ on
$(\mathcal{X}_{j},\mathcal{Y}_{j})$.

Output Classifiers $\mathcal{F}=\\{f_{j}\\}_{j=1}^{j=k}$ and cluster centroids
$\mu=\\{\mu_{j}\\}_{j=1}^{j=k}$

Algorithm 1 CAC

##  7 DeepCAC

#### Network Architecture:

We propose to employ a Stacked Autoencoder (SAE) for dimensionality reduction.
Figure 2 illustrates the DeepCAC architecture. An SAE consists of an encoder
(E) and decoder (D) parameterized by $(\mathcal{U},\mathcal{V})$ as
$E(\mathcal{U}):X\xrightarrow{}Z$ and $D(\mathcal{V}):Z\xrightarrow{}X$. The
encoder transforms the raw data into the embedded data space $Z$ (or the
‘bottleneck’ layer). The ‘decoding’ layers that try to reconstruct the data
from the latent space are on the right-hand side. In the subsequent
classification stage after the clustering stage, there exist $k$ local
networks $(\\{LN_{j}(\mathcal{W}_{j})\\}_{j=1}^{k})$ that are trained
separately from the autoencoder. Similar to CAC, the data points are clustered
but now in the embedded data space $Z$. Note that, unlike cluster-then-predict
approaches, clustering is not independent of classification since class labels
are used during clustering as described below.

|
---|---

(a)

(b)

Figure 1:  (a) Silhouette scores vs. epochs. (b) Sensitivity Analysis with
AUC/AUPRC and Silhouette scores (on DeepCAC) on CIC dataset. $k=3$ in all
experiments.

#### Loss Function:

The DeepCAC loss function consists of 3 parts: The auto-encoder reconstruction
error term ($\|x_{i}-D(E(x_{i}))\|^{2}$) that regularizes the encoder as
suggested by [35]. The sum of squared errors (SSE) term
$\left(\frac{\|E(x_{i})-Ms_{i}\|^{2}}{|C_{j}|-1+\delta}\right)$ that
encourages points to lie to close to their cluster centroid thus forming
$k$-means friendly clusters, and a third term that we explain in the next
paragraph. Unlike previous approaches [36] that employ ad-hoc methods like
cluster resampling in the case of an empty cluster, we normalize the cluster
SSE (dividing it by the size of cluster) to stabilize training and prevent
degenerate solutions.

The CAC loss function encourages cluster structure formation and intra-cluster
class separation by directly optimizing for the distance between class cluster
centroids. The class separation term in CAC encourages a gap between
individual class points in respective clusters. But we observed that DeepCAC
was not able to directly optimize such a formulation of class separability
through gradient descent. So we replace the CAC class separation term with the
well-known Additive Margin Softmax Loss (AM Softmax) [37] as another way of
inducing class separability within clusters. The AM Softmax loss includes an
additive margin to the standard softmax loss to push the classification
boundary closer to the weight vector of each class. The final loss function of
DeepCAC thus becomes:

$\displaystyle L$ $\displaystyle=\sum_{j=1}^{k}\sum_{i\in
C_{j}}\|x_{i}-D(E(x_{i}))\|^{2}+\frac{\beta*\|E(x_{i})-Ms_{i}\|^{2}}{|C_{j}|-1+\delta}-$
(2)
$\displaystyle\frac{\alpha}{|C_{j}|}\sum_{i}\log\frac{e^{s\cdot\left(W_{y_{i}}^{T}z_{i}-m\right)}}{e^{s\cdot\left(W_{y_{i}}^{T}z_{i}-m\right)}+\sum_{j=1,j\neq
y_{i}}^{c}e^{sW_{j}^{T}z_{i}}}$ $\displaystyle\text{s.t.}\
s_{j,i}\in\\{0,1\\},\mathbf{1}^{T}s_{i}=1\ \forall i,j$

where $W^{T}_{j}$ is the $j$-th column of the last fully connected layer of
the AMSoftmax loss. $M$ denotes the centroid matrix and $s_{i,j}$ is the
assignment vector of data point $x_{i}$ which has only one non-zero element.
$s_{j,i}$ denotes the $j^{th}$ element of $s_{i}$. $\mu_{k}$, the $k^{th}$
column of $M$, denotes the centroid of the $k^{th}$ cluster, $z_{i}$ is the
embedding for $x_{i}$ and $|C_{j}|$ is the cardinality of cluster $C_{j}$.

#### How does AM Softmax loss induce class separability?

######  Theorem 3 (Proof in Appendix 11.4).

Let $X=(x_{1},x_{2},\cdots,x_{N})$ be a training dataset with $N$ records
$x_{i}\in\mathbb{R}^{d}$ together with binary labels
$y_{i}\in\left\\{0,1\right\\}$. Define the AM Softmax loss over the entire
dataset as :
$-\sum_{i}\log\frac{e^{s\cdot\left(W_{y_{i}}^{T}z_{i}-m\right)}}{e^{s\cdot\left(W_{y_{i}}^{T}z_{i}-m\right)}+\sum_{j=1,j\neq
y_{i}}^{c}e^{sW_{j}^{T}z_{i}}}$. Then,

$K_{1}-\Gamma(K_{3}\mu^{+}-K_{4}\mu^{-})\leq L_{AMS}(X)\leq
K_{2}-\Gamma(K_{3}\mu^{+}-K_{4}\mu^{-})$

where $K_{1}=N\left(\log 2+\frac{sm}{2}\right),\ K_{2}=N(1+sm),\
K_{3}=sN^{+},\ K_{4}=sN^{-},\ N^{+}=\sum_{x_{i}\in X}y_{i}$,
$N^{-}=\sum_{x_{i}\in X}(1-y_{i})$ and $\Gamma=W^{T}_{+}-W^{T}_{-}$.

The upper and lower bounds for the AM-softmax loss are strikingly similar to
those of the logistic loss found in theorem 2. We note that as $L_{AMS}$
decreases, it pushes the lower bound to become smaller. The agent vectors
($W_{+/-}$) will lie nearby the class centroids ($\mu^{+/-}$) [38] and can
thus be approximated as $W_{+}\sim\mu^{+}$ and $W_{-}\sim\mu^{-}$. The lower
bound for $L_{AMS}$ can then be simplified as
$K_{1}-\Gamma(K_{3}\mu^{+}-K_{4}\mu^{-})=K_{1}-sN(1-\mu^{+}\cdot\mu^{-})$
(since $|\mu^{+}|=|\mu^{-}|=1$). This implies that as $L_{AMS}$ pushes down
the lower bound, $\mu^{+}\cdot\mu^{-}$ must decrease i.e. class centroids move
further away (separate) from each other on the $L_{2}$ hypersphere. From
theorem 2, we know that an increasing class separation decreases the training
log-loss. Thus replacing CAC loss with the AM-Softmax loss achieves the same
purpose.

Figure 2: In the clustering stage an encoder is trained to find
representations that are clustered with good class separability. In the
classification stage, cluster-specific classifiers are trained on the
representations. $L_{AM}$ and $L_{C}$ are defined in eqn. 2.

#### Training:

DeepCAC is trained in 3 stages: (i) Pre-training, (ii) Training the clustering
network and (iii) Training the local networks. During pre-training the
autoencoder parameters $(\mathcal{U},\mathcal{V})$ are initialized by training
the autoencoder to minimize the reconstruction loss without activating the
DeepCACloss functions. Once the autoencoder is initialized, the data
embeddings are clustered using the $k$-means algorithm and the cluster
centroids are initialized. The overall DeepCAC loss function is non-convex and
difficult to optimize. Stochastic gradient descent (SGD) cannot be directly
applied to jointly optimize $\mathcal{U},\mathcal{V},M$, and $\\{s_{i}\\}$
because the block variable $\\{s_{i}\\}$ is constrained on a discrete set. We
thus use an alternating scheme, similar to [30], to optimize the subproblems
w.r.t. one of $M,\\{s_{i}\\}$ and $(\mathcal{U},\mathcal{V})$ while keeping
the other two sets of variables fixed. Further details regarding the updating
of network parameters can be found in Appendix 12. Finally, the local networks
are trained on the clusters found by the encoder in the representation space.
Algorithm 2 summarizes the entire procedure.

Input: Training Data: $X\in\mathbb{R}^{n\times d}$, class labels $y^{n\times
1}\in[\mathcal{B}]^{n}$, $\\{C_{j}\\}_{1}^{k}$, $\\{f_{j}\\}_{1}^{k}$

1 $\triangleright$ Initialization

2 Pretrain $E$ and $D$ to initialize $\mathcal{U},\mathcal{V}$

3 Compute $\mu(C_{j})\forall\ C_{j}\ s.t.\ j\in\\{1,\cdots,k\\}$.

4 $\triangleright$ Algorithm

5 while  _not converged_ do

6 for  _every mini-batch $\mathcal{X}_{b}$_ do

7 Update Network parameters by backpropagating $L$ (Eq. 2)

8 Update cluster assignments

9 Update cluster centroids

10

11$\triangleright$ Train Classifiers

12 $\mathcal{Z}\leftarrow E(\mathcal{X})$

13 For every cluster $C_{j}$, train a classifier $f_{j}$ on
$(\mathcal{Z}_{j},\mathcal{Y}_{j})$.

Output Output Trained Network $E$ and cluster centroids
$\mu=\\{\mu_{j}\\}_{j=1}^{j=k}$ in embedded space.

Algorithm 2 DeepCAC

##  8 Experiments

We perform two sets of experiments. The first set of experiments, on synthetic
data, studies the sensitivity of CAC on various characteristics of the data
like cluster separation and class separation within clusters. We find that
cluster-then-predict method does enhance overall classifier performance and
exploiting class separation can lead to further improvements. Appendix 11.8
presents the details of these experiments and the results. In the second set
of experiments, described below, we compare the performance of CAC with that
of other methods on real benchmark datasets.

Table 1: Dataset Summary. MAJ: proportion of majority class. Dataset | #Instances | #Features | MAJ
---|---|---|---
Sepsis [39] | $30661$ | $209$ | $0.07$
WID Mortality [40] | $91711$ | $241$ | $0.91$
Diabetes [41] | $100000$ | $9$ | $0.41$
Respiratory [42] | $22450$ | $486$ | $0.92$
CIC [43] | $12000$ | $117$ | $0.85$
CIC-LOS | $12000$ | $116$ | $-$

#### Real Datasets:

We evaluate CAC and DeepCAC on 6 clinical datasets (Table 1). CIC refers to
the dataset from the 2012 Physionet challenge [44] to predict in-hospital
mortality of intensive care unit (ICU) patients at the end of their hospital
stay. The dataset has time-series records, comprising various physiological
parameters, of $12,000$ patient ICU stays. We follow the data processing
scheme of [43] (the top-ranked team in the competition) to obtain a static
117-dimensional feature vector for each patient. The Sepsis dataset is derived
from the 2019 Physionet challenge of sepsis onset prediction. It has time
series records, comprising various physiological parameters of $\sim 40000$
patients. We follow the data processing scheme of the competition winners [45]
to obtain static 89 dimensional features for each patient. WID data is from
the Women In Data Science challenge [40] to predict patient mortality. The
Diabetes dataset is from the UCI Repository where the task is to predict
patient readmission. The Respiratory data has been extracted by us for the
tasks of Acute Respiratory Distress Syndrome (ARDS) prediction. For the Sepsis
and ARDS datasets, we use the first, last, median, minimum, and maximum values
in the first 24 hours as features for the temporal variables. The final
feature vector dimensions for ARDS and Sepsis data are 486 and 209
respectively. All the above tasks are posed as binary classification problems.
We also derive a multiclass dataset (CIC-LOS) from the CIC dataset where we
predict the Length of Stay (LOS), discretized into 3 classes (based on 3
quartiles).

Table 2: AUPRC of DeepCAC and other baselines. Best values in bold. Following
KM, DCN, and IDEC, we use the same local classifier (denoted by -Z) that is
used by DeepCAC. AUC values, that show a similar trend, are shown in Appendix
13.

Dataset | k | KM-Z | DCN-Z | IDEC-Z | DMNN | AC-TPC | GRASP | DeepCAC
---|---|---|---|---|---|---|---|---
|  | $-$ | (2017) | (2017) | (2020) | (2020) | (2021) | (Ours)
Diabetes | $2$ | $0.528\pm 0.011$ | $0.556\pm 0.002$ | $0.553\pm 0.007$ | $0.53\pm 0.005$ | $-$ | $0.538\pm 0.007$ | $\mathbf{0.558\pm 0.004}$
| $3$ | $0.514\pm 0.016$ | $0.556\pm 0.003$ | $0.548\pm 0.01$ | $0.539\pm 0.007$ | $0.523\pm 0.0$ | $0.542\pm 0.007$ | $0.56\pm 0.002$
| $4$ | $0.507\pm 0.02$ | $0.556\pm 0.003$ | $0.553\pm 0.005$ | $0.536\pm 0.004$ | $0.5\pm 0.0$ | $0.544\pm 0.008$ | $0.555\pm 0.006$
CIC | $2$ | $0.568\pm 0.014$ | $0.609\pm 0.036$ | $0.674\pm 0.036$ | $0.636\pm 0.03$ | $-$ | $\mathbf{0.757\pm 0.036}$ | $0.753\pm 0.023$
| $3$ | $0.527\pm 0.028$ | $0.612\pm 0.017$ | $0.587\pm 0.032$ | $0.667\pm 0.016$ | $0.656\pm 0.0$ | $0.755\pm 0.039$ | $0.746\pm 0.018$
| $4$ | $0.54\pm 0.033$ | $0.594\pm 0.025$ | $0.618\pm 0.016$ | $0.636\pm 0.025$ | $0.663\pm 0.0$ | $0.743\pm 0.031$ | $0.743\pm 0.014$
CIC-LoS | $2$ | $0.396\pm 0.008$ | $0.44\pm 0.02$ | $0.452\pm 0.013$ | $0.429\pm 0.007$ | $-$ | $0.478\pm 0.021$ | $0.485\pm 0.004$
| $3$ | $0.353\pm 0.019$ | $0.425\pm 0.022$ | $0.406\pm 0.029$ | $0.435\pm 0.013$ | $0.426\pm 0.0$ | $0.473\pm 0.026$ | $\mathbf{0.488\pm 0.008}$
| $4$ | $0.344\pm 0.018$ | $0.443\pm 0.025$ | $0.437\pm 0.014$ | $0.429\pm 0.007$ | $0.402\pm 0.0$ | $0.474\pm 0.018$ | $0.487\pm 0.006$
ARDS | $2$ | $0.552\pm 0.023$ | $0.563\pm 0.031$ | $0.601\pm 0.009$ | $0.536\pm 0.017$ | $-$ | $0.493\pm 0.004$ | $\mathbf{0.604\pm 0.013}$
| $3$ | $0.527\pm 0.022$ | $0.582\pm 0.017$ | $0.565\pm 0.025$ | $0.525\pm 0.012$ | $0.553\pm 0.004$ | $0.492\pm 0.004$ | $0.594\pm 0.014$
| $4$ | $0.503\pm 0.015$ | $0.533\pm 0.03$ | $0.588\pm 0.008$ | $0.551\pm 0.016$ | $0.55\pm 0.015$ | $0.569\pm 0.069$ | $0.592\pm 0.029$
Sepsis | $2$ | $0.532\pm 0.014$ | $0.595\pm 0.023$ | $0.597\pm 0.021$ | $0.539\pm 0.003$ | $-$ | $0.5\pm 0.005$ | $0.646\pm 0.037$
| $3$ | $0.515\pm 0.019$ | $0.593\pm 0.017$ | $0.596\pm 0.012$ | $0.531\pm 0.012$ | $0.579\pm 0.013$ | $0.496\pm 0.001$ | $\mathbf{0.654\pm 0.031}$
| $4$ | $0.517\pm 0.012$ | $0.553\pm 0.029$ | $0.601\pm 0.011$ | $0.531\pm 0.018$ | $0.574\pm 0.02$ | $0.499\pm 0.002$ | $0.628\pm 0.02$
WID-M | $2$ | $0.645\pm 0.026$ | $0.71\pm 0.029$ | $0.69\pm 0.061$ | $0.597\pm 0.013$ | $-$ | $0.702\pm 0.023$ | $\mathbf{0.723\pm 0.015}$
| $3$ | $0.565\pm 0.037$ | $0.679\pm 0.053$ | $0.666\pm 0.062$ | $0.583\pm 0.014$ | $0.596\pm 0.0$ | $0.698\pm 0.021$ | $0.721\pm 0.011$
| $4$ | $0.535\pm 0.044$ | $0.664\pm 0.048$ | $0.677\pm 0.049$ | $0.593\pm 0.014$ | $0.619\pm 0.0$ | $0.681\pm 0.014$ | $0.714\pm 0.021$

#### Experimental Setup:

We evaluate the performance of CAC with a cluster-then-predict approach where
$k$-means is used to cluster and multiple classifiers are used. We also
compare its performance with that of the classifier directly, where no
clustering is used. These are evaluated on a held-out test split comprising
$25\%$ of the data. DeepCAC and its baselines are evaluated on $5$ random
train-validation-test splits for each dataset in the ratio 57-18-25 (Test data
is 25% of the entire dataset and the validation dataset is 25% of the
remaining data). Standard binary classification metric, the AUPRC (Area Under
Precision-Recall curve) score is used to evaluate classifier performance, as
there is an imbalance in many datasets. All models are trained until the AUPRC
score on the validation data set plateaus. The Area under the ROC Curve (AUC)
is also reported in Appendix 13, Table 6.

#### Baselines:

For evaluating CAC, we consider $9$ classical base classifiers (X), both
linear and nonlinear and report results of X, KM+X, and CAC+X. These are LR,
Linear SVM, XGBoost (#estimators = 10), Linear Discriminant Analysis (LDA),
single Perceptron, Random Forest (#trees = 10), $k$ Nearest Neighbors ($k=5$),
SGD classifier and Ridge classifier (Ridge regressor predicting over the range
$[-1,1]$).

For evaluating DeepCAC, we use two kinds of baselines. The first set has
classifiers that employ a simple cluster-then-predict kind of method where
clustering is independently performed first and classifiers are trained on
each cluster (denoted by -Z). We compare with $3$ clustering methods $k$-means
(where we use an autoencoder to get embeddings which are then clustered using
$k$-means), Deep Clustering Network DCN [30], Improved Deep Embedded
Clustering (IDEC) [35] and DMNN [46]. The second set of baselines includes
methods where clustering and classification happen simultaneously. We compare
DeepCAC with GRASP [26] modified to use the same backbone model i.e. the
encoder. We also compare with AC-TPC [27] which uses an actor-critic model to
refine clusters depending on the feedback from the classification process.

#### Hyperparameters:

For DMNN and DeepCAC, the autoencoder has $3$ layers of sizes $64-32-64$ and a
two-layer local predictor network of size $30-1$. The local prediction
networks use Softmax and ReLU activation functions and are not regularized.
The hyperparameters for deep learning methods, KM-Z, DCN-Z ($\beta=2$), IDEC-Z
($\beta=0.5$) and DeepCAC ($\beta=20,\alpha=5$) are selected by conducting a
sensitivity analysis (see Fig. 1) on the training set of the CIC-LoS dataset.
For GRASP and AC-TPC, we use the hyperparameters suggested by the authors
found using sensitivity analysis. The learning rate for DeepCAC is set to
$2e-3$. The predictor, selector and encoder networks in AC-TPC are FCNs with
$64-64$, $64-64$, and $32-32$ neurons respectively.

#### Results:

The results for CAC are presented in Table 5 (Appendix 11.9) that summarises
the F1 scores of CAC and baselines evaluated in clinical data sets. This is in
line with Theorem 1 which predicts the better performance of multiple simple
classifiers compared to a single simple classifier. We also observe that CAC
performs better than the simple $k$-means + classification approach on 20 out
of 27 ($74\%$) experiments. This also serves as ablative evidence of the
contribution of linear separability criteria since removing the latter reduces
CAC to applying $k$-means and then predicting.

Table 2 presents the AUPRC scores obtained by DeepCAC and its baselines.
DeepCAC is consistently better than the simple combined clustering and
classification (cluster-then-predict) baselines i.e., DMNN, KM-Z, DCN-Z, and
IDEC-Z. This shows that classification aware clustering is necessary, as done
by GRASP and DeepCAC, to ensure good downstream classification performance.
GRASP and DeepCAC perform comparably on the CIC (moderately sized) dataset.2
DeepCAC outperforms GRASP by a significant margin on the rest of the datasets
(the larger and more imbalanced datasets) for different number of clusters.
Similar performance improvements are also observed when AUC is used as a
metric (in Appendix 13). The code for AC-TPC (provided by the authors) did not
run for $k=2$ on all datasets. Figure 1 and 5 show how the clustering
performance of DeepCAC does not deteriorate with increasing epochs as compared
to CAC.

#### Case Study:

To show the practical clinical applicability of DeepCAC we present a case
study in Appendix 14 on length of stay prediction. As expected, we see that
inferred clusters have differences in risk factors tailored to each
subpopulation.

|
---|---

(a)

(b)

Figure 3: Sensitivity Analysis and Ablation Study for DeepCAC w.r.t. $\alpha$ and $\beta$ hyperparameters for $k=3$ Table 3: AUPRC Scores for Time series datasets. Row-wise best result in bold. AC-TPC did not finish execution in time. AUPRC | k | GRASP-TS | DeepCAC-TS
---|---|---|---
ARDS-TS | 2 | $0.498$ | $\mathbf{0.615}$
ARDS-TS | 3 | $0.506$ | $\mathbf{0.605}$
ARDS-TS | 4 | $0.5$ | $\mathbf{0.565}$
Sepsis-TS | 2 | $0.501$ | $\mathbf{0.704}$
Sepsis-TS | 3 | $0.507$ | $\mathbf{0.672}$
Sepsis-TS | 4 | $0.495$ | $\mathbf{0.648}$

#### Ablation Study and Sensitivity Analysis:

We study the effect of $\alpha$ and $\beta$ hyperparameters on the
classification performance of DeepCAC by varying them on the range $[0.0,100]$
(see Fig. 3). Both AUC and AUPRC scores fall sharply as $\alpha$ is increased
from 0 but they eventually increase, plateauing after $\alpha=5$. The
classification performance does not vary much with $\beta$. A value of 0 leads
to the removal of the loss term; better results are obtained with non-zero
values indicating that both loss terms contribute to performance.

#### Extending DeepCAC for Other Data Modalities:

DeepCAC can be easily extended for other input data modalities such as images,
text and time series by modifying the encoder and decoder appropriately. We
demonstrate one such case by using an LSTM-based AE for time series data (see
Appendix 15 for more details). We evaluate all algorithms on the ARDS and
Sepsis datasets as mentioned in table 1. We use the first 24 hours of data to
predict risk (of each condition, separately) in the remaining ICU stay, which
is aligned with a hospital-centric schedule for prediction. Our experimental
evaluation shows that DeepCAC outperforms similar extensions of GRASP. As
expected, DeepCAC-TS also performs better than DeepCAC on the non time series
versions of ARDS and Sepsis datasets.

##  9 Conclusion

In this paper, we theoretically analyze potential reasons for the good
performance of classifiers trained on underlying clusters in data. Our
analysis yields insights into the benefits of using simple classifiers trained
on clusters compared to simple or complex classifiers trained without
clustering. We use our analysis to develop a simple prototype algorithm, CAC,
that enforces class separability within each group during cluster discovery.
Empirical and theoretical analysis of CAC further illuminates reasons for
clustering aiding classification. To further improve clustering in such
settings, we combine the benefits of deep representation learning and CAC in
our algorithm DeepCAC. We use novel techniques to stabilize training and
induce class separability within clusters in DeepCAC. Experiments on clinical
benchmark datasets demonstrate the efficacy of DeepCAC in classification and
clustering. A limitation of DeepCAC is that the hard definition of point
clusters forces the local classifiers to treat interior and fringe points
equally. This can lead to a loss in predictive performance and can be
addressed in the future.

## References

  * [1] Qiang Qian, Songcan Chen, and Weiling Cai.  Simultaneous clustering and classification over cluster structure representation.  Pattern Recognit., 45:2227–2236, 2012.
  * [2] Quanquan Gu and Jiawei Han.  Clustered support vector machines.  In AISTATS, 2013.
  * [3] Tanmoy Chakraborty.  Ec3: Combining clustering and classification for ensemble learning.  2017 IEEE International Conference on Data Mining (ICDM), pages 781–786, 2017.
  * [4] Xiangrui Li, D. Zhu, and Phillip D. Levy.  Predicting clinical outcomes with patient stratification via deep mixture neural networks.  AMIA Joint Summits on Translational Science proceedings. AMIA Joint Summits on Translational Science, 2020:367–376, 2020.
  * [5] Ralph Snyderman.  Personalized health care: From theory to practice.  Biotechnology Journal, 7, 2012.
  * [6] Ahmed M. Alaa, Jinsung Yoon, Scott Hu, and Mihaela van der Schaar.  Personalized risk scoring for critical care patients using mixtures of gaussian process experts.  ArXiv, abs/1605.00959, 2016.
  * [7] Harini Suresh, Jen J. Gong, and John V. Guttag.  Learning tasks for multitask learning: Heterogenous patient populations in the icu.  Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018.
  * [8] Zina M. Ibrahim, Honghan Wu, Ahmed A. Hamoud, Lukas Stappen, Richard J. B. Dobson, and Andrea Agarossi.  On classifying sepsis heterogeneity in the icu: insight using machine learning.  Journal of the American Medical Informatics Association : JAMIA, 27:437 – 443, 2020.
  * [9] Tae-Kyun Kim and Roberto Cipolla.  Mcboost: Multiple classifier boosting for perceptual co-clustering of images and visual features.  In NIPS, 2008.
  * [10] Mohammad Peikari, Sherine Salama, Sharon Nofech-Mozes, and Anne L. Martel.  A cluster-then-label semi-supervised learning approach for pathology image classification.  Scientific Reports, 8, 2018.
  * [11] Izzat Alsmadi and Ikdam Alhami.  Clustering and classification of email contents.  J. King Saud Univ. Comput. Inf. Sci., 27:46–57, 2015.
  * [12] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar.  Foundations of machine learning.  MIT Press, 2012.
  * [13] Sibylle Hess, Wouter Duivesteijn, and Decebal Constantin Mocanu.  Softmax-based classification is k-means clustering: Formal proof, consequences for adversarial attacks, and improvement through centroid based tailoring.  ArXiv, abs/2001.01987, 2020.
  * [14] Hind Elouedi, Walid Meliani, Zied Elouedi, and Nahla Ben Amor.  A hybrid approach based on decision trees and clustering for breast cancer classification.  2014 6th International Conference of Soft Computing and Pattern Recognition (SoCPaR), pages 226–231, 2014.
  * [15] Martin Vincent and Niels Richard Hansen.  Sparse group lasso and high dimensional multinomial classification.  Comput. Stat. Data Anal., 71:771–786, 2014.
  * [16] Andrea Visentin, Alessia Nardotto, and Barry O’Sullivan.  Predicting judicial decisions: A statistically rigorous approach and a new ensemble classifier.  2019 IEEE 31st International Conference on Tools with Artificial Intelligence (ICTAI), pages 1820–1824, 2019.
  * [17] Ahmed M. Mahfouz, Abdullah Abuhussein, Deepak Venugopal, and Sajjan G. Shiva.  Ensemble classifiers for network intrusion detection using a novel network attack dataset.  Future Internet, 12:180, 2020.
  * [18] William H. Beluch, Tim Genewein, A. Nürnberger, and Jan M. Köhler.  The power of ensembles for active learning in image classification.  2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9368–9377, 2018.
  * [19] Ivan Titov, A. Klementiev, Kevin Small, and Dan Roth.  Unsupervised aggregation for classification problems with large numbers of categories.  In AISTATS, 2010.
  * [20] Botao Hao, Will Wei Sun, Yufeng Liu, and Guang Cheng.  Simultaneous clustering and estimation of heterogeneous graphical models.  Journal of machine learning research : JMLR, 18, 2017.
  * [21] Guo-Jun Qi, Qi Tian, and Thomas S. Huang.  Locality-sensitive support vector machine by exploring local correlation and global regularization.  CVPR 2011, pages 841–848, 2011.
  * [22] Lubor Ladicky and Philip H. S. Torr.  Locally linear support vector machines.  In ICML, 2011.
  * [23] Kilian Q. Weinberger and Lawrence K. Saul.  Distance metric learning for large margin nearest neighbor classification.  In NIPS, 2005.
  * [24] Kun Song, Feiping Nie, Junwei Han, and Xuelong Li.  Parameter free large margin nearest neighbor for distance metric learning.  In AAAI, 2017.
  * [25] Weiling Cai, Songcan Chen, and Daoqiang Zhang.  A simultaneous learning framework for clustering and classification.  Pattern Recognit., 42:1248–1259, 2009.
  * [26] Chaohe Zhang, Xin Gao, Liantao Ma, Yasha Wang, Jiangtao Wang, and Wen Tang.  Grasp: Generic framework for health status representation learning based on incorporating knowledge from similar patients.  In AAAI, 2021.
  * [27] Changhee Lee and Mihaela Van Der Schaar.  Temporal phenotyping using deep predictive clustering of disease progression.  In ICML, 2020.
  * [28] Stuart P. Lloyd.  Least squares quantization in pcm.  IEEE Trans. Inf. Theory, 28:129–136, 1982.
  * [29] Adam Coates and A. Ng.  Learning feature representations with k-means.  In Neural Networks: Tricks of the Trade, 2012.
  * [30] Bo Yang, Xiao Fu, N. Sidiropoulos, and Mingyi Hong.  Towards k-means-friendly spaces: Simultaneous deep learning and clustering.  In ICML, 2017.
  * [31] Bo Yang, Xiao Fu, and N. Sidiropoulos.  Learning from hidden traits: Joint factor analysis and latent clustering.  IEEE Transactions on Signal Processing, 65:256–269, 2017.
  * [32] Jianwei Yang, Devi Parikh, and Dhruv Batra.  Joint unsupervised learning of deep representations and image clusters.  2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 5147–5156, 2016.
  * [33] Peter L Bartlett and Shahar Mendelson.  Rademacher and gaussian complexities: Risk bounds and structural results.  JMLR, 2002.
  * [34] Matus Telgarsky and Andrea Vattani.  Hartigan’s method: k-means clustering without voronoi.  In AISTATS, 2010.
  * [35] Xifeng Guo, Long Gao, Xinwang Liu, and Jianping Yin.  Improved deep embedded clustering with local structure preservation.  In IJCAI, 2017.
  * [36] Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin.  Unsupervised learning of visual features by contrasting cluster assignments.  ArXiv, abs/2006.09882, 2020.
  * [37] Feng Wang, Jian Cheng, Weiyang Liu, and Haijun Liu.  Additive margin softmax for face verification.  IEEE Signal Processing Letters, 25(7):926–930, 2018.
  * [38] Feng Wang, Xiang Xiang, Jian Cheng, and Alan Loddon Yuille.  Normface: L2 hypersphere embedding for face verification.  Proceedings of the 25th ACM international conference on Multimedia, 2017.
  * [39] Matthew A Reyna, Chris Josef, Salman Seyedi, Russell Jeter, Supreeth P Shashikumar, M Brandon Westover, Ashish Sharma, Shamim Nemati, and Gari D Clifford.  Early prediction of sepsis from clinical data: the physionet/computing in cardiology challenge.  In CinC, 2019.
  * [40] M. Lee et. al.  WiDS (Women in Data Science) Datathon 2020: ICU Mortality Prediction, 2020.
  * [41] M. Lichman.  Uci repository.  UCI, 2013.
  * [42] Alistair EW Johnson, Tom J Pollard, Lu Shen, Li-wei H Lehman, Mengling Feng, Mohammad Ghassemi, Benjamin Moody, Peter Szolovits, Leo Anthony Celi, and Roger G Mark.  Mimic-iii, a freely accessible critical care database.  Scientific data, 3(1):1–9, 2016.
  * [43] Ikaro Silva, George B. Moody, Daniel J. Scott, Leo Anthony Celi, and Roger G. Mark.  Predicting in-hospital mortality of icu patients: The physionet/computing in cardiology challenge 2012.  2012 Computing in Cardiology, pages 245–248, 2012.
  * [44] Ikaro Silva, George B. Moody, Daniel J. Scott, Leo Anthony Celi, and Roger G. Mark.  Predicting in-hospital mortality of icu patients: The physionet/computing in cardiology challenge 2012.  2012 Computing in Cardiology, pages 245–248, 2012.
  * [45] James Morrill, Andrey Kormilitzin, Alejo J. Nevado-Holgado, Sumanth Swaminathan, Sam, Howison, and Terry Lyons.  The signature-based model for early detection of sepsis from electronic health records in the intensive care unit.  2019 Computing in Cardiology (CinC), pages Page 1–Page 4, 2019\.
  * [46] Xiangrui Li, Dongxiao Zhu, and Phillip Levy.  Predicting clinical outcomes with patient stratification via deep mixture neural networks.  AMIA Summits on Translational Science, 2020.
  * [47] Manchek A Wong and JA Hartigan.  Algorithm as 136: A k-means clustering algorithm.  Journal of the Royal Statistical Society. Series C (Applied Statistics), 1979.
  * [48] Sanjoy Dasgupta.  The hardness of k-means clustering.  University of California, 2008.
  * [49] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, et al.  Scikit-learn: Machine learning in Python.  JMLR, 2011.
  * [50] J. Gou, B. Yu, S. J. Maybank, and D. Tao.  Knowledge distillation: A survey.  International Journal of Computer Vision, 129(6):1789–1819, 2021\.

## Appendix

##  10 CAC details

###  10.1 Class Separability

We use a simple heuristic to measure class separability within each cluster.
For each cluster $C_{j}$ ($j\in[k]$), we define: cluster centroid:
$\mu(C_{j}):=|C_{j}|^{-1}\sum_{x\in C_{j}}x_{i}$, positive centroid:
$\mu^{+}(C_{j}):=(\sum_{x_{i}\in C_{j}}y_{i})^{-1}\sum_{x_{i}\in
C_{j}}y_{i}x_{i}$, and negative centroid: $\mu^{-}(C_{j}):=({\sum_{x_{i}\in
C_{j}}(1-y_{i})})^{-1}\sum_{x_{i}\in C_{j}}(1-y_{i})x_{i}$.

Class separability is defined by considering the distance between positive and
negative centroids within each cluster. Figure 7 shows two clusters $C_{1}$
and $C_{2}$. $C_{1}$ has greater class separation while in $C_{2}$, the data
points are more intermingled and thus their centroids are closer. Thus,
$\|\mu_{1}^{+}-\mu_{1}^{-}\|>\|\mu_{2}^{+}-\mu_{2}^{-}\|$.

###  10.2 Finding the clusters

The most common heuristic to find $k$-means clusters is Lloyd’s Algorithm
[28]. It begins with an initial clustering and iteratively computes cluster
centroids and assigns points to clusters corresponding to their closest
centroids. However, using this heuristic with our proposed cost may not
guarantee convergence. (See our discussion after Theorem 11.5). Instead, we
adopt an approach based on Hartigan’s method [47]. For $k$-means clustering,
Hartigan’s method proceeds point by point in a greedy manner. Each point is
reassigned to a cluster such that the overall cost is reduced.

In our setting, denote the cost of merging a point $x$ to some cluster $C_{q}$
as $\Gamma^{+}(C_{q},x)=\phi(C_{q}\cup\\{x\\})-\phi(C_{q})$. Symmetrically,
denote the cost of removing a point $x$ from some cluster $C_{p}$ as
$\Gamma^{-}(C_{p},x)=\phi(C_{p}\setminus\left\\{x\right\\})-\phi(C_{p})$.

The cost function of cluster $C_{j}$ with respect to point $i$ is calculated
as $\|x_{i}-\mu_{j}\|^{2}-\alpha\|\mu^{+}(C_{j})-\mu^{-}(C_{j})\|^{2}$.
$\alpha$ is a hyperparameter which controls the weightage given to the class
separation parameter. Typical value of $\alpha$ lies within the range $0$ to
$2$ but it can vary according to the size of the dataset.

Consequently, define the improvement in cost by moving a point $x\in C_{p}$
from cluster $C_{p}$ to cluster $C_{q}$ to be
$\Phi(x;C_{p},C_{q}):=\Gamma^{+}(C_{q},x)+\Gamma^{-}(C_{p},x)$. The exact
expressions for $\Gamma^{+}(C_{q},x)$ and $\Gamma^{-}(C_{p},x)$ w.r.t
$x,\mu,\mu^{\pm}$ can be easily derived from above definitions and the CAC
cost function (not shown here due to lack of space).

The main idea is from Hartigan’s method of clustering [34]: It begins with an
initial clustering ($k$-means found clusters) and then proceeds iteratively in
rounds. In each round, all points are checked to determine if a point has to
be re-assigned to another cluster. For a point in the current iteration,
$x_{i}$, if moving $x_{i}\in C_{p}$ would result in $C_{p}/x_{i}$ having
points of only one class, then it is not moved. If not, the cluster $C_{q}$
that results in the maximum decrease in cost $\Phi(x_{i};C_{p},C_{q})$ is
found and $x_{i}$ is moved from its current cluster $C_{p}$ to $C_{q}$.

In each round, all three centroids for each cluster are updated and once the
loss function has become stagnant, the algorithm is considered to have
converged. Base classifiers are then trained on the clusters found and are
used for predicting labels for the unseen test data.

Classifiers $f_{j}$ are trained to minimize their corresponding supervised
training loss $\ell(f,C)=\sum_{j=1}^{k}\ell(f_{j},C_{j})$. The best collection
of classifiers, chosen based on a user-defined performance metric (e.g.,
training loss or validation set performance), is the final output, along with
the corresponding cluster centroids.

The CAC algorithm runs until convergence and outputs the best collection of
classifiers $f_{best}$ that minimizes the empirical loss.

######  Remark (Hartigan vs. Lloyd).

For $k$-means clustering, both Lloyd’s method and Hartigan’s method converge
since the cost function always decreases monotonically with each update. Note
that Lloyd’s method does not consider the change in centroids while updating
the assignment of a point, and instead, directly assign points to their
current closest centroids. In our setting, Lloyd’s method can similarly fix
all centroids, compute a new assignment, and update the centroids accordingly.
For instance, replacing the assignment rule of $x_{i}$ in Algorithm 1 by
$q:=\mathop{\mathrm{argmin}}_{j}\|x_{i}-\mu(C_{j})\|^{2}-\alpha\cdot\|\mu^{+}(C_{j})-\mu^{-}(C_{j})\|^{2}$.
However, our cost function contains an additional squared distance term
between positive and negative centroids, i.e.,
$-\alpha\cdot\|\mu^{+}(C_{j})-\mu^{-}(C_{j})\|^{2}$. There is no guarantee
that this term monotonically decreases by Lloyd’s method during the update of
$\mu^{+}(C_{j})$ and $\mu^{-}(C_{j})$ after an assignment. Hence, it is non-
trivial to ensure and prove the convergence of Lloyd’s method with our cost
function. However, with the use of Hartigan’s method, convergence is ensured
by design. As for the rate of convergence, empirical experiments demonstrate
that the rate of convergence is positively related to $\alpha$.

###  10.3 CAC Prediction

CAC outputs a set of cluster representatives denoted by their centroids and
the trained classifiers associated with those clusters. To make predictions
for a test point $\hat{x}$, the first step is to find the cluster to which the
test point is most likely to belong. This can be done by assigning the test
point to a cluster represented by the ‘closest’ centroid $C_{j}$ in the data
space i.e. $j=\mathop{\mathrm{argmin}}_{l}\|\hat{x}-\mu_{l}\|^{2}$. The
corresponding classifier $f_{j}$ can then be used to predict
$\hat{y}=f_{j}(\hat{x})$.

Figure 4: Total CAC cost v/s # of iterations for different $\alpha$.

Figure 5: CAC clustering Silhouette score v/s training epochs

##  11 Proof of Theorems

###  11.1 Proof of Theorem 1

The following lemma is from [33, 12, Theorem 3.1]:

######  Lemma 1.

Let $\mathcal{F}$ be a set of maps $x\mapsto f(x)$. Suppose that
$0\leq\ell\left(q,y\right)\leq\lambda$ for any
$q\in\\{f(x):f\in\mathcal{F},x\in\mathcal{X}\\}$ and $y\in\mathcal{Y}$. Then,
for any $\delta>0$, with probability at least $1-\delta$ (over an i.i.d. draw
of $m$ i.i.d. samples $((x_{i},y_{i}))_{i=1}^{m}$), the following holds: for
all maps $f\in\mathcal{F}$,

$\displaystyle\mathbb{E}_{x,y}[\ell(f(x),y)]$
$\displaystyle\leq\frac{1}{m}\sum_{i=1}^{m}\ell(f(x_{i}),y_{i})+2\hat{\mathcal{R}}_{m}(\ell\circ\mathcal{F})+$
$\displaystyle 3\lambda\sqrt{\frac{\ln(1/\delta)}{2m}},$ (3)

where
$\hat{\mathcal{R}}_{m}(\ell\circ\mathcal{F}):=\mathbb{E}_{\sigma}[\sup_{f\in\mathcal{F}}\frac{1}{m}\sum_{i=1}^{m}\sigma_{i}\ell(f(x_{i}),y_{i})]$
and $\sigma_{1},\dots,\sigma_{m}$ are independent uniform random variables
taking values in $\\{-1,1\\}$.

We can use Lemma 1 to prove the following:

######  Theorem 1.

Let $\mathcal{F}_{j}$ be a set of maps $x\in C_{j}\mapsto f_{j}(x)$. Let
$\mathcal{F}=\\{x\mapsto f(x):f(x)=\sum_{j=1}^{K}\mathbbm{1}\\{x\in
C_{j}\\}f_{j}(x),f_{j}\in\mathcal{F}_{j}\\}$. Suppose that
$0\leq\ell\left(q,y\right)\leq\lambda_{j}$ for any
$q\in\\{f(x):f\in\mathcal{F}_{j},x\in C_{j}\\}$ and $y\in\mathcal{Y}_{j}$.
Then, for any $\delta>0$, with probability at least $1-\delta$, the following
holds: for all maps $f\in\mathcal{F}$,

$\displaystyle\mathbb{E}_{x,y}[\ell(f(x),y)]\leq\sum_{j=1}^{K}\Pr(x\in C_{j})$
$\displaystyle\left(\frac{1}{m_{j}}\sum_{i=1}^{m_{j}}\ell(f(x_{i}^{j}),y_{i}^{j})+2\hat{\mathcal{R}}_{m_{j}}(\ell\circ\mathcal{F}_{j})+3\lambda_{j}\sqrt{\frac{\ln(K/\delta)}{2m_{j}}}\right),$
(4)

where
$\hat{\mathcal{R}}_{m}(\ell\circ\mathcal{F}_{j}):=\mathbb{E}_{\sigma}[\sup_{f_{j}\in\mathcal{F}_{j}}\frac{1}{m}\sum_{i=1}^{m}\sigma_{i}\ell(f_{j}(x_{i}),y_{i})]$,
$Pr(x\in C_{j})=1$ if $x\in C_{j}$ and $\sigma_{1},\dots,\sigma_{m}$ are
independent uniform random variables taking values in $\\{-1,1\\}$.

###### Proof of Theorem 1.

We have the following.

$\displaystyle\mathbb{E}_{x,y}[\ell(f(x),y)]$
$\displaystyle=\sum_{j=1}^{K}\Pr(x\in C_{j})\mathbb{E}_{x,y}[\ell(f(x),y)\mid
x\in C_{j})]$ (5) $\displaystyle=\sum_{j=1}^{K}\Pr(x\in
C_{j})\mathbb{E}_{x,y}[\ell(f_{j}(x),y)\mid x\in C_{j})].$

Since the conditional probability distribution is a probability distribution,
we apply Lemma 1 to each term and take a union bound to obtain the following:
for any $\delta>0$, with probability at least $1-\delta$, for all
$j\in\\{1,\dots,K\\}$ and all $f_{j}\in F_{j}$,

$\displaystyle\mathbb{E}_{x,y}[\ell(f_{j}(x),y)\mid x\in C_{j})]$
$\displaystyle\leq\frac{1}{m_{j}}\sum_{i=1}^{m_{j}}\ell(f_{j}(x_{i}^{j}),y_{i}^{j})+2\hat{\mathcal{R}}_{m_{j}}(\ell\circ\mathcal{F}_{j})+3\lambda_{j}\sqrt{\frac{\ln(K/\delta)}{2m}}$
$\displaystyle=\frac{1}{m_{j}}\sum_{i=1}^{m_{j}}\ell(f(x_{i}^{j}),y_{i}^{j})+2\hat{\mathcal{R}}_{m_{j}}(\ell\circ\mathcal{F}_{j})+3\lambda_{j}\sqrt{\frac{\ln(K/\delta)}{2m}}.$

Thus, using (5), we sum up both sides with factors $\Pr(x\in C_{j})$ to yield:

$\displaystyle\mathbb{E}_{x,y}[\ell(f(x),y)]$
$\displaystyle=\sum_{j=1}^{K}\Pr(x\in
C_{j})\mathbb{E}_{x,y}[\ell(f_{j}(x),y)\mid x\in C_{j})]$
$\displaystyle\leq\sum_{j=1}^{K}\Pr(x\in
C_{j})(\frac{1}{m_{j}}\sum_{i=1}^{m_{j}}\ell(f(x_{i}^{j}),y_{i}^{j})+$
$\displaystyle
2\hat{\mathcal{R}}_{m_{j}}(\ell\circ\mathcal{F}_{j})+3\lambda_{j}\sqrt{\frac{\ln(K/\delta)}{2m}})$
(6)

∎

###  11.2 Proof of Lemma 2

######  Lemma 2.

For $d$ dimensional vectors $\mathbf{u},\mathbf{v}$ and $\boldsymbol{\beta}$,
$\frac{\partial\Delta}{\partial\|\mathbf{u}\|}<0$ for
$\Delta=A-(B{\boldsymbol{\beta}}\mathbf{u}+C{\boldsymbol{\beta}}\mathbf{v})$
if $\beta_{i}u_{i}>0,\forall i\in\\{1,2,\cdots,d\\}$ and $A,B>0$.

###### Proof.

Let $u_{i}$ be the $i^{th}$ element of $\mathbf{u}$. Expanding
$\frac{\partial\Delta}{\partial\|\mathbf{u}\|}$ using chain rule, we get

$\displaystyle\frac{\partial\Delta}{\partial\|\mathbf{u}\|}=\frac{\partial\Delta}{\partial\mathbf{u}}\cdot\frac{\partial\mathbf{u}}{\partial\|\mathbf{u}\|}=-B\boldsymbol{\beta}\cdot\frac{\partial\mathbf{u}}{\partial\|\mathbf{u}\|}\
\ \text{(Since
$\frac{\partial\Delta}{\partial\mathbf{u}}=-B\boldsymbol{\beta}\mathbf{u}$)}$

Let $u_{i}$ denote the $i^{th}$ element of $\mathbf{u}$. Then, from the
definition of vector derivatives we have,

$\displaystyle\frac{\partial\mathbf{u}}{\partial\|\mathbf{u}\|}$
$\displaystyle=\left[\frac{\partial
u_{1}}{\partial\|\mathbf{u}\|},\frac{\partial
u_{2}}{\partial\|\mathbf{u}\|},\cdots,\frac{\partial
u_{d}}{\partial\|\mathbf{u}\|}\right]$
$\displaystyle=\left[\left(\frac{\partial\|\mathbf{u}\|}{\partial
u_{1}}\right)^{-1},\left(\frac{\partial\|\mathbf{u}\|}{\partial
u_{2}}\right)^{-1},\cdots,\left(\frac{\partial\|\mathbf{u}\|}{\partial
u_{d}}\right)^{-1}\right]$
$\displaystyle=\|\mathbf{u}\|\left[\frac{1}{u_{1}},\frac{1}{u_{2}},\cdots,\frac{1}{u_{d}}\right]$

Thus,
$\frac{\partial\Delta}{\partial\|\mathbf{u}\|}=-B\cdot\|\mathbf{u}\|\cdot{\sum}_{i=1}^{d}\frac{\beta_{i}}{u_{i}}$.
where $u_{i}=\mu^{+}_{i}-\mu^{-}_{i}$ and $v_{i}=\mu^{+}_{i}+\mu^{-}_{i}$.

Since $\beta\cdot\mu^{+}>0$ and $\beta\cdot\mu^{-}<0$, it implies that
$\beta\cdot\mathbf{u}>0$. Assuming that every dimension of $\mathbf{u}$ lies
on the same side of regression plane $\beta$ as the original point, i.e.
$\beta_{i}u_{i}=\beta_{i}>0,\forall i$, $\frac{\beta_{i}}{u_{i}}>0\ \forall
i$, then $\frac{\partial\Delta}{\partial\|\mathbf{u}\|}<0$ as $B$ and
$\|\mathbf{u}\|$. Thus under above assumption, we prove that $\Delta$
decreases as $\|\mathbf{u}\|$ increases.

∎

###  11.3 Proof of Theorem 2

######  Theorem 2.

Let $X=(x_{1},x_{2},\cdots,x_{N})$ be a training dataset with $n$ records
$x_{i}\in\mathbb{R}^{d}$ together with binary labels
$y_{i}\in\left\\{0,1\right\\}$. Define the log-loss over the entire dataset as
:

$\ell(X)=-\Sigma_{i}y_{i}\ln(p(x_{i}))+(1-y_{i})\ln(1-p(x_{i}))$

where $p(x_{i})=[1+\exp(-\beta x_{i})]^{-1}$ and
$\beta=\mathop{\mathrm{argmin}}_{\beta}\ell(X)$. Then,

$C_{1}-(C_{3}\beta\mu^{+}-C_{4}\beta\mu^{-})\leq\ell(X)\leq
C_{2}-(C_{3}\beta\mu^{+}-C_{4}\beta\mu^{-})$

where $C_{1}=N\ln(2),\ C_{2}=N\ln(1+\exp(c))-\frac{Nc}{2},\
C_{3}=\frac{N^{+}}{2},\ C_{4}=\frac{N^{-}}{2},\ N^{+}=\sum_{x_{i}\in X}y_{i}$,
$N^{-}=\sum_{x_{i}\in X}(1-y_{i})$ and $c=\mathop{\mathrm{argmax}}_{i}\|\beta
x_{i}\|$.

###### Proof.

Lower Bound Let
$\ell(X,y)=\Sigma_{y_{i}=1}\ell^{+}(x_{i})+\Sigma_{y_{i}=0}\ell^{-}(x_{i})$
s.t.

$\displaystyle\ell^{+}(x_{i})=-\ln(p_{i}),\ \ell^{-}(x_{i})=-\ln(1-p_{i})$ (7)

Applying Jensen’s inequality on $\ell^{+}$ and $\ell^{-}$,

$\displaystyle\ell(X)=$ $\displaystyle\Sigma_{x_{i}\in
X^{+}}\ell^{+}(x_{i})+\Sigma_{x_{i}\in X^{-}}\ell^{-}(x_{i})$ $\displaystyle=$
$\displaystyle-\Sigma_{y_{i}=1}\ln[1+\exp(-\beta x_{i})]^{-1}-$
$\displaystyle\Sigma_{y_{i}=0}\ln[1-(1+\exp(-\beta x_{i}))^{-1}]$ (By eq. 7)

$\displaystyle\geq$
$\displaystyle-N^{+}\ln\left[1+\exp\left(-\beta\cdot\left(\frac{\Sigma_{x_{i}\in
X^{+}}x_{i}}{N^{+}}\right)\right)\right]^{-1}$
$\displaystyle-N^{-}\ln\left[1-\left(1+\exp\left(-\beta\cdot\left(\frac{\Sigma_{x_{i}\in
X^{-}}x_{i}}{N^{-}}\right)\right)\right)^{-1}\right]$ (Jensen’s inequality for
convex functions) $\displaystyle\geq$ $\displaystyle
N^{+}\ln[1+\exp(-\beta\mu^{+})]-N^{-}\ln\left[\frac{\exp(-\beta\mu^{-})}{1+\exp(-\beta\mu^{-})}\right]$
(Substituting $\mu^{+}$ and $\mu^{-}$) $\displaystyle\geq$ $\displaystyle
N^{+}\ln[1+\exp(-\beta\mu^{+})]+N^{-}\ln[1+\exp(\beta\mu^{-})]$

We observe that $\ln(1+\exp(x))\geq\ln(2)+\frac{x}{2}\ \forall x\in\mathbb{R}$
by considering the Taylor series expansion of $\ln(1+\exp(x))$ at $x=0$.
$\ln(1+\exp(x))=\ln(2)+\frac{x}{2}+\frac{x^{2}}{8}+\mathcal{O}(x^{4})$. Then,

$\displaystyle\ell(X)$ $\displaystyle\geq
N^{+}\left(\ln(2)-\frac{\beta\mu^{+}}{2}\right)+N^{-}\left(\ln(2)+\frac{\beta\mu^{-}}{2}\right)$
$\displaystyle\geq
N\ln(2)-\frac{1}{2}\cdot(N^{+}\beta\mu^{+}-N^{-}\beta\mu^{-})$

where $C_{1}=N\ln(2),C_{3}=\frac{N^{+}}{2},C_{4}=\frac{N^{-}}{2}$.

Upper Bound

Since all points $x_{i}$ are constrained within their respective clusters, we
note that the maximum log-loss for a point $x_{i}$ labelled as $y_{i}$ is not
unbounded. Let $c=\mathop{\mathrm{argmax}}_{i}\|\beta x_{i}\|$. Since
$\ell^{+}$ is a monotonically decreasing function and $\ell^{-}$ is
monotonically increasing, we can bound them using linear functions $s^{+}$ and
$s^{-}$ respectively. $s^{+}\geq\ell^{+}$ and $s^{-}\geq\ell^{-}$ for all
points $X^{+}$ and $X^{-}$ respectively. $s^{+}(x_{i})$ passes through
$(-c,\ln(p(-c)))$ and $(c,\ln(p(c)))$. Hence $s^{+}(x)=K_{1}-K_{2}\cdot\beta
x$ where $K_{1},K_{2}>0$. Similarly, $s^{-}(x)=K_{3}+K_{4}\cdot\beta x$ where
$K_{3},K_{4}>0$.

Solving for $K_{1}\cdots K_{4}$, we get

$\displaystyle K_{1}=K_{3}=\ln(1+\exp(c))-\frac{c}{2},\
K_{2}=K_{4}=\frac{1}{2}$

Then,

$\displaystyle\ell(X)$ $\displaystyle=\Sigma_{x_{i}\in
X^{+}}\ell^{+}(x_{i})+\Sigma_{x_{i}\in X^{-}}\ell^{-}(x_{i})$
$\displaystyle<\Sigma_{x_{i}\in X^{+}}s^{+}(x_{i})+\Sigma_{x_{i}\in
X^{-}}s^{-}(x_{i})$ $\displaystyle\leq N^{+}s^{+}\left(\frac{\Sigma_{x_{i}\in
X^{+}}x_{i}}{N^{+}}\right)+N^{-}s^{-}\left(\frac{\Sigma_{x_{i}\in
X^{-}}x_{i}}{N^{-}}\right)$ (Jensen’s inequality for a linear function)
$\displaystyle\leq N^{+}s^{+}(\mu^{+})+N^{-}s^{-}(\mu^{-})$ $\displaystyle\leq
N^{+}(K_{1}-K_{2}\cdot\beta\mu^{+})+N^{-}(K_{3}+K_{4}\cdot\beta\mu^{-})$
$\displaystyle\leq C_{2}-(C_{3}\beta\mu^{+}-C_{4}\beta\mu^{-})\
\text{(Rearranging terms)}$

where $C_{2}=N\ln(1+\exp(c))-\frac{Nc}{2}$ and
$C_{3}=\frac{N^{+}}{2},C_{4}=\frac{N^{-}}{2}$. ∎

###  11.4 Proof of Theorem 3

######  Theorem 3.

Let $X=(x_{1},x_{2},\cdots,x_{N})$ be a training dataset with $n$ records
$x_{i}\in\mathbb{R}^{d}$ together with binary labels
$y_{i}\in\left\\{0,1\right\\}$. Define the AM Softmax loss over the entire
dataset as :
$-\sum_{i}\log\frac{e^{s\cdot\left(W_{y_{i}}^{T}z_{i}-m\right)}}{e^{s\cdot\left(W_{y_{i}}^{T}z_{i}-m\right)}+\sum_{j=1,j\neq
y_{i}}^{c}e^{sW_{j}^{T}z_{i}}}$. Then,

$K_{1}-\Gamma(K_{3}\mu^{+}-K_{4}\mu^{-})\leq\ell(X)\leq
K_{2}-\Gamma(K_{3}\mu^{+}-K_{4}\mu^{-})$

where $K_{1}=N\left(\log 2+\frac{sm}{2}\right),\ K_{2}=N(1+sm),\
K_{3}=sN^{+},\ K_{4}=sN^{-},\ N^{+}=\sum_{x_{i}\in X}y_{i}$,
$N^{-}=\sum_{x_{i}\in X}(1-y_{i})$ and $\Gamma=W^{T}_{+}-W^{T}_{-}$.

###### Proof.

Rewriting $L_{AM}$ by collecting all the terms for the positive and negative
classes, we get

$\displaystyle L_{AM}=-$
$\displaystyle\sum_{i:y_{i}=0}\log\frac{e^{s\cdot\left(W_{-}^{T}z_{i}-m\right)}}{e^{s\cdot\left(W_{-}^{T}z_{i}-m\right)}+e^{sW_{+}^{T}x_{i}}}+$
$\displaystyle-$
$\displaystyle\sum_{i:y_{i}=1}\log\frac{e^{s\cdot\left(W_{+}^{T}z_{i}-m\right)}}{e^{s\cdot\left(W_{+}^{T}z_{i}-m\right)}+e^{sW_{-}^{T}x_{i}}}$
$\displaystyle=$ $\displaystyle\sum_{i:y_{i}=0}\log
1+{e^{sm+sz_{i}(W_{+}-W_{-})}}+$ $\displaystyle\sum_{i:y_{i}=1}\log
1+{e^{sm+sz_{i}(W_{-}-W_{+})}}$

#### Lower Bound

Let $g^{+}=\log[1+{e^{sm+sz_{i}(W_{-}-W_{+})}}]$ and
$g^{-}=\log[1+{e^{sm+sz_{i}(W_{+}-W_{-})}}]$. Note that $g^{+}$ and $g^{-}$
are convex functions. Applying Jensen’s inequality on $g^{+}$ and $g^{-}$ we
get:

$\displaystyle L_{AM}=$
$\displaystyle\sum_{i:y_{i}=0}\log[1+{e^{sm+sz_{i}(W_{+}-W_{-})}}]+$
$\displaystyle\sum_{i:y_{i}=1}\log[1+{e^{sm+sz_{i}(W_{-}-W_{+})}}]$
$\displaystyle>N^{+}\log[1+{e^{sm+sz\mu^{+}(W_{+}-W_{-})}}]+$ $\displaystyle
N^{-}\log[1+{e^{sm+sz\mu^{-}(W_{-}-W_{+})}}]$

Since $\log(1+e^{x})>\log 2+\frac{x}{2}\ \forall x$, we can further simplify
the above expression.

$\displaystyle L_{AM}>$ $\displaystyle
N^{-}\log[1+{e^{sm+sz\mu^{+}(W_{+}-W_{-})}}]+$ $\displaystyle
N^{+}\log[1+{e^{sm+sz\mu^{-}(W_{-}-W_{+})}}]$ $\displaystyle>N^{-}[\log
2+\frac{1}{2}(sm+s\mu^{-}(W_{+}-W_{-}))]+$ $\displaystyle N^{+}[\log
2+\frac{1}{2}(sm+s\mu^{+}(W_{-}-W_{+}))]$ $\displaystyle>N\left(\log
2+\frac{sm}{2}\right)-s(W_{+}-W_{-})[N^{+}\mu^{+}-N^{-}\mu^{-}]$

#### Upper Bound

For all $x>0$, $\log(1+e^{x})<1+x$. Since $sm+sz_{i}(W_{+}-W_{-})>0$ for all
$z_{i}$ s.t. $y_{i}=0$ and $sm+sz_{i}(W_{-}-W_{+})>0$ for all $z_{i}$ s.t.
$y_{i}=1$ (see [37]), we can safely apply the above mentioned inequality to
get an upper bound for $L_{AM}$.

$\displaystyle L_{AM}=$
$\displaystyle\sum_{i:y_{i}=0}\log[1+{e^{sm+sz_{i}(W_{+}-W_{-})}}]+$
$\displaystyle\sum_{i:y_{i}=1}\log[1+{e^{sm+sz_{i}(W_{-}-W_{+})}}]$
$\displaystyle L_{AM}<$ $\displaystyle N^{+}[1+sm+sz_{i}(W_{-}-W_{+})]+$
$\displaystyle N^{-}[1+sm+sz_{i}(W_{-}-W_{+})]$ $\displaystyle<$
$\displaystyle(N^{+}+N^{-})(1+sm)+sN^{-}\mu^{-}(W_{+}-W_{-})+$ $\displaystyle
sN^{+}\mu^{+}(W_{-}-W_{+})$ $\displaystyle<$ $\displaystyle
N(1+sm)-s(W_{+}-W_{-})(N^{+}\mu^{+}-N^{-}\mu^{-})$

∎

###  11.5 Theorem on Convergence of CAC

######  Theorem 2.

Algorithm 1 converges to a local minimum.

###### Proof.

To prove convergence, it suffices to verify that the cost function, that re-
assigns point $x$ from cluster $C_{p}$ to cluster $C_{q}$, monotonically
decreases at each iteration. This is equivalent to showing
$\phi(C_{p}\setminus\left\\{x_{i}\right\\})+\phi(C_{q}\cup\left\\{x_{i}\right\\})<\phi(C_{p})+\phi(C_{q})\implies(\phi(C_{p}\setminus\left\\{x_{i}\right\\})-\phi(C_{p}))+(\phi(C_{q}\cup\left\\{x_{i}\right\\})-\phi(C_{q}))<0\implies\Gamma^{+}(C_{q},x)+\Gamma^{-}(C_{p},x)<0\implies\Phi(x_{i},C_{p},C_{q})<0.$

$\Phi(x_{i},C_{p},C_{q})<0$ is exactly the update condition for the algorithm
that ensures that the total cost function is always decreasing with every
point update and in every iteration. If we move $\epsilon<1$ away from our
binary cluster indicator then we do not get a binary result anymore, which is
not in the feasible set and which is hence not minimizing the objective. Hence
the clustering derived is trivially a local minimum. ∎

|  |  |
---|---|---|---

(a)

(b)

(c)

(d)

Figure 6: Evaluating the effect of different parameters on the performance of
CAC

###  11.6 Theorem on Time Complexity of CAC

######  Theorem 3.

The time complexity for each round of CAC is $O(ndk)$.

###### Proof.

For the time complexity of each round, it suffices to prove the running time
for each point $x_{i}$ is $O(dk)$. For each $j\in[k]$, we denote the centroid,
positive centroid and negative centroid of $C_{j}\cup\left\\{x_{i}\right\\}$
as $\tilde{\mu}(C_{j})$, $\tilde{\mu}^{+}(C_{j})$ and $\tilde{\mu}^{-}(C_{j})$
respectively. Given a cluster $C_{j}$ and a point $z\in\mathbb{R}^{d}$, we
denote the clustering cost of $C$ w.r.t. $z$ to be

$g(C_{j},z):=\sum_{x\in C_{j}}\|x-z\|^{2}.$

A standard result from the $k$-means literature [48] is the following bias-
variance decomposition of the $k$-means cost function:

$g(C_{j},z)=\phi(C_{j},\mu(C_{j}))+|C_{j}|\cdot\|\mu(C_{j})-z\|^{2}.$

Note that the above result holds for CAC cluster cost function also as can be
shown easily by a little algebra. Based on this property, we have

$\displaystyle\Gamma^{+}(C_{j},x_{i})$ $\displaystyle=$
$\displaystyle\|\tilde{\mu}-x_{i}\|^{2}+|C_{j}|\cdot\|\tilde{\mu}(C_{j})-\mu(C_{j})\|^{2}$
$\displaystyle+\alpha|C_{j}|\cdot\|\mu^{+}(C_{j})-\mu^{-}(C_{j})\|^{2}$
$\displaystyle-\alpha(|C_{j}|+1)\cdot\|\tilde{\mu}^{+}(C_{j})-\tilde{\mu}^{-}(C_{j})\|^{2}$
$\displaystyle\Gamma^{-}(C_{j},x_{i})$ $\displaystyle=$
$\displaystyle-\|\mu(C_{j})-x_{i}\|^{2}-(|C_{j}|-1)\|\tilde{\mu}(C_{j})-\mu(C_{j})\|^{2}$
$\displaystyle+\alpha|C_{j}|\cdot\|\mu^{+}(C_{j})-\mu^{-}(C_{j})\|^{2}$
$\displaystyle-\alpha(|C_{j}|-1)\cdot\|\tilde{\mu}^{+}(C_{j})-\tilde{\mu}^{-}(C_{j})\|^{2}$

Then it suffices to prove that both $\Gamma^{+}(C_{j},x_{i})$ and
$\Gamma^{-}(C_{j},x_{i})$ can be computed in $O(d)$ time, which implies
$O(dk)$ time for computing
$q:=\mathop{\mathrm{argmin}}_{j}{\Phi(x_{i};C_{p},C_{j})}$. Moreover, by the
above formulations, it suffices to prove that $\tilde{\mu}(C_{j})$,
$\tilde{\mu}^{+}(C_{j})$ and $\tilde{\mu}^{-}(C_{j})$ can be computed in
$O(d)$ time. Note that
$\tilde{\mu}(C_{p})=\frac{|C_{p}|\cdot\mu(C_{p})-x_{i}}{|C_{p}|-1}$ and
$\tilde{\mu}(C_{j})=\frac{|C_{j}|\cdot\mu(C_{j})+x_{i}}{|C_{j}|+1}$ for $j\neq
p$. Hence, each $\tilde{\mu}(C_{j})$ can be computed in $O(d)$ time. We
discuss the following two cases for the computation of
$\tilde{\mu}^{+}(C_{j})$ and $\tilde{\mu}^{-}(C_{j})$.

  * •

Case $y_{i}=1$. We have that
$\tilde{\mu}^{+}(C_{p})=\frac{\left(\sum_{x_{l}\in\mathcal{C}_{p}}y_{l}\right)\cdot\mu_{p}^{+}-x_{i}}{\sum_{x_{l}\in\mathcal{C}_{p}}y_{l}-1}$
and $\tilde{\mu}^{-}(C_{p})=\mu^{-}(C_{p})$. For $j\neq p$, we have that
$\tilde{\mu}^{+}(C_{j})\leftarrow\frac{\left(\sum_{x_{l}\in\mathcal{C}_{j}}y_{l}\right)\cdot\mu_{j}^{+}+x_{i}}{\sum_{x_{l}\in\mathcal{C}_{j}}y_{l}+1}$
and $\tilde{\mu}^{-}(C_{j})=\mu^{-}(C_{j})$.

  * •

Case $y_{i}=0$. We have that
$\tilde{\mu}_{p}^{-}\leftarrow\frac{\left(\sum_{x_{l}\in\mathcal{C}_{p}}(1-y_{l})\right)\cdot\mu_{p}^{-}-x_{i}}{\sum_{x_{l}\in\mathcal{C}_{p}}(1-y_{l})-1}$
and $\tilde{\mu}^{+}(C_{p})=\mu^{+}(C_{p})$. For $j\neq p$, we have that
$\tilde{\mu}_{j}^{-}\leftarrow\frac{\left(\sum_{x_{l}\in\mathcal{C}_{j}}(1-y_{l})\right)\cdot\mu_{j}^{-}+x_{i}}{\sum_{x_{l}\in\mathcal{C}_{j}}(1-y_{l})+1}$
and $\tilde{\mu}^{+}(C_{j})=\mu^{+}(C_{j})$.

By the above update rules, both $\tilde{\mu}^{+}(C_{j})$ and
$\tilde{\mu}^{-}(C_{j})$ can be computed in $O(d)$ time, which completes the
proof. ∎

###  11.7 Hyperparameter Details

CAC’s $\alpha$ values are found by performing a $5$-fold CV Grid search (see
App. 11.7). Table 4 shows the tuned values of $\alpha$ used by different
variants of CAC on different datasets. We find these values by performing a
$5$-fold Grid search cross validation. Figure 4 shows how the CAC cost
function decreases monotonically (as proved in Theorem 11.5) over iterations
for different values of $\alpha$.

Figure 7: CAC problem setting (with dummy values for illustrative purposes): (a) The total CAC cost of this clustering is $60$; (b) Point $p_{1}$ is selected to be reassigned to cluster $C_{1}$ based on the cluster update equations; (c) $p_{1}$ is assigned to $C_{1}$ and the cost functions of $C_{1}$ and $C_{2}$ are updated; (d) At testing time, $\hat{x}$ is assigned to cluster $C_{2}$ as it lies nearest to $\hat{x}$. Table 4: Tuned $\alpha$ values used for CAC in experiments found after 5-fold GridCV search Classifier | LR | SVM | LDA | Perceptron | RF | KNN | SGD | Ridge | XGB
---|---|---|---|---|---|---|---|---|---
Diabetes | 2.5 | 2.5 | 2.5 | 2.5 | 2.5 | 2.5 | 2.5 | 2.5 | 3
CIC | 0.05 | 0.5 | 0.05 | 0.5 | 0.5 | 0.5 | 0.01 | 0.5 | 0.01
WID-M | 0.05 | 0.5 | 0.05 | 0.5 | 0.5 | 0.5 | 0.01 | 0.5 | 0.01
Table 5: F1 scores of CAC compared against baseline and $k$-means+X for
different base classifiers on different datasets evaluated on a separate held
out testing dataset. Highlighted values signify the best result in that
category.

Dataset/Classifier | Diabetes | CIC | WID-M
---|---|---|---
LR | $0.111$ | $0.443$ | $0.398$
$KM$ \+ LR | $0.503$ | $0.492$ | $0.41$
CAC + LR | $\mathbf{0.505}$ | $\mathbf{0.492}$ | $\mathbf{0.41}$
SVM | $\mathbf{0.523}$ | $0.255$ | $0.152$
$KM$ \+ SVM | $0.116$ | $0.426$ | $\mathbf{0.354}$
CAC + SVM | $0.506$ | $\mathbf{0.452}$ | $0.332$
XGB (n_est=10) | $0.236$ | $0.454$ | $0.41$
$KM$ \+ XGB | $0.358$ | $0.486$ | $0.453$
CAC + XGB | $\mathbf{0.506}$ | $\mathbf{0.49}$ | $\mathbf{0.457}$
LDA | $0.112$ | $0.479$ | $\mathbf{0.46}$
$KM$ \+ LDA | $0.24$ | $\mathbf{0.497}$ | $0.427$
CAC + LDA | $\mathbf{0.506}$ | $0.492$ | $0.419$
Perceptron | $0.349$ | $0.421$ | $\mathbf{0.346}$
$KM$ \+ Perceptron | $0.333$ | $0.375$ | $0.342$
CAC + Perceptron | $\mathbf{0.506}$ | $\mathbf{0.45}$ | $0.331$
RF (n_tree=10) | $0.406$ | $0.308$ | $0.345$
$KM$ \+ RF | $0.407$ | $0.313$ | $\mathbf{0.347}$
CAC + RF | $\mathbf{0.505}$ | $\mathbf{0.449}$ | $0.332$
KNN | $0.406$ | $0.218$ | $0.219$
$KM$ \+ KNN | $0.407$ | $0.235$ | $0.237$
CAC + KNN | $\mathbf{0.506}$ | $\mathbf{0.45}$ | $\mathbf{0.331}$
SGD | $0.204$ | $0.433$ | $0.387$
$KM$ \+ SGD | $0.198$ | $\mathbf{0.444}$ | $0.383$
CAC + SGD | $\mathbf{0.506}$ | $0.432$ | $\mathbf{0.393}$
Ridge | $0.104$ | $0.347$ | $0.285$
$KM$ \+ Ridge | $0.116$ | $0.372$ | $0.294$
CAC + Ridge | $\mathbf{0.506}$ | $\mathbf{0.45}$ | $\mathbf{0.331}$

###  11.8 Results on Synthetic Data

We analyse how the performance of CAC depends on the following data/algorithm
parameters:

  1. 1.

Inner Class Separation ($ICS$): Distance between class centroids in an
individual cluster.

  2. 2.

Outer Cluster Separation ($OCS$): Distance between cluster centroids.

  3. 3.

Number of natural clusters in the dataset ($K$).

  4. 4.

Number of classifiers used in CAC ($k$), i.e., the number of clusters used as
input.

To study the performance of CAC as a function of these $4$ parameters, we
modify the make classification function of sklearn library [49], to generate
custom datasets with varying ICS, OCS, and $K$. We choose Logistic Regression
(LR) as the base classifier for CAC while testing its performance on the
synthetic dataset. The range of these parameters in our simulations is as
follows: $ICS\in\\{0,0.2,0.5,1,1.5,2\\}$, $OCS\in\\{1,1.5,2\\}$,
$K\in\\{2,3,5,10,15,20,30\\}$ and $k\in\\{2,3,4,5\\}$. We run CAC+LR for all
combinations of parameters.

Figure 6 presents the results of the experiments. In each subfigure, the
results are averaged over all the parameters not shown in the axes. In Figure
6a, note that the performance of CAC improves as Inner Class Separation within
the clusters increases. This is in line with our hypothesis that if the
classes are well separated within the clusters, then it will improve the
performance of the classifiers. The performance of CAC does not depend much on
the Outer Cluster Separation (Figure 6b). This is also expected as a
classifier will be relatively unaffected by the presence of another cluster,
irrespective of its distance as the data in that cluster is not a part of its
training set.

As the number of natural clusters in the dataset increases, the performance of
CAC decreases (Figure 6c). This phenomenon is expected from linear classifiers
as they cannot handle nonlinearities in data. Hence, dividing the data into
multiple groups will decrease the piece-wise nonlinearity and the overall
algorithm will work better [2]. In Figure 6d, we observe that the results are
better for the cases when $k\geq K$ (i.e., closer to the points near the
x-axis). This shows that the performance is better when the number of clusters
given as input is not less than the natural clusters in the data, compared to
the case when the input number of clusters is less than the natural number of
clusters. In the latter case, each (linear) classifier has to learn a non-
linear boundary due to the intrinsic cluster structure that leads to a
decrease in the performance.

Table 6: AUC of DeepCAC and other baselines. Best values in bold. KM, DCN, and
IDEC use the same local classifier as used by DeepCAC.

Dataset | k | KM-Z | DCN-Z | IDEC-Z | DMNN | AC-TPC | GRASP | DeepCAC
---|---|---|---|---|---|---|---|---
|  | $-$ | (2017) | (2017) | (2020) | (2020) | (2021) | (Ours)
Diabetes | 2 | $0.534\pm 0.012$ | $0.571\pm 0.004$ | $0.565\pm 0.007$ | $0.536\pm 0.005$ | $0.0\pm 0.0$ | $0.569\pm 0.006$ | $0.57\pm 0.006$
| 3 | $0.517\pm 0.02$ | $0.569\pm 0.003$ | $0.558\pm 0.012$ | $0.546\pm 0.007$ | $0.540\pm 0.0$ | $0.565\pm 0.005$ | $\mathbf{0.573\pm 0.004}$
| 4 | $0.508\pm 0.027$ | $0.569\pm 0.003$ | $0.564\pm 0.007$ | $0.545\pm 0.008$ | $0.5\pm 0.0$ | $0.561\pm 0.004$ | $0.568\pm 0.005$
CIC | 2 | $0.606\pm 0.036$ | $0.7\pm 0.054$ | $0.766\pm 0.053$ | $0.737\pm 0.039$ | $0.0\pm 0.0$ | $\mathbf{0.827\pm 0.015}$ | $0.82\pm 0.021$
| 3 | $0.535\pm 0.059$ | $0.705\pm 0.033$ | $0.657\pm 0.039$ | $0.762\pm 0.026$ | $0.757\pm 0.0$ | $0.81\pm 0.022$ | $0.815\pm 0.027$
| 4 | $0.549\pm 0.052$ | $0.681\pm 0.043$ | $0.687\pm 0.029$ | $0.731\pm 0.039$ | $0.782\pm 0.0$ | $0.799\pm 0.023$ | $0.811\pm 0.013$
CIC-LoS | 2 | $0.576\pm 0.007$ | $0.625\pm 0.017$ | $0.638\pm 0.012$ | $0.61\pm 0.007$ | $0.0\pm 0.0$ | $0.654\pm 0.02$ | $\mathbf{0.664\pm 0.005}$
| 3 | $0.524\pm 0.026$ | $0.611\pm 0.022$ | $0.596\pm 0.028$ | $0.617\pm 0.012$ | $0.630\pm 0.0$ | $0.65\pm 0.026$ | $0.663\pm 0.01$
| 4 | $0.512\pm 0.02$ | $0.625\pm 0.025$ | $0.623\pm 0.012$ | $0.615\pm 0.009$ | $0.601\pm 0.0$ | $0.639\pm 0.025$ | $0.663\pm 0.005$
ARDS | 2 | $0.605\pm 0.044$ | $0.658\pm 0.052$ | $0.705\pm 0.01$ | $0.584\pm 0.041$ | $-$ | $0.457\pm 0.03$ | $\mathbf{0.716\pm 0.022}$
| 3 | $0.546\pm 0.044$ | $0.704\pm 0.022$ | $0.648\pm 0.077$ | $0.571\pm 0.036$ | $0.655\pm 0.019$ | $0.443\pm 0.029$ | $0.705\pm 0.019$
| 4 | $0.483\pm 0.055$ | $0.593\pm 0.095$ | $0.697\pm 0.019$ | $0.629\pm 0.024$ | $0.647\pm 0.022$ | $0.564\pm 0.119$ | $0.704\pm 0.039$
Sepsis | 2 | $0.621\pm 0.033$ | $0.795\pm 0.011$ | $0.792\pm 0.013$ | $0.656\pm 0.021$ | $-$ | $0.495\pm 0.029$ | $\mathbf{0.803\pm 0.014}$
| 3 | $0.55\pm 0.09$ | $0.782\pm 0.014$ | $0.781\pm 0.007$ | $0.603\pm 0.055$ | $0.714\pm 0.034$ | $0.474\pm 0.008$ | $0.793\pm 0.034$
| 4 | $0.549\pm 0.054$ | $0.691\pm 0.077$ | $0.773\pm 0.014$ | $0.631\pm 0.066$ | $0.684\pm 0.05$ | $0.488\pm 0.01$ | $0.794\pm 0.022$
WID-M | 2 | $0.783\pm 0.035$ | $0.843\pm 0.044$ | $0.835\pm 0.052$ | $0.722\pm 0.023$ | $0.0\pm 0.0$ | $0.788\pm 0.022$ | $\mathbf{0.854\pm 0.01}$
| 3 | $0.669\pm 0.068$ | $0.814\pm 0.055$ | $0.799\pm 0.08$ | $0.708\pm 0.022$ | $0.722\pm 0.0$ | $0.762\pm 0.024$ | $0.851\pm 0.006$
| 4 | $0.584\pm 0.105$ | $0.795\pm 0.059$ | $0.811\pm 0.053$ | $0.716\pm 0.019$ | $0.734\pm 0.0$ | $0.79\pm 0.015$ | $0.847\pm 0.01$

###  11.9 Results of CAC evaluated on Real Datasets

We use 9 different base classifiers, implemented by sklearn library (BSD
licenced): LR, Linear SVM, XGBoost (#estimators = 10), Linear Discriminant
Analysis (LDA), single Perceptron, Random Forest (#trees = 10), $k$ Nearest
Neighbors ($k=5$), SGD classifier and Ridge classifier (Ridge regressor
predicting over the range $[-1,1]$) as a baseline directly and with $k$-means
(KM+X) in a ‘cluster-then-predict’ approach. We evaluate CAC on the Diabetes,
WID-M and CIC datasets due to computational considerations related to large
sizes of the ARDS and Sepsis datasets.

##  12 DeepCAC Training Details

Updating Clustering Parameters For optimizing the clustering loss, we follow
the procedure defined in [30]. For fixed network parameters and cluster
assignment matrix $M$, the assignment vectors of the current sample, i.e.,
$s_{i}$, are updated in an online fashion. Specifically, $s_{i}$ is updated as
follows:

$s_{i,j}=\begin{cases}1,&\text{if
}j=\mathop{\mathrm{argmin}}_{l}\|f(x_{i})-\mu_{l}\|^{2}\\\
0,&\text{otherwise}\end{cases}$

In [30], the authors update the cluster centroids in an online manner instead
of simply taking the average of every mini-batch as the current minibatch
might not be representative of the global cluster structure. So the cluster
centroids are updated as follows by a simple gradient step:

$\mu_{j}\xleftarrow{}\mu_{j}-\frac{1}{c_{k}^{i}}(\mu_{j}-f(x_{i}))s_{k,i}$

where $c_{k}^{i}$ is the count of the number of times algorithm assigned a
sample to cluster $k$ before handling the incoming sample $x_{i}$. The class
cluster centroids $\mu_{k}^{b}$ are also updated in a similar, online manner
due to the above mentioned reasons.

Updating Autoencoder’s weights. For fixed $(M,{s_{i}})$, the subproblem of
optimizing $(\mathcal{W},\mathcal{U})$ is similar to training an SAE – but
with an additional loss term on clustering performance. Modern deep learning
libraries like PyTorch allow us to easily backpropagate both the losses
simultaneously. To implement SGD for updating the network parameters, we look
at the problem w.r.t. the incoming data $x_{i}$:

$\min_{\mathcal{U},\mathcal{W}}L^{i}=\ell(g(f(x_{i})),x_{i})+\beta\|f(x_{i})-Ms_{i}\|+\alpha\sum_{j=1}^{k}L_{AM}$

The gradient of the above function over the network parameters is easily
computable, i.e., $\nabla
X_{\mathcal{J}}L_{i}=\frac{\partial\ell(g(f(x_{i};\mathcal{W});\mathcal{U})}{\partial\mathcal{J}}+\alpha\frac{\partial
f(x_{i})}{\partial\mathcal{J}}(f(x_{i})-Ms_{i})$, where
$\mathcal{J}=(\mathcal{W},\mathcal{U},\mathcal{V})$ is a collection of network
parameters and the gradients $\frac{\partial l}{\partial\mathcal{J}}$ can be
calculated by back-propagation. Then, the network parameters are updated by

$\mathcal{J}\xleftarrow{}\mathcal{J}-\tau\nabla_{\mathcal{J}}L^{i}$

where $\tau$ is the diminishing learning rate.

Table 7: Most distinguishing features amongst clusters Feature | C1 Mean | C2 mean | C3 mean
---|---|---|---
UrineOutputSum | 10.18 | 11.221 | 14.81
MechVentLast8Hour | 0.424 | 0.524 | 0.903
MechVentDuration | 1568.97 | 1762.353 | 2314.388
WBC_last | 10.355 | 12.284 | 13.734
GCS_median | 14.368 | 12.732 | 9.162
Age | 62.202 | 67.46 | 62.134
Creatinine_last | 0.947 | 1.32 | 1.657
BUN_last | 17.159 | 25.647 | 30.013
Albumin_last | 3.091 | 2.984 | 2.756
WBC_first | 10.65 | 12.509 | 15.313
Table 8: Important Features for mortality prediction in respective clusters. Features common in all three clusters are highlighted in yellow while those common in two are highlighted in purple. The rest are unique to their respective clusters. Class ratios are depicted under cluster sizes. $|C_{1}|=1856$ | $|C_{2}|=2845$ | $|C_{3}|=2049$
---|---|---
$6.25:2.07:1$ | $1.27:1.15:1$ | $1:1.14:3.07$
WBC_last | HCT_last | SysABP_first
SOFA | BUN_first | GCS_last
HCT_first | PaO2_last | Age
Platelets_first | Creatinine_first | PaO2_last
Na_last | NIMAP_lowest | Glucose_last
HR_highest | MechVentDuration | HR_last
HR_lowest | Glucose_highest | Na_first
NISysABP_highest | GCS_highest | PaCO2_first
PaO2_last | HR_lowest | DiasABP_lowest
PaO2_first | Glucose_last | Weight

##  13 Extended Results

Table 6 present the AUC score (5-fold averaged on test dataset) of DeepCAC and
baselines. DeepCAC beats GRASP in $5$ out of $6$ experiments.

##  14 Case Study: ICU Length of Stay Prediction

As a case study, we illustrate the use of DeepCAC in the CIC-LOS ICU Length of
Stay (LoS) prediction data for $k=3$ clusters. Since we are clustering with a
view to induce class separability by making use of training labels, the
clusters are influenced by the target label, i.e., LoS indicator, and thus by
design DeepCAC is expected to find LoS subtypes. In other words, we expect the
inferred clusters to have different risk factors tailored to each underlying
subpopulation. To evaluate this, we examine feature importances for each
cluster’s local risk model. We distill the knowledge of local networks into a
simpler student model [50], a Gradient Boosting Classifier in our case, which
provides importance values of characteristics. Note that the number of
clusters need not be the same as number of classes in the target variable as
is imposed by the cluster assumption. In Table 8, we list the cluster sizes
$C_{i}$, the proportion of patients in the three quartiles of Length of Stay
($7,13,295$ hours) and the top 10 most important features in each cluster. We
see that, as expected, the risk models created by DeepCAC deem different sets
of features as important for predicting mortality. Out of the $10$ most
important features, there is 1 feature (PaO2_last) that is common across all 3
clusters and 2 features are common across the two models. Otherwise, each
model has $8$, $7$, and $8$ features unique to the respective clusters.

For the above case study, DeepCAC attains an AUPRC score of $0.495$ while the
student model trained on the prediction scores of DeepCAC attains an AUPRC of
$0.358$ (both evaluated on the same training and test datasets). $C_{3}$ has a
majority of patients who spend a large time in the ICU while $C_{1}$’s
majority population spent a relatively small time in the ICU. In Table
LABEL:tab:cluster_features we report the features that are most significant
across the 3 clusters (determined using p-values). This indicates that the
three clusters are most directly distinguished by the Mechanical Ventilation
parameters and the UrineOutput. But within those clusters, the patient LoS
depends on variables presented in Table 8. We can cluster the dataset with any
other variable also (say Age) and thus discover how LoS depends on different
variables for various age groups.

Table 9: AUC Scores for Time series datasets. Row-wise best result in bold. ${}^{\ast}p<0.05$, ${}^{\ast\ast}p<0.01$ indicates significantly better performance of DeepCAC-TS compared to the baseline. AUC |  | ACTPC-TS | GRASP-TS |  DeepCAC-TS
---|---|---|---|---
ARDS-TS | 2 | - | $0.493$ | $\mathbf{0.615}^{\ast\ast}$
ARDS-TS | 3 | - | $0.519$ | $\mathbf{0.605}^{\ast}$
ARDS-TS | 4 | - | $0.505$ | $\mathbf{0.565}^{\ast}$
Sepsis-TS | 2 | - | $0.491$ | $\mathbf{0.76}^{\ast\ast}$
Sepsis-TS | 3 | - | $0.528$ | $\mathbf{0.769}^{\ast}$
Sepsis-TS | 4 | - | $0.465$ | $\mathbf{0.752}^{\ast\ast}$

##  15 DeepCAC-TS

We extend DeepCAC, ACTPC and GRASP to handle time series data by replacing the
Stacked Autoencoder with LSTM based autoencoder. $\alpha$ and $\beta$ for
DeepCAC-TS are set to 20 and 5 respectively. For GRASP and ACTPC, we use the
hyperparameters recommended in their original papers.

We evaluate all algorithms on the ARDS and Sepsis datasets as mentioned in
table 1. We use the first 24 hours of data to predict risk (of each condition,
separately) in the remaining ICU stay, which is aligned with a hospital-
centric schedule for prediction. Risk prediction is formulated as a binary
classification problem. The prediction task is to predict whether a patient
will develop the condition at point in time after the 24 hours of stay in the
ICU. All patients whose length of ICU stay is $<24$ hours and those who
develop the condition within 24 hours of their ICU stay are excluded.

The AUC and AUPRC scores are mentioned in tables 9 and 3. We note that
DeepCAC-TS performs better than GRASP for both the datasets and for all
$k=2,3,4$. ACTPC-TS did not finish in time for both the datasets. All results
are 3-fold averaged over the test dataset. The AUC and AUPRC scores for
DeepCAC-TS are better than those obtained by DeepCAC on the static ARDS and
Sepsis datasets as expected.