计算机研究 -谱聚类算法研究.pdf
版权申诉
9 浏览量
2022-07-01
22:00:55
上传
评论
收藏 8.35MB PDF 举报
Ａｂｓｔｒａｃｔ
Ｃｌｕｓｔｅｒｉｎｇ
ａｎａｌｙｓｉｓ
ｉｓ
ｔｈｅ
ｃｌａｓｓｉｃ
ｐｒｏｂｌｅｍ
ｉｎ
ｍａｃｈｉｎｅ
ｌｅａｒｎｉｎｇ．Ｃｌｕｓｔｅｒｉｎｇ
ｃａｎ
ｂｅ
ｄｉｖｉｄｅｄ
ｉｎｔｏ
ｕｎｓｕｐｅｒｖｉｓｅｄ
ｃｌｕｓｔｅｒｉｎｇ
ａｎｄ
ｓｅｍｉ－ｓｕｐｅｒｖｉｓｅｄ
ｃｌｕｓｔｅｒｉｎｇ．Ｕｎｓｕｐｅｒｖｉｓｅｄ
ｃｌｕｓｔｅｒｉｎｇ
ｅｘｔｒａｃｔｓ
ｐｏｔｅｎｔｉａｌ
ｓｔｒｕｃｔｕｒｅ
ｏｆ
ｄａｔａ，ｇｒｏｕｐｓ
ｔｈｅ
ｓｉｍｉｌａｒ
ｄａｔａ
ｉｎｔｏ
ｔｈｅ
ｓａｍｅ
ｃｌｕｓｔｅｒ
ｗｉｔｈｏｕｔ
ａｎｙ
ｐｒｉｏｒ
ａｎｄ
ａｓｓｕｍｐｔｉｏｎ
ｉｎｆｏｒｍａｔｉｏｎ．Ｉｎ
ｔｈｅ
ｅｘｉｓｔｉｎｇ
ｕｎｓｕｐｅｒｖｉｓｅｄ
ｃｌｕｓｔｅｒｉｎｇ
ａｌｇｏｒｉｔｈｍｓ，ｋ－ｍｅａｎｓ
ｃｌｕｓｔｅｒｉｎｇ
ｉｓ
ｔｈｅ
ｐｏｐｕｌａｒ
ａｎｄ
ｓｉｍｐｌｅ
ｃｌｕｓｔｅｒｉｎｇ
ａｌｇｏｒｉｔｈｍ．Ｋ—ｍｅａｎｓ
ｃｌｕｓｔｅｒｉｎｇ
ｈａｓ
ａ
ｇｏｏｄ
ｐｅｒｆｏｒｍａｎｃｅ
ｉｎ
ｔｈｅ
ｓｐｈｅｒｉｃａｌ
ｄｉｓｔｒｉｂｕｔｉｏｎ
ｄａｔａ．Ｂｕｔ
ｋ－ｍｅａｎｓ
ｃｌｕｓｔｅｒｉｎｇ
ｔｅｎｄｓ
ｔｏ
ｆａｉｌｕｒｅ
ｉｎ
ｔｈｅ
ｎｏｎ－ｃｏｎｔｅｘｔ
ｄａｔａ．Ａｎｄ
ｋ－ｍｅａｎｓ
ｃｌｕｓｔｅｒｉｎｇ
ｕｓｅｓ
ｉｔｅｒａｔｉｖｅ
ｏｐｔｉｍｉｚａｔｉｏｎ
ｍｅｔｈｏｄ
ｔｏ
ｆｉｎｄ
ｏｐｔｉｍａｌ
ｓｏｌｕｔｉｏｎ，ｔｈｕｓ
Ｃａｌｌ’ｔ
ｇｕａｒａｎｔｅｅ
ｃｏｎｖｅｒｇｅ
ｔｏ
ｔｈｅ
ｇｌｏｂａｌ
ｏｐｔｉｍａｌ
ｓｏｌｕｔｉｏｎ．
Ｓｐｅｃｔｒａｌ
ｃｌｕｓｔｅｒｉｎｇ
ｉｓ
ａｎ
ｕｎｓｕｐｅｒｖｉｓｅｄ
ｃｌｕｓｔｅｒｉｎｇ
ａｌｇｏｒｉｔｈｍ
ａｐｐｅａｒｉｎｇ
ｒｅｃｅｎｔｌｙ．Ｓｐｅｃｔｒａｌ
ｃｌｕｓｔｅｒｉｎｇ
ｏｖｅｒｃｏｍｅｓ
ｔｈｅ
ｓｈｏｒｔｃｏｍｉｎｇ
ｏｆ
ｋ－ｍｅａｎｓ
ｃｌｕｓｔｅｒｉｎｇ．Ｓｐｅｃｔｒａｌ
ｃｌｕｓｔｅｒｉｎｇ
ｃａｎ
ｒｅｃｏｇｎｉｚｅ
ｎｏｎ—ｃｏｎｖｅｘ
ｄｉｓｔｒｉｂｕｔｉｏｎ
ｃｌｕｓｔｅｒｉｎｇ，ｉｓ
ｓｕｉｔａｂｌｅ
ｔｏ
ｐｒａｃｔｉｃａｌ
ｐｒｏｂｌｅｍｓ．Ｓｐｅｃｕａｌ
ｃｌｕｓｔｅｒｉｎｇ
ｓｈｏｕｌｄｎ’ｔ
ｇｅｔ
ｌｏｃａｌ
ｏｐｔｉｍａｌ
ｓｏｌｕｔｉｏｎ，ａｎｄ
ｃａｎ
ａｖｏｉｄ
ｓｉｎｇｕｌａｒ
ｐｒｏｂｌｅｍ
ｃａｕｓｅｄ
ｂｙ
ｔｈｅ
ｅｘｔｒａ
ｄｉｍｅｎｓｉｏｎ
ｏｆ
ｄａｔａ．Ｉｎ
ｔｈｉｓ
ｐａｐｅＬ
ｗｅ
ｄｏ
ｔｗｏ
ａｓｐｅｃｔｓ
ｒｅｓｅａｒｃｈ
ｂａｓｅｄ
ｏｎ
ｓｐｅｃｔｒａｌ
ｃｌｕｓｔｅｒｉｎｇ
ａｌｇｏｒｉｔｈｍ
１．ｗｅ
ｐｒｏｐｏｓｅ
ａ
ｃｌｕｓｔｅｒｉｎｇ
ａｌｇｏｒｉｔｈｍ
ｈｉｅｒａｒｃｈｉｃａｌ
ｓｐｅｃｔｒａｌ
ｃｌｕｓｔｅｒｉｎｇ（ＨＳＣ）．Ｔｈｅ
ｐｒｏｐｏｓｅｄ
ＨＳＣ
ａｌｇｏｒｉｔｈｍ
ａｂｓｏｒｂｓ
ｈｉｇｈｅｒ
ｃｌｕｓｔｅｒｉｎｇ
ａｃｃｕｒａｃｙ
ｏｆ
ｈｉｅｒａｒｃｈｉｃａｌ
ｃｌｕｓｔｅｒｉｎｇ
ａｎｄ
ａｖｏｉｄｓ
ｓｋｅｗｅｄ
ｄｉｖｉｓｉｏｎｓ
ｂｅｃａｕｓｅ
ｏｆ
ｕｓｉｎｇ
ｓｐｅｃｔｒａｌ
ｃｌｕｓｔｅｒｉｎｇ．Ｅｘｐｅｒｉｍｅｎｔａｌ
ｒｅｓｕｌｔｓ
ｓｈｏｗ
ｔｈａｔ
ｔｈｅ
ｐｒｏｐｏｓｅｄ
ｈｉｅｒａｒｃｈｉｃａｌ
ｓｐｅｃｔｒａｌ
ｃｌｕｓｔｅｒｉｎｇ
ｉｓ
ｓｕｐｅｒｉｏｒ
ｔｏ
ｓｐｅｃｔｒａｌ
ｃｌｕｓｔｅｒｉｎｇ
ｏｒ
ｈｉｅｒａｒｃｈｉｃａｌ
ｃｌｕｓｔｅｒｉｎｇ
ｏｎ
ｃｌｕｓｔｅｒ
ｑｕａｌｉｔｙ
ａｎｄ
ｉｓ
ｓｕｐｅｒｉｏｒ
ｔｏ
ｈｉｅｒａｒｃｈｉｃａｌ
ｃｌｕｓｔｅｒｉｎｇ
ｏｎ
ｃｏｍｐｕｔａｔｉｏｎａｌ
ｓｐｅｅｄ
２．ｗｅ
ｐｒｏｐｏｓｅ
ａ
ｓｐｅｃｔｒａｌ
ｃｌｕｓｔｅｒｉｎｇ
ｂａｓｅｄ
ｏｎ
ａｆｆｉｎｉｔｙ
ｐｒｏｐａｇａｔｉｏｎ．Ｔｈｉｓ
ｃｌｕｓｔｅｒｉｎｇ
ａｌｇｏｒｉｔｈｍ
ｕｓｅ
ｔｈｅ
ｄｉｍｅｎｓｉｏｎ
ｒｅｄｕｃｔｉｏｎ
ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ
ｏｆ
ｓｐｅｃｔｒａｌ
ｃｌｕｓｔｅｒｉｎｇ
ｔｏ
ｏｂｔａｉｎ
ｔｈｅ ｄｉｓｔｒｉｂｕｔｉｏｎ
ｏｆ
ｄａｔａ
ｉｎ
ｔｈｅ
ｍａｐｐｉｎｇ
ｓｐａｃｅ，ｔｈｅｎ
ｄｏ
ａｆｆｉｎｉｔｙ
ｐｒｏｐａｇａｔｉｏｎ
ｃｌｕｓｔｅｒｉｎｇ
ｏｎ
ｓａｍｐｌｅｓ
ｉｎ
ｍａｐｐｉｎｇ
ｓｐａｃｅ．Ｔｈｉｓ
ｍｅｔｈｏｄ
ｐｒｏｖｉｄｅ
ｄｉｍｅｎｓｉｏｎ
ａｎｄ
ｔｉｇｈｔｅｎｅｄ
ｉｎｐｕｔ
ｆｏｒ
ａｆｆｉｎｉｔｙ
ｐｒｏｐａｇａｔｉｏｎ
ｃｌｕｓｔｅｒｉｎｇ
ｔｈｒｏｕｇｈ
ｓｐｅｃｔｒａｌ
ｍａｐｐｉｎｇ．Ａｎｄ
ａｆｆｉｎｉｔｙ
ｐｒｏｐａｇａｔｉｏｎ
ａｌｇｏｒｉｔｈｍ
ｃａｎ
ｆａｓｔ
ｃｏｖｅｒａｇｅ
ｔｏ
ｇｌｏｂａｌ
ｏｐｔｉｍｉｚａｔｉｏｎ
ｓｏｌｕｔｉｏｎ
ａｎｄ
ｎｏｔ
ｓｅｎｓｉｔｉｖｅ
ｔｏ
ｔｈｅ
ｉｎｉｔｉａｔｉｏｎ
Ｔｈｅ
ｃｌｕｓｔｅｒｉｎｇ
ｒｅｓｕｌｔｓ
ｂａｓｅｄ
ｏｎ
ＭＰＥＧ－７
ｄａｔａｂａｓｅ
ａｎｄ
ｔｈｅ
ｓｕｂｓｅｔ
ｓｈｏｗ
ｔｈｅ
ｇｏｏｄ
ｐｅｒｆｏｒｍａｎｃｅ
ｏｆ
ｔｈｅ
ｓｐｅｃｔｒａｌ
ｃｌｕｓｔｅｒｉｎｇ
ｂａｓｅｄ
ｏｎ
ａｆｆｉｎｉｔｙ
ｐｒｏｐａｇａｔｉｏｎ
ＫＥＹ
ＷＯＲＤＳ：ｉｍａｇｅ
ｃｌｕｓｔｅｒｉｎｇ，ｈｉｅｒａｒｃｈｉｃａｌ
ｃｌｕｓｔｅｒｉｎｇ，ｓｐｅｃｔｒａｌ
ｃｌｕｓｔｅｒｉｎｇ，ａｆｆｉｎｉｔｙ
ｐｒｏｐａｇａｔｉｏｎ
ＩＩＩ
剩余44页未读，继续阅读
资源评论
