A novel minorization–maximization framework for simultaneous feature selection and clustering of high-dimensional count data

Abstract

Count data are commonly exploited in machine learning and computer vision applications; however, they often suffer from the well-known curse of dimensionality, which declines the performance of clustering algorithms dramatically. Feature selection is a major technique for handling a large number of features, which most are often redundant and noisy. In this paper, we propose a probabilistic approach for count data based on the concept of feature saliency in the context of mixture-based clustering using the generalized Dirichlet multinomial distribution. The saliency of irrelevant features is reduced toward zero by minimizing the message length, which equates to doing feature and model selection simultaneously. It is proved that the developed approach is effective in identifying both the optimal number of clusters and the most important features, and so enhancing clustering performance significantly, using a range of challenging applications including text and image clustering.

Appendix A: Surrogate function construction

The complete data log-likelihood of proposed model (Eq. 7) is given by:

$$\begin{aligned} {\mathcal {L}}=\sum _{i=1}^{N} \sum _{j=1}^{M} p_j&\Bigg [ \sum _{l=1}^{D} \log (\rho _{jl}) + \log (\pi _{jl}\dots [\pi _{jl}+(X_{il}-1)\theta _{jl}]) \nonumber \\&+\log \Big ((1-\pi _{jl})\dots [1-\pi _{jl}+(Y_{il+1}-1)\theta _{jl}]\Big ) \nonumber \\&-\log (1\dots [1+(Y_{il}-1)\theta _{jl}]) + \log (1-\rho _{jl}) \nonumber \\&+ \log (\mu _{l}\dots [\mu _{l}+(X_{il}-1)\lambda _{l}]) \nonumber \\&+\log \Big ((1-\mu _{l})\dots [1-\mu _{l}+(Y_{il+1}-1)\lambda _{l}]\Big ) \nonumber \\&-\log (1\dots [1+(Y_{il}-1)\lambda _{l}]) \Bigg ] \end{aligned}$$

(A1)

To construct an MM algorithm, we need to minorize terms such as $\log (\pi _{jl}+ k)$, $\log (\mu _{jl}+k)$. Noticing that the term $\log (\pi _{jl}+ k)$ occurs in the log-likelihood if and only if $X_{il} \ge k+1$ , and the term $\log (\mu _{jl}+k)$ occurs in the log-likelihood if and only if $Y_{il} \ge k+1$, we define the following associated counts for $l=1,\dots , D$ :

$$\begin{aligned} r_{lk}=\sum _{i=1}^t 1_{\{X_{il} \ge k+1\}}, \quad s_{lk}=\sum _{i=1}^t 1_{\{Y_{il} \ge k+1\}} \end{aligned}$$

where the index k ranges from 0 to $\max _i m_i-1$. Recalling that $\upsilon _{ijl}=P(Z_i=j,\phi _{jl}=1 \mid X_i)$ and $\nu _{ijl}=P(Z_i=j,\phi _{jl}=0 \mid X_i)$, thus, Eq.(A1) can be re-written as:

$$\begin{aligned} {\mathcal {L}}(\Theta )&=\sum _i \upsilon _{ijl} \Bigg [- \sum _l \sum _k s_{lk} \log (1+k\theta _{jl})\nonumber \\&+ \sum _l \sum _k r_{lk} \log (\pi _{jl}+k \theta _{jl})\nonumber \\&+\sum _l \sum _k s_{lk} \log \Big ((1-\pi _{jl})+k\theta _{jl}\Big ) \Bigg ] \nonumber \\&+\sum _i (\sum _j \nu _{ijl}) \Bigg [-\sum _l \sum _k s_{lk} \log (1+k\lambda _{l}) \nonumber \\&+ \sum _l \sum _k r_{lk} \log (\mu _{l}+k \lambda _{l})\nonumber \\&+\sum _l \sum _k s_{lk} \log \Big ((1-\mu _{l})+k\lambda _{l}\Big ) \Bigg ] \end{aligned}$$

(A2)

Then, we apply the basic minorization functions found by Zhou and Lange (see equations 2.3 and 2.4 in [35]) to the previous equation which yields the surrogate function as:

$$\begin{aligned} {\mathcal {G}}(\Theta )&= \sum _i \upsilon _{ijl} \Bigg [- \sum _l \sum _k s_{lk} \frac{k}{1+k\theta _{jl}^n} \theta _{jl} \nonumber \\&+ \sum _l \sum _k r_{lk} \Bigg \{\frac{\pi _{jl}^n}{\pi _{jl}^n+k\theta _{jl}^n} \log \pi _{jl} + \frac{k \theta _{jl}^n}{\pi _{jl}^n+k\theta _{jl}^n} \log \theta _{jl}\Bigg \} \nonumber \\&+\sum _l \sum _k s_{lk} \Bigg \{\frac{1-\pi _{jl}^n}{(1-\pi _{jl}^n)+k\theta _{jl}^n} \log (1-\pi _{jl})\nonumber \\& + \frac{k \theta _{jl}^n}{(1-\pi _{jl}^n)+k \theta _{jl}^n } \log k\theta _{jl}^n\Bigg \} \Bigg ] \nonumber \\&+\sum _i (\sum _j \nu _{ijl}) \Bigg [-\sum _l \sum _k s_{lk} \frac{k}{1+k\lambda _{l}^n} \lambda _{l} \nonumber \\&+ \sum _l \sum _k r_{lk} \Bigg \{\frac{\mu _{l}^n}{\mu _{l}^n+k\lambda _{l}^n} \log \mu _{l} + \frac{k \lambda _{l}^n}{\mu _{l}^n+k\lambda _{l}^n} \log \lambda _{l}\Bigg \} \nonumber \\&+\sum _l \sum _k s_{lk} \Bigg \{\frac{1-\mu _{l}^n}{(1-\mu _{l}^n)+k\lambda _{l}^n} \log (1-\mu _{l})\nonumber \\& + \frac{k \lambda _{l}^n}{(1-\mu _{l}^n)+k\lambda _{l}^n }\log k\lambda _{l}^n \Bigg \} \Bigg ] \end{aligned}$$

(A3)