遺傳聚合演算法

1. CMU 15445 9. 排序和聚合演算法

我們需要排序，因為在關系模型中，表中的元組沒有特定的順序排序，但可能在ORDER BY，GROUP BY，JOIN和DISTINCT運算符中使用。
我們可以通過從左到右掃描葉子節點來使用群集B +樹加速排序。 但是，如果我們使用非聚集B +樹進行排序，這是一個壞主意，因為它會導致大量I / O讀取（通過指針追蹤隨機訪問）。
如果我們需要排序的數據適合內存，那麼我們可以使用標准排序演算法，如quicksort。 如果數據不合適，我們需要使用能夠根據需要溢出到磁碟的外部排序。

外部排序 分為2個部分。首先在內存里排序部分data然後寫入磁碟。 隨後把小塊的文件合並成一個排完序的大文件。

第1個pass：把每B個 PAGES(B 取決於buffer pool 支持的最大page 數量）讀到內存。排序，隨後把他們寫回磁碟。每一個排序的page組稱為一個run
之後的pass：遞歸的合並每一對run，成為下一個run。每一次都會少掉一般的run。

讀完b個page之後，對這整個page做排序。
隨後在合並的時候，n/b 個大page要merge

在合並的時候，我們可以用b-1個來並發。因為還要留一個page去寫。
所以有上圖公式。

還有一些情況可以不用外部排序，比如說是聚集的b+樹索引。我們可以簡單去遍歷樹的葉子節點來做聚合。但是非聚集的索引就不方便。

一般聚合函數又sum,count,min,max等。
實現聚合的主要手段又2種。一種是排序，一種是hash

首先對GROUP BY鍵上的元組進行排序。 如果內存足夠，則放入緩沖池,使用內存排序演算法（例如，快速排序）
如果數據大小超過內存，外部合並排序演算法。
然後，DBMS對已排序的數據執行順序掃描以計算聚合。 operator的輸出將按key排序。

散列計算聚合比排序計算聚合更高效。 DBMS在掃描表時填充哈希表。 對於每條記錄，檢查哈希表中是否已有條目並執行適當的修改。
如果哈希表的大小太大而無法容納在內存中，那麼DBMS必須將其溢出到磁碟：

在ReHash階段，DBMS可以存儲表單對（GroupByKey→RunningValue）來計算聚合。 RunningValue的內容取決於聚合函數。 要將新元組插入哈希表：
•如果我們找到匹配的GroupByKey，只需適當更新RunningValue。
•否則插入新的（GroupByKey→RunningValue）對。

2. 聚合分類數學演算法 是什麼意思

聚合就是對一組數據進行計算，最後得到一個數據，在SQL中，使用聚合函數來計算，例如求和函數sum（）、最大值函數max（）等，分類就是將一組無序數據按某一類別分組排列得到另一組有序的數據，在SQL中，通過關鍵字order by來實現分類查詢，聚合函數一般要與分類查詢配合使用，分類查詢可以單獨使用！

3. 如何提升自底向上的聚合聚類演算法的計算效率

提升自底向上的聚合聚類演算法的計算效率的方法：
1、通過計算各類別中數據之間的相似度，最終創建一棵有層次的嵌套聚類樹。
2、起核心思想，在不同層次上思考問題。
3、計算數據集的相似矩陣。
4、假設每個樣本點為一個簇類。

4. 時間序列分類演算法

歐式距離不能很好地針對時間序列的波動模式進行分類，研發更適合時間序列分類的距離度量就成為關鍵，這其中最經典的時間序列距離度量就是Dynamic Time Warping （DTW）。 DTW的原理如下：

比如說，給定一個樣本序列X和比對序列Y,Z：
X：3，5，6，7，7，1
Y：3，6，6，7，8，1，1
Z：2，5，7，7，7，7，2
請問是X和Y更相似還是X和Z更相似？
DTW首先會根據序列點之間的距離(歐氏距離)，獲得一個序列距離矩陣 MM，其中行對應X序列，列對應Y序列，矩陣元素為對應行列中X序列和Y序列點到點的歐氏距離：

DTW通過對時間序列波動模式的分析可得到更好的時間序列分類結果。研究表明，在時間序列分類問題上，DTW距離度量配合簡單的最小距離分類法（nearest neighbor）就可以取得較傳統歐式距離演算法（如SVM、經典多層神經網路、決策樹、Adaboost）壓倒性的優勢。

DTW更進一步衍生出多種不同的變種，例如由Keogh和 Pazzani 提出的基於序列一階導數的改進便取得了良好的效果；其中一種簡單的方法叫Complexity Invariant distance (CID)，其利用一階導數信息對DTW距離做計算，在某些問題上具有突出效果。

除了DTW，還有其他考量時間序列的波動模式演算法。例如Ye 和Keogh提出的Shapelet方法：考察序列中具有代表意義的子序列來作為Shapelet特徵而進行分類。Lin等人提出了基於字典的方法，將序列根據特定的字典轉化為詞序列，從而進行分類。Deng提出了基於區間的方法，從區間中提取波動的特徵。

除了上述方法外，聚合演算法（將多種不同演算法聚合在一起）的研究也有了長足的進步。最近提出的COTE演算法幾乎將上述所有不同分類演算法聚合在一起，得到了優異的分類效果。

這一類的方法都是一些通過某種度量關系來提取相關特徵的方法，如詞袋法，通過找到該時間序列中是否有符合已有詞袋中的特徵（序列的樣子），將一個序列用詞來表示，再對詞進行分類。而其他的基於特徵的方法都是利用了類似的方法，如提取統計量，基於規則等，再通過分類模型進行分類。

1、MLP、FCN、ResNet
MLP的輸入是一個向量（數組），通過全連接的形式對整體數組的每一個元素逐層賦予權重，並求得最後的分類，這種方法是一種比較粗暴的學習方法，直接學習所有元素直接的線性或非線性相關關系，但是並沒有去深度挖掘數組中更好的表現特徵，分類效果不佳。

FCN是將MLP中的全鏈接層用卷積層進行替代，Resnet也是，但是其中的卷積層都用一維卷積核進行了替代。

來自於Time Series Classifification from Scratch with Deep Neural Networks: A Strong Baseline.可以看到深度學習的方法效果基本上與傳統方法相接近，甚至有所超過，其中整體表現最好的是FCN。

LSTM_FCN的方法比較簡單，是將輸入分別輸入到兩個分支中，LSTM和FCN，並在最後將兩個輸出分支進行concat進行softmax獲得分類結果。在這篇論文中，作者說這種方法取得了比FCN更好的效果。
在其他的一些比賽方案中，也有resnet+LSTM+FC的組合形式，通過Resnet的一維卷積先提取相關特徵，然後通過LSTM學習一維特徵向量的相關關系，再進行分類，可能針對於不同的問題還是要試試才知道哪個的效果更加好。
BiGRU-CNN與以上方法相比實際上並沒有做什麼大的改進，就是將LSTM分支替換成雙向的GRU分支。

5. 什麼是多維聚合演算法

是一種統計分析方法。根據查詢公開信息得知，多維聚合演算法是指研究分類問題的一種統計分析方法，同時也是數據挖掘的一種重要演算法。

6. 聚合校對是什麼

聚合校對如下：

這里的「聚合校對」指的是DNA聚合酶的校隊作用。DNA聚合酶有聚合校對、切除修復的作用，反轉錄又稱逆轉錄，是以RNA為模板提取出DNA遺傳信息的過程。這里的DNA聚合酶是DNA復制的重要酶，具有催化DNA合成和修復DNA的作用。

聚合酶的特點：

1957年，美國科學家阿瑟·科恩伯格（Arthur Kornberg）首次在大腸桿菌中發現DNA聚合酶，這種酶被稱為DNA聚合酶I（DNA polymerase I，簡稱：Pol I）。

1970年，德國科學家羅爾夫·克尼佩爾斯（Rolf Knippers）發現DNA聚合酶II（Pol II）。隨後，DNA聚合酶III（Pol III）被發現。原核生物中主要的DNA聚合酶及負責染色體復制的是Pol III。

以上內容參考：網路-聚合酶

7. 大數據之點聚合演算法

在地圖上查詢結果通常以標記點的形式展現，但是如果標記點較多，不僅會大大增加客戶端的渲染時間，讓客戶端變得很卡，而且會讓人產生密集恐懼症（圖1）。為了解決這一問題，我們需要一種手段能在用戶有限的可視區域范圍內，利用最小的區域展示出最全面的信息，而又不產生重疊覆蓋。

直接距離法，數據量大的話數據會比較慢，聚合效果也不太真實

這里直接選用網格距離法

1、網格法，聚合出所要的點

2、直接距離法，進一步聚合

8. 遺傳演算法

參考文獻： 知乎    遺傳演算法     編碼解碼知識

實現遺傳演算法的第一步就是明確對求解問題的編碼和解碼方式。對於函數優化問題，一般有兩種編碼方式，各具優缺點

實數編碼：直接用實數表示基因，容易理解且不需要解碼過程，但容易過早收斂，從而陷入局部最優

二進制編碼：穩定性高，種群多樣性大，但需要的存儲空間大，需要解碼且難以理解

對於求解函數最大值問題，我選擇的是二進制編碼。

以我們的目標函數 f(x) = x + 10sin(5x) + 7cos(4x), x∈[0,9] 為例。

假如設定求解的精度為小數點後4位，可以將x的解空間劃分為 (9-0)×(1e+4)=90000個等分。

2^16<90000<2^17，需要17位二進制數來表示這些解。換句話說，一個解的編碼就是一個17位的二進制串。

一開始，這些二進制串是隨機生成的。

一個這樣的二進制串代表一條染色體串，這里染色體串的長度為17。

對於任何一條這樣的染色體chromosome，如何將它復原(解碼)到[0,9]這個區間中的數值呢？

對於本問題，我們可以採用以下公式來解碼：

decimal( ): 將二進制數轉化為十進制數

一般化解碼公式：

lower_bound: 函數定義域的下限

upper_bound: 函數定義域的上限

chromosome_size: 染色體的長度

通過上述公式，我們就可以成功地將二進制染色體串解碼成[0,9]區間中的十進制實數解。

染色體，就是指由 DNA 組成的聚合體，DNA 上的每個基因都編碼了一個獨特的性狀，比如，頭發或者眼睛的顏色

可以將他看作是一個優化問題，它可以嘗試找出某些輸入，憑借這些輸入我們便可以得到最佳的輸出值或者是結果

遺傳演算法要點：

1.初始化

初始化候選全體，隨機初始化

2.查找適應函數

3.選擇：物競天擇，適者生存

先選擇能量強的個體，然後再進行隨機選擇，選出適應度雖然小，但是倖存下來的個體

4.交叉：

5.變異：根據需要進行選擇

9. 聚類演算法 - 凝聚層次聚類

層次聚類 就是通過對數據集按照某種方法進行層次分解，直到滿足某種條件為止。按照分類原理的不同，可以分為凝聚和分裂兩種方法。

層次聚類方法對給定的數據集進行層次的分解，直到某種條件滿足為止。具體又可分為 凝聚 和 分裂 的兩種方案：

凝聚的層次聚類是一種自底向上的策略，首先將每個對象作為一個簇，然後合並這些原子簇為越來越大的簇，直到所有的對象都在一個簇中，或者某個終結條件被滿足，絕大多數層次聚類方法屬於這一類，它們只是在簇間相似度的定義上有所不同。.

分裂的層次聚類與凝聚的層次聚類相反，採用自頂向下的策略，它首先將所有對象置於同一個簇中，然後逐漸細分為越來越小的簇，直到每個對象自成一簇，或者達到了某個終止條件。

本篇主要討論凝聚的層次聚類。

第一步 ，將訓練樣本集中的每個數據點都當做一個聚類
第二步 ，計算每兩個聚類之間的距離，將距離最近的或最相似的兩個聚類進行合並，如同下圖中的p1和p2、p5和p6
第三步 ，重復上述步驟，依舊計算每個聚類的距離，當然這次因為已經有聚合起來的簇了因此距離的計算方式有多種： 【單鏈】簇內的最近的點的距離、【全鏈】簇內的最遠的點的距離、【組平均】簇的平均距離、簇的相似度等
第四步 ，直到得到的當前聚類數是合並前聚類數的10%，即90%的聚類都被合並了；當然還可以設置其他終止條件，這樣設置是為了防止過度合並，此時需要幾個簇，那麼就可以用一條橫線去截取分出的簇，如下圖分出3類、4類、5類的橫線截止

ps：距離在通常的情況下可以計算歐幾里得距離，就是普通的直線距離，還可以計算餘弦相似度
具體的動畫效果可以參考視頻，這是----> 傳送門

1）距離和規則的相似度容易定義，限制少
2）不像kmeans，不需要預先制定聚類數
3）可以發現類的層次關系

1）計算復雜度太高
2）奇異值也能產生很大影響
3）由於根據距離來聚合數據，演算法很可能聚類成鏈狀

10. 二十七、ElasticSearch聚合分析中的演算法講解

1、易並行聚合演算法，三角選擇原則，近似聚合演算法
（1）、易並行聚合演算法：比如max

（2）、不易的，如count(distinct)

（2）精準+大數據：hadoop，批處理，非實時，可以處理海量數據，保證精準，可能會跑幾個小時
（3）大數據+實時：es，不精準，近似估計，可能會有百分之幾的錯誤率
（4）、近似聚合演算法
如果採取近似估計的演算法：延時在100ms左右，0.5%錯誤
如果採取100%精準的演算法：延時一般在5s~幾十s，甚至幾十分鍾，幾小時， 0%錯誤
2、cardinality去重及演算法優化和HLL演算法分析
es，去重，cartinality metric，對每個bucket中的指定的field進行去重，取去重後的count，類似於count(distcint)

precision_threshold優化准確率和內存開銷可以提高去重性能
cardinality演算法，會佔用precision_threshold * 8 byte 內存消耗，100 * 8 = 800個位元組
HyperLogLog++ (HLL)演算法性能優化
默認情況下，發送一個cardinality請求的時候，會動態地對所有的field value，取hash值; 將取hash值的操作，前移到建立索引的時候

3、percentiles百分比演算法以及網站訪問時延統計
需求：比如有一個網站，記錄下了每次請求的訪問的耗時，需要統計tp50，tp90，tp99
tp50：50%的請求的耗時最長在多長時間
tp90：90%的請求的耗時最長在多長時間
tp99：99%的請求的耗時最長在多長時間

數據：

不同概率百分比之間的防問效率：

分組統計防問百分比，並計算平均值

4、percentile ranks網站訪問時延SLA統計

SLA：就是你提供的服務的標准
例以地區分組，計算以不同時間的響應百分比

5、doc value原理
（1）index-time生成
PUT/POST的時候，就會生成doc value數據，也就是正排索引
（2）核心原理與倒排索引類似
正排索引，也會寫入磁碟文件中，os cache先進行緩存，以提升訪問doc value正排索引的性能，如果os cache內存大小不足夠放得下整個正排索引，doc value，就會將doc value的數據寫入磁碟文件中
（3）性能問題：
es官方是建議，es大量是基於os cache來進行緩存和提升性能的，不建議用jvm內存來進行緩存，那樣會導致一定的gc開銷和oom問題給jvm更少的內存，給os cache更大的內存。
（4）、column壓縮
doc1: 550
doc2: 550
doc3: 500
合並相同值，550，doc1和doc2都保留一個550的標識即可
（1）所有值相同，直接保留單值
（2）少於256個值，使用table encoding模式：一種壓縮方式
（3）大於256個值，看有沒有最大公約數，有就除以最大公約數，然後保留這個最大公約數
（4）如果沒有最大公約數，採取offset結合壓縮的方式：
如果的確不需要doc value，比如聚合等操作，那麼可以禁用，減少磁碟空間佔用
PUT my_index
{
"mappings": {
"my_type": {
"properties": {
"my_field": {
"type": "keyword"
"doc_values": false
}
}
}
}
}
6、對於分詞的field執行aggregation，發現報錯。。。

如果直接對分詞field執行聚合，報錯，大概意思是說，你必須要打開fielddata，然後將正排索引數據載入到內存中，才可以對分詞的field執行聚合操作，而且會消耗很大的內存

給分詞的field，設置fielddata=true，發現可以執行

也可以用內置field不分詞，對string field進行聚合

7、分詞field+fielddata的工作原理
（1）、不分詞的所有field，可以執行聚合操作 --> 如果你的某個field不分詞，那麼在index-time時，就會自動生成doc value --> 針對這些不分詞的field執行聚合操作的時候，自動就會用doc value來執行
（2）、分詞field，是沒有doc value的。在index-time，如果某個field是分詞的，那麼是不會給它建立doc value正排索引的，因為分詞後，佔用的空間過於大，所以默認是不支持分詞field進行聚合的
fielddata載入到內存的過程是lazy載入的，對一個analzyed field執行聚合時，才會載入，而且是field-level載入的。一個index的一個field，所有doc都會被載入，而不是少數doc，不是index-time創建，是query-time創建
為什麼fielddata必須在內存？因為分詞的字元串，需要按照term進行聚合，需要執行更加復雜的演算法和操作，如果基於磁碟和os cache，那麼性能會很差。

8、fielddata相關優化配置
（1）、內存限制
indices.fielddata.cache.size: 20%，超出限制，清除內存已有fielddata數據，fielddata佔用的內存超出了這個比例的限制，那麼就清除掉內存中已有的fielddata數據
默認無限制，限制內存使用，但是會導致頻繁evict和reload，大量IO性能損耗，以及內存碎片和gc

（2）監控fielddata內存使用
GET /_stats/fielddata?fields=*
GET /_nodes/stats/indices/fielddata?fields=*
GET /_nodes/stats/indices/fielddata?level=indices&fields=*

（3）、circuit breaker斷路器
如果一次query load的feilddata超過總內存，就會oom --> 內存溢出
circuit breaker會估算query要載入的fielddata大小，如果超出總內存，就短路，query直接失敗
indices.breaker.fielddata.limit：fielddata的內存限制，默認60%
indices.breaker.request.limit：執行聚合的內存限制，默認40%
indices.breaker.total.limit：綜合上面兩個，限制在70%以內

（4）、fielddata filter的細粒度內存載入控制

min：僅僅載入至少在1%的doc中出現過的term對應的fielddata
比如說某個值，hello，總共有1000個doc，hello必須在10個doc中出現，那麼這個hello對應的fielddata才會載入到內存中來
min_segment_size：少於500 doc的segment不載入fielddata
載入fielddata的時候，也是按照segment去進行載入的，某個segment裡面的doc數量少於500個，那麼這個segment的fielddata就不載入

（5）、fielddata預載入

query-time的fielddata生成和載入到內存，變為index-time，建立倒排索引的時候，會同步生成fielddata並且載入到內存中來，這樣的話，對分詞field的聚合性能當然會大幅度增強
（6）、global ordinal序號標記預載入

有很多重復值的情況，會進行global ordinal標記
doc1: status1
doc2: status2
doc3: status2
doc4: status1

status1 --> 0 status2 --> 1

doc1: 0
doc2: 1
doc3: 1
doc4: 0

建立的fielddata也會是這個樣子的，這樣的好處就是減少重復字元串的出現的次數，減少內存的消耗