图 书 馆
直接求解归一化割的大规模数据光谱聚类Spectral Clustering of Large-scale Data by Directly Solving Normalized Cut |
|
| 课程网址: | http://videolectures.net/kdd2018_chen_clustering_normalized/ |
| 主讲教师: | Xiaojun Chen |
| 开课单位: | 深圳大学 |
| 开课时间: | 2018-11-23 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | During the past decades, many spectral clustering algorithms have been proposed. However, their high computational complexities hinder their applications on large-scale data. Moreover, most of them use a two-step approach to obtain the optimal solution, which may deviate from the solution by directly solving the original problem. In this paper, we propose a new optimization algorithm, namely Direct Normalized Cut (DNC), to directly optimize the normalized cut model. DNC has a quadratic time complexity, which is a significant reduction comparing with the cubic time complexity of the traditional spectral clustering. To cope with large-scale data, a Fast Normalized Cut (FNC) method with linear time and space complexities is proposed by extending DNC with an anchor-based strategy. In the new method, we first seek a set of anchors and then construct a representative similarity matrix by computing distances between the anchors and the whole data set. To find high quality anchors that best represent the whole data set, we propose a Balanced k-means (BKM) to partition a data set into balanced clusters and use the cluster centers as anchors. Then DNC is used to obtain the final clustering result from the representative similarity matrix. A series of experiments were conducted on both synthetic data and real-world data sets, and the experimental |
| 关 键 词: | 光谱聚类算法; 高计算复杂性; 传统光谱聚类; 线性时间和空间复杂性 |
| 课程来源: | 视频讲座网 |
| 数据采集: | 2023-01-24：cyh |
| 最后编审: | 2023-01-24：cyh |
| 阅读次数: | 38 |