摘要：在流式傳輸過程中下抑堡，作者提供了一種算法瀑构，這種方法對聚類查詢有更快的響應(yīng)速度普舆，即該方法能更快的查找到聚類中心帐萎。算法提出了一種新穎的思想—“coreset cache”（核心集緩存），它按一定規(guī)則重用了核心集來回答最新的聚類查詢敞曹。
針對的是查詢數(shù)據(jù)集中的聚類中心
一账月、引言
很多時候，待分析的數(shù)據(jù)不是全都已經(jīng)獲得了澳迫，而是源源不斷地到來局齿，甚至可能沒有盡頭，這叫做流數(shù)據(jù)纲刀，而流式k-means聚類與傳統(tǒng)k-means自然也就有了許多不同，首先担平，它就需要一種算法來保存足夠的狀態(tài)信息示绊，在更多的數(shù)據(jù)到來時，能夠增量地更新各個簇暂论；其次面褐，當(dāng)提出新的查詢時，算法需要返回當(dāng)前所有數(shù)據(jù)的k個聚類中心取胎。
-
過去的算法：已獲得的數(shù)據(jù)流S被分為了多個塊S1,S2,......每個塊被壓縮緊了一個核心集展哭，多個核心集又被遞歸地合并成了高層次的coreset tree（核心集樹）。
這種算法的效率與需要被合并的核心集數(shù)量成比例闻蛀，因而匪傍，在核心集數(shù)量巨大時，查詢時間也會變得很高觉痛。當(dāng)查詢到來時役衡，內(nèi)存中所有活動的核心集會被合并到一起，然后在這個合并的數(shù)據(jù)集中應(yīng)用聚類算法比如k-means++薪棒，最后輸出k個聚類中心手蝎。
-
論文的貢獻：提出了三種算法CC榕莺、RCC、OnlineCC棵介，這些算法的精髓就是coreset caching钉鸯，它的工作原理是重用在以前的查詢中計算過的coreset，以加速對當(dāng)前查詢的coreset的計算邮辽。即利用一種聚類數(shù)據(jù)結(jié)構(gòu)來更好地存儲流式數(shù)據(jù)唠雕，以使得在需要用到這些數(shù)據(jù)時，能提供低延時的響應(yīng)逆巍。
當(dāng)查詢到達時及塘，該算法不需要將當(dāng)前內(nèi)存中所有的coreset合并起來，只需要把最近那次查詢的coreset(存儲在coreset cache中)和那次查詢之后到達的點的coresets合并起來锐极。也就是合并coreset cache的核心集和增量窗口的核心集們笙僚。
（1）最簡單的算法：CC(Cached Coreset Tree）
（2）遞歸地應(yīng)用CC：RCC（Recursive Cached Coreset Tree）
（3）結(jié)合CC和順序流的思想：OnlineCC 現(xiàn)有流聚類算法：Sequential k-means、BIRCH灵再、CluStream肋层、STREAMLS
二、Preliminaries and Notation
- k-meas聚類：把每個點x歸到k個簇中去翎迁，w(x)權(quán)值函數(shù)實現(xiàn)的是把d維的點x映射為一個整數(shù)栋猖，以和歐氏距離做計算
- k-means++：不是隨機選擇種子點（seeds），而是通過一定的算法來選擇初始種子點汪榔。
見https://www.cnblogs.com/shelocks/archive/2012/12/20/2826787.html -
k-means Coreset：coreset的變體蒲拉，適合實現(xiàn)k-means算法。公式意為在容忍一定的錯誤率的情況下痴腌，在核心集上進行k-means計算可替代在原巨大的數(shù)據(jù)集P上的計算雌团。
符號 coreset(k, ε, P) 表示k-means coreset。
三士聪、 流聚類和核心集樹
- 作者為了解釋論文中的算法是怎么樣實現(xiàn)的锦援，特地描述了一個適用于各種流聚類算法的驅(qū)動算法，也介紹了過去的CT（Corset Tree）算法剥悟，從而用其來演示驅(qū)動算法是怎么工作的灵寺，即，怎么往驅(qū)動算法中套入各種流聚類算法区岗。
-
Driver Algorithm（驅(qū)動算法）
驅(qū)動算法由一個聚類數(shù)據(jù)結(jié)構(gòu)D的特定實現(xiàn)和到來的數(shù)據(jù)大小m初始化略板，這兩種數(shù)據(jù)都存儲在對象 H 中。算法把到來的數(shù)據(jù)點分成每組大小為m的batches慈缔，并將之插入聚類數(shù)據(jù)結(jié)構(gòu)中蚯根。H 中存有額外信息，如 H.C 和 H.n ，前者表示當(dāng)前的batch（最大可存m個數(shù)據(jù)點颅拦，超過則需要重新建一個H.C）蒂誉，后者表示目前為止所接受到的點的數(shù)量。
而論文中所提及的各種算法距帅，如CT右锨、CC、RCC碌秸、OnlineCC等都是對數(shù)據(jù)結(jié)構(gòu)D的實現(xiàn)绍移。
-
CT（r路合并核心集樹）
（1）CT是核心集樹，由于沒用到緩存讥电，所以每次合并Coreset的時候蹂窖，需要從內(nèi)存中搜索全部coreset，極其耗時恩敌。
（2） 桶(bucket)：用來存儲數(shù)據(jù)流中的數(shù)據(jù)點（對象）瞬测，有一個參數(shù)m，表示每個桶至多能存儲m個數(shù)據(jù)對象纠炮。coreset是我們定義的數(shù)據(jù)結(jié)構(gòu)月趟，而對應(yīng)到存儲層面，用桶來表示它恢口，也就是說孝宗，每個桶中的數(shù)據(jù)對象，可求得一個核心集耕肩。核心集樹在多層維護桶因妇，所以桶是分級的。
① level = 0的桶稱為基桶（base bucket）猿诸，新到達的數(shù)據(jù)都是存儲在基桶中的婚被；
② 一旦基桶的數(shù)據(jù)已=m，則新建一個基桶两芳，并比較該層的基桶數(shù)目是否已經(jīng) > r摔寨，若是去枷，則需要將基桶合并怖辆，得到 level = 1的桶；
③ level = l的桶由r^l個基桶的信息合并而來删顶。當(dāng)level = 3竖螃，r = 2 時，表示該層的bucket由23 = 8個基桶的信息合并而來（合并桶的方法是求coreset）逗余，即統(tǒng)計了8個基桶中的數(shù)據(jù) ==> 即8*m個數(shù)據(jù)點的總結(jié) ==> 即該桶對應(yīng)的coreset總結(jié)了數(shù)據(jù)流中8*m個數(shù)據(jù)點的信息特咆。
四、三個快速的流聚類算法
- CC（Coreset Tree with Caching）
使用了coreset caching來加速查詢過程，方法是重用之前的查詢中已經(jīng)構(gòu)建好的核心集腻格。
coreset cache 中存有舊核心集的子集画拾。
-
當(dāng)需要回答新的查詢時，CC避免了從CT多層次合并核心集的開銷菜职，而是只需要檢索核心集樹中的一小部分額外的核心集即可青抛。
細節(jié)：
（1）每個緩存的核心集都是基桶1~基桶u的summary，u表示核心集的右端點酬核，區(qū)間[1,u]則稱作桶的“span”蜜另。
（2）哪些核心集會被緩存呢？
①. 整數(shù)分解嫡意。將n個batches到來后举瑰，將n進行如圖所示的整數(shù)分解，其中蔬螟，αi是遞增的此迅，即將n表示為以r為底的遞增次冪的項之和
② 將公式的第一項，即i=0時的值賦給變量minor(n,r)促煮，剩下的值賦給變量major(n,r) 邮屁， 即 major(n,r) = n - minor(n,r)
③ 又有n_k_如下圖，相當(dāng)于是把分解后的n的最小的k項刪除后得到 n_k_菠齿，即n分解后的后面 j-k 項
④ 變量 prefixsum(n,r)表示所有 n_k_ 的集合佑吝，如圖，則prefixsum(n,r)由 n_1,n_2,......,n_j 組成- 可知一定有 major(n,r) ∈ prefixsum(n,r) Ｉ取Ｓ蠓蕖！＜部谩８旮帧！
例如是尔， n = 47 殉了，r = 3. 則47 =1·33+2·32+2·30，于是有 minor(47, 3) = 2, major(47, 3) = 45拟枚，而 prefixsum(47, 3) = {27, 45}.
⑤ 若某個 coreset 的右端點 u ∈ prefixsum(n,r) 中薪铜，則CC緩存這個coreset。
（3）當(dāng)查詢來臨恩溅，此時已收到N個batch隔箍，則CC的任務(wù)就是計算一個coreset，其 span=[1,N]脚乡。
①. CC會首先令 N1 = major(N,r) 蜒滩，然后將 [1, N] 劃分為 [1, N1]∪[N1+1, N] , 因為 major(N,r) ∈ prefixsum(N,r)，所以[1, N1]一定已經(jīng)在cache中了，因而此后只需要去核心集樹中檢索[N1+1, N]即可俯艰。
② . CC的工作算法如圖捡遍，表示的是當(dāng)Batch N到達之后，CT 和 CC 各自是什么樣子竹握，以及若是此時有新查詢到來稽莉，CT算法和CC算法各會合并哪些coreset。CC示意圖以N=4和N=7為例涩搓。
（1）. 當(dāng) N = 4 時污秆，有4 = 0·20 + 0·21 + 1·22 ==> premixsum = {n_2} = {4} ==> 只有[ 1,4 ]在cache中（以前舊的coreset需要被清除掉）==> 回應(yīng)查詢時直接回[1,4]即可
（2）. 當(dāng) N = 7 時， 有7 = 1·20 + 1·21 + 1·2^2 ==> premixsum = {n_1, n_2} = {6, 4} ==> [1,4] 和 [1, 6]在cache中（舊的coreset [1,4]不用被清除掉） ==> 回應(yīng)查詢時昧甘，需要合并 [1, 6] 和 [7, 7]
- RCC: Recursive Coreset Cache
- CC存在問題良拼，層次太多，時間開銷仍會增加充边。
- 用遞歸的方式來實現(xiàn)核心集緩存的思想庸推，使得coreset的層次少一點，同時運行時間小浇冰。
- 在CT的單層中也使用CC的思想贬媒，則在查詢的時候，甚至不用再合并r個coreset肘习。
- 提高合并coreset的合并度际乘，從而減少層數(shù)；而每層都有許多個未合并的coreset漂佩，因此為他們又單獨遞歸地建立了CT和CC脖含。
實現(xiàn)：
（1） 數(shù)據(jù)結(jié)構(gòu)RCC的定義：每個RCC(i)由以下幾部分組成
① cache(i)，
② RCC(i)的每一層又由兩個數(shù)據(jù)結(jié)構(gòu)組成投蝉，其一是一個列表List_l养葵，表示 l 這一層的桶集；其二就是RCC_l, 存儲的是RCC(i-1)第 l 層信息瘩缆。
- Online Coreset Cache: a Hybrid of CC and Sequential k-means
- 流聚類由兩個組件構(gòu)成关拒，其一是構(gòu)建的coreset以減小數(shù)據(jù)量，其二是聚類算法庸娱。CC和RCC都在討論怎樣通過減少查詢時需要合并的coreset數(shù)量來減少第一個組件的運行時間着绊。
- 就流聚類問題而言，CC和RCC都還需要支付聚類的時間開銷涌韩，因而需要減少這部分的運行時間畔柔。
- OnlineCC 大多數(shù)情況下運行一個更簡單的算法（計算開銷僅O(1)）來實現(xiàn)聚類以回答查詢氯夷，只偶爾運行 k-means++臣樱。
- OnlineCC 結(jié)合了CC和在線k-means算法，在保證聚類質(zhì)量的前提下更快地找出聚類中心。前者由CC保證雇毫，后者由在線k-means算法保證玄捕。
- 維護了一個評估系統(tǒng)，以適時地回到k-means++算法棚放。
實現(xiàn)：
（1） 當(dāng)數(shù)據(jù)到來時枚粘，算法會將數(shù)據(jù)點存入coreset，并直接利用在線k-means更新聚類中心飘蚯，因而在查詢的時候可以在O(1)的時間內(nèi)回答出聚類中心馍迄；
（2） cost0表示CC+普通k-means++的聚類花銷，EstCost表示對當(dāng)前聚類中心集C進行更新所需聚類花銷的評估局骤，alpha > 1表示其評估系數(shù)攀圈。
（3） 當(dāng)查詢來臨，若此時的EstCost比alpha·cost0還高峦甩，則算法回退至CC+普通k-means++赘来，需要重新計算coreset，然后實現(xiàn)組件一和組件二凯傲。否則直接回答當(dāng)前的聚類中心集C即可犬辰。
OnlineCC示意圖
