基于两阶段分层抽样的近似聚合查询方法

以数据仓库应用为代表的交互式查询分析技术为智能决策提供了支持。随着数据规模的不断增大,准确计算聚合查询结果往往需要全局数据扫描,使得这类查询面临着实时响应能力不足的问题。基于预先抽取的样本数据,复杂聚合查询提供快速的近似答案,在许多场景下是解决该问题的可行方案。分析了分层抽样优于随机抽样的具体条件,提出了一种两阶段分层抽样方法。首先针对业务特征进行分组,每个分组中使用随机抽样方法进行随机抽样,并评估其抽样效果。再针对抽样效果较差的分组,利用自组织特征映射网络（Self-organizing feature mapping,SOM）对数值进行聚类分组,改进其近似查询效果。基于公开数据集和实际电网数据的实验结果表明：本文方法相比于随机抽样、分层随机抽样以及国会抽样算法在相同抽样率下可达到15%的性能提升;与使用K-means、基于密度的聚类算法（Density-based spatial clustering of applications with noise,DBSCAN）等聚类方法相比,自SOM具有较好的近似查询结果。     

基于改进Leaders算子的审计潜在疑点发现

数据库查询方法审计疑点发现依赖于审计人员先验知识,当经验不足且审计数据量巨大时,难以发挥大数据优势并从海量数据中发现疑点。为解决这一问题,提出基于改进Leaders算子迭代聚类的审计大数据潜在疑点发现方法。该方法在无先验知识的情形下,通过Leaders算法自动完成审计大数据的初始聚类,在此基础上通过随机抽样融合方法对初始聚类结果优化,最后通过多次迭代聚类的方法,对实例数较少或可疑程度易被掩盖的小簇进一步聚类,实现审计大 数据的精确聚类,并将实例较少且行为明显异常的数据聚类识别为潜在疑点,配合审计人员审计经验快速精确定位审计疑点。实验结果验证了算法的有效性,表明算法有助于从海量数据中自主发现审计疑点,缩小疑点筛查范围,提高审计效率。     

利用快速无偏分层图抽样算法的MapReduce负载平衡方法

提出一种基于快速无偏分层图抽样的MapReduce负载平衡方法.将聚类算法融合到MapReduce连接操作中,提出MapReduce并行聚类连接算法的实现方法;根据聚类结果动态调整抽样率的无偏分层图抽样算法,从而实现连接操作目标数据的准确、平衡抽样.通过合成数据集和真实数据集下的数据处理实验,与Hash连接算法及基于NS抽样的聚类算法进行对比,验证了所提出的算法方案在不同数据倾斜程度下都具有良好的负载平衡性能,其运行效率也没有因为新采样算法的采用而受到影响.     

基于自适应Nyström采样的大数据谱聚类算法

面对结构复杂的数据集,谱聚类是一种灵活而有效的聚类方法,它基于谱图理论,通过将数据点映射到一个由特征向量构成的低维空间,优化数据的结构,得到令人满意的聚类结果.但在谱聚类的过程中,特征分解的计算复杂度通常为O(n³),限制了谱聚类算法在大数据中的应用.Nyström扩展方法利用数据集中的部分抽样点,进行近似计算,逼近真实的特征空间,可以有效降低计算复杂度,为大数据谱聚类算法提供了新思路.抽样策略的选择对Nyström扩展技术至关重要,设计了一种自适应的Nyström采样方法,每个数据点的抽样概率都会在一次采样完成后及时更新,而且从理论上证明了抽样误差会随着采样次数的增加呈指数下降.基于自适应的Nyström采样方法,提出一种适用于大数据的谱聚类算法,并对该算法的可行性和有效性进行了实验验证.     

一种基于抽样的大规模混合数据聚类集成算法

混合数据聚类是聚类分析中一个重要的问题。现有的混合数据聚类算法主要是在全体样本的相似性度量的基础上进行聚类,因此对大规模数据进行聚类时,算法效率不高。基于此,设计了一种新的抽样策略,在此基础上,提出了一种基于抽样的大规模混合数据聚类集成算法。该算法对利用新的抽样策略得到的多个样本子集分别进行聚类,并将结果集成得到最终聚类结果。实验证明,与改进的K-prototypes算法相比,该算法的效率有了显著提高,同时聚类有效性指标基本相同。     

面向大数据处理的并行优化抽样聚类K-means算法

