基于数据流的任意形状聚类算法
ＩＳＳＮ１０００—９８２５，ＣＯＤＥＮＲＵＸＵＥＷ
ＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ，Ｖｏｌ１７。Ｎｏ３，Ｍａｒｃｈ２００６，ＰＰ３７９—３８７
ＤＯＩ：１０１３６０／ｊｏｓｌ７０３７９
ｏ２００６ｂｙＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅＡｌｌｒｉｇｈｔｓｒｅｓｅｒｖｅｄ
基于数据流的任意形状聚类算法。
束蔚恒＋，印鉴，谢益煌
（中山大学计算机科学系，广东广州５１０２７５）
ＡｒｂｉｔｒａｒｙＳｈａｐｅＣｌｕｓｔｅｒＡｌｇｏｒｉｔｈｍｆｏｒＣｌｕｓｔｅｒｉｎｇＤａｔａＳｔｒｅａｍＺＨＵＷｅｉ—Ｈｅｎｇ，ＹＩＮＪｉａｎ，ＸＩＥＹｉ—Ｈｕａｎｇ
（ＤｅｐａｎｍｅｎｔｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，ＳｕｎＹａｔ－ＳｅｎＵｎｉｖｅｒｓｉｔｙ，Ｇｕａｎｇｚｈｎｕ５１０２７５，Ｃｈｉｎａ）
＋Ｃｏｒｒｅｓｐｏｎｄｉｎｇａｕｔｈｏｒ：Ｅ－ｍａｉｌ：ｇｚ＿ｚｗｈ＠２６３ｉｌｅｔ，ｈｔｔｐ：／／ｗｗｗｓｙｓｕｅｄｕｃｎ
Ｅ—ｍａｉｌ：ｊｏｓ＠ｉｓｃａｓａｃｃｎｈｔｔｐ：／／ｗｗｗ．ｊｏｓｏｒｇｃｎＴｅｌ／Ｆａｘ：＋８６－１０．６２５６２５６３
ＺｈｕＷＨ，ＹｉｎＪ＿ＸｉｅＹＨ．Ａｒｂｉｔｒａｒｙｓｈａｐｅｃｌｕｓｔｅｒａｌｇｏｒｉｔｈｍｆｏｒｃｌｕｓｔｅｒｉｎｇｄａｔａｓｔｒｅａｍ．ＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ，２００６，１７（３）：３７９—３８７．ｈｔｔｐ：／／ｗｗｗ．ｊｏｓ．ｏｒｇｅｎ／１０００?９８２５／１７／３７９．ｈｔｍ
Ａｂｓｔｒａｃｔ：ＣｌｕＳｔｒｅａｍｉｓａｐｏｐｕｌａｒｄａｔａｓｔｒｅａｍｃｌｕｓｔｅｒａｌｇｏｒｉｔｈｍ，ｈｏｗｅｖｅｒ，ｉｔｉｓｎｏｔｃａｐａｂｌｅｅｎｏｕｇｈｔｏｃｌｕｓｔｅｒａｒｂｉｔｒａｒｙｓｈａｐｅｓａｎｄｍａｋｅｃｌｕｓｔｅｒｓｉｎｐｅｒｉｏｄｉｃｄａｔａ．ＴｈｉｓｐａｐｅｒｉｎｔｒｏｄｕｃｅｓａｎｅｗａｌｇｏｒｉｔｈｍＡＣｌｕＳｔｒｅａｍｔｏｓｏｌｖｅｔｈｅｓｅｐｒｏｂｌｅｍｓ．ＴｈｅＡＣｌｕＳｔｒｅａｍｉｓｂａｓｅｄｏｎｔｈｅｐａｒｔｉｔｉｏｎａｎｄａｓｓｅｍｂｌｅｏｆｔｈｅｓｐａｃｅａｎｄｃｌｕｓｔｅｒｂｙｄｅｎｓｉｔｙＩｎｔｈｅｅｘｐｅｒｉｍｅｎｔ，ｉｔｉｓｓｈｏｗｎｔｈａｔＡＣｌｕＳｔｒｅａｍｉｓｂｅｔｔｅｒｔｈａｎＣｌｕＳｔｒｅａｍｉｎｓｐｅｅｄａｎｄａｃｃｕｒａｃｙ
Ｋｅｙｗｏｒｄｓ：ｄａｔａｓｔｒｅａｍ；ｃｌｕｓｔｅｒｉｎｇ；ｄａｔａｍｉｎｉｎｇ
摘要：详细分析了数据流聚粪算法ＣｌｕＳｔｒｅａｍ的不足之处，如对非球形的聚类效果不好、对周期性数据的聚类变化反映不完整等．并针对这些不足之处提出了一种采用空问分割、组合以及按密度聚类的算法ＡＣｌｕＳｔｒｅａｍ．实验结果表明，ＡＣｌｕＳｔｒｅａｍ在准确度和速度上都比ＣｌｕＳｔｒｅａｍ有较大的提高．
关键词：数据流；聚类；数据挖掘
中图法分类号：ＴＰ３１１文献标识码：Ａ
近年来，由于硬件技术的高速发展，人们获取数据的能力得到了极大的提高现实生活中，经常可以看到这样的情况：大量需要处理的数据以很快的速度产生例如，美国条高速公路上的传感器网络每天可以收集到高达几百万条的数据．而电讯电话公司大型交换机上每天记录的通话记录就高达几下万条．由于数据量太大、数据产生的速度太快，按传统的数据库应用模式处理这些数据，即完整、详细地收集这些数据，清洗后将其储存在数据库中，再交由计算机仔细处理已成为不可能完成的任务．由有限的数据到有限的数据处理能力，计算机工作者们面临着新的挑战．
．ＳｕｐｐｏｒｔｅｄｂｖｔｈｅＮａｔｉｏｎａｌＮａｔｕｒａｉＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＣｈｉｎａｕｎｄｅｒＧｒａｎｔＮｏ６０５７３０９７（国家自然科学基金）；ｔｈｅＲｅｓｅａｒｃｈＦｏｕｎｄａｔｉｏｎｏｆＮａｔｉｅｎａｌＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙＰｌａｎＰｒｏｊｅｃｔｏｆＣｈｉｎａｕｎｄｅｒＧｒａｎｔＮｏ２００４ＢＡ７２ＩＡ０２（国家科技计划）：ｔｈｅＲｅｓｅａｒｃｈＦｏｕｎｄａｔｉｏｎｏｆＤｉｓｃｉｐｌｉｎｅｓＬｅａｄｉｎｇｔｏＤｏｃｔｏｒａｔｅＤｅｇｒｅｅｏｆＣｈｉｎｅｓｅＵｎｉｖｅｒｓｉｔｉｅｓｕｎｄｅｒＧｒａｎｔＮｏ２００５０５５８０１７（高等学校博士学科点专项科研基金１：ｔｈｅＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＣ，ｕａｎｇｄｏｎｇＰｒｏｖｉｎｃｅｏｆＣｈｉｎａｕｎｄｅｒＧｒａｎｔＮｏｓ０５２００３０２，０４３００４６２（广东省自然科学基金１，ｔｈｅＲｅｓｅａｒｃｈＦｏｕｎｄａｔｉｏｎｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙＰｌａｎＰｒｏｊｅｃｔｉｎＧｕａｎｇｄｏｎｇＰｒｏｖｉｎｃｅｏｆＣｈｉｎａｕｎｄｅｒＧｒａｎｔＮｏ２００５８１０１０１０３２ｒ广东省科技计划项目）
Ｒｅｃｅｉｖｅｄ２００４．０９－２８；Ａｃｃｅｐｋｄ２００５—０３—１１
万方数据