Ensemble cluster pruning via convex-concave programming

Ensemble learning is the process of aggregating the decisions of different learners/models. Fundamentally, the performance of the ensemble relies on the degree of accuracy in individual learner predictions and the degree of diversity among the learners. The trade-off between accuracy and diversity within the ensemble needs to be optimized to provide the best grouping of learners as it relates to their performance. In this optimization theory article, we propose a novel ensemble selection algorithm which, focusing specifically on clustering problems, selects the optimal subset of the ensemble that has both accurate and diverse models. Those ensemble selection algorithms work for a given number of the best learners within the subset prior to their selection. The cardinality of a subset of the ensemble changes the prediction accuracy. The proposed algorithm in this study determines both the number of best learners and also the best ones. We compared our prediction results to recent ensemble clustering selection algorithms by the number of cardinalities and best predictions, finding better and approximated results to the optimum solutions.     

Fingerprint optimization method for the indoor localization system

The accuracy of the indoor localization is influenced directly by the quality of the fingerprint. But the indoor localization algorithms in existence are almost conducted based on the original fingerprint which is not optimized. The k-means is introduced to optimize the fingerprint in this paper. And deleting the collected bad-points through the theory of cluster could make the fingerprint more accurate for the indoor localization algorithm. Compared with the indoor localization systems in existence, the result of experiments shows that the optimized fingerprint can increase the accurate of indoor localization with a higher probability.     

基于改进的K-means聚类的多区域物流中心选址算法

针对当前多区域物流中心选址需建立配送中心个数不定、位置、覆盖范围不明的问题,本文提出了一种改进的k-means聚类算法,以城市经济引力模型为基础,将城市运输距离与居民消费能力的指标相结合,重新定义对象之间相似性度量的距离因子.并将密度思想引入k-means算法,提出类内差分均值的概念确定最优聚类数.实现分区后,分别在这些区域中利用重心法对配送中心进行最终的确定.最后实例分析了在西部地区37个城市创建物流配送中心的选址过程,并通过和传统的k-means聚类的选址结果对比,说明改进后的算法不仅可以节省配送时间,而且大大降低了运输成本,有很好的经济利用价值.     

A Fast and Effective Multiple Kernel Clustering Method on Incomplete Data

Multiple kernel clustering is an unsupervised data analysis method that has been used in various scenarios where data is easy to be collected but hard to be labeled. However, multiple kernel clustering for incomplete data is a critical yet challenging task. Although the existing absent multiple kernel clustering methods have achieved remarkable performance on this task, they may fail when data has a high value-missing rate, and they may easily fall into a local optimum. To address these problems, in this paper, we propose an absent multiple kernel clustering (AMKC) method on incomplete data. The AMKC method first clusters the initialized incomplete data. Then, it constructs a new multiple-kernel-based data space, referred to as K-space, from multiple sources to learn kernel combination coefficients. Finally, it seamlessly integrates an incomplete-kernel-imputation objective, a multiple-kernel-learning objective, and a kernel-clustering objective in order to achieve absent multiple kernel clustering. The three stages in this process are carried out simultaneously until the convergence condition is met. Experiments on six datasets with various characteristics demonstrate that the kernel imputation and clustering performance of the proposed method is significantly better than state-of-the-art competitors. Meanwhile, the proposed method gains fast convergence speed.     

Trade-Off between Efficiency and Effectiveness: A Late Fusion Multi-View Clustering Algorithm

Late fusion multi-view clustering (LFMVC) algorithms aim to integrate the base partition of each single view into a consensus partition. Base partitions can be obtained by performing kernel k-means clustering on all views. This type of method is not only computationally efficient, but also more accurate than multiple kernel k-means, and is thus widely used in the multi-view clustering context. LFMVC improves computational efficiency to the extent that the computational complexity of each iteration is reduced from O(n³) to O(n) (where n is the number of samples). However, LFMVC also limits the search space of the optimal solution, meaning that the clustering results obtained are not ideal. Accordingly, in order to obtain more information from each base partition and thus improve the clustering performance, we propose a new late fusion multi-view clustering algorithm with a computational complexity of O(n²). Experiments on several commonly used datasets demonstrate that the proposed algorithm can reach quickly convergence. Moreover, compared with other late fusion algorithms with computational complexity of O(n), the actual time consumption of the proposed algorithm does not significantly increase. At the same time, comparisons with several other state-of-the-art algorithms reveal that the proposed algorithm also obtains the best clustering performance.     

