基于聚类算法的有限制单纯形均匀随机抽样研究

针对单纯形在抽样算法设计方案中无法适用复杂限制情况下的条件分布以及满足高维情形要求,需要提出一种行之有效的抽样算法,即Gibbs抽样算法,来为有限制单纯形均匀随机抽样提供一个可靠算法框架,同时为了获得有限制单纯形上均匀分布的代表点,此研究引入了3种聚类算法。从数值模拟结果可以看出,提出的抽样方法能够获取到较为均匀的样本,能够广泛应用至各种有限制或高维等复杂条件中,且对聚类算法的抽样算法框架有显著提升试验点的价值属性。

基于随机抽样和聚类特征的聚类算法

在分析BIRCH算法不足的基础上,提出了一种基于随机抽样和聚类特征的聚类算法(CLAP).该算法采用随机抽样技术,从数据库中抽取一部分数据进行聚类的预处理过程,这样大大降低了运行时间.CLAP通过设立索引树的叶节点的直径和聚类直径,提高了聚类的精度,并采用全局搜索和局部搜索相结合的方式,消除了输入顺序对聚类质量的影响.测试结果表明,CLAP算法不仅提高了聚类速度,而且改善了聚类质量.

MapReduce框架下基于抽样的分布式K-Means聚类算法

提出一种MapReduce框架下基于抽样的分布式K-Means聚类算法,解决海量数据环境下并行执行K-Means算法时,时间开销较大的问题.该算法使用抽样方法,在保证数据分布不变的前提下,对数据集的规模进行约减,并在MapReduce框架下对聚类算法进行优化.实验结果表明,该算法在保持良好聚类效果的同时,能有效缩短聚类时间,对大规模数据集具有较高的执行效率和较好的可扩展性.

一种基于抽样改进加权核K-means的大数据谱聚类算法

经典谱聚类将数据聚类转化为加权图划分问题,在分析Normalized Cut目标函数与加权核K-means函数等价基础上,设计了一种基于抽样改进加权核K-means算法的大规模数据谱聚类算法。算法通过Leaders进行初始聚类预处理,以控制后续随机抽样的数据规模及对原始数据类别的覆盖,通过抽样子集内加权核K-means迭代优化,避免Laplacian矩阵特征分解的大量资源占用,从而以部分核矩阵的使用避免全部核矩的时间、空间复杂度。试验结果表明,改进算法在保持与经典算法相近聚类精度基础上,大幅提高了聚类效率。

基于密度偏差抽样的聚类算法研究

随着网络的普及和信息量的急剧增加,从海量数据中提取有用的数据信息已迫在眉睫。在对已有的基于密度偏差抽样算法改进的基础上,提出了一种基于密度偏差抽样的聚类算法。实验表明,随着信息量、数据维数的增加,该算法聚类的正确率以及对数据的处理速度都要较传统的聚类算法有所提高。

抽样改进加权核大数据谱聚类算法

经典谱聚类算法将数据聚类转为图划分问题,在分析其Normalized Cut函数与传统加权核k-means等价基础上,设计了一种基于抽样改进加权核k-means算法的大规模数据集谱聚类算法,算法通过加权核k-means迭代优化避免Laplacian矩阵特征分解的大量资源占用,通过随机映射得到近似奇异值分解,并由近似奇异向量确定各点数据权重及抽样概率,以此得到快速合理抽样,通过数据抽样并将聚类中心约束到抽样点生成的子空间中,避免全部核矩阵的使用,从而降低经典算法的时间空间复杂度。实验结果表明,改进算法在保持与经典算法相近精度基础上,大幅提高了聚类效率,实验验证了改进算法的有效性。

基于聚类方法的审计分层抽样算法研究

针对审计抽样中最复杂的抽样算法—分层抽样,从数据挖掘中"聚类"的角度出发,较好地运用了聚类思想于审计抽样的分层抽样算法之中,为该算法的实现提供了一种新的解决方案。AICPA39没有为分层抽样提供具体的实现方式,国内的学者曾从统计学角度有过实现,将从计算机科学角度实现方法与统计学实现方法进行分析比较,这是对分层抽样算法实现的有益新探索。

