数据挖掘中的随机算法和数据流管理系统是什么？

随机算法——以随机抽样和蓝图形式出现的随机算法用于处理大型、高维数据流。与已知的确定性算法相比，随机化的需求导致了更简单、更有效的算法。

如果一个随机算法持续返回正确答案，但运行时间发生变化，则称为拉斯维加斯算法。相反，蒙特卡洛算法对运行时间有界限，但无法恢复真实结果。它通常可以考虑蒙特卡洛算法。随机算法的重要性仅仅是作为一组确定性算法上的概率分布。

鉴于随机算法将随机变量作为结果恢复，它可能对该随机变量的尾概率有界限。这告诉我们随机变量偏离其期望值的概率很小。主要工具是切比雪夫不等式。

设X是一个均值为μ，标准差为σ（方差σ²）的随机变量。切比雪夫不等式表明：

$$\mathrm{P(|X-\mu|>k)<\frac{\sigma^2 }{k^2}}$$

对于任何给定的正实数k。该不等式用于限制随机变量的方差。在许多情况下，可以使用多个随机变量来提高结果的置信度。考虑到这些随机变量是完全独立的，可以使用切尔诺夫界。

设X₁X₂ … X_n为独立泊松试验。在泊松试验中，成功的概率在每次试验中都会发生变化。如果X是X₁到X_n的和，则切尔诺夫界的一个较弱版本告诉我们：

$$\mathrm{P[X<(1+\delta)\mu]< e^{-\mu\delta^2}}$$

其中δ ∈ (0, 1]。这表明概率随着它远离均值而呈指数下降，这使得较差的估计不太可能。

数据流管理系统——在数据流管理系统中，存在多个数据流。它们在线出现，是连续的、时间序列的，并且可能是无限的。因为数据流中的一个组件已经被处理，它就被丢弃或存档，除非它被显式地保存在内存中，否则不能简单地检索它。

流数据查询处理结构包括三个元素：最终用户、查询处理器和暂存空间（可以包括主内存和磁盘）。最终用户向DSMS提出查询，查询处理器接收查询，使用保存在暂存空间中的数据处理它，并将结果恢复给用户。

查询可以是一次性查询或连续查询。一次性查询在数据集的某个时间点的快照上计算一次，并将答案返回给用户。连续查询在数据流持续出现时持续计算。

Ginni

更新于：2022年2月17日

2K+ 次查看

启动您的职业生涯

通过完成课程获得认证

开始学习