數(shù)據(jù)摘要的常見方法
在許多計(jì)算設(shè)置中，相同信息的超載是一個(gè)需要關(guān)注的問題。例如，跟蹤其網(wǎng)絡(luò)應(yīng)用以識(shí)別整個(gè)網(wǎng)絡(luò)的健康狀況以及現(xiàn)場(chǎng)異?；蛐袨樽兓Ｈ欢?，事件發(fā)生的規(guī)模是巨大的，每個(gè)網(wǎng)絡(luò)元素每小時(shí)可能會(huì)發(fā)生數(shù)以萬計(jì)的網(wǎng)絡(luò)事件。雖然技術(shù)上允許監(jiān)控事件的規(guī)模和粒度在某個(gè)數(shù)量級(jí)內(nèi)的增加，但是，處理器、內(nèi)存和磁盤理解這些事件的能力幾乎沒有增加。即使規(guī)模很小，信息量也可能過大，無法方便地放在存儲(chǔ)中。
為了應(yīng)對(duì)這一挑戰(zhàn)，流數(shù)據(jù)處理模型變得越來越流行。其目的不再是捕獲、存儲(chǔ)和索引每一事件，而是快速處理每一個(gè)觀察結(jié)果，以便創(chuàng)建當(dāng)前狀態(tài)的摘要。處理完成后，事件被刪除，不再可訪問。這樣的處理意味著另一種權(quán)衡: 對(duì)世界的描述是近似的而不是精確的，而且需要回答的問題性質(zhì)必須事先決定，因此有些問題是無法解決的。然而，用適度的資源以極快的速度處理大量數(shù)據(jù)的能力，可以突破數(shù)據(jù)量的限制。因此，流處理技術(shù)已經(jīng)在許多領(lǐng)域得到應(yīng)用，從電信擴(kuò)展到搜索引擎、社交網(wǎng)絡(luò)、金融以及時(shí)間序列分析領(lǐng)域（例如IoT領(lǐng)域）。數(shù)據(jù)摘要的方法是更具成本效益，涉及到算法技巧、系統(tǒng)知識(shí)和數(shù)學(xué)洞察力的混合。
具體的方法可能有哪些呢？
抽樣
當(dāng)面對(duì)大量需要處理的相同信息時(shí)，可能有一種強(qiáng)烈的誘惑，就是完全忽略它。一個(gè)稍微有點(diǎn)原則的方法就是忽略大部分，也就是從整個(gè)數(shù)據(jù)集中選取少量的樣本，在這個(gè)子集上執(zhí)行計(jì)算，然后嘗試外推到整個(gè)數(shù)據(jù)集。為了給出一個(gè)好的估計(jì)，抽樣必須是隨機(jī)的。
抽樣方式有很多種，最基本的方式是均勻隨機(jī)抽樣。對(duì)于大量的數(shù)據(jù)記錄，隨機(jī)選擇少量記錄作為樣本。然后根據(jù)樣本回答各種問題， 例如，估計(jì)什么比例的客戶在一個(gè)特定的城市或購買了一個(gè)特定的產(chǎn)品。
那么，樣本應(yīng)該有多大才能提供好的結(jié)論呢？根據(jù)標(biāo)準(zhǔn)的統(tǒng)計(jì)結(jié)果，對(duì)于像客戶記錄中的抽樣問題，s 大小的樣本的標(biāo)準(zhǔn)誤差與1/s 成正比。粗略地說，這意味著在從樣本中估計(jì)一個(gè)比例時(shí)，誤差應(yīng)該看起來像 ± 1/s。因此，觀察一個(gè)1000個(gè)用戶投票的一個(gè)意見調(diào)查，其誤差大約為3% ，即真實(shí)的答案在樣本結(jié)果的3% 之內(nèi)，增加樣本數(shù)量會(huì)使錯(cuò)誤以一種可以預(yù)測(cè)的方式減少，如果將調(diào)查的誤差降低到0.3% 需要聯(lián)系100,000個(gè)用戶。
其次，如何抽取樣本？簡單地獲取第一個(gè) s 記錄并不能保證是隨機(jī)的，所以需要確保每個(gè)記錄都有同樣的機(jī)會(huì)被包含在樣本中。這可以通過使用標(biāo)準(zhǔn)的隨機(jī)數(shù)生成器來選擇要包含在樣本中的記錄。一個(gè)常見的技巧是給每個(gè)記錄附加一個(gè)隨機(jī)數(shù)，然后根據(jù)這個(gè)隨機(jī)標(biāo)記對(duì)數(shù)據(jù)進(jìn)行排序，并按照排序順序獲取第一個(gè) s 記錄。只要對(duì)整個(gè)數(shù)據(jù)集進(jìn)行排序不會(huì)花費(fèi)太多的成本，這種方法就可以很好地工作。
最后，當(dāng)增加新數(shù)據(jù)時(shí)，如何維護(hù)樣本呢？一個(gè)簡單的方法是，對(duì)于 p 的某個(gè)選擇值，以概率 p 來挑選每條記錄。當(dāng)一個(gè)新的記錄出現(xiàn)時(shí)，在0和1之間隨機(jī)選擇一個(gè)分?jǐn)?shù)，如果它小于 p，將記錄放入樣本中。這種方法的問題在于，我們事先并不知道 p 應(yīng)該是什么。在以前的分析中，需要一個(gè)固定的樣本大小 s，并且使用固定的抽樣率 p。這意味著最初的元素太少，而隨著記錄的增加又會(huì)使元素太多。這個(gè)問題就像是一個(gè)算法難題，事實(shí)上這是多年來技術(shù)面試中常見的問題。一個(gè)解決方案是隨著新記錄的到來，遞增地調(diào)整 p。維護(hù)抽樣的一種簡單而優(yōu)雅的方法是采用隨機(jī)標(biāo)記的思想。向每個(gè)記錄附加一個(gè)隨機(jī)標(biāo)記，并將樣本定義為具有最小標(biāo)記值的 s 記錄。當(dāng)新記錄到達(dá)時(shí)，標(biāo)記值決定是否將新記錄添加到樣本中，并刪除舊記錄以保持樣本大小固定在 s。
抽樣方法是如此普遍，應(yīng)用的示例很多，一個(gè)簡單的例子是在數(shù)據(jù)庫系統(tǒng)中，為了進(jìn)行查詢規(guī)劃，通常需要保存一個(gè)大型關(guān)系的樣本。在決定如何執(zhí)行查詢時(shí)，評(píng)估不同的策略可以估計(jì)每個(gè)步驟中可能發(fā)生的數(shù)據(jù)縮減量。另一個(gè)例子來自數(shù)據(jù)集成和鏈接領(lǐng)域，其中的一個(gè)子問題是測(cè)試來自不同表的兩列是否可以與同一組實(shí)體相關(guān)。全面比較各個(gè)列可能會(huì)耗費(fèi)時(shí)間，特別是在希望測(cè)試所有列對(duì)的兼容性時(shí)，比較小的樣本通常足以確定列是否有任何機(jī)會(huì)與相同的實(shí)體相關(guān)。
抽樣方法如此簡單而通用，那為什么還需要其他方法來總結(jié)數(shù)據(jù)呢？事實(shí)證明，抽樣并不能適用于某些問題。任何需要詳細(xì)了解數(shù)據(jù)中各個(gè)記錄的問題都不能通過抽樣方法來解決。這樣的問題最終需要記錄所有的信息，并且可以通過高度緊湊的編碼來解決。一個(gè)更復(fù)雜的例子是當(dāng)問題涉及到確定數(shù)量基數(shù)的時(shí)候，在具有許多不同值的數(shù)據(jù)集中，某種類型的不同值有多少？例如，在一個(gè)特定的客戶數(shù)據(jù)集中有多少個(gè)不同的姓氏？使用一個(gè)樣本基并不能揭示這個(gè)信息。最后，一些樣本可以估計(jì)的數(shù)量，但是對(duì)于這些數(shù)量，還有更好的摘要方法。
對(duì)于諸如估計(jì)一個(gè)特定屬性(如居住城市)的頻率問題，可以建立一個(gè) s 大小的樣本集，保證的誤差是1/s。這是相當(dāng)強(qiáng)大的采樣保證，只有提高了我們投入更多的空間，草圖。本文后面描述的 Count-Min 示意圖具有此屬性。其中一個(gè)限制是，必須在設(shè)置草圖之前指定感興趣的屬性，而示例允許您評(píng)估查詢中所采樣項(xiàng)目的任何記錄屬性。假設(shè)在100萬個(gè)記錄中的1000個(gè)樣本中，只有900個(gè)姓氏出現(xiàn)在抽樣的名字中。關(guān)于這些名字在其他數(shù)據(jù)集中的流行程度，您能得出什么結(jié)論？完整數(shù)據(jù)集中的幾乎所有其他名稱也都是唯一的?；蛘撸纠械拿總€(gè)唯一名稱在剩余的數(shù)據(jù)中重復(fù)出現(xiàn)數(shù)十次或數(shù)百次。由于樣本信息的存在，這兩種情況無法區(qū)分，導(dǎo)致了這兩種統(tǒng)計(jì)方法的巨大置信區(qū)間。跟蹤有關(guān)基數(shù)的信息，并省略重復(fù)的信息，可以通過諸如 HyperLogLog 之類的技術(shù)進(jìn)行處理，稍后將進(jìn)行處理。
布隆過濾器
布隆過濾器是一種緊湊的數(shù)據(jù)結(jié)構(gòu)，可以作為一組數(shù)據(jù)項(xiàng)的摘要。任何計(jì)算機(jī)科學(xué)的數(shù)據(jù)結(jié)構(gòu)類型都有“字典”，例如數(shù)組、鏈表、哈希表和許多平衡樹及其變體。這些結(jié)構(gòu)的共同特點(diǎn)是，都可以回答某個(gè)項(xiàng)目是否存儲(chǔ)在結(jié)構(gòu)中。布隆過濾器也可以回答這樣的成員資格問題，而且空間利用率更高。
為了理解這個(gè)過濾器，考慮一個(gè)簡單成員問題的精確解是有幫助的。假設(shè)希望跟蹤一百萬個(gè)可能記錄中的哪一個(gè)，并且每個(gè)記錄都被貼上了 ID 標(biāo)簽，然后可以保持一個(gè)一百萬位的數(shù)組，初始化的0。每次看到記錄 i 時(shí)，只需將數(shù)組中的第 i 位設(shè)置為1。對(duì)記錄j 的查找查詢相應(yīng)地非常簡單，只需查看位 j 是1還是0。該結(jié)構(gòu)非常緊湊，如果將位數(shù)據(jù)放到內(nèi)存中，125KB 就足夠了。
然而，真正的數(shù)據(jù)很少有這么好的結(jié)構(gòu)。一般來說，可能有一個(gè)更大的輸入集，例如客戶的名稱，其中可能的名稱字符串?dāng)?shù)量是巨大的。不過，可以通過借用不同的字典結(jié)構(gòu)來調(diào)整位數(shù)組的方法。假設(shè)位數(shù)組是一個(gè)哈希表，將使用哈希函數(shù) h 將輸入空間映射到表的索引范圍。也就是說，給定輸入 i，現(xiàn)在將關(guān)鍵字 i 設(shè)置為1。當(dāng)然，我們會(huì)注意哈希沖突。這里顯然有一個(gè)權(quán)衡，最初，添加額外的哈希函數(shù)可以減少出現(xiàn)假陽性的機(jī)會(huì)，然而，隨著越來越多的哈希函數(shù)被添加，位數(shù)組中的1個(gè)值越來越多，因此更有可能發(fā)生沖突。這種權(quán)衡可以通過數(shù)學(xué)方法進(jìn)行分析，通過假設(shè)哈希函數(shù)看起來完全是隨機(jī)的 ，并通過查看不在集合中任意元素存在的幾率來進(jìn)行工作。
如果在一個(gè)大小為 m 的布隆過濾器中存儲(chǔ)了 n 個(gè)不同的項(xiàng)，并且使用了 k 哈希函數(shù)，那么一個(gè)成員資格查詢得到一個(gè)假陽性結(jié)果的機(jī)會(huì)大約是 exp (k ln (1 exp (kn/m)))。一些簡單的分析表明，通過選擇 k = (m/n) ln 2，這個(gè)比率可以最小化，即過濾器中大約一半位為1，一半位為0的情況相對(duì)應(yīng)。
為了實(shí)現(xiàn)這一點(diǎn)，過濾器中的位數(shù)應(yīng)該是存儲(chǔ)在其中的記錄數(shù)的幾倍。一個(gè)常見的設(shè)置是 m = 10n 和 k = 7，這意味著假陽性率低于1% 。請(qǐng)注意，這里沒有魔法可以壓縮超出信息理論限制的數(shù)據(jù)，在這些參數(shù)下，布隆過濾器每個(gè)條目使用約10位，并且必須使用與存儲(chǔ)的不同條目數(shù)量成比例的空間。當(dāng)表示整數(shù)值時(shí)，這是一個(gè)適度的節(jié)省，但是當(dāng)存儲(chǔ)項(xiàng)具有大的描述符(比如 url 等任意字符串)時(shí)，這是一個(gè)相當(dāng)大的好處。因?yàn)?，將這些數(shù)據(jù)存儲(chǔ)在傳統(tǒng)的結(jié)構(gòu)中，比如哈希表或平衡搜索樹，每個(gè)項(xiàng)目將消耗數(shù)十或數(shù)百個(gè)字節(jié)。
當(dāng)一個(gè)假陽性的結(jié)果不是在計(jì)算中引入一個(gè)錯(cuò)誤，而只是一些額外的工作，并且不對(duì)系統(tǒng)的整體性能產(chǎn)生不利影響時(shí)，布隆過濾器是最有吸引力的。一個(gè)很好的例子來自于瀏覽網(wǎng)頁的場(chǎng)景，如果用戶試圖訪問一個(gè)已知的惡意站點(diǎn)時(shí)，Web 瀏覽器通常會(huì)警告用戶。簡單對(duì)比“惡意”URL 數(shù)據(jù)庫檢查 URL 就可以做到這一點(diǎn)，但是需要數(shù)據(jù)庫足夠大，把完整的數(shù)據(jù)庫作為瀏覽器的一部分是很難操作的，尤其是在移動(dòng)設(shè)備上。相反，數(shù)據(jù)庫的布隆過濾器編碼可以包含在瀏覽器中，每個(gè)訪問過的 URL 都可以根據(jù)它進(jìn)行檢查。糟糕的結(jié)果只是瀏覽器可能認(rèn)為一個(gè)無辜網(wǎng)站在黑名單上，為了處理這個(gè)問題，瀏覽器可以聯(lián)系數(shù)據(jù)庫并檢查列表中是否有完整的 URL，以遠(yuǎn)程數(shù)據(jù)庫查找為代價(jià)來消除誤報(bào)。布隆過濾器為大多數(shù) URL 提供所有信息，并且對(duì)一小部分url產(chǎn)生輕微的延遲。這比在瀏覽器中保存數(shù)據(jù)庫副本的解決方案和對(duì)每個(gè) URL 進(jìn)行遠(yuǎn)程查找都要好的多，像 Chrome 和 Firefox 這樣的瀏覽器就采用了這個(gè)概念。?
布隆過濾器是在1970年作為一種緊湊存儲(chǔ)字典的方式引入的，當(dāng)時(shí)的內(nèi)存很珍貴。隨著計(jì)算機(jī)內(nèi)存的增長，似乎不再需要它了。然而，隨著網(wǎng)絡(luò)的迅速發(fā)展，已經(jīng)出現(xiàn)了許多布隆過濾器的應(yīng)用，許多大型分布式數(shù)據(jù)庫(Google 的 Bigtable、 Apache 的 Cassandra 和 HBase)都使用布隆過濾器作為分布式數(shù)據(jù)塊的索引。它們使用過濾器來跟蹤數(shù)據(jù)庫的哪些行或列存儲(chǔ)在磁盤上，從而避免對(duì)不存在的屬性進(jìn)行磁盤訪問。
Count-min
也許規(guī)范的數(shù)據(jù)匯總問題是最不重要的，一個(gè)簡單的計(jì)數(shù)器就足夠了，每觀察一次就增加一次。計(jì)數(shù)器必須有足夠的位深度，以應(yīng)付所觀察到的事件的大小。當(dāng)存在不同類型的數(shù)據(jù)項(xiàng)時(shí)，如果希望計(jì)算每個(gè)類型的數(shù)量時(shí)，自然的方法是為每個(gè)項(xiàng)分配一個(gè)計(jì)數(shù)器。然而，當(dāng)項(xiàng)目類型的數(shù)量增長巨大時(shí)，會(huì)遇到困難，為每個(gè)項(xiàng)目類型分配一個(gè)計(jì)數(shù)器可能不實(shí)用，當(dāng)計(jì)數(shù)器的數(shù)量超過內(nèi)存的容量時(shí)，遞增相關(guān)計(jì)數(shù)器的時(shí)間成本可能會(huì)變得過高。例如，社交網(wǎng)絡(luò)可能希望跟蹤一條記錄在外部網(wǎng)站顯示的頻率，有如果數(shù)十億個(gè)網(wǎng)頁，每個(gè)網(wǎng)頁原則上都可以鏈接到一個(gè)或多個(gè)記錄，因此為每個(gè)網(wǎng)頁分配計(jì)數(shù)器是不可行的，也是不必要的。尋找一種更緊湊的方式來對(duì)項(xiàng)目計(jì)數(shù)進(jìn)行編碼是很自然的事情，盡管可能會(huì)失去一些精確度。
Count-Min 也是一種數(shù)據(jù)結(jié)構(gòu)，允許進(jìn)行這種權(quán)衡，它在一個(gè)小數(shù)組中對(duì)大量的記錄類型進(jìn)行編碼。保證大的計(jì)數(shù)將被相當(dāng)準(zhǔn)確地保存，而小的計(jì)數(shù)可能會(huì)有誤差。Count-Min 由一組計(jì)數(shù)器和一組哈希函數(shù)組成，這些函數(shù)將數(shù)據(jù)項(xiàng)映射到數(shù)組中。乍一看，很像布隆過濾器，但在細(xì)節(jié)方面存在著顯著的差異。確切地說，數(shù)組被視為一個(gè)行序列，每個(gè)項(xiàng)目由第一個(gè)哈希函數(shù)映射到第一行，由第二個(gè)哈希函數(shù)映射到第二行，以此類推，并遞增映射到的計(jì)數(shù)器。注意，這與 布隆過濾器不同，后者允許哈希函數(shù)映射到重疊的范圍。
對(duì)于給定的一個(gè)數(shù)據(jù)項(xiàng)，Count-min允許對(duì)其計(jì)數(shù)進(jìn)行估計(jì): 檢查第一行中由第一個(gè)哈希函數(shù)映射項(xiàng)的計(jì)數(shù)器，以及第二行中由第二個(gè)哈希函數(shù)映射項(xiàng)的計(jì)數(shù)器，依此類推。每一行都有一個(gè)計(jì)數(shù)器，該計(jì)數(shù)器已按該項(xiàng)的每次出現(xiàn)次數(shù)遞增。但是，由于預(yù)期會(huì)發(fā)生沖突，計(jì)數(shù)器還可能因映射到同一位置的其他項(xiàng)。給定包含所需計(jì)數(shù)器和噪聲的計(jì)數(shù)器集合，將這些計(jì)數(shù)器中的最小值作為估計(jì)值。
Count-min也實(shí)現(xiàn)了輸入數(shù)據(jù)的緊湊表示，并在精確度上進(jìn)行了權(quán)衡。如果使用布隆過濾器，答案是二進(jìn)制的，所以有可能出現(xiàn)假陽性; 使用 Count-Min ，答案是頻率，所以有可能出現(xiàn)一個(gè)被夸大的滅國。Count-Min 最適合處理輕微的頻率膨脹，不適用于可能使用 布隆過濾器的情況，如果一個(gè)數(shù)據(jù)項(xiàng)是否存在非常重要，那么 Count-Min 引入的不確定性將掩蓋這種精確程度。但是，count-min 非常適合跟蹤哪些數(shù)據(jù)項(xiàng)超過了給定的流行度閾值。Count-Min 具有更大的壓縮性，它的大小可以被認(rèn)為與輸入大小無關(guān)，而只取決于所期望的精度保證。
自問世以來，Count-Min 已在跟蹤頻率統(tǒng)計(jì)數(shù)據(jù)的系統(tǒng)中有了廣泛的應(yīng)用，例如不同群體的內(nèi)容流行程度、不同用戶群體中在線視頻的流行程度，以及通信網(wǎng)絡(luò)中的流行節(jié)點(diǎn)。網(wǎng)絡(luò)流量的摘要分布可以檢測(cè)到熱點(diǎn)，為網(wǎng)絡(luò)規(guī)劃的決策提供了信息，也可以用來檢測(cè)何時(shí)發(fā)生了流行趨勢(shì)的變化，作為簡單的異常檢測(cè)。
HyperLogLog
如何跟蹤在大量的可能性中有多少不同的項(xiàng)目呢?例如，Web 網(wǎng)站可能希望跟蹤有多少不同的人接觸到了特定的廣告。在這種情況下，不希望對(duì)同一個(gè)用戶瀏覽進(jìn)行多次計(jì)數(shù)。當(dāng)記錄項(xiàng)數(shù)量不太大時(shí)，保持一個(gè)列表或二進(jìn)制數(shù)組是一個(gè)自然的解決方案。當(dāng)可能的項(xiàng)目數(shù)量變得非常大時(shí)，這些方法所需的空間與所跟蹤的項(xiàng)目數(shù)量成正比。能指望做得更好嗎？
HyperLogLog 承諾了更強(qiáng)大的功能，成本只需依賴于計(jì)算量的對(duì)數(shù)。當(dāng)然，也有一些縮放常數(shù)，這意味著所需的空間并不像表示的那么小，但最終的結(jié)果往往只需要幾K字節(jié)的空間，就可以高精度地估計(jì)數(shù)量。HyperLogLog的本質(zhì)是使用應(yīng)用于數(shù)據(jù)項(xiàng)標(biāo)識(shí)符的哈希函數(shù)來確定如何更新計(jì)數(shù)器，以便對(duì)重復(fù)項(xiàng)進(jìn)行相同的處理。對(duì)每個(gè)數(shù)據(jù)項(xiàng) i 應(yīng)用一個(gè)散列函數(shù) g，g 以2j 的概率將數(shù)據(jù)項(xiàng)映射到 j ，例如，在均勻的二進(jìn)制展開式中取前導(dǎo)零位的數(shù)目。然后可以保留一組位標(biāo)識(shí)，指示到目前為止已經(jīng)得到的那些j 值。這里只需要一個(gè)對(duì)數(shù)位數(shù)，因?yàn)橹恍枰@么多不同的 j 值。HyperLogLog方法只保留應(yīng)用哈希函數(shù)時(shí)看到的最大 j 值，從而進(jìn)一步減少了位數(shù)。這可能與基數(shù)相關(guān)，為了減少這種變化，使用第二個(gè)哈希函數(shù)將項(xiàng)分成組，因此同一項(xiàng)總是放在同一組中，并保留關(guān)于每個(gè)組中最大哈希的信息。每個(gè)組都會(huì)產(chǎn)生估計(jì)值，這些估計(jì)值都被組合起來以獲得總基數(shù)的估計(jì)值。方法是計(jì)算估計(jì)值的平均值，使用調(diào)和平均值來減少這種影響。算法的分析具有一定的技術(shù)性，但該算法已被廣泛采用并在實(shí)踐中應(yīng)用，例如Redis。
HyperLogLog 的一個(gè)典型示例就是跟蹤在線廣告的收視率。在許多網(wǎng)站和不同的廣告中，每天可能發(fā)生數(shù)以萬億計(jì)的觀看事件。廣告商感興趣的是有多少不同的人接觸過這些內(nèi)容。收集和傳輸這些數(shù)據(jù)并不是不可行的，只是相當(dāng)笨拙，特別是如果希望執(zhí)行更高級(jí)的查詢(例如，計(jì)算有多少獨(dú)立訪問者同時(shí)看到兩個(gè)特定的廣告)。HyperLogLog使得這種查詢可以直接得到答案，而不是通過搜索整個(gè)數(shù)據(jù)。近似差異計(jì)數(shù)在 web 系統(tǒng)中也被廣泛使用，例如，谷歌的廣告系統(tǒng)提供了不同的計(jì)數(shù)，作為日志數(shù)據(jù)分析的原語。
小結(jié)
在處理大型高維數(shù)值數(shù)據(jù)時(shí)，通常尋求在保持?jǐn)?shù)據(jù)逼真度的同時(shí)降低維數(shù)。假設(shè)數(shù)據(jù)處理和建模的艱苦工作已經(jīng)完成，數(shù)據(jù)可以被建模為一個(gè)巨大的矩陣，其中每一行是一個(gè)樣本點(diǎn)，每一列編碼為數(shù)據(jù)的一個(gè)屬性。一種常用的技術(shù)是應(yīng)用 PCA從數(shù)據(jù)中提取少量的“方向”，沿著每個(gè)方向的每一行數(shù)據(jù)會(huì)產(chǎn)生不同的數(shù)據(jù)表示形式，這些表示形式可以捕獲數(shù)據(jù)集的大部分變化。其局限性是需要找到協(xié)方差矩陣的特征向量，這對(duì)于大型矩陣來說就變得不可持續(xù)。與其尋找“最佳”方向，不如使用(數(shù)量稍大的)隨機(jī)向量。數(shù)據(jù)矩陣的每一行的隨機(jī)投影可以看作是數(shù)據(jù)摘要的一個(gè)例子。更直接的是，Count-Min 可以被看作是各種類型的隨機(jī)投影，這是加速高維機(jī)器學(xué)習(xí)方法的基礎(chǔ)，例如哈希核函數(shù)方法。
數(shù)據(jù)摘要的一個(gè)目標(biāo)是允許任意復(fù)雜的大量數(shù)據(jù)上快速得到近似結(jié)果。一些核心的數(shù)學(xué)運(yùn)算可以通過數(shù)據(jù)摘要的思路來解決，例如隨機(jī)數(shù)值線性代數(shù)。一個(gè)簡單的例子是矩陣乘法矩陣: 給定兩個(gè)大矩陣 A 和 B，找到它們的乘積 AB。一種數(shù)據(jù)摘要方法是為A 的每一行和 B 的每一列建立一個(gè)降維的數(shù)據(jù)摘要，提供一個(gè)估計(jì)。在這個(gè)領(lǐng)域中已解決的問題包括了回歸。這輸入是一個(gè)高維數(shù)據(jù)集，建模為矩陣 A 和列向量 b， A的每一行都是一個(gè)數(shù)據(jù)點(diǎn)，b 的相應(yīng)條目是與該行關(guān)聯(lián)的值, 目標(biāo)是找到最小二乘法的回歸系數(shù) x。這個(gè)問題的精確解是可能的，但是時(shí)間上的開銷與行的數(shù)量有關(guān)，而在矩陣 A上應(yīng)用數(shù)據(jù)摘要可以解決低維空間的問題。
對(duì)于圖，有一些技術(shù)可以概括每個(gè)節(jié)點(diǎn)的鄰接信息，從而可以提取連通性和生成樹信息。對(duì)于幾何數(shù)據(jù)來說，解決聚類等問題的輸入可以捕獲大量的總體結(jié)構(gòu)信息，通過將聚類合并在一起，也可以保留整體點(diǎn)密度分布的良好特征。
一般地，簡單的方法可以提供準(zhǔn)確的答案，但需要保留完整的信息。而在許多情況下，近似方法可以更快，更節(jié)省空間。布隆過濾器有時(shí)被認(rèn)為是“大數(shù)據(jù)分析”必須掌握的核心技術(shù)之一，通常，基于快速數(shù)據(jù)摘要的技術(shù)可以提供不同的折衷。
【關(guān)聯(lián)閱讀】