MATLAB代做FPGA代做网络Kmeans算法.docx

《MATLAB代做FPGA代做网络Kmeans算法.docx》由会员分享，可在线阅读，更多相关《MATLAB代做FPGA代做网络Kmeans算法.docx（5页珍藏版）》请在第一文库网上搜索。

1、数据挖掘与聚类分析2.1 聚类分析概述数据挖掘技术出现的时间不长，相应聚类方面的研究时间也不长，但是其发展非常迅速,在工程中的应用，特别是在搜索引擎中的应用非常广泛，聚类的理论和技术迅速增加。各种经典聚类算法相应出现，在聚类过程中，每种聚类算法表现出一定的缺点和局限性，针对这些问题，人们不断的对聚类算法的再改进，同时提出相应的理论作为改进的基础。比如提出孤立点的问题，计算样本间距离的不同计算方法，聚类结果质量的评定等。K-means算法作为一种基于划分的经典算法，开始只是提出了一种聚类过程的思想，当然存在很多缺点和局限性。从提出到现在的整个发展过程中，人们针对它存在的问题，在原k-means算

2、法的基础上提出了大量的改进算法。所有的改进算法，大部分都是把其他的聚类方法，比如，基于层次方法、基于密度方法等，应用到K-means的算法步骤当中，而改进之后，也只是解决某一方面的问题。现在随着网络用户的快速增加，数据信息的膨胀速度更是惊人，那么在聚类过程中对大数据量的聚类效果和时间也成为聚类研究非常关心的问题，人们也提出了一些解决办法，但是真正解决还需时间。针对K-means算法，改进之后会出现用户输入参数增加，聚类数据形状要求严格等问题现在一直没有得到很好的解决。而最关键的用户输入参数直接影响聚类的效果，如何解决这一问题，还需要进一步研究。聚类分析是数据挖掘的一个重要领域，而聚类算法是研究

3、的核心。聚类是将没有类别标记的对象，根据其特征，将其划分为不同的数据类。目的是使得属于同一类别的个体之间的距离尽可能的小（很高的相似度），而不同类别上的个体间的距离尽可能的大（相似度尽可能的小）。聚类方法包括统计、机器学习方法、神经网络方法和面向数据库的方法。2.2 聚类分析中的数据类型聚类算法中，经常要处理数据对象，这些数据对象可能表示人、房子、文档、国家等。许多基于内存的聚类算法都选择如下两种有代表性的数据结构：数据矩阵是一个对象-属性结构。它是由n个对象组成，设聚类问题中有n个对象组成：七(i=1,2,每个对象有P个属性，第i个对象第j个属性的观测值为勺。数据矩阵采用关系表形式或n*p矩

4、阵来表示。1，123，idx2P22j,*x2xnd_上式常称为数据矩阵，其中第i个对象P个变量的观测值记为：%=(Xj,Xj2,x加)C(2.2)相异度矩阵是一个对象对象结构。它存放所有n个对象彼此之间所形成的相似性。它一般采用n*n矩阵来表示。-O43,1),43,2),。(2.3)_4小1尸4小2),dgi),。一其中，40)表示对象i和对象j之间的相异性的量化表示，通常为一个非负数。当对象i和对象j非常相似或彼此“接近”时，该数值接近S该数值越大，就表示对象i和对象j越不相似。显然，d(ij)=d(Ji)Rd(ii)=o.数据矩阵经常被称为双模式矩阵，而相似性矩阵被称为单模矩阵。因为前

