1. 算法分析与设计练习

完整源代码已在本文尾部给出

1.1. No1. 优先级队列（大小顶堆）

堆是一种经过排序的完全二叉树，其中任一非终端节点的数据值均不大于（或不小于）其左子节点和右子节点的值。最小(大)堆能保证堆顶元素最小(大)，相比于用数组存放数据，如果要查找所有数据中最小(大)的数据时，数组的时间复杂度为O(n)，而最小(大)堆的时间复杂度为O(1)。而数据增删数据时，需要保证最小(大)堆的动态可维护性仅需O(logN)。因此对于特定的需求环境，最小(大)堆这种数据结构非常高效。

1. Apriori算法简介

• Apriori是一种在事务数据库上进行频繁项集挖掘和关联规则学习的算法。
• 它通过识别数据库中的频繁单项，并将经常出现的项扩展到越来越大的项目集。
• Apriori确定的频繁项目集可用于确定关联规则，能够显示出数据库中项的一般趋势，故常应用于诸如市场购物栏分析的领域中（决策分析）。

1. 集成学习AdaBoost算法简介

AdaBoost全称是adaptive boosting，该算法基本思想:多个结构较为简单，分类或预测精度较低的弱学习算法可以通过某种方式结合成具有较强学习能力的强学习算法。根据统计学习方法的三要素，AdaBoost 方法=加法模型+指数损失函数(策略)+前向分步 算法。

1. 安装Docker

1.1. 一键安装Docker

Manjaro系统下pacman命令一键安装Docker

1

sudo pacman -S docker

1. ID3算法简介

• ID3算法最早是由罗斯昆（J.Ross Quinlan）于1975年在悉尼大学提出的一种分类预测算法，算法的核心是“信息熵（Information entropy）”。
• ID3算法通过计算每个属性的信息增益，认为信息增益高的是好属性，每次划分选取信息增益最高的属性为划分标准，重复这个过程，直至生成一个能完美分类训练样例的决策树。

1. DBSCAN算法简介

• 基于密度的噪声应用空间聚类（DBSCAN）是Martin Ester，Hans-Peter Kriegel，JörgSander和Xiaowei Xu于1996年提出的数据聚类算法。
• 它是一种基于密度的聚类算法：给定一些空间中的一组点，它将紧密堆积在一起的点（具有许多邻近邻居的点）组合在一起，标记为单独位于低密度区域的离群点（最近的点）邻居们太远了）。
• DBSCAN是最常见的聚类算法之一，也是科学文献中引用最多的算法。
• 2014年，该算法在领先的数据挖掘会议KDD上获得了时间奖的测试（在理论和实践中获得了大量关注的算法奖）。
  展开阅读全文 »

1. 实现PAM算法对部分含有高斯噪声的waveform数据集进行聚类

1.1. PAM算法简介

• PAM方法于1987年提出，用于l1范数和其他距离的工作。
• k-medoid是一种经典的聚类分割技术，它将n个对象的数据集聚为k个聚类，假设聚类的数量k是先验的。如果未知，则可以使用诸如轮廓的方法来确定k。 与k均值相比，它对噪声和异常值更具鲁棒性，因为它最小化了成对差异的总和，而不是欧几里德距离的平方和。
• 可以将medoid定义为群集的对象，其与群集中的所有对象的平均差异最小。即，它是群集中位于最中心的点（迭代选取最中心的点，而非Kmeans的中心计算值，抗噪声能力更强）。

1. 实现K-means算法对无噪声的waveform数据集进行分割

1.1. K-means算法简介

• k均值聚类是一种矢量量化方法，最初来自信号处理，是数据挖掘中聚类分析的常用方法。
• k均值聚类的目的是将n个观测值划分为k个聚类，其中每个观测值属于具有最近均值的聚类，作为聚类的原型。这导致数据空间划分为Voronoi单元。

1. 快速排序概念

快速排序（Quick Sort）由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序是不稳定的算法，时间复杂度在最坏情况下是O(N^2)，平均的时间复杂度是O(N*lgN)。