机群系统上基于映射和抽样划分的并行聚类算法

采用映射和抽样划分方法,基于MPI消息传递编程模式,在机群系统上设计与实现一种并行聚类算法.该算法将生物基因序列映射成整数值,采用整数值取代字符串进行聚类,使得聚类过程快速,通过多次抽样一次聚类寻找初值在一定程度上避免了聚类结果陷入局部解的问题,优化了聚类质量.在PC机群系统上对基因序列进行并行聚类的实验结果表明该算法获得了较好的加速和可扩展性.

抽样子空间约束改进大数据谱聚类算法

在分析经典谱聚目标函数与加权核k-means目标函数等价基础上,设计了一种基于抽样子空间约束的改进大规模数据谱聚类算法,算法通过加权核k-means迭代优化避免矩阵特征分解的大量资源被占用,通过数据抽样及聚类中心的子空间约束,避免全部核矩阵都被使用,从而降低经典算法的时间空间复杂度。理论分析和实验结果表明,改进算法保持与经典算法相近聚类精度,提高了聚类效率,验证了改进算法的有效性。

面向大规模数据快速聚类K-means算法的研究

为进一步提高K-means算法对大规模数据聚类的效率,结合MapReduce计算模型,提出一种先利用Hash函数进行样本抽取,再利用Pam算法获取初始中心的并行聚类方法。通过Hash函数抽取的样本能充分反映数据的统计特性,使用Pam算法获取初始聚类中心,改善了传统聚类算法依赖初始中心的问题。实验结果表明该算法有效提高了聚类质量和执行效率,适用于对大规模数据的聚类分析。

编制价格指数的爬虫数据抽样方法研究

文章针对全量爬虫数据编制价格指数成本高的问题,提出了一种抽样方法。该方法采用“大数据—小数据”思想,在基期通过网络爬虫技术全量抓取电商平台的商品交易数据,形成抽样框;在连续性调查中采用抽样技术,根据分层抽样思想,运用聚类算法及其轮廓系数实现总体数据分层,并通过不等概率随机抽样获取各层代表性样本;考虑到连续性调查中入选样本存在无回答现象,提出正式和备选样本思路,针对每个正式样本,采用最近邻匹配法挑选若干个备选样本,当正式样本无回答时,以备选样本作为替补来完成价格指数编制。以天猫商城粮油品类为例进行验证,结果表明:在抓取的数据中,基期全量爬虫数据有18351条,第2—8期连续性调查的平均抽样比为10.18%,抽样的平均相对误差为0.59%,说明该方法是可行的。

一种基于近似类抽样的组合聚类方法

FCM聚类算法具有线性的时间复杂度,但它对初始化非常敏感。而k-中心点轮换法对初始化不太敏感,但其缺点就是时间复杂度较高,不能直接应用到海量数据集的聚类分析中。为克服这两类聚类算法的缺点,而充分利用它们的优点,很自然地提出一种基于近似类抽样的组合聚类算法。这种组合聚类算法的时间复杂度是O(n2m)。仿真实验表明,它具有稳定的聚类结果。

基于区域生长顺序聚类-RANSAC的水稻苗带中心线检测