5、者行和列分别表示不同的实体，而后者行和列则表示同一实体。许多聚类算法都是基于差异度矩阵进行聚类分析的。如果数据是用数据矩阵的形式表现的，在使用该类算法之前要将其转化为相异度矩阵。在聚类分析中，经常涉及到的属性有间隔数值属性、二值属性、符号属性、顺序属性和比例(属性、或属性等，将这些属性组合进行描述的数据对象之间的差异值。利用数据对象差异值就可以对对象进行聚类分析了。2.3 主要聚类算法分类目前主要聚类算法可以大致分为以下几种类型：基于划分的方法、基于层次的方法、基于密度的方法、基于网格的方法、以及基于模型的方法。下面对这些主要的聚类算法进行简单介绍，并进行分析和比较。2.3.1 划分方法基于划

6、分方法是采用目标函数最小化的策略，把数据集合X中的N个数据对象划分为指定的k个集合，使得在同一个集合中的数据对象之间的相似度较高，而在不同集合中的数据对象之间的相似度较低。相似度定义是划分方法的关键，目标函数的一般形式如公式2,4所示，并采用启发式方法寻求目标函数的最优值解。IKN_J=FEEUNB,jN川i=(2.4)其中，J为集合X中所有数据对象与相应聚类簇中心的均方差之和，苍为是数据集空间内的一个数据对象，高为聚类簇Cj的均值；而为表示数据对象与聚类簇的归属关系：若若属于Cj,则=1,否则=0。公式(2.4)的聚类目标函数旨在使得聚类结果具有以下特点：各聚类簇内部尽可能的紧凑，而各聚类簇

7、之间尽可能的分散。可以看出，这种聚类分析同时满足以下两个条件：(1)每个聚类簇至少包含一个数据对象;(2)每个数据对象必须属于且仅属于一个聚类簇。最著名与最常用的基于划分方法的聚类算法是K-均值(K-means)算法和K-中心点(K-medoids)算法。本文，我们将重点研究K-均值(K-means)算法及其改进。2.3.2 层次方法层次聚类算法按数据分层组织为若干聚类簇，并形成相应的一棵以簇为节点的树来进行聚类。如果按自底向上进行层次分解，则称为凝聚的层次聚类；而按自顶向下进行层次分解的，则称为分裂的层次聚类。凝聚的层次聚类首先将每个对象作为一个簇，然后逐渐合并这些簇形成较大的簇，直到所有的

8、数据对象都在同一个簇中，或者满足指定的某个终止准则。分裂的层次聚类与之相反，此类算法首先将所有的数据对象置于同一个簇中，然后逐渐划分为越来越小的簇，直到每个数据对象自成一簇，或者满足指定的某个终止准则。这类算法包括B1RCH算法、CURE算法、Re）CK算法和Chame1eOn算法等。2.3.3 基于密度的方法对于非球状数据集，用距离来描述是不够的。对于这种情况，需要用密度来取代相似性,这就是基于密度的聚类算法。基于密度的算法从数据对象的分布密度出发，把密度足够大的区域连接起来，从而能够帮助发现具有任意形状的聚类簇。此类算法的基本思想是，一般来说，在一个数据对象空间中，高密度的对象区域被低密度

9、（稀疏）的对象区域所分割。此类算法还能够有效去除噪声点和孤立点数据对象；常见的基于密度的聚类算法有DBSCAN算法、OPT1CS算法和DENC1UE算法等。2.3.4 基于网格的方法基于网格聚类方法利用多维网格数据结构，把数据对象空间划分为有限数目的单元，从而构建一个可用于进行聚类分析的网格结构。这种方法的主要特点就是处理时间与数据集中的数据对象数目无关，而与数据空间在每个维度上所划分的单元数相关，因此基于网格的聚类算法处理速度很快。此外，此类聚类算法的精度取决于网格单元的大小。基于网格的聚类算法的缺点是只能发现边界是水平或垂直的聚类簇，而不能检测到具有斜边界的簇。此类算法不适用于高维数据集，

10、因为网格单元的数目随着维数的增加呈指数增长。基于网格的聚类算法中，有代表性的算法包括：STING算法、WaVeCkISter算法和C1IQUE算法等。235基于模型的方法基于模型的聚类方法假定数据是按照内在的概率分布生成的。此类算法试图优化给定数据集与某些数学模型之间的拟合度。基于模型的方法主要有两类：统计学方法和神经网络方基于统计学的聚类方法中，最著名的是FiSher提出的CoBWEB算法。COBWEB算法是一种流行的简单增量概念聚类算法。它的输入对象用分类属性-值对来描述。基于神经网络聚类方法是将每个聚类簇描述成一个样本。每个样本作为聚类簇的一个例证，且不一定与特定的实例或数据对象相对应。可以根据新对象与哪个样本最相似（基于某种距离计算方法）而分配到相应的聚类簇中。可以通过聚类簇的样本属性来预测分配到该簇的某个数据对象的相应属性。2.4 本章总结本章主要对数据聚类的基本概念作了介绍，并为后面章节K-means算法的研究奠定了基础。