区间型数据的可能性聚类算法

什么是聚类分析？聚类分析方法的类别

聚类分析是指将数据对象的集合分组为由类似的对象组成的多个类的分析过程。

基本概念

聚类（Clustering）就是一种寻找数据之间内在结构的技术。聚类把全体数据实例组织成一些相似组，而这些相似组被称作簇。处于相同簇中的数据实例彼此相同，处于不同簇中的实例彼此不同。

聚类技术通常又被称为无监督学习，与监督学习不同的是，在簇中那些表示数据类别的分类或者分组信息是没有的。

数据之间的相似性是通过定义一个距离或者相似性系数来判别的。图 1

显示了一个按照数据对象之间的距离进行聚类的示例，距离相近的数据对象被划分为一个簇。

图 1 聚类分析示意

聚类分析可以应用在数据预处理过程中，对于复杂结构的多维数据可以通过聚类分析的方法对数据进行聚集，使复杂结构数据标准化。

聚类分析还可以用来发现数据项之间的依赖关系，从而去除或合并有密切依赖关系的数据项。聚类分析也可以为某些数据挖掘方法（如关联规则、粗糙集方法），提供预处理功能。

在商业上，聚类分析是细分市场的有效工具，被用来发现不同的客户群，并且它通过对不同的客户群的特征的刻画，被用于研究消费者行为，寻找新的潜在市场。

在生物上，聚类分析被用来对动植物和基因进行分类，以获取对种群固有结构的认识。

在保险行业上，聚类分析可以通过平均消费来鉴定汽车保险单持有者的分组，同时可以根据住宅类型、价值、地理位置来鉴定城市的房产分组。

在互联网应用上，聚类分析被用来在网上进行文档归类。

在电子商务上，聚类分析通过分组聚类出具有相似浏览行为的客户，并分析客户的共同特征，从而帮助电子商务企业了解自己的客户，向客户提供更合适的服务。

聚类分析方法的类别

目前存在大量的聚类算法，算法的选择取决于数据的类型、聚类的目的和具体应用。聚类算法主要分为 5

大类：基于划分的聚类方法、基于层次的聚类方法、基于密度的聚类方法、基于网格的聚类方法和基于模型的聚类方法。

一篇文章透彻解读聚类分析及案例实操

【数盟致力于成为最卓越的数据科学社区，聚焦于大数据、分析挖掘、数据可视化领域，业务范围：线下活动、在线课程、猎头服务、项目对接】【限时优惠福利】数据定义未来，2016年5月12日-14日DTCC2016中国数据库技术大会登陆北京！大会云集了国内外数据行业顶尖专家，设定2个主会场，24个分会场，将吸引共3000多名IT人士参会！马上领取数盟专属购票优惠88折上折，猛戳文末“阅读原文”抢先购票！

摘要：本文主要是介绍一下SAS的聚类案例，希望大家都动手做一遍，很多问题只有在亲自动手的过程中才会有发现有收获有心得。这里重点拿常见的工具SAS+R语言+Python介绍!

1 聚类分析介绍1.1 基本概念聚类就是一种寻找数据之间一种内在结构的技术。聚类把全体数据实例组织成一些相似组，而这些相似组被称作聚类。处于相同聚类中的数据实例彼此相同，处于不同聚类中的实例彼此不同。聚类技术通常又被称为无监督学习，因为与监督学习不同，在聚类中那些表示数据类别的分类或者分组信息是没有的。通过上述表述，我们可以把聚类定义为将数据集中在某些方面具有相似性的数据成员进行分类组织的过程。因此，聚类就是一些数据实例的集合，这个集合中的元素彼此相似，但是它们都与其他聚类中的元素不同。在聚类的相关文献中，一个数据实例有时又被称为对象，因为现实世界中的一个对象可以用数据实例来描述。同时，它有时也被称作数据点(Data Point)，因为我们可以用r 维空间的一个点来表示数据实例，其中r 表示数据的属性个数。下图显示了一个二维数据集聚类过程，从该图中可以清楚地看到数据聚类过程。虽然通过目测可以十分清晰地发现隐藏在二维或者三维的数据集中的聚类，但是随着数据集维数的不断增加，就很难通过目测来观察甚至是不可能。

1.2 算法概述

目前在存在大量的聚类算法，算法的选择取决于数据的类型、聚类的目的和具体应用。大体上，主要的聚类算法分为几大类。

第３４卷第６期　２０１３年６月　仪　器　仪　表　学　报　