基于聚类和用户偏好的协同过滤推荐算法

协同过滤推荐算法使用评分数据作为学习的数据源,针对协同过滤推荐算法中存在的评分数据稀疏以及算法的可拓展性问题,提出了一种基于聚类和用户偏好的协同过滤推荐算法。为了挖掘用户的偏好,该算法引入了用户对项目类型的平均评分到评分矩阵中,并加入了基于用户自身属性的相似度;同时,为了降低数据稀疏性,该算法使用Weighted Slope One算法填充评分数据中的未评分项,并通过融入密度和距离优化初始聚类中心的K-means算法聚类填充后的评分数据中的用户,缩小了相似用户的搜索空间;最后在聚类后的数据集中使用传统的协同过滤推荐算法生成目标用户的推荐结果。通过使用MovieLens100K数据集实验证明,提出的算法对推荐效果有所改善。     

COS:度量分布式大数据处理系统的效率

【目的】在大数据处理领域,分布式计算系统得到广泛应用,它们的可扩展性得到重点关注,但其绝对性能往往没有得到重视。我们希望提出科学合理、与时俱进的度量标准,对分布式系统的性能进行评估。【方法】本文通过对比特定任务的单机实现和分布式实现来讨论分布式系统的性能,提出COS(Configuration that Outperforms a Single machine)这一指标,来衡量分布式系统在达到单台机器的性能时,需要的硬件资源数量。我们选取k-means聚类和逻辑回归两个经典机器学习算法,对其进行单机多线程实现,并通过向量化计算、优化内存分配与访问等方式对性能进行了优化,为分布式多机系统的性能提供参考。【结果】以Apache Spark作为对标系统,实验发现无论是使用其原生编程接口,还是经过悉心优化的机器学习库,都要使用数倍甚至数百倍的机器,才能达到单机多线程实现的性能。【局限】分布式系统与单机实现进行性能对比并不是完全公平的,分布式系统的额外开销客观存在。【结论】但COS指标仍能反映分布式系统存在的绝对性能较差、没有充分利用硬件优势等问题。     

最小化误差平方和k-means初始聚类中心优化方法

传统的k-均值算法对初始聚类中心和孤立点敏感,文中以最大程度地减少误差平方和为基本思想,提出一种最大化减少当前误差平方和的k-means初始聚类中心优化方法。在初始聚类中心选择阶段,每次增加聚类中心时,计算所有数据点作为当前聚类中心能够减少的误差平方和,选择能够最大化减少误差平方和的数据点作为聚类初始中心。利用真实数据集,同其他算法进行对比,实验结果表明该方法在选择初始聚类中心方面能够有效地减少聚类的迭代次数,提高聚类质量。同时人工模拟数据表明该方法对孤立点相对不敏感。     

Email Sentiment Analysis Through k-Means Labeling and Support Vector Machine Classification

Sentiment analysis for social media and online document has been a burgeoning area in text mining for the last decade. However, Email sentiment analysis has not been studied and examined thoroughly even though it is one of the most ubiquitous means of communication. In this research, a hybrid sentiment analysis framework for Email data using term frequency-inverse document frequency term weighting model for feature extraction, and k-means labeling combined with support vector machine classifier for sentiment classification is proposed. Empirical results indicate comparatively better classification results with the proposed framework than other combinations.     

基于聚类与分类结合的多示例预测算法

针对训练包不含标签的无监督多示例问题,本文提出了聚类和分类结合的多示例预测算法。首先利用多示例聚类算法完成无监督多示例学习的聚类任务,并根据聚类结果,将各个簇中的每个包转换成相应的k维特征向量。在标准多示例预测模型和一般性多示例预测模型上进行实验,可以得到较高的预测准确度,与其它多示例预测算法相比,本文算法具有较好的性能。