试析偏差抽样技术在聚类挖掘中的应用

《试析偏差抽样技术在聚类挖掘中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、西南农业大学硕士学位论文偏差抽样技术在聚类挖掘中的应用姓名：葛继科申请学位级别：硕士专业：农业机械化工程指导教师：余建桥20050501-_______I__目

2、___l_E自目E!g自E

3、!Egg_-_目

4、E自_!!_l!!!!s!s目!_占茹捅要数据挖掘fOataMining，豌称DhD或称为效据库中的知识发现。是为了发现事先来知的规则和联系而对大量数据进行选择、探索和建模的过程。数据挖掘是一个年轻而又欣欣向荣的研究领域，随着研究的不断深入t出现了许多用于挖掘不同类型数据的算法和技术。常用的数据挖掘方法包括描述、分类、关联规则、聚类、孤立点检测、模式匹配、数据可视化等。在

5、前人研究的基础上，对数据挖掘领域中的聚类分析方法进行了重点研究。通过对数据集进行聚类-所形成的簇可以对未来发展规划提供理论支持。指明了聚类的未来发展方向和面临的挑战．对聚类中的常用方法如划分方法、层次方法、基于密度的方法、基于网格的方法及基于模型的方法等进行了详细的论述。另外．对K一均值聚类算法进行了一些有益的改进，使其在处理稀疏数据集时效率更高。在当前的数据挖掘领域中。大规模数据集越来越普遍．它们大多具有很高的维数和海量的数据记录。现有的数据挖掘方法大多运行在低维、小数据集上．针对这些日益增多的大型、多维数据集来说。这些方法的处理结果不很理想，并且在处理大数据集时对系统的需

6、求也比较高。由于大规模数据集的内在复杂性，因此在应用特定的数据挖掘方法(如聚类)对给定的数据集进行处理时，往往不是在整个数据集上进行处理，而是把抽样技术引入数据挖掘过程中，先抽取出一个样本，然后在样本数据集上进行处理，最后根据处理结果来推测总体数据集的情况。其中，用的较多的抽样方法是简单随机抽样，这种方法简单易行，所以应用比较广泛。但是这种抽样方法也经常被人们抱怨，由于现实世界中的数据集大多是非对称、不均匀分布的，而简单随机抽样则是以相同的抽样概率来抽取数据集中的每一点。因此，经过简单随机抽样后得到的样本数据集不能很好地反映原始数据集的总体特性。在极端的情况下，如果随机抽样选

7、择的代表点都不是原始数据集中包含重要信息的数据对象，那么样本数据集根本无法反映出原始数据集的特征。鉴于这种原因，引入了偏差抽样的概念。可以按照数据集的密度应用偏差抽样来加速常规数据挖掘任务的运行，本文对此进行了研究。偏差抽样克服了简单随机抽样的局限，可以在相同概率的情况下，使用较小的样本来满足具体数据挖掘任务的要求。但是．由于不知道数据点的优先级，所以没有明确的方法对数据集中的点进行偏差抽样。研究发现，数据集的概率密度函数可以提供足够的信息来定位样本中的点，但是这需要一个密度估算函数．通过这个函数可以把样本密度映射为抽样概率。根据数据密度进行的偏差抽样能够使用任何密度估算函数

8、，并且在一些文献中也介绍了如何使用不同方法来发现多维数据集的密度估算函数的方法。从理论上来说，偏差抽样技术可以使用任何密度估算方法。由于核密度估算方法不利用有关数据分布的先验知识，并且通过一次数据扫描就可以获取一个核密度估算函数，因此，核密度估算函数是～个较好的选择。核密度估算技术是基于统计方法尤其是基于西南农业大学硕士学位论文墙尊核函数理论进行的，虽然核函数的准确形式对结果的近似值影响不大，为了处理问题的简便性，选择Epanechn诹ov核函数。文中把这种基于密度的偏差抽样方法作为一种数据约简技术应用在加速大型多维数据集中的聚类挖掘任务中。在密度偏差抽样中。给定点被包含在样

9、本中的概率依赖于数据集的密度，基于这种观点提出了一种技术，它能够根据用户的需要，对感兴趣的特性进行抽样。在偏差抽样过程中，为了发现数据集中高密度区域的簇，可以过抽样数据集的密集区域；为了发现低密度区域中较小的或稀疏的簇；也可以在数据集的稀疏区域多抽取一些数据点。这种方法能够充分保证原始数据集中的高密度区域在样本中依然密集，从而不至于丢失任何高密度区域中的簇。该方法也可以对极低密度的区域进行抽样来发现孤立点，文中对此没有傲过多的研究。在基于密度的偏差样本上运行聚类算法来评价偏差抽样的准确性。为了聚类样本点，使用一个层次聚类算法，这是一种凝聚的方法，也称为自底向上的方法。一开始将

10、每个对象作为单独的一个组，然后相继地合并相近的对象或组，直到所有的组合并为一个或达到一个终止条件。该方法的一个典型代表是CURE，它不用单个质心或对象来代表一个簇，而是选择数据空间中固定数目的具有代表性的点。层次聚类方法的运行时间复杂度是二次的，但是，即使对几千个数据点运行一个二次算法也是很困难的，更不要说运行在具有几十万个数据点的大数据集上了。克服这种困难的一个可行的方法是缩小数据集的长度，但必须在能够保护感兴趣的信息和不防碍整体技术的方式下进行。一个运行在偏差样本上的层次聚类算法是在原始数据集上进行