Ｃｈｉｎｅｓｅ　Ｊｏｕｒｎａｌ　ｏｆ　Ｓｃｉｅｎｔｉｆｉｃ　Ｉｎｓｔｒｕｍｅｎｔ　Ｖｏ１．３４　Ｎｏ．６　Ｊｕｎ．２０１３　

一种多维不确定性数据流聚类算法　

罗清华　，彭　宇　，彭喜元　

（１．哈尔滨工业大学（威海）信息与电气工程学院威海２６４２０９；　

２．哈尔滨工业大学自动化测试与控制研究所哈尔滨１５００８０）　

摘要：目前在很多不确定性数据流聚类方法研究中，存在着聚类模型和数据流的数据模型失配问题，且它们往往假定不确定　

性数据的概率密度函数、概率分布函数或者概率是已知的，然而这些信息在实际系统中很难获得。鉴于此，本文提出一种基于　

区间数的多维不确定性数据流聚类算法（ＵＩＤＭｉｃｒｏ）。在该算法中，首先利用区间数结合不确定性数据的统计信息表示多维不　

确定性数据流，然后采用“当前簇”和“候选簇”两层簇窗口对不确定性数据流进行聚类，通过动态调整两层簇窗口实现聚类模　

型和数据模型的实时匹配。实验结果表明，该方法具有较高的聚类精度和处理效率。　

关键词：不确定性数据流；聚类算法；区间数　

中图分类号：ＴＰ３９３　文献标识码：Ａ　国家标准学科分类代码：５１０．５０１５　

Ｍｕｌｔｉ－ｄｉｍｅｎｓｉｏｎａｌ　ｕｎｃｅｒｔａｉｎ　ｄａｔａ　ｓｔｒｅａｍ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍ　

Ｌｕｏ　Ｑｉｎｇｈｕａ　，Ｐｅｎｇ　Ｙｕ　，Ｐｅｎｇ　Ｘｉｙｕａｎ。　

（　．Ｓｃｈｏｏｌ　ｏｆｉｎｆｏｒｍａｔｉｏｎ　ａｎｄ　ｅｌｅｃｔｒｉｃａｌ　ｅｎｇｉｎｅｅｒｉｎｇ，Ｈａｒｂｉｎ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，Ｗｅｉｈａｉ　２６４２０９，Ｃｈｉｎａ；　

２．Ａｕｔｏｍａｔｉｃ　Ｔｅｓｔ　ａｎｄ　Ｃｏｎｔｒｏｌ　Ｉｎｓｔｉｔｕｔｅ，Ｈａｒｂｉｎ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，Ｈａｒｂｉｎ　１５００８０，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ａｔ　ｐｒｅｓｅｎｔ，ｔｈｅｒｅ　ａｒｅ　ｓｏｍｅ　ｐｒｏｂｌｅｍｓ　ｉｎ　ｔｈｅ　ｓｔｕｄｙ　ｏｆ　ｅｘｉｓｔｉｎｇ　ｕｎｃｅｒｔａｉｎ　ｄａｔａ　ｓｔｒｅａｍ　ｃｌｕｓｔｅｒｉｎｇ　ｍｅｔｈｏｄｓ，ｓｕｃｈ　ａｓ　

第３２卷　Ｖｏ１．３２　第２２期　Ｎｏ．２２　计算机工程　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　２００６年ｌ１月　Ｎｏｖｅｍｂｅｒ　２００６　・博士论文－　文章编号：１ｏｏｌ卜＿３４２８（２００６）２２＿一ｌｏ０４＿一ｌ３　文献标识码ｌ　Ａ　中田分类号：ＴＰ３９１　基于聚类的区间数时间序列的索引方法　

｜奠『小清　，沈钧毂‘　（１．西安交通大学软件所，西安７１００４９；２．河北经贸大学计算机－｛Ｉ心，石家庄０５００６１）　摘要：在时间序列数据库中，大多数现有的相似性搜索方法都集中在如何提高算法的效率，而对于由不精确数据纰成的时间序列如何进　行相似性搜索，则研究比较少，不精确数据经常用区间数据来表示；通过识别Ⅸ问数时间序列中的取要区问数，使得　间数时间序列的维　数大幅度降低，该文针对由区问数组成的时问序列，提出了一种基于低分率聚粪的索引方法。实验表明，该，『法加快了Ⅸ问数时间序列的　查找过程，　会出现漏报现象　关量词：区间数时间序列；相似性搜索；聚类；索引　Ｔｉｍｅ　Ｓｅｒｉｅｓ　ｏｆ　Ｉｎｔｅｒｖａｌｓ　Ｉｎｄｅｘ　Ｂａｓｅｄ　ｏｎ　Ｃｌｕｓｔｅｒｉｎｇ　