为提高水稻苗带中心线检测的适应性和实时性,满足巡田机器人导航的低成本、轻量级计算、高实时性需求,针对水稻苗带中心线检测结果容易受到光照变化和机器震动等原因产生图像噪声影响的问题,该研究以返青期和分蘖初期水稻秧苗为研究对象,提出基于区域生长顺序聚类-随机抽样一致性算法(random sample consensus,RANSAC)的水稻苗带中心线检测方法。首先,对采集的水稻秧苗图像运用归一化超绿特征法(excess green,ExG)和最大类间方差法(Otsu)分割水田背景和秧苗区域,应用先腐蚀后开运算的形态学方法去除秧苗图像噪声点;然后,采用基于水平带的秧苗轮廓质心检测方法提取秧苗特征点,利用区域生长顺序聚类方法将同一秧苗行的特征点聚成一类;最后,通过RANSAC算法拟合苗带中心线,从而得到巡田机器人视觉导航基准线。试验结果表明:该方法对返青期和分蘖初期水稻苗带中心线检测率均在97%以上,比已有YOLOv3算法提高6.12个百分点,比基于区域生长均值漂移聚类算法降低2.41个百分点;平均误差角度为2.34°,比已有YOLOv3算法高1.37°,比基于区域生长均值漂移聚类算法低0.12°,平均每帧图像检测时间为15.53 ms,比已有YOLOv3算法缩短81.19%,比基于区域生长均值漂移聚类算法缩短82.74%,本文方法在保证检测精度的基础上,大幅提升了检测速度,具有良好的适应性和实时性。研究结果可为巡田机器人视觉导航提供参考。

一种基于DBS的聚类算法

随着网络的普及和信息量的急剧增加,从海量数据中提取有用的数据信息已迫在眉睫。本文提出了一种基于密度偏差抽样的聚类算法,实验表明,随着信息量、数据维数的增加,该算法聚类的正确率以及对数据的处理速度都要较传统的聚类算法有所提高。

MapReduce下融合PAM算法与仔细播种的多样本归并聚类

传统PAM(Partitioning Around Medoids)算法时间复杂度较高,处理大数据集时效率低下.近年来,越来越多研究者使用MapReduce模型来使聚类算法获得更高的性能,然而MapReduce模型在算法迭代过程中需要多次重启任务、从文件系统读取数据和数据洗牌,影响数据处理效率.本文提出两种基于MapReduce的融合PAM算法与仔细播种的聚类处理模型,在保持PAM算法聚类有效性的同时,在算法性能上获得显著提高.性能试验和聚类有效性实验的结果表明本文提出的方法达到了预期的效果且具有很好的可扩展性.

基于聚类分层的地理空间数据抽样研究

文章针对地理空间数据质检大量人力物力消耗的情况,利用地理空间数据的空间相关性,提出基于聚类分层的地理空间数据质检的优化方案,其中聚类分层是基于欧氏距离的K-Means聚类算法。通过某地的高程数据Monte Carlo模拟抽样实验,从相对误差和分层效率验证相对于传统简单随机抽样,聚类分层抽样的可行性和有效性。

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

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

基于Dijkstra算法的社交网络抽样生成

针对社交网络中随机抽样算法抽样结果不能很好地代表原始网络的问题,设计了一种基于Dijkstra最短路径的抽样算法。首先,利用Dijkstra算法多次抽取社交网络中节点之间的最短路径;然后,对抽取到的路径中边出现的频率进行排序,选择较高频率的边组成抽样的子图。该算法解决了随机抽样算法存在的一些问题,实现了较好的生成抽取社交网络的功能。仿真实验结果表明,与随机抽样方法相比,所提抽样算法能减少抽样误差,更好地反映原始网络。

改进欠抽样方法及其在非平衡数据集分类中的应用

欠抽样方法在非平衡数据集分类时,未充分考虑数据分布变化对分类结果造成的影响。为此,提出一种基于聚类融合去冗余的改进欠抽样方法。采用聚类算法得到多数类样本高密度分布区域的聚类中心,将多数类样本划分为不同子集,通过计算各子集的相似度冗余系数对多数类样本进行去冗余删除,以达到欠抽样的目的。对15个不同平衡率的数据集欠抽样后,利用代价敏感混合属性多决策树模型进行分类。实验结果表明,在不降低非平衡数据集分类准确率的前提下,该方法能够提高少数类样本的正类率及预测模型的G-mean值。

一个新的入侵检测分类算法

针对传统分类方法对入侵检测不均衡数据集中小类别攻击的检测率较低的问题,本文提出了一种欠抽样和二级分类结合的算法。用欠抽样方法对训练数据进行预处理,改善训练集的不均衡程度,用二次分类避免欠抽样中丢失有用信息。实验表明本文提出的算法对小类攻击有很好的识别精度。