网站开发流程的8个步骤,优秀平面广告设计赏析,网站每年多少钱,网页制作平台基本概念#xff1a;
给定数据集D {d1#xff0c;d2 ,.. #xff0c;dn}#xff0c;p和q是D中的两个任意对象。我们使用欧氏距离来评估p和q之间的距离#xff0c;表示为 dist#xff08;p#xff0c;q#xff09;。 我们将首先给出k-最近邻集合和反向的定义k-最近邻集…基本概念
给定数据集D {d1d2 ,.. dn}p和q是D中的两个任意对象。我们使用欧氏距离来评估p和q之间的距离表示为 distpq。 我们将首先给出k-最近邻集合和反向的定义k-最近邻集合。 尽管学术中给出了类似的定义 我们把它们放在这里以方便读者理解我们的新算法。
下面是算法需要用到的以下定义
定义1(kNN) k近邻p的集合是k(k0)的集合由kNN(p)表示换句话说kNN(p)是D数据集中组成的一个集合对象。 |kNN(p)| k;和分别是的第k和第k1最近邻则定义2(反向k近邻的集合或者简称为R-kNN).p的反向k近邻集合属于kNN包含p的集合命名为R-kNN。 请注意在学术中反向kNN通常是简称为RNN这里使用的是R-kNN而不是RNN因为每个RNN集合都是在确定的k值基础上。kNN(p)和R-kNN(p)采用双向去探索关于对象p和它的邻近集合一方面kNN(p)是p自身的邻近点组成的集合另一方面R-kNN(p)表示的邻近结合点中包含p的点。这种双向描述任意的关系物体及其邻域给出了更清晰更准确的位置图 在本地和全局的数据集中这取决于k的值而不仅仅是使用kNN。 在下文中我们将给出一个定义对象的邻居。定义3(r近邻或者简称为rNB)。得到一个真实数字rp的近邻集合关于(其余部分简称 w.r.t)r的关系成为rNM(p)是集合对象位于以p作为圆的中心点r为半径的范围内的点。 定义4(k近邻简称kNB)。对于D数据集中的每个对象p使得.该p的k近邻被写作kNB(p)被定义为rNB(p), kNB(p) rNB(p).我们称呼kNB(p)作为p的k近邻kNN(p) 定义3和定义4定义从两个不同角度定义两个不同形式的近邻:rNB(p)是被定义通过使用一个显性半径。相反kNB(p)是被定义通过一个隐性半径它是相当于被圆的局域给覆盖通过kNN(p)。很明显因为可能有多个物体位于邻域的边缘圆定义5(反向k近邻简称R-kNB)。p是kNB包含p的对象集合由R-kNB表示可以写成 同样在数据集中的数据点能够被专业分类成三类密集点、稀疏点、均匀点。直观的说集群中的点是密集点或均匀点集群边上上的点最可能是疏松点。离散点和噪音也是疏松点目前大多数基于密度的聚类算法(eg.DBSCAN)使用使用一种直观直接的方法来测量密度即数据对象密度是给定的邻域中包含的数据对象的数量半径。显然这是一种绝对和全局密度。这样的密度测量使DBSCAN无法检测小的、密集的簇。来自大而稀疏的星团。本文提出了一种新的测量方法密度基于邻域的密度因子或简单的ndf它将我们的新聚类算法NBC的基础。定义6(基于邻域的密度因子或简称为NDF)p点的NDF求法如下 那么NDF的定义是什么呢?让我们来理解它|kNB(p)|是数字p的k-最近邻域中的对象是数字包含在p的k-最近邻域中的对象。对于大多数数据对象这个值大约是k根据定义4它可能会更大但不是小于k。 | R-KNBP|是p反向k近邻中包含的对象数邻域即将p作为其成员的对象的数量k-最近的邻域。对于不同的数据点该值非常不一致。 直观地更大的| R-kNBp|是这意味着更多的其他对象将p作为他们k个最近邻域的成员即更密集的p 邻域是或更大的NDFp。在这种情况下NDFp 1. 对于均匀分布的点如果q在kNBp中则p最可能在kNBq中因此kNBp≈ R-kNBp即NDFp≈1。因此NDF实际上是测量任何数据对象的邻域或数据对象的密度相对非绝对意义上的局部密度。此外这样的测量是直观易于理解简单易于实施和有效存在能够找到DBSCAN无法检测到的一些集群结构。为了证明NDF作为局部密度测量的能力我们 举一个图1中的例子。图1a是一个包含两个簇C1、C2的数据集由图可看出C1中的数据均匀分布; C2中的数据符合高斯分布分配。 图1b显示了数据集中所有数据点的NDF值。 如我们可以看到集群C1内的数据点大约有NDF值等于1而位于C1边界的数据点具有较小的NDF值。 对于群集C2最密集的点靠近C2的质心其具有最大的NDF值而其他对象的NDF值较小而且此外从质心定位的点它们的NDF值越小。使用NDF在下文中我们给出了三种类型数据的定义局部意义上的点局部事件点局部密集点和局部稀疏点。定义7(局部密集点简称DP)对象P是局部密集点如果它的NDFP大于1我们也把p称为与kNBp有关的密点NDP(p)越大p的k邻域越密集。定义8(局部稀疏点简称SP)p是局部稀疏点如果它的NDF(p) 1,我们称p为kNB(p)的局部稀疏点.NDP(q)越小k近邻越稀疏。定义9(局部平均点简称EP)p是局部平均点如果它的NDF(p) 1(或者接近于1),我们称p为kNB(p)的局部平均点 根据上面定义的概念下面我们将介绍基于邻域的集群的概念。我们的定义遵循dbscan的方式。定义10(基于邻域密度直接可达)从数据集D中得到p、q点满足一下要求p是一个基于邻域直接可达 q是一个DP或者EP定义11(领域可达)从数据集D中得到p、q点p是一个领域可达来自q如果有对象链p1,...,pn,p1p,pnq,这样pi可以从pi1邻域可达定义12(基于邻域紧密连接)从数据集D中得到p、q点p和q是基于邻域紧密连接如果q是邻域可达来自pk或者q是邻域可达来自p或者第三个对象o这样p和q都是邻域可达来自o 基于以上定义现在我们能够定义基于领域聚类的定义定义13(基于领域聚类)得到一个数据集D集群C 关于 k是D的非空子集 集群中的p、qp和q是邻域可达如果并且q是领域可达来自p则以上定义保证了簇是领域可达的最大集合对象关于k
NBC算法NBC算法由两部分组成
1.评估NDF值。我们查找kNB和R-kNB来自目标集合然后测量它的NDF。
2.聚类数据集。随机获取对象p()如果p是DP或EP则新建一个新的簇(社团)表示为p的簇并继续找其它的领域可达的来自p关于k涉及到所有对象属于p集群的所有对象如果p是一个SP那么就把它放好暂时搁置并继续检索下一个要处理的点这是递归操作直到发现所有集群更具体地说给定一个局部密集点或者平均点来自数据库首先找到对象直接邻域可达来自p关于k。kNB中一批对象将被移动到p的集群中然后找到另一个直接邻域可达可以从p的簇得到每个DP或EP在p的集群中直到那里不再有对象可以添加到p的集群中。第二、从剩下的数据集中获取另一个DP或EP已构建另一个集群。当没有更过的DP或EP来获取创建集群算法终止。不在集群中的点属于噪声或者是异常值下图有NBC算法的伪代码。
这里数据集指示聚类的数据集k是NBC中用于评估kNB和R-kNB的唯一输入参数。 k的值可以由数据库中的专家在一开始或通过实验来设置。参数k的确定将在下一小节中讨论。 DPset保留当前处理的群集的DP或EP。 DPset中的对象用于扩展相应的集群。将DP或EP的kNB移动到当前群集后将从DPset中删除它。在那里完全检测到群集 在DPset中不是对象。当NBC算法停止时clst no属性为NULL的未分类对象被视为噪声或异常值。 NBC算法以CalcNDF函数开始计算kNB 数据集中每个对象的R-kNB和NDF。在传统的指数结构中 R * -Tree和X-tree通常用于提高kNB的效率 查询处理相对较低维度的数据集。但是很少有索引结构在高维数据集上有效地工作。为了解决这个问题我们采用基于单元格的方法来支持kNB查询处理。 数据空间被切割成高维单元格VA文件[3]用于组织单元格。由于篇幅限制我们忽略了这里的细节。
//伪代码
void NBC(DataSet, k){for each object p int Dataset{p.clst_no NULL;//初始化集合中的每个对象}CalcNDF(Dataset, k);//计算NDFNoiseSet.empty();//初始化脏数据集合Cluster_count 0;//初始化社团数量为0for each object p int Dataset{//扫描整个库if(p.clst_no ! NULL or p.ndf 1){continue}p.clst_no cluste_count;//标记一个新的社团DPSet.empty();//初始化DPsetfor each object q in kNB(p){//找出与p关联的社团q.clst_no cluster_count;if(p.ndf 1){//ndf 1加入DPset.add(q);}}while(Dpset ! null){//继续扩展社团p DPset.getFirstObject();for each object q int kNB(p){if(q.clst_no ! NUll)continue;q.clst_no cluster_count;if(q.ndf 1)DPset.add(q);}DPset.remove(p);}cluster_count;}for each object p int Dataset{if(p.clst_no NULL){NoiseSet.add(p);}}}
}
算法分析
k值的意义
k值的确定。参数k粗略地确定了 数据库中最小集群的大小。根据基于邻域的聚类概念和NBC算法的过程找到一个聚类我们 必须首先找到至少一个其R-kNB大于或等于其kNB的DP或EP即NDF的值不小于1。假设C是最小的簇w.r.t.数据库D中的kp是第一个扩展簇C的DP或EP。 kNBp中的所有对象自然地分配给C.考虑到p本身因此C的最小尺寸是k 1。因此我们可以使用参数k来限制要找到的最小簇的大小。 集群是一组数据对象显示一些相似且独特的模式。 如果群集的大小太小则其模式不容易演示。在这种情况下数据表现得更像异常值。在实验中我们通常会设置 从k到10我们可以在数据库中找到最有意义的聚类。复杂度?
NBC算法的过程可以分为两个独立的部分计算NDF和发现簇。最耗时的 计算NDF的工作是评估kNB查询。让N成为 d维数据集D的大小。将对象映射到适当的单元格需要ON时间。对于正确定位的细胞长度l的值平均来说细胞长度为1 搜索需要3层每个单元包含k个对象。因此评估kNB查询的时间复合度是OmN其中m k * 5d。对于大 数据集m小于等于 N它变成ON。但是考虑到m 1因此CalcNDF的时间复杂度为OmN。发现集群的递归过程需要ON。因此NBC算法的时间复杂度为OmN。
