Convex clustering, turning clustering into a convex optimization problem, has drawn wide attention. It overcomes the shortcomings of traditional clustering methods such as K-means, Density-Based Spatial Clustring of Applications with Noise (DBSCAN) and hierarchical clustering that can easily fall into the local optimal solution. However, convex clustering is vulnerable to the occurrence of outlier features, as it uses the Frobenius norm to measure the distance between data points and their corresponding cluster centers and evaluate clusters. To accurately identify outlier features, this paper decomposes data into a clustering structure component and a normalized component that captures outlier features. Different from existing convex clustering evaluating features with the exact measurement, the proposed model can overcome the vast difference in the magnitude of different features and the outlier features can be efficiently identified and removed. To solve the proposed model, we design an efficient algorithm and prove the global convergence of the algorithm. Experiments on both synthetic datasets and UCI datasets demonstrate that the proposed method outperforms the compared approaches in convex clustering.

The paper proposes the optimization problem of maximizing the sum of suBmodular and suPermodular (BP) functions with partial monotonicity under a streaming fashion. In this model, elements are randomly released from the stream and the utility is encoded by the sum of partial monotone suBmodular and suPermodular functions. The goal is to determine whether a subset from the stream of size bounded by parameter $k$ subject to the summarized utility is as large as possible. In this work, a threshold-based streaming algorithm is presented for the BP maximization that attains a $\mathrm{(}\mathrm{(}\mathrm{1}\mathrm{-}\kappa \mathrm{)}\mathrm{/}\mathrm{(}\mathrm{2}\mathrm{-}\kappa \mathrm{)}\mathrm{-}𝒪\mathsf{}\mathrm{(}\epsilon \mathrm{)}\mathrm{)}$-approximation with $𝒪\mathsf{}\mathrm{(}\mathrm{1}\mathrm{/}{\epsilon }^{\mathrm{4}}\mathsf{}{\log }^{\mathrm{3}}\mathsf{}\mathrm{(}\mathrm{1}\mathrm{/}\epsilon \mathrm{)}\mathsf{}\log \mathsf{}\mathrm{(}\mathrm{(}\mathrm{2}\mathrm{-}\kappa \mathrm{)}\mathsf{}k\mathrm{/}{\mathrm{(}\mathrm{1}\mathrm{-}\kappa \mathrm{)}}^{\mathrm{2}}\mathrm{)}\mathrm{)}$ memory complexity, where $\kappa$ denotes the parameter of supermodularity ratio. We further consider a more general model with fair constraints and present a greedy-based algorithm that obtains the same approximation. We finally investigate this fair model under the streaming fashion and provide a $\mathrm{(}{\mathrm{(}\mathrm{1}\mathrm{-}\kappa \mathrm{)}}^{\mathrm{4}}\mathrm{/}{\mathrm{(}\mathrm{2}\mathrm{-}\mathrm{2}\mathsf{}\kappa \mathrm{+}{\kappa }^{\mathrm{2}}\mathrm{)}}^{\mathrm{2}}\mathrm{-}𝒪\mathsf{}\mathrm{(}\epsilon \mathrm{)}\mathrm{)}$-approximation algorithm.