图 书 馆
寻找低误差的分类On Finding Low Error Clusterings |
|
| 课程网址: | http://videolectures.net/mlss09us_balcan_flec/ |
| 主讲教师: | Maria-Florina Balcan |
| 开课单位: | 乔治亚理工学院 |
| 开课时间: | 2009-07-30 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | There has been substantial work on approximation algorithms for clustering data under distance-based objective functions such as k-median, k-means, and min-sum objectives. This work is fueled in part by the hope that approximating these objectives well will indeed yield more accurate solutions. That is, for problems such as clustering proteins by function, or clustering images by subject, there is some unknown correct "target" clustering and the implicit assumption is that clusterings that are approximately optimal in terms of these distance-based measures are also approximately correct in terms of error with respect to the target. In this work we show that if we make this implicit assumption explicit - that is, if we assume that any c-approximation to the given clustering objective Phi is epsilon-close to the target - then we can produce clusterings that are O(epsilon)-close to the target, even for values c for which obtaining a c-approximation is NP-hard. In particular, for the k-median, k-means, and min-sum objectives, we show that we can achieve this guarantee for any constant c > 1. Our results shows how for these clustering objectives one can get much better guarantees on accuracy than those implied by results obtained so far in the approximation literature, by wisely using all the available information for the problem at hand. |
| 关 键 词: | 计算机科学; 机器学习; 聚类 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2021-01-30：nkq |
| 阅读次数: | 41 |