基于分布式低秩表示的子空间聚类算法

计算机研究与发展ＤＯＩ：１０．７５４４桙ｉｓｓｎ１０００‐１２３９．２０１６．２０１４８３６２ＪｏｕｒｎａｌｏｆＣｏｍｐｕｔｅｒＲｅｓｅａｒｃｈａｎｄＤｅｖｅｌｏｐｍｅｎｔ５３（７）：１６０５１６１１，２０１６　收稿日期：２０１４－１２－０９；修回日期：２０１５－０６－０９

　基金项目：国家自然科学基金项目（６１３７３０５５）；江苏省自然科学基金项目（ＢＫ２０１４０４１９）；江苏省高校自然科学研究计划重大项目

（１４ＫＪＢ５２０００１）

ＴｈｉｓｗｏｒｋｗａｓｓｕｐｐｏｒｔｅｄｂｙｔｈｅＮａｔｉｏｎａｌＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＣｈｉｎａ（６１３７３０５５），ｔｈｅＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＪｉａｎｇｓｕＰｒｏｖｉｎｃｅｏｆＣｈｉｎａ（ＢＫ２０１４０４１９），ａｎｄｔｈｅＭａｊｏｒＰｒｏｇｒａｍｏｆＲｅｓｅａｒｃｈＰｌａｎｏｆｔｈｅＮａｔｕｒａｌＳｃｉｅｎｃｅｉｎＨｉｇｈｅｒＥｄｕｃａｔｉｏｎｏｆＪｉａｎｇｓｕＰｒｏｖｉｎｃｅｏｆＣｈｉｎａ（１４ＫＪＢ５２０００１）．　通信作者：吴小俊（ｗｕ＿ｘｉａｏｊｕｎ＠ｊｉａｎｇｎａｎ．ｅｄｕ．ｃｎ）基于分布式低秩表示的子空间聚类算法

许　凯　吴小俊　尹贺峰

（江南大学物联网工程学院　江苏无锡　２１４１２２）

（ｘｕｋａｉ３４７＠ｓｉｎａ．ｃｏｍ）

ＤｉｓｔｒｉｂｕｔｅｄＬｏｗＲａｎｋＲｅｐｒｅｓｅｎｔａｔｉｏｎ‐ＢａｓｅｄＳｕｂｓｐａｃｅＣｌｕｓｔｅｒｉｎｇＡｌｇｏｒｉｔｈｍＸｕＫａｉ，ＷｕＸｉａｏｊｕｎ，ａｎｄＹｉｎＨｅｆｅｎｇ（ＳｃｈｏｏｌｏｆＩｎｔｅｒｎｅｔｏｆＴｈｉｎｇｓＥｎｇｉｎｅｅｒｉｎｇ，ＪｉａｎｇｎａｎＵｎｉｖｅｒｓｉｔｙ，Ｗｕｘｉ，Ｊｉａｎｇｓｕ２１４１２２）

