遗传聚合算法

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也会是这个样子的，这样的好处就是减少重复字符串的出现的次数，减少内存的消耗