针对大数据环境下K-means聚类算法聚类精度不足和收敛速度慢的问题,提出一种基于优化抽样聚类的K-means算法(OSCK)。首先,该算法从海量数据中概率抽样多个样本;其次,基于最佳聚类中心的欧氏距离相似性原理,建模评估样本聚类结果并去除抽样聚类结果的次优解;最后,加权整合评估得到的聚类结果得到最终k个聚类中心,并将这k个聚类中心作为大数据集聚类中心。理论分析和实验结果表明,OSCK面向海量数据分析相对于对比算法具有更好的聚类精度,并且具有很强的稳健性和可扩展性。     

基于B/S架构的复杂抽样调查统计推断系统

基于B/S构架的复杂抽样调查统计推断系统采用跨平台设计,与业务系统及数据库无缝链接。系统提供随机抽样、分层抽样、Neyman分层抽样、不等概率抽样(PPS)、多阶段抽样等常用抽样算法。系统用户根据研究目标自定义组合抽样方法,系统根据样本和总体属性及用户抽样方案自动推算统计推断结果及置信区间,实现抽样调查、统计推断的自动化与系统化。     

聚类与关联规则在信息舞弊识别中的应用

针对现代电子数据迅速膨胀,传统的审计方式已经无法应对海量的业务数据,试图将数据挖掘中的聚类和关联规则算法引入审计领域．在研究聚类与关联规则算法的含义及相关算法—K-Means和Apriori算法的基础上,提出了一种基于聚类与关联规则的审计模型,并以某市城镇医疗保险的审计为例,首先利用聚类分析进行数据筛选,然后利用关联规则挖掘海量数据之间潜在的关系,为审计提供线索．文章通过案例分析为数据挖掘在信息舞弊识别领域的应用提供参考．     

K均值和最大加权熵在彩色图像分割中的应用

K均值算法属于聚类方法的一种,常用于图像分割。针对如何确定最优聚类数K这一关键问题,在彩色图像的HSI颜色空间中,以马氏距离为距离测度进行K均值聚类,从信息论的角度出发,利用最大加权熵定义了一个目标函数,将最优聚类个数K的求取转换为目标函数的寻优,实现了彩色图像的无监督分割。该方法原理简单,易于实现,能获得比传统方法更好的分割效果。     

考虑类内不平衡的谱聚类过抽样方法

不平衡数据分类问题是数据挖掘领域的关键挑战之一。过抽样方法是解决不平衡分类问题的一种有效手段。传统过抽样方法没有考虑类内不平衡,为此提出基于改进谱聚类的过抽样方法。该方法首先自动确定聚类簇数,并对少数类样本进行谱聚类,再根据各类内包含样本数与总少数类样本数之比,确定在类内合成的样本数量,最后通过在类内进行过抽样,获得平衡的新数据集。在4个实际数据集上验证了算法的有效性。并在二维合成数据集上对比k均值聚类和改进谱聚类的结果,解释基于两种不同聚类的过抽样算法性能差异的原因。     

改进型分层抽样技术及性能研究

报文抽样技术是高速网络流量测量和管理中使用的一项关键技术。本文通过引进分层特征、层数L、分层边界、各层样本量分配、层内抽样策略5个分层抽样参数,并对其进行重新配置和简单理论探讨,实现对分层抽样技术的改进。同时文章使用简单线性估计推断原始流数据,并借助于Φ偏差检验方法,对改进的分层抽样技术和其它抽样技术在测量网络报文长度分布方面进行准确性性能比较。结果表明,改进的分层抽样技术在测量报文长度分布方面的准确性性能远高于其它抽样方式,提高了测量的精度。     

Fast balanced sampling for highly stratified population

Balanced sampling is a very efficient sampling design when the variable of interest is correlated to the auxiliary variables on which the sample is balanced. A procedure to select balanced samples in a stratified population has previously been proposed. Unfortunately, this procedure becomes very slow as the number of strata increases and it even fails to select samples for some large numbers of strata. A new algorithm to select balanced samples in a stratified population is proposed. This new procedure is much faster than the existing one when the number of strata is large. Furthermore, this new procedure makes it possible to select samples for some large numbers of strata, which was impossible with the existing method. Balanced sampling can then be applied on a highly stratified population when only a few units are selected in each stratum. Finally, this algorithm turns out to be valuable for many applications as, for instance, for the handling of nonresponse.     

SNS:一种快速无偏的分层图抽样算法