Ａｂｓｔｒａｃｔ　Ｖｉｓｉｏｎｐｒｏｂｌｅｍｒａｎｇｉｎｇｆｒｏｍｉｍａｇｅｃｌｕｓｔｅｒｉｎｇｔｏｍｏｔｉｏｎｓｅｇｍｅｎｔａｔｉｏｎｃａｎｎａｔｕｒａｌｌｙｂｅｆｒａｍｅｄａｓｓｕｂｓｐａｃｅｓｅｇｍｅｎｔａｔｉｏｎｐｒｏｂｌｅｍ，ｉｎｗｈｉｃｈｏｎｅａｉｍｓｔｏｒｅｃｏｖｅｒｍｕｌｔｉｐｌｅｌｏｗｄｉｍｅｎｓｉｏｎａｌｓｕｂｓｐａｃｅｓｆｒｏｍｎｏｉｓｙａｎｄｃｏｒｒｕｐｔｅｄｉｎｐｕｔｄａｔａ．Ｌｏｗｒａｎｋｒｅｐｒｅｓｅｎｔａｔｉｏｎ‐ｂａｓｅｄｓｕｂｓｐａｃｅｓｅｇｍｅｎｔａｔｉｏｎａｌｇｏｒｉｔｈｍ（ＬＲＲ）ｆｏｒｍｕｌａｔｅｓｔｈｅｐｒｏｂｌｅｍａｓａｃｏｎｖｅｘｏｐｔｉｍｉｚａｔｉｏｎａｎｄａｃｈｉｅｖｅｓｉｍｐｒｅｓｓｉｖｅｒｅｓｕｌｔｓ．Ｈｏｗｅｖｅｒ，ｉｔｎｅｅｄｓｔｏｔａｋｅａｌｏｎｇｔｉｍｅｔｏｓｏｌｖｅｔｈｅｃｏｎｖｅｘｐｒｏｂｌｅｍ，ａｎｄｔｈｅｃｌｕｓｔｅｒｉｎｇａｃｃｕｒａｃｙｉｓｎｏｔｈｉｇｈｅｎｏｕｇｈ．Ｔｈｅｒｅｆｏｒｅ，ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｓａｄｉｓｔｒｉｂｕｔｅｄｌｏｗｒａｎｋｒｅｐｒｅｓｅｎｔａｔｉｏｎ‐ｂａｓｅｄｓｐａｒｓｅｓｕｂｓｐａｃｅｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ（ＤＬＲＲＳ）．ＤＬＲＲＳａｄｏｐｔｓｔｈｅｄｉｓｔｒｉｂｕｔｅｄｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇｔｏｇｅｔｔｈｅｃｏｅｆｆｉｃｉｅｎｔｍａｔｒｉｘ，ｔｈｅｎｔａｋｅｔｈｅａｂｓｏｌｕｔｅｖａｌｕｅｏｆｅａｃｈｅｌｅｍｅｎｔｏｆｔｈｅｃｏｅｆｆｉｃｉｅｎｔｍａｔｒｉｘ，ａｎｄｒｅｔａｉｎｔｈｅｋｌａｒｇｅｓｔｃｏｅｆｆｉｃｉｅｎｔｓｐｅｒｃｏｌｕｍｎａｎｄｓｅｔｔｈｅｏｔｈｅｒｅｌｅｍｅｎｔｓｔｏ０ｔｏｇｅｔａｎｅｗｃｏｅｆｆｉｃｉｅｎｔｍａｔｒｉｘ．Ｆｉｎａｌｌｙ，ＤＬＲＲＳｐｅｒｆｏｒｍｓｓｐｅｃｔｒａｌｃｌｕｓｔｅｒｉｎｇｏｖｅｒｔｈｅｎｅｗｃｏｅｆｆｉｃｉｅｎｔｍａｔｒｉｘ．Ｂｕｔｉｔｄｏｅｓｎ摧ｔｈａｖｅｉｎｃｒｅｍｅｎｔａｌｌｅａｒｎｉｎｇｆｕｎｃｔｉｏｎ，ｓｏｔｈｅｒｅｉｓａｓｃａｌａｂｌｅｄｉｓｔｒｉｂｕｔｅｄｌｏｗｒａｎｋｒｅｐｒｅｓｅｎｔａｔｉｏｎ‐ｂａｓｅｄｓｐａｒｓｅｓｕｂｓｐａｃｅｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ（ＳＤＬＲＲＳ）ｈｅｒｅ．Ｉｆｎｅｗｓａｍｐｌｅｓａｒｅｂｒｏｕｇｈｔｉｎ，ＳＤＬＲＲＳｃａｎｕｓｅｔｈｅｆｏｒｍｅｒｃｌｕｓｔｅｒｉｎｇｒｅｓｕｌｔｔｏｃｌａｓｓｉｆｙｔｈｅｎｅｗｓａｍｐｌｅｓｔｏｇｅｔｔｈｅｆｉｎａｌｒｅｓｕｌｔ．ＥｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｏｎＡＲａｎｄＥｘｔｅｎｄｅｄＹａｌｅＢｄａｔａｓｅｔｓｓｈｏｗｔｈａｔｔｈｅｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍｓｃａｎｎｏｔｏｎｌｙｏｂｖｉｏｕｓｌｙｒｅｄｕｃｅｔｈｅｒｕｎｎｉｎｇｔｉｍｅ，ｂｕｔａｌｓｏａｃｈｉｅｖｅｈｉｇｈｅｒａｃｃｕｒａｃｙ，ｗｈｉｃｈｖｅｒｉｆｉｅｓｔｈａｔｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｓａｒｅｅｆｆｉｃｉｅｎｔａｎｄｆｅａｓｉｂｌｅ．Ｋｅｙｗｏｒｄｓ　ｌｏｗｒａｎｋｒｅｐｒｅｓｅｎｔａｔｉｏｎ；ｓｕｂｓｐａｃｅｃｌｕｓｔｅｒｉｎｇ；ｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇ；ｉｎｃｒｅｍｅｎｔａｌｌｅａｒｎｉｎｇ；ｃｏｅｆｆｉｃｉｅｎｔｓｒｅｃｏｎｓｔｒｕｃｔｉｏｎ

摘　要　针对基于低秩表示的子空间分割算法运算时间较长、

聚类的准确率也不够高，提出一种基于分布式低秩表示的稀疏子空间聚类算法（ｄｉｓｔｒｉｂｕｔｅｄｌｏｗｒａｎｋｒｅｐｒｅｓｅｎｔａｔｉｏｎ‐ｂａｓｅｄｓｐａｒｓｅｓｕｂｓｐａｃｅｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ，ＤＬＲＲＳ），该算法采用分布式并行计算来得到低秩表示的系数矩阵，然后保留系数矩阵每列的前ｋ个绝对值最大系数，其他系数置为０，用此系数矩阵构造一个稀疏的样本关系更突出的相似度矩阵，接着用谱聚类得到聚类结果．但是其不具备增量学习功能，为此再提出一种基于分布式低秩表示的增量式稀疏子空间聚类算法（ｓｃａｌａｂｌｅｄｉｓｔｒｉｂｕｔｅｄｌｏｗｒａｎｋｒｅｐｒｅｓｅｎｔａｔｉｏｎｂａｓｅｄｓｐａｒｓｅｓｕｂｓｐａｃｅｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ，ＳＤＬＲＲＳ），如果有新增样本，可以利用前面的聚类结果对新增样本进行