没有合适的资源?快使用搜索试试~ 我知道了~
5790完全动态k-中心聚类�0T-H. Hubert Chan †0香港大学 香港hubert@cs.hku.hk0LTCI,巴黎高科大学巴黎,法国arnaud.guerquin@ens-paris-saclay.fr0Mauro Sozio ‡0LTCI,巴黎高科大学巴黎,法国sozio@telecom-paristech.fr0摘要0静态和动态聚类算法是任何机器学习库中的基本工具。在开发动态机器学习和数据挖掘算法方面,大部分工作都集中在滑动窗口模型(在任何给定时间点,只保留最新的数据项)或更简单的模型上。然而,在许多实际应用中,可能需要处理任意的删除和插入。例如,可能需要删除不一定是最旧的数据项,因为它们被标记为包含不适当内容或涉及隐私问题。聚类轨迹数据可能还需要处理更一般的更新操作。我们在完全动态对抗模型下开发了一个(2 +ϵ)-近似算法,用于具有“小”摊销成本的k-中心聚类问题。在这种模型中,可以任意添加或删除点,前提是对手无法访问我们算法的随机选择。当输入中任意两点之间的最大距离和最小距离之比受到多项式限制时,我们的算法的摊销成本是多对数的,而k和ϵ是常数。我们的理论结果与来自Twitter、Flickr以及轨迹数据的动态数据的广泛实验评估相结合,证明了我们方法的有效性。0ACM参考格式:T-H. Hubert Chan,Arnaud Guerquin和MauroSozio。2018年。完全动态k-中心聚类。在WWW2018:2018年网络会议,2018年4月23日至27日,法国里昂。ACM,美国纽约,9页。https://doi.org/10. 1145/3178876.318612401 引言0在Twitter上每秒发布超过6000条推文,Google每秒处理超过40000个查询,每分钟上传超过400小时的YouTube视频,迫切需要开发动态机器学习和数据挖掘。0�该研究部分得到香港研究资助局和法国驻香港总领事馆赞助的香港法国联合研究计划项目F-HKU702/16的资助。† 该研究部分得到香港研究资助局的资助,资助号为17217716。‡该研究部分得到法国国家研究局(ANR)项目FIELDS(ANR-15-CE23-0006)的资助。0本文发表在知识共享署名4.0国际许可证(CC BY4.0)下。作者保留在个人和公司网站上传播作品的权利,并附上适当的归属。WWW2018,2018年4月23日至27日,法国里昂© 2018IW3C2(国际万维网会议委员会),根据知识共享CC BY 4.0许可证发布。ACM ISBN978-1-4503-5639-8/18/04。https://doi.org/10.1145/3178876.31861240算法。在这方面的大部分工作都集中在计算的滑动窗口模型[6,7],其中在任何给定时间点只保留最新的数据项,或者更简单的模型。然而,在许多实际应用中,可能需要处理任意的删除和插入。例如,可能需要删除不一定是最旧的数据项,因为它们被标记为包含不适当内容或涉及隐私问题。由于“被遗忘的权利”原则的出现,后一种情况越来越普遍。聚类轨迹数据可能还需要处理比滑动窗口模型建模的更一般的更新操作。聚类算法是任何机器学习库中的基本工具。近年来,对聚类问题进行理论和实践研究的工作越来越多[6,8,11,12]。在我们的工作中,我们考虑了一个完全动态对抗模型,其中可以任意添加或删除点,前提是对手无法访问我们算法的随机选择。此外,我们的算法不知道更新操作。我们的主要目标是在完全动态环境中研究其他机器学习和数据挖掘问题。我们开发了一个(2 +ϵ)-近似算法,用于k-中心聚类问题,该算法在完全动态对抗模型下需要“小”的预期摊销成本。特别地,当输入中任意两点之间的最大距离和最小距离之比受到多项式限制时,预期摊销成本是多对数的,而k和ϵ是常数。我们还证明了我们的算法的运行时间在很大程度上集中在其期望值附近。我们的理论结果与来自Twitter、Flickr以及轨迹数据的动态数据的广泛实验评估相结合,证明了我们方法的有效性。我们还将我们的算法与[6]提出的滑动窗口模型下的相同问题的方法进行了评估。我们的实验评估显示,与[6]相比,我们的算法提供了具有较小最大半径的聚类解,尽管这是以稍微较差的平均运行时间和更多的空间为代价的。我们算法的另一个优点是它在完全对抗模型下是高效的,而[6]在滑动窗口模型下工作。本文的其余部分组织如下。我们在第2节讨论相关工作,第3节介绍了必要的定义和符号。在第4节中,我们介绍了我们的主要算法,而第5节提供了其理论分析。第6节包含了我们算法的实验评估。0Track:社交网络分析和Web上的图算法WWW 2018年4月23日至27日,法国里昂·5800针对真实数据的最先进方法进行了对比。最后,第7节包含了我们的结论和未来工作。02相关工作0近年来,从实际和理论的角度,对聚类算法的研究越来越多[1-3, 6, 8,11-13]。在[4]中首次提出了一种动态聚类算法,作者开发了一种8近似算法,仅适用于插入情况。后来,[14]基于[4]的结果开发了一种(2+ϵ)近似算法。在同一工作中,作者还研究了带有异常值的情况(其中输入中可以删除有限数量的点),并开发了一种(4+ϵ)近似算法。流模型中的聚类文献丰富多样。我们提到了[10]中的工作,其中作者给出了k-中位数的第一个单次常数近似算法,后来在[5]中进行了改进。与我们最相关的工作是[6],其中作者研究了滑动窗口模型下的k-中心聚类问题。他们开发了一种(6+ϵ)近似算法,需要O(k∙logδ0ϵ)时间更新(平均而言),其中δ是输入中任意两个点之间的最大距离和最小距离之比的上界。该算法需要O(k∙logδ0ϵ)空间。他们主要从理论角度研究了他们的算法。我们的工作之一是对[6]中的算法在真实数据上进行实验评估。注意,我们的算法需要O(N∙log(δ)0ϵ)空间,其中N是任意时间点上出现的点的最大数量的上界,而所提出的算法[6]需要O(k∙log(δ)0ϵ)空间。然而,在我们的情况下,可以在O(1)时间内测试簇成员资格,而给定点的同一簇C中的所有点可以在O(|C|)时间内产生。这是在监测传感器数据或随时间演变的轨迹时的一个吸引人的特性。我们算法的另一个优点是其近似保证,即2+ϵ的因子。注意,任何小于2的近似比率都意味着P=NP[9]。此外,正如[6]中证明的那样,任何近似比率小于4的算法都需要Ω(N^3)空间。表1总结了这两种算法的近似保证、平均运行时间、空间需求和查询时间。03符号和定义0我们研究k-中心聚类问题,其形式化定义如下。0定义3.1(k-中心聚类)。给定一组带有某个度量d的点集S和一个整数k>0。我们希望找到一组k个点(中心)C={c1,...,ck},以便最小化max x∈S d(x,C),其中d(x,C)=min c∈C d(x,c)。0观察到一组中心定义了S的一个划分(聚类)成k个集合。我们考虑以下对抗性计算模型。0对抗模型。我们假设对手首先固定一个(可能是可数无穷)操作序列O,其中对于每个t∈N,操作ot∈X×{−,+}由度量空间中的点xt∈X和一个指示标志(表示插入+或删除−)组成。通过自然地将度量空间扩展到X×N,我们可以假设最多只有一个点的副本被插入到序列中。我们还假设任何要删除的点都已经在之前被插入。算法事先不知道序列O。然而,我们假设算法使用的任何随机性都是在对手固定序列之后生成的。我们将这个对抗模型称为完全动态模型。04 算法0集合,并停止。否则,我们任意选择一个点 x i 从 X \ [ i − 1 j = 1 C j中,并创建一个以 x i 为中心,包含所有距离 x i 不超过 2 β 的点的集合 C i。可以证明,如果 β 等于最优解的值,那么这样的算法给出了一个2-近似解。这是因为如果已经形成了 k 个簇并且 X \ [ k j = 1 C j 不为空,那么存在 k+ 1 个点两两之间的距离大于 2 β ,这意味着半径不超过 β 的 k个簇无法形成,这与我们对 β 的假设矛盾。如果最优解的值未知,我们可以对 Γ = {(1 + ϵ ) i : d min � ( 1 + ϵ ) i � ( 1 + ϵ ) ∙ d max , i 2 N } 中的每个 β运行上述算法,其中 d max 和 d min 分别表示 X中任意两点之间的最大和最小距离。注意,如果 β太小,我们可能无法对所有点进行聚类,这可能导致一组未聚类的点 U 。使得 X的所有点都被划分(即 [ k j = 1 C j = X )的最小 β 给出了一个 ( 2 + ϵ )-近似解。可以从上述算法中得到一个简单(但效率低下)的增量算法。在任何时刻,对于 Γ 中的每个 β ,我们保持以下不变性。我们要么维护 k + 1 个点(其中 k个是中心),它们两两之间的距离大于 2 β ,要么维护所有点的一个最大半径为 2 β的聚类。前者保证了不存在最大半径为 β 的聚类。对于 Γ 中的每个 β,我们希望维护与上述讨论的算法计算出的相同的簇集。当插入一个新点 x时,我们按照以下步骤进行。对于 Γ 中的每个 β ,令 C 1 , . . . , C k , U分别为对应的簇,其中心为 c 1 , . . . , c k 。如果 x 距离 c i 不超过 2 β ,我们将 x插入到簇 C i 中。否则,如果没有这样的中心,我们将 x 插入到 U 中。这对于 Γ中的每个 β 重复,以确保不变性得以维持。这样的算法给出了一个 ( 2 + ϵ )-近似解,其平摊代价为 O ( k ∙ 10和 O (| X | ∙ 10d min )空间.0Track: 社交网络分析和网络图算法 WWW 2018,2018年4月23-27日,法国里昂FD�SW6 1 + �klog(�)klo5810近似平均运行时间空间模型 x 2 C ? 列出所有 y 使得 x , y 2 C0ϵ 完全动态 O ( 1 ) | C |0ϵ 滑动窗口 O ( k ) k ∙ N0表1:我们的算法(FD)和[6]中提出的算法(SW)的总结。0现在,假设点是均匀随机删除的。如果没有删除任何一个 k个中心点,那么不会违反不变性。否则,我们可能需要重新对所有点进行聚类以保持不变性。然而,删除任何这样一个点的概率是 k0n 而重新聚类的成本最多为 k ∙ n ,其中 n是点的数量。因此,这样的随机算法的期望平摊代价为 O ( k 2 ∙ 10d min )。不幸的是,如果删除不是随机的,这样的算法可能不是高效的。为了解决这个问题,我们给算法加上一些随机性,以便即使在存在对手删除的情况下,它也能高效运行。对于 Γ 中的每个 β,我们按照以下方式创建和维护一组聚类 C 1 ,...,C k :设 X是当前点集。首先,从 X 中均匀随机选择第一个中心 c 1,并构建一个聚类 C 1 ,就像前一个算法一样。对于 1 < i ≤ k ,从X \ [ i − 1 j = 1 C j 中均匀随机选择 c i 。当一个0当中心 c i 被删除时,我们只重新聚类 A = [ k j = i C j [ U,这最多需要 k ∙ | A | 次操作。注意,当选择 c i 作为中心时,A中的每个点都是可能的候选点。换句话说,选择 c i作为中心的概率与处理 c i 的删除成本成反比(乘以 k )。设 o 1,...,o m 是在算法执行之前由对手固定的一组更新操作,其中 o i= ( x , + ) 表示在第 i 步添加 x ,o i = ( x , -) 表示在第 i 步删除 x。考虑操作 o i = ( x , -) 。算法保持以下不变式:当执行 o i 时,x成为中心的概率与处理 c i的删除成本成反比。这表明预期的摊销成本在某种程度上受到限制。算法的预期摊销成本的分析是非平凡的,因为删除和插入可能会任意交织。需要更多的努力来证明摊销成本集中在其预期值附近。算法的理论分析在第 5 节中给出。算法的形式化描述以及伪代码在第4.1-4.4 节中给出。特别地,算法 1 和算法 2显示了处理删除的过程的伪代码。注意,每当删除一个中心时重新聚类所有点的变体可能不是高效的。特别地,对手可能能够强制某个点成为中心,然后重复删除和插入该点。每次这样的更新操作将导致总成本为 k ∙ n ,其中 n 是当前点的数量。04.1 动态聚类的数据结构0我们将用 d min 和 d max分别表示插入的任意两个点之间的最小距离和最大距离。我们允许更新操作的集合是可数无穷的,但是我们假设 d min 和 d max总是提供一个较低或等于最小距离和最大距离的值。0分别是任意两个点之间的最小和最大距离的上界。我们开始描述算法时假设 d min 和 dmax 是预先已知的,而在第 4.4 节中讨论更一般的情况。设 Γ = {( 1 + ϵ ) i : d min ≤ (1 + ϵ ) i ≤ d max , i ∈ N } ,并且记 γ = | Γ | = O ( 10d min ) 。对于 Γ 中的每个 β ,对于当前点集 X,我们维护一个数据结构 L β ,包括以下组件和不变性:• 一个列表S β = { c 1 , c 2 , . . . , c κ } ,其中 κ ≤ k ,对于所有 x , y ∈ S β, d ( x , y ) > 2 β 。• 一个不相交的聚类集合 C β = { C 1 , C 2 , . . ., C κ } ,对于所有 i ∈ [ κ ] ,对于所有 x ∈ C i , d ( x , c i ) ≤ 2 β。• 一个未聚类点集 U β = X \ ([ i ∈ [ κ ] C i ) ,对于所有 i ∈ [ κ ],对于所有 x ∈ U β , d ( c i , x ) > 2 β 。此外,我们要求 U , ;意味着 κ = k 。注意,我们可以使用 O (| X |) 的空间存储数据结构 Lβ ,对于 X 中的任何 x ,返回包含 x 的聚类并判断 x 是否是 S β中的中心都只需要 O ( 1 ) 的时间。04.2 任意插入0插入一个新点x很简单。对于Γ中的每个β,考虑数据结构Lβ = (Sβ,Cβ, Uβ),其中κ = |Sβ| = |Cβ|。首先检查是否存在Sβ中的ci使得d(x,ci) ≤2β。如果是这种情况,则将x插入到聚类Ci中。如果找不到这样的ci,并且κ < k,则设置cκ+1 := x和Cκ+1 :={x}。否则,如果没有这样的ci且κ = k,则将x插入到Uβ中。04.3 任意删除0维护Lβ以支持删除某个点x稍微复杂一些。简单情况是当x 2β,相应的半径≤2β的聚类,以及一组未聚类的点U。03: κ ← 004: 当U ≠ �,κ < k时执行以下操作05: κ ← κ + 106: 从U中均匀随机选择ck。07: Cκ ← {x ∈ U : d(x, cκ) ≤ 2β}08: U ← U ∪ Cκ09: 返回(S {c1, c2, ..., cκ}, C {C1, C2, ..., Cκ}, U)。如果U ≠�,则最优聚类半径大于β。0对于插入的前k个点,同时在算法的执行过程中更新它们。注意,每当dmin或dmax发生变化时,就需要计算缺失的Γ中每个β的Sβ,Cβ和Uβ。去除这样的假设使得算法在实践中更加高效,而不会影响对期望摊销成本的理论保证。我们将我们的算法称为FDC。在下一节中,我们将证明我们的算法在期望摊销成本上具有强大的理论保证,同时表明其摊销成本与其期望值接近的概率很高。05 摊销分析0我们分析数据结构Lβ的删除操作的预期摊销成本。在第5.1节中,我们对随机删除一个随机点的情况进行了预热分析。在第5.2节中,我们将分析任意插入和删除的情况。05.1 预热:随机删除0观察到只有当最多k个中心之一被移除时,删除操作才会昂贵。因此,我们很容易得到以下引理。0L����5.1.对于随机删除一个均匀随机点,算法1中的删除操作的预期成本为O(0P����。观察到当一个S β中的中心被移除时,成本为O(nk),其中n = | X|是当前存储在数据结构中的点的数量;否则,成本为O(1)。由于中心被移除的概率最多为k,因此成本为O(nk)。0由于n,预期成本为O(k^2)。 �05.2 任意插入和删除0对于t∈N,我们使用上标t来表示第t步结束时数据结构的状态。例如,我们使用X t来表示当前存储在数据结构中的点集。0用来表示当前存储在数据结构L β中的点集,我们令 n t := | X t |。0收费方案的直觉。数据结构Lβ上的每个插入操作对于Γ中的每个β都具有成本O(k)。然而,为了支付删除操作的成本,我们将为每个插入操作额外收取k^2的成本,作为未来删除操作的信用存储。当调用删除操作时,其成本将通过存储的一些信用(由F t表示)和可能的额外成本(由Zt表示)支付。观察到只有当Sβ中的一个中心被移除时,删除操作才是昂贵的。以下是F t 和Z t 的形式描述。0明确地。0收费方案的形式描述。我们详细描述我们的收费方案如下。假设在第t步,我们有以下操作之一:(1) 插入(L β,x)。在插入的点x上存储k^2的信用。在这种情况下,定义Z t = F t =0。(2) 删除(L β,x)。如果要删除的点x不是其中一个中心,则成本为O(1),我们设置Z t= F t =0。否则,假设要删除的点x是当前κ个中心中的中心ci。那么,在这种情况下,重建成本为O(k∙|bX|),其中bX = (([j ≥ i Cj) [U β) \{x}是需要重新聚类的点。我们的收费方案为每个点u∈bX支付k的成本。具体来说,我们将重新聚类成本k∙|bX| = F t + Z t分解如下,并分别分析F t 和Z t。(a) 定义X new ={u∈bX:当选择ci作为中心时,点u尚未插入}。定义F t = k∙|Xnew|。在这种情况下,对于每个u∈Xnew,我们将使用u上存储的k个信用来支付成本;因此,这个成本不会对Z t 有贡献。我们将在引理5.2中证明,我们始终在X new中的点上存储足够的信用来以这种方式支付。(b) 定义X old ={u∈bX:当选择ci作为中心时,点u已经插入}。定义Z t = k∙|Xold|。因此,对于每个这样的点u∈X old,我们将产生一个对Z t有贡献的成本k。观察到这样的点u在其插入后可以多次重新聚类。除了可以在情况2(a)中支付的初始次数外,对于每个后续的某个步骤τ中的重新聚类,其重新聚类成本将计入相应的Z τ。0跟踪:社交网络分析和Web上的图算法 WWW 2018,2018年4月23日至27日,法国里昂5830L���� 5.2 (C������ ���R �����������N �� P�����).固定t∈N。假设at是从开始到(包括)第t步的插入次数。那么,以概率1,我们有Õtτ=1Fτ≤at∙k^2。0P����.观察到t∙k^2是在第t步之前插入的点所接收的总学分数。为了证明所需的不等式,只需证明存储在每个插入点u中的k^2个学分足以支付其在充电方案的2(a)情况下的重新聚类成本。假设在插入u时,中心点为{c01,c02,...,c0k},聚类为{C01,...,C0k}以及未聚类集合U0。假设r∈[k]是满足u∈(j≥rC0j)[U0的最大索引。然后,只有在某些后续步骤中删除W:={c01,...,c0r}中的点时,存储在u中的学分才会被消耗。由于W中最多有k个这样的中心点,并且每当从W中删除这样一个中心时,从u中消耗k个学分,我们可以得出结论,存储在u中的k^2个学分足够。这完成了引理的证明。�0对于每个t∈N,我们还写Zt:=Õki=1Zti,其中Zti是删除中心ci(在第t步开始时)时产生的额外成本。观察到对于固定的t,最多只有一个i∈[k]使得Zti非零。0L���� 5.3 (B�������E ����������). 对于每个t∈N,E[Zt]≤k^2。0P����.回想一下Zt:=Õki=1Zti,其中Zti是删除中心ci时产生的额外成本。因此,只需证明E[Zti]≤k。观察到ci是一个随机对象。观察到中心ci是在某次调用算法2的第6行中选择的。我们使用Ui来表示在选择ci时第6行中的U。同样,观察到Ui是一个随机对象。我们接下来使用第6行中使用的随机性来分析E[Zti|Ui]。观察到当要删除的点是ci时,只有U中的点对Zti有贡献。然而,Ui中的一些点可能已经在t时刻之前被删除。让bU∈U表示在第t步开始时仍然存在的点。因此,只有当在第6行中选择的点xt∈bU时,Zti才非零,这发生的概率最多为1/|bU|(在Ui上条件概率)。0因此,可以得出E[Zti|Ui]≤1|bU|∙k∙|bU|=k。0此时,我们想提醒读者,Zt只计算描述中情况2(b)中的重新聚类成本。对于在ci被选择为中心之后插入的点,它们的重新聚类成本使用存储在它们自身中的学分支付,就像充电方案的2(a)情况一样。对随机变量E[Zti|Ui]取期望得到E[Zti]≤k,如所需。�0T������5.4.对于任何ϵ>0,对于任何T个N个插入/删除操作的序列,F����D��C����算法维护了k-cent的一个(2+ϵ)近似解,同时需要O(logδ的时间。0ϵ∙k^2T)的期望时间和O(logδ)的期望时间。0ϵ∙|N|)空间下的0完全动态模型,其中N:=maxt∈[T]|Xt|。可以在O(1)的时间内测试聚类成员资格,而在输出给定点所在聚类C中的所有点时需要O(k+|C|)的时间。0P����.算法始终保持第4.1节讨论的所有不变量。因此,聚类Cβ,其中β是最小的使得Uβ为空集的值,给出了一个(2+ϵ)近似解。对于Γ中的任何给定β,Lβ中的删除操作的总成本是ÕTt=1O(Ft+Xt)。引理5.2和5.3表明其期望最多为O(k^2T)。通过回顾有|Γ|=O(logδ的证明,我们得出结论。0ϵ) β的值。�0高概率陈述。引理5.3意味着对于数据结构上的任何T个插入/删除操作序列,期望代价为O(k^2T)。我们接下来证明,高概率下,代价也是O(k^2T)。正如在引理5.3的证明中所看到的,我们的分析基于Algorithm2的第6行中使用的随机性。假设N是数据结构在任何时间点存储的点的上界。对于n ≤N,考虑随机变量ζ n,它以概率1取值为n0n以概率1 - 1取值为00n。与著名的Cherno�界的证明类似,我们分析ζn的矩生成函数以证明测度集中结果。0L����5.5 (M�����G ���������F ������� �� ζ)。对于n ≤ N和0 ≤ θ ≤ 10N,E [e θζ n] ≤ e θ + 304 ∙ θ 2N。0P����。对于0 ≤ θ ≤ 10N,我们有0E [e θζ n] = (1 - 10n) + 0n ∙ e θn (1)0≤ exp(e θn 0n) (2)0≤ e θ + 30对于4 ∙ θ 2 n (3)0≤ e θ + 30对于4 ∙ θ 2 N,(4)0其中(2)来自于1 + x ≤ e x,(3)来自于不等式e x ≤ 1 + x + 30对于0 ≤ x ≤ 1,有4 ∙ x 2。�0L����5.6。假设N是数据结构Lβ在任何时间点存储0对于任意的0 ≤ θ ≤ 10对于kN和T ∈ N,我们有E [e θ Õ t 2[T] Z t i]≤0e T (θk + 304 ∙ θ 2k^2N)。0P����。我们通过对T进行归纳来证明该陈述。基本情况T =0是显然成立的。接下来考虑步骤T + 1。设F是由随机变量(Z t i:t 2[T])和指示变量(I t j:j 2 [k],t 2 [T])生成的sigma代数,其中I t j =1表示在步骤t中选择了一个新的中心cj。我们接下来定义一个随机对象U T + 1。在步骤T +1开始时,考虑中心c i及其在某个先前步骤中被选择的时刻。观察到ci是在Algorithm 2的第6行中的某次调用中被选择的。将U T +1定义为那个时刻第6行中的U。观察到在c i被选为中心到步骤T +1开始之间的时间内,U T + 1中的一些点可能会被删除。将bU定义为在步骤T + 1开始时仍然存在的点集U T + 1。0Track: Social Network Analysis and Graph Algorithms for the Web WWW 2018, April 23-27, 2018, Lyon, France6.1Datasets5840类似于引理5.3的证明,我们证明在给定历史(F和U T +1)的条件下,随机变量Z T + 1 i在k ∙ ζ | b U|的支配下是随机的;注意,如果这个事件是平凡的,那么它显然成0(T + 1)次操作是插入,因为在这种情况下Z T + 1 i等于0。我们接下来论证当(T +1)次操作是删除时,这也是正确的。观察到在给定历史F和U T +1的条件下,我们确切地知道当前中心c i 是在哪一步被选择的,即最大的i ≤ t,使得I t i= 1。因此,在给定F和U T + 1的条件下,当前中心c i 是b U中的一个均匀随机点。因此,可以得出结论,中心c i 在步骤T +1中被删除的概率至多为10b U ,这会产生一个代价为 k ∙ | b U | 的代价0发生。因此,在给定F和U T + 1的条件下,Z T + 1 i在k ∙ ζ | b U|的支配下是随机的,如所需。因此,根据引理5.5,04∙θ^2k^2N。最后,通过考虑以下条件期望完成归纳步骤:0E[e^θÕt∈[T+1]Zti|F,UT+1]=e^θÕt∈[T]Zti∙E[e^θZT+1i|F,UT+1]。0≤e^θÕt∈[T]Zti∙e^θk+3。04∙θ^2k^2N。0然后,取期望并使用归纳假设完成归纳证明。�。0L5.7.假设N是数据结构Lβ在任何时间存储的点的上界,并且对于任何0对于任意λ≥2,Pr[Õt∈[T]Zti≥λkT]≤e^(-Ω(λT))。0N)。0P[...]。使用矩母函数的标准方法,如切尔诺界的证明中所述,我们选择θ=1。0kN,(7)。0Pr[0t∈[T]Zti≥λkT]=Pr[e^θÕt∈[T]Zti≥e^θλkT] (5)。0≤E[e^θÕt∈[T]Zti]∙e^(-θλkT) (6)。0≤e^-(λ-7)。0N,(7)。0其中(6)由马尔可夫不等式得出,(7)由引理5.6和选择θ=1得出。0kN。�。0以下定理由定理5.4和引理5.7得出。0T5.8.对于任何ϵ>0,对于任何序列T∈N的插入/删除操作,FDC算法对k-center问题维护了一个(2+ϵ)近似解。此外,总时间超过Ω(logδ)的概率最多为logδ。0ϵ∙λk^2T)0,对于任何λ≥2,全动态的ϵ∙N)空间0ϵ∙ke−Ω(λT)。0N),对于任何λ≥2,在完全动态的ϵ∙N)空间下0模型。该算法的时间复杂度为O(logδ)。06实验。0随机变量Z被随机变量Y随机支配,如果对于所有实数x,Pr[Z≥x]≤Pr[Y≥x]。06.1数据集。0我们的所有实验都是在一台配备两个Intel(R) Xeon(R) CPU E5-2660v3,主频为2.60GHz,内存为250GB的机器上进行的。我们使用的Twitter数据集以及我们用C语言实现的算法已经公开可用。由于隐私问题,我们仅保留每个推文的时间戳和GPS坐标。我们在广泛范围的k、ϵ和滑动窗口W的值下评估算法。在所有实验中,默认值为k=20和ϵ=0.1,除非另有说明。对于我们的随机算法,每个结果是十次运行的平均值,除非另有说明。0我们考虑一些公开可用的数据集,以及我们从Twitter收集的数据集。Twitter。我们通过TwitterAPI收集了带有地理标记的推文。我们能够在2017年9月9日至2017年10月20日期间收集到2100万条推文。每个推文都与GPS坐标(如经度和纬度)以及时间戳相关联。Flickr。雅虎Flickr创意共享100百万(YFCC100m)数据集是一个包含2011年至2015年之间在Flickr上发布的1亿张图片的元数据数据集。每张图片都与GPS坐标和时间戳相关联。我们使用了具有有效时间戳和GPS坐标的4700万张图片的元数据。轨迹。该数据集包含葡萄牙波尔图市的442辆出租车行驶的轨迹。每个轨迹由一组二维点组成,每个点都与时间戳相关联。轨迹每15秒更新一次,大多数轨迹最多包含500个点。该数据集总共包含8300万个二维点,共计8300万个更新。表2总结了我们在实验评估中考虑的数据集的统计信息。06.2 距离度量0根据手头的数据集,我们考虑不同的距离度量。对于Twitter和Flickr,我们计算两个GPS坐标之间的大圆距离[15]。对于轨迹,我们使用对称Hausdor�距离[16],其定义如下。设P和Q是欧几里得空间中的两组点。H(P,Q):= max p∈P min q∈Qd(p,q),其中d是欧几里得距离。0轨迹P和Q之间的对称Hausdor�距离定义为b H(P,Q) = max(H(P,Q),H(Q,P))。我们实验中考虑的所有距离度量都是度量。06.3 动态计算模型0对于Twitter和Filckr,我们在滑动窗口模型下评估算法[6,7]。在这种情况下,如果一个点在时间t被插入,它将在时间t +W被移除,其中W是滑动窗口的持续时间。02 https://github.com/fe6Bc5R4JvLkFkSeExHM/k-center 3http://yfcc100m.appspot.com/ 4https://archive.ics.uci.edu/ml/datasets/Taxi+Service+Trajectory+-+Prediction+Challenge,+ECML+PKDD+20150Track: Social Network Analysis and Graph Algorithms for the Web WWW 2018, April 23-27, 2018, Lyon, FranceWe evaluate the algorithms under a wide range of values for k,�and the length of the sliding window W . In all experiments thedefault values are k = 20, eps = 0.1. For Twitter, the length of thesliding window is two hours, while for Flickr it is six hours. Boththose values result in a sliding window containing 60K points.We start by evaluating the accuracy of the two algorithms. Inparticular, we measure the ratio between the maximum radius ofthe clustering produced by each algorithm and a lower bound onthe optimum radius. At any point in time, we compute such a lowerbound as follows. Let � be largest such that the set U� computed byour algorithm is not the empty set. Our lower bound is computedas half the minimum pairwise distance between the k + 1 points(cluster centers) in S�. We observe that in practice it is importantto have small maximum radius, in that, this might lead to more“meaningful” clusters.Figure 1 (left) measures the approximation ratio as a functionof k, while Figure 1 (right) measures the approximation ratio as afunction of � in Twitter. For any given value of k and � we reportthe median, the rst and third quartiles, as well as maximum andminimum approximation ratio obtained by the algorithm whenexecuted on the whole dataset. The two algorithms have beentested for the same value of k and �, however, some additional spacebetween the corresponding values in the plot has been introducedto improve the presentation.We can observe that our algorithm (FD) consistently deliversbetter approximation ratio then the algorithm presented in [6] (SW).In particular, we can observe
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功