ＷＥＮＧ　Ｘｉａｏｑｉｎｇ　．＿．ＳＨＥＮ　Ｊｕｎｙｉ　（１　Ｉｎｓｔｉｔｕｔｅ　ｏｆＣｏｍｐｕｔｅｒ　Ｓｏｆｔｗａｒｅ，Ｘｉ’ａｎ　ＪｉａｏｔｏｎｇＵｎｉｖｅｒｓｉｔｙ，Ｘｉ’ａｎ　７１００４９；　２．Ｃｏｍｐｕｔｅｒ　Ｃｅｎｔｅｒ，Ｈｅｂｅｉ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｅｃｏｎｏｍｉｃｓ　ａｎｄ　Ｔｒａｄｅ，Ｓｈｉｊｉａｚｈｕａｎｇ　０５００６　Ｉ）　［Ａｂｓｔｒａｃｔｌ　Ｍｏｓｔ　ｅｘｉｓｔｉｎｇ　ａｐｐｒｏａｃｈｅｓ　ｏｆ　ｓｉｍｉｌａｒｉｔｙ　ｓｅａｒｃｈ　ｉｎ　ｔｉｍｅ　ｓｅｒｉｅｓ　ｄａｔａｂａｓｅｓ　ｆｏｃｕｓ　ｏｎ　ｔｈｅ　ｅｆｆｉｃｉｅｎｃｙ　ｏｆ　ａｌｇｏｒｉｔｈｍｓ　ｂｕｔ　ｓｅｌｄｏｍ　ｐｒｏｖｉｄｅ　ａ　ｍｅａｎｓ　ｔｏ　ｈａｎｄｌｅ　ｉｍｐｒｅｃｉｓｅ　ｄａｔａ．Ｔｈｅ　ｉｍｐｒｅｃｉｓｅ　ｄａｔａ　ａｒｅ　ｎｏｒｍａｌｌｙ　ｐｒｅｓｅｎｔｅｄ　ｉｎ　ｔｈｅ　ｉｎｔｅｒｖａ１．Ｂｙ　ｉｄｅｎｔｉｆｙｉｎｇ　ｔｈｅ　ｉｍｐｏｒｔａｎｔ　ｉｎｔｅｒｖａｌ　ｖａｌｕｅｓ　ｆｒｏｍ　ｔｈｅ　ｔｉｍｅ　ｓｅｒｉｅｓ　ｏｆ　ｉｎｔｅｒｖａｌｓ　ｔｈｅ　ｄｉｍｅｎｓｉｏｎａｌｉｔｙ　ｏｆ　ｔｈｅ　ｔｉｍｅ　ｓｅｒｉｅｓ　ｏｆ　ｉｎｔｅｒｖａｌｓ　Ｃａｌｌ　ｂｅ　ｇｒｅａｔｌｙ　ｒｅｄｕｃｅｄ．Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｓ　ａｎ　ｉｎｄｅｘｉｎｇ　ａｐｐｒｏａｃｈ　ｏｆ　ｔｉｍｅ　ｓｅｒｉｅｓ　ｏｆ　ｉｎｔｅｒｖａｌｓ，ｂａｓｅｄ　ｏｎ　ｃｌｕｓｔｅｒｉｎｇ　ｔｈｅ　ｔｉｍｅ　ｓｅｒｉｅｓ　ｏｆ　ｉｎｔｅｒｖａｌｓ　ｉｎ　ｌｏｗ　ｒｅｓｏｌｕｔｉｏｎ．Ａｓ　ｄｅｍｏｎｓｔｒａｔｅｄ　ｂｙ　ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔｓ，ｔｈｅ　ｐｒｏｐｏｓｅｄ　ａｐｐｒｏａｃｈ　ｓｐｅｅｄｓ　ｕｐ山ｅ　ｔｉｍｅ　ｓｅｒｉｅｓ　ｏｆ　ｉｎｔｅｒｖａｌｓ　ｑｕｅｒｙ　ｐｒｏｃｅｓｓ　ｗｈｉｌｅ　ｉｔ　ａｌｓｏ　ｇｕａｒａｎｔｅｅｓ　ｎｏ　ｆａｌｓｅ　ｄｉｓｍｉｓｓａｌｓ．　［Ｋｅｙ　ｗｏｒｄｓＩ　Ｔｉｍｅ　ｓｅｒｉｅｓ　ｏｆ　ｉｎｔｅｒｖａｌｓ；Ｓｉｍｉｌａｒｉｔｙ　ｓｅａｒｃｈ；Ｃｌｕｓｔｅｒｉｎｇ；Ｉｎｄｅｘ　时间序列数据库是数据序列的集合，序列中的元素按照　时间先后的顺序排列；对给定的需要查询的时间序列，在时　间序列数据库中查找与之变化模式相似的时间序列的过程，　称为相似性搜索（Ｓｉｍｉｌａｒｉｔｙ　ｓｅａｒｃｈ）。大多数现有的相似性搜索　方法都集中在如何提高算法的效率，但是对于由不精确　（ｉｍｐｒｅｃｉｓｅ　ｄａｔａ）、不确定（ｕｎｃｅｒｔａｉｎｔｙ　ｄａｔａ）数据组成的时间序　列，如何建立索引，如何进行相似性搜索，则研究比较少。　然而在现实世界中，不精确、不确定、不完善的数据到处存　在，如我们无法用精确的数据来描述某天的气温情况，只能　用　问数据来描述某天气温的变化范围在ｆ６”Ｃ，ｌ５”ｃ１之间，又　如我们无法用精确的数据来描述ＩＢＭ公司某天的股票价格，　只能用区间数据来描述该公司某天的股价在［１５５，２２５］之间波　动。文献【１　Ｊ给出了两个区间数时问序列之间的相似度定义，　然而由于计算较繁杂，该文没有给出区间数时间序列的索引　方法。　本文针对区间数时间序列数据库，提出了一种基于低分　辨砗ｃ聚类的索引方法，对“最优”聚类个数Ｋ的值进行了估　计，用多元方差分析对聚类的效果进行了检验。　１相关定义　定义１区间数时间序列…：　区间数时间序列ｘ为有限个区间数所组成的序列，　（ＸＩ，Ｘ２，．－，Ｘｎ），其中ｘｉ＝『　，，　是一个区间数。　令　。。（　，＿ｘ２一・，　）是区间数时间序Ｘ的下限序列，　Ｘ＝（ｘ　Ｌ，Ｘ　２，．．．，　）是ｐ（问数序列　的上限序列，则区间数时　间序列ｘ也可以表示为（ｘ．　，区间数时间序列在Ｆ文中简　称为区间数序列。　——　——　倒１茼兰阿姆斯特丹某年前６个月份气温变化情况组成　一个区间数时间序列　Ｊ：　ｘ＝（【一４，４Ｊ，【－５，３１．ｆ２，１２１，【５，１５　Ｊ，【７，１７１，【１０，２０１）　倒２　ＩＢＭ公司某周５个交易日股票价格波动情况组成一　个区间数序列［５１：　［９２，９３．０９１，［９２．１４，９３．１９１，Ｉ９２　４７，９３．３８１、Ｌ９２．０３，９３．２１¨９１，９２．３５　Ｊ，）　定义２设ｘ和Ｙ足两个长度都为Ｉ１的区间数时间序列，　ｘ与Ｙ之间的距离ｄ（Ｘ，Ｙ）为　’　ｄ（Ｘ，Ｙ）＝ｍａｘ（Ｉ　，一　Ｉ，Ｉ　一Ｙ　ｌ，１　ｊ　ｎ）　Ｒａｎｇａｒａｊａｎ等　’证明了ｄ（Ｘ，Ｙ）满足作为距离度量的３个　公理（ｔｌｚ负、对称和三角不等式）。　倒３阿姆斯特丹以及苏黎世某年　季度气温变化情况　分别为　ｘ＝（【一４，４］，ｆ・５，３１，１２，１２１），Ｙ＝（Ｉ一１　１，９Ｊ，【一８，１５１＇【・７，１８１）　按定义容易计算出这两个区间数序列之间的距离为　ｄ（Ｘ．Ｙ１＝１２　２重要区间数的识别　２．１识别时间序列中的重要点　这里所说的重要点是时问序列的一些极值点；从时间序　列中提取重要点的方法如下”　：　图ｌ给出了从时间序列Ｔ：（０．１，０．４，０．３，０．７。０．９。０．６，０．７，０．４，　０．３，０．５）识别出前５个审要点的操作过程。　基金疆日：国家自然科学基金资助项目（６０１７３０５８）　作者倚介：翁小清（１９６５一），男，博士生、副教授，：ｔ－￣Ｊｆ方向：数据　挖掘；沈钧毅，教授、博导　收稿日期：２００５－１２－０８　Ｅ－ｍａｉｌ：ｘｑｗｅｎｇ＠ｓｔｕ　ｘ　ｉｔｕ．ｅｄｕ．ｃ