抽样作为一种有效的统计分析方法,常被用于大规模图数据分析领域以提升性能。现有的图抽样算法大多存在高度节点或低度节点过度入样的问题,较大程度地影响了算法的性能。复杂网络具有无标度特性,即节点的度服从幂律分布,节点个体之间存在较大差异。在基于点选择策略的抽样方法的基础上,通过结合节点的近似度分布策略,设计并实现了高效无偏的分层图抽样算法SNS。在3个真实的图数据集上的实验结果表明,SNS算法比其他图抽样算法保留了更多的拓扑属性,且执行效率比FFS更高。SNS算法在度的无偏性、抽样结果拓扑属性近似性方面的表现均优于现有算法。     

基于使用模型的软件可靠性加速测试

给出了一种使用分层抽样和重要抽样方法并基于Markov链使用模型的软件可靠性加速测试的方法,在根据统计测试结果得到软件可靠性无偏估计的前提下,可以有效提高安全攸关软件的测试效率,部分解决了安全攸关软件统计测试时间和费用开销过大的问题.实例仿真结果表明,该方法可以有效地提高软件可靠性关键操作的测试效率.     

在癌症分类中基于分层抽样的神经网络集成算法

在基因表达谱数据的分析中,针对有效合理地选择特征基因集的问题,本文将分层抽样技术引入特征基因选择,提高特征基因集的分类能力。以神经网络作为分量分类器,神经网络集成进行分类预测。并在结肠癌数据集上进行实验,实验结果表明该方法能有效地降低特征基因集选择的复杂性,提高对于未知样本的分类预测效果。     

Stratified sampling for data mining on the deep web

In recent years, the deep web has become extremely popular. Like any other data source, data mining on the deep web can produce important insights or summaries of results. However, data mining on the deep web is challenging because the databases cannot be accessed directly, and therefore, data mining must be performed by sampling the datasets. The samples, in turn, can only be obtained by querying deep web databases with specific inputs. In this paper, we target two related data mining problems, association mining and differential rulemining. These are proposed to extract high-level summaries of the differences in data provided by different deep web data sources in the same domain. We develop stratified sampling methods to perform these mining tasks on a deep web source. Our contributions include a novel greedy stratification approach, which recursively processes the query space of a deep web data source, and considers both the estimation error and the sampling costs. We have also developed an optimized sample allocation method that integrates estimation error and sampling costs. Our experimental results show that our algorithms effectively and consistently reduce sampling costs, compared with a stratified sampling method that only considers estimation error. In addition, compared with simple random sampling, our algorithm has higher sampling accuracy and lower sampling costs.     

基于分层抽样算法的异常攻击流量检测

在高速互联网应用中,海量数据无法逐包检测分析,异常攻击流量也不易被识别。为解决该问题,利用泊松帕累托突发过程的经典流量模型对网络流量自相似特性进行分析,将网络流量分为长流与短流,并根据数据流到达时间的抽样比增量进行分层抽样,由此实现异常攻击流量的检测。在基于数据报文级检测的snort异常入侵检测系统上对该方法进行仿真实验,结果证明其能有效缩小异常攻击数据范围,快速准度地检测出攻击。     

一种业务流自适应尽力采样方法

基于业务流的网络流量监测是网络管理、运维、实现基于业务的计费、流量工程等的重要手段．精确、高效的采样技术是实现高速网络流量业务流监测分析的重要技术．基于分段采样思想提出一种尽力最优的自适应随机采样方法，实现特大业务流的精确估计，其中把监测系统本身的处理能力作为选择采样概率的参数．实验结果显示算法能够很好地调节采样概率，使得采样包速率基本等于预先设定的监测系统的处理能力．     

运用聚类方法的分层采样粒子滤波算法

针对跟踪过程中运动目标形态不断变化及跟踪不精确导致鲁棒性差的问题,提出了一种运用聚类方法的分层采样粒子滤波算法。通过分层采样把采样空间分成多个部分,使采样点集中于被采样概率密度函数值大的部分,采样误差降低到了原算法的一半;聚类方法利用权重实现合理分配粒子,使粒子的多样性得到保持,因而粒子跟踪的精度得到了提高。实验结果表明,所提算法的跟踪误差不到原算法的一半,每个仿真时间里稳定性都有加强,而且跟踪精度也有所提高。     

分段抽样模型中抽中目标的概率分析

为了增大基于种群操作的搜索技术在有限时间内捕捉到决策空间中的特定目标的概率,基于古典概率模型建立不划分的随机抽样模型和划分成多个子区域的随机抽样模型(简称划分模型),分析比较了两个模型分别进行多次独立随机抽样至少抽中1次特定目标的概率,并证明：当总体中特定目标的数量为1或2时,划分模型抽中特定目标的概率恒大于不划分模型的概率。