2015, 26(11):2749-2751. DOI: 10.13328/j.cnki.jos.004909
摘要:
2015, 26(11):2752-2761. DOI: 10.13328/j.cnki.jos.004890
摘要:随机优化算法是求解大规模机器学习问题的高效方法之一.随机学习算法使用随机抽取的单个样本梯度代替全梯度,有效节省了计算量,但却会导致较大的方差.近期的研究结果表明:在光滑损失优化问题中使用减小方差策略,能够有效提高随机梯度算法的收敛速率.考虑求解非光滑损失问题随机优化算法COMID(compositeobjective mirror descent)的方差减小问题.首先证明了COMID具有方差形式的O(1/√T+σ2/√T)收敛速率,其中,T是迭代步数,σ2是方差.该收敛速率保证了减小方差的有效性,进而在COMID中引入减小方差的策略,得到一种随机优化算法α-MDVR(mirror descent with variance reduction).不同于Prox-SVRG(proximal stochastic variance reduced gradient),α-MDVR收敛速率不依赖于样本数目,每次迭代只使用部分样本来修正梯度.对比实验验证了α-MDVR既减小了方差,又节省了计算时间.
2015, 26(11):2762-2780. DOI: 10.13328/j.cnki.jos.004892
摘要:目标领域已有类别标注的数据较少时会影响学习性能,而与之相关的其他源领域中存在一些已标注数据.迁移学习针对这一情况,提出将与目标领域不同但相关的源领域上学习到的知识应用到目标领域.在实际应用中,例如文本-图像、跨语言迁移学习等,源领域和目标领域的特征空间是不相同的,这就是异构迁移学习.关注的重点是利用源领域中已标注的数据来提高目标领域中未标注数据的学习性能,这种情况是异构直推式迁移学习.因为源领域和目标领域的特征空间不同,异构迁移学习的一个关键问题是学习从源领域到目标领域的映射函数.提出采用无监督匹配源领域和目标领域的特征空间的方法来学习映射函数.学到的映射函数可以把源领域中的数据在目标领域中重新表示.这样,重表示之后的已标注源领域数据可以被迁移到目标领域中.因此,可以采用标准的机器学习方法(例如支持向量机方法)来训练分类器,以对目标领域中未标注的数据进行类别预测.给出一个概率解释以说明其对数据中的一些噪声是具有鲁棒性的.同时还推导了一个样本复杂度的边界,也就是寻找映射函数时需要的样本数.在4个实际的数据库上的实验结果,展示了该方法的有效性.
2015, 26(11):2781-2794. DOI: 10.13328/j.cnki.jos.004901
摘要:在之前的研究中,已经针对李群多连通空间上具有不同类别特征的研究对象,提出了多连通覆盖学习算法,成功地将覆盖学习应用到多连通李群空间.主要针对多连通覆盖学习算法中连通道路的交叉问题,考虑在李群空间上寻找一条测地曲线,使得映射后不同单连通空间上的道路的关联度最小化、同一单连通空间上的道路的关联度最大化,从而实现连通空间上类别判别性能的优化.首先回顾李群连通性质的相关知识;然后,简单介绍了多连通覆盖学习算法,并针对问题给出新的优化算法;最终,通过与经典覆盖学习算法、李群均值算法以及原始算法的比较实验,证明了该优化算法具有更好的分类性能.
2015, 26(11):2795-2810. DOI: 10.13328/j.cnki.jos.004897
摘要:在很多现实的分类应用中,新数据的类标需要由领域专家最终确定,而分类器的分类结果仅起辅助作用.另外,随着大数据所隐含价值越发被人们重视,分类器的训练会从面向单一数据集逐渐过渡到面向分布式空间数据集,大数据环境下辅助分类也将成为未来分类应用的重要分支.然而,现有的分类研究缺乏对此类应用的关注.大数据环境中的辅助分类面临以下3个问题:1) 训练集是分布式大数据集;2) 在空间上,训练集所包含的各局部数据源的类别分布不尽相同;3) 在时间上,训练集是动态变化的,会发生类别迁移现象.在考虑以上问题的基础上,提出一种大数据环境中分布式辅助关联分类方法.该方法首先给出一种大数据环境中分布式关联分类器构建算法,在该算法中,通过横向加权考虑分类数据集在空间上的类别分布差异,并给出"前件空间支持度-相关系数"的度量框架,改进关联分类算法面对不平衡数据的性能缺陷;然后,给出一种基于适应因子的辅助关联分类器动态调整方法,能够在分类器应用过程中充分利用领域专家实时反馈的结果对分类器进行动态调整,以提升其面向动态数据集的分类性能,减缓分类器的退化和重新训练的频率.实验结果表明,该方法能够面向分布式数据集较快地训练出有较高分类准确率的关联分类器,并在数据集不断扩充变化时提升分类性能,是一种有效的大数据环境中辅助分类应用方法.
2015, 26(11):2811-2819. DOI: 10.13328/j.cnki.jos.004908
摘要:如何利用标记间关系来提高学习性能,是多标记学习领域的一个重要问题.分类器链方法及其变型是解决这类问题的一个有效技术.然而,它的学习过程需要预先给定标记的学习次序,这个信息真实情况难以获得.次序选择不当会导致学习性能提高受限.针对这个问题,提出用于多标记学习的分类器圈方法.该方法随机生成标记的学习次序,通过圈结构依次迭代地更新每个标记的分类器.实验结果表明,该方法在多个数据集上取得了比分类器链方法以及一系列经典多标记学习方法更好的性能.
2015, 26(11):2820-2835. DOI: 10.13328/j.cnki.jos.004902
摘要:针对处理大数据时传统聚类算法失效或效果不理想的问题,提出了一种大数据的密度统计合并算法(density-based statistical merging algorithm for large data sets,简称DSML).该算法将数据点的每个特征看作一组独立随机变量,并根据独立有限差分不等式获得统计合并判定准则.首先,使用统计合并判定准则对Leaders算法做出改进,获得代表点集;随后,结合代表点的密度和邻域信息,再次使用统计合并判定准则完成对整个数据集的聚类.理论分析和实验结果表明,DSML算法具有近似线性的时间复杂度,能处理任意形状的数据集,且对噪声具有良好的鲁棒性,非常有利于处理大规模数据集.
2015, 26(11):2836-2846. DOI: 10.13328/j.cnki.jos.004888
摘要:谱聚类将聚类问题转化成图划分问题,是一种基于代数图论的聚类方法.在求解图划分目标函数时,一般利用Rayleigh熵的性质,通过计算Laplacian矩阵的特征向量将原始数据点映射到一个低维的特征空间中,再进行聚类.然而在谱聚类过程中,存储相似矩阵的空间复杂度是O(n2),对Laplacian矩阵特征分解的时间复杂度一般为O(n3),这样的复杂度在处理大规模数据时是无法接受的.理论证明,Normalized Cut图聚类与加权核k-means都等价于矩阵迹的最大化问题.因此,可以用加权核k-means算法来优化Normalized Cut的目标函数,这就避免了对Laplacian矩阵特征分解.不过,加权核k-means算法需要计算核矩阵,其空间复杂度依然是O(n2).为了应对这一挑战,提出近似加权核k-means算法,仅使用核矩阵的一部分来求解大数据的谱聚类问题.理论分析和实验对比表明,近似加权核k-means的聚类表现与加权核k-means算法是相似的,但是极大地减小了时间和空间复杂性.
2015, 26(11):2847-2855. DOI: 10.13328/j.cnki.jos.004895
摘要:当今社会处在信息急剧膨胀的时代,数据的规模和维度都在不断增大,传统的聚类方法有很多难以适应这一趋势.尤其是移动计算平台的高速发展,其平台自身的特性限制了算法的内存使用规模,因此,以往的很多方法若不进行改进,在这类平台上将无法运行.提出了一种基于近邻表示的聚类方法,该方法基于近邻的思想构造出新的表示形式,这种表示可以进行压缩,因此有效地减少了聚类所需要的存储开销.实现了直接对近邻表示压缩后的数据进行聚类的算法,称为Bit k-means.实验结果表明,该方法取得了较好的效果,在提高准确率的同时,大幅度降低了存储空间开销.
2015, 26(11):2856-2868. DOI: 10.13328/j.cnki.jos.004905
摘要:核方法是一类应用较为广泛的机器学习算法,已被应用于分类、聚类、回归和特征选择等方面.核函数的选择与参数优化一直是影响核方法效果的核心问题,从而推动了核度量标准,特别是普适性核度量标准的研究.对应用最为广泛的5种普适性核度量标准进行了分析与比较研究,包括KTA,EKTA,CKTA,FSM和KCSM.发现上述5种普适性度量标准的度量内容为特征空间中线性假设的平均间隔,与支持向量机最大化最小间隔的优化标准存在偏差.然后,使用模拟数据分析了上述标准的类别分布敏感性、线性平移敏感性、异方差数据敏感性,发现上述标准仅是核度量的充分非必要条件,好的核函数可能获得较低的度量值.最后,在9个UCI数据集和20Newsgroups数据集上比较了上述标准的度量效果,发现CKTA是度量效果最好的普适性核度量标准.
乔少杰 , 李天瑞 , 韩楠 , 高云君 , 元昌安 , 王晓腾 , 唐常杰
2015, 26(11):2869-2883. DOI: 10.13328/j.cnki.jos.004889
摘要:已有的轨迹预测算法针对移动对象运动模式,使用数学模型进行交通流模拟,难以对路网中的移动对象进行准确的描述.为了解决这一问题,提出基于隐马尔可夫模型(hidden Markov model,简称HMM)的自适应轨迹预测模型SATP(self-adaptive trajectory prediction model based on HMM),对大数据环境下移动对象海量轨迹利用基于密度的聚类方法进行位置密度分区和高效分段处理,减少HMM的状态数量.根据输入轨迹自动选取参数组合,避免HMM模型中隐状态不连续、状态停留等问题.实验结果表明,SATP模型在实验中表现出较高的预测准确性,并维持较低的时间开销.针对速度随机改变的移动对象,其平均预测准确率为84.1%;相同情况下,平均高出朴素预测算法46.7%.
2015, 26(11):2884-2896. DOI: 10.13328/j.cnki.jos.004893
摘要:如何在人群密度大、变化快、存在大量遮挡的密集场景中实现可靠的人群事件检测,是领域研究的难点和热点.在密集场景时空建模的基础上提出了一种基于多尺度时间递归神经网络的人群异常事件检测和定位方法.首先对人群场景进行网格化划分,并利用多尺度光流直方图对每个网格的人群动态进行刻画;然后,连接各个局部的人群动态获得整体的人群动态,实现整体人群动态的时间序列建模;最后,利用多尺度时间递归神经网络实现异常事件的检测和定位.其中,多尺度隐含层实现了密集场景中不同规模相邻网格之间的空间联系,节点间的反馈关系则为时间维度上的关系表达提供了有效方案.与多种代表性算法的对比实验,验证了本方法的有效性.
2015, 26(11):2897-2911. DOI: 10.13328/j.cnki.jos.004894
摘要:将基于视频的人脸识别转换为图像集识别问题,并提出两种流形来表示每个图像集:一种是类间流形,表示每个图像集的平均脸信息;另一种是类内流形,表示每个图像集的所有原始图像的信息.类间流形针对图像集之间的区别提取整体判别信息,作用是选出几个与待识别图像集较为相似的候选图像集.类内流形则考虑图像集内各原始图像之间的关系,负责从候选图像集中找出最为相似的一个.不同于现有的非线性流形方法中每幅图像对应流形中的一个点,采用分片技术学习两种流形的投影矩阵,每个分片对应流形中的一个点,所学到的特征更具有判别性,进而使流形边界更加清晰,同时解决了传统非线性流形方法中的角度偏差和不充分采样问题.还提出了与分片技术相匹配的流形之间的距离度量方法.最后在几个广为研究的数据集上进行了实验,结果表明:新方法的识别准确率高,尤其适用于不受控环境下的视频识别,而且不受视频段长短的影响.
2015, 26(11):2912-2929. DOI: 10.13328/j.cnki.jos.004896
摘要:提出一种基于差值局部方向模式的人脸特征表示方法(difference local directional pattern,简称DLDP):首先,通过Kirsch掩模卷积运算,为每个像素计算8个方向的边缘响应值;然后,计算8个相邻边缘响应值的强度差,前k个最突出的强度差对应的方向编码为1,其他方向编码为0,形成一个8位二进制数表示对应的DLDP模式;此外,针对高分辨率的Kirsch掩模单纯考虑方向性而没有考虑像素位置权重的问题,提出相应的掩模权值设计方法;最后,把每幅图像划分成多个不重叠的局部图像块,通过统计图像块上不同DLDP模式个数生成相应的子直方图,所有子直方图被串联起来表示一幅人脸图像.实验结果表明,该方法在光照、表情、姿态和遮挡方面获得了较好的结果,尤其针对遮挡情况,表现更为突出.
2015, 26(11):2930-2938. DOI: 10.13328/j.cnki.jos.004898
摘要:设计图像块特征表示是计算机视觉领域内的基本研究内容,优秀的图像块特征表示能够有效地提高图像分类、对象识别等相关算法的性能.SIFT(scale-invariant feature transform)和HOG(histogram of oriented gradient)是人为设计图像块特征表示的优秀代表,然而,人为设计图像块特征间的差异往往不能足够理想地反映图像块间的相似性.核描述子(kernel descriptor,简称KD)方法提供了一种新的方式生成图像块特征,在图像块间匹配核函数基础上,应用核主成分分析(kernel principal component analysis,简称KPCA)方法进行特征表示,且在图像分类应用上获得不错的性能.但是,该方法需要利用所有联合基向量去生成核描述子特征,导致算法时间复杂度较高.为了解决这个问题,提出了一种算法生成图像块特征表示,称为有效图像块描述子(efficient patch-level descriptor,简称EPLd).算法建立在不完整Cholesky分解基础上,自动选择少量的标志性图像块以提高算法效率,且利用MMD(maximum mean discrepancy)距离计算图像间的相似性. 实验结果表明,该算法在图像/场景分类应用中获得了优秀的性能.
2015, 26(11):2939-2950. DOI: 10.13328/j.cnki.jos.004899
摘要:人体行为识别是计算机视觉研究的热点问题,现有的行为识别方法都是基于监督学习框架.为了取得较好的识别效果,通常需要大量的有标记样本来建模.然而,获取有标记样本是一个费时又费力的工作.为了解决这个问题,对半监督学习中的协同训练算法进行改进,提出了一种基于多学习器协同训练模型的人体行为识别方法.这是一种基于半监督学习框架的识别算法.该方法首先通过基于Q统计量的学习器差异性度量选择算法来挑取出协同训练中基学习器集,在协同训练过程中,这些基学习器集对未标记样本进行标记;然后,采用了基于分类器成员委员会的标记近邻置信度计算公式来评估未标记样本的置信度,选取一定比例置信度较高的未标记样本加入到已标记的训练样本集并更新学习器来提升模型的泛化能力.为了评估算法的有效性,采用混合特征来表征人体行为,从而可以快速完成识别过程.实验结果表明,所提出的基于半监督学习的行为识别系统可以有效地辨识视频中的人体动作.
2015, 26(11):2951-2963. DOI: 10.13328/j.cnki.jos.004907
摘要:随着在线社交媒体的快速发展和可定位设备的大量普及,地理位置作为社交媒体大数据中一种质量极高的信息资源,开始在疾病控制、人口流动性分析和广告精准投放等方面得到广泛应用.但是,由于大量用户没有指定或者不能准确指定位置,社交媒体上的地理位置数据十分稀疏.针对此数据稀疏性问题,提出一种基于用户生成内容的位置推断方法UGC-LI(user generate content driven location inference method),实现对社交媒体用户和生成文本位置的推断,为基于位置的个性化信息服务提供数据支撑.通过抽取用户生成文本中的本地词语,构建一个基于词汇地理分布差异和用户社交图谱的概率模型,在多层次的地理范围内推断用户位置.同时,提出一个基于位置的参数化语言模型,计算用户生成文本发出的城市.在真实数据集上进行的评估实验表明:UGC-LI方法能够在15km偏移距离准确定位64.2%的用户,对用户所在城市的推断准确率达到81.3%;同时,可正确定位32.7%的用户生成文本发出的城市,与现有方法相比有明显的提高.
2015, 26(11):2964-2980. DOI: 10.13328/j.cnki.jos.004891
摘要:在大数据时代,数据图的规模急剧增长,增量图模式匹配算法能够在数据图或模式图发生变化时避免重新在整个数据图上进行匹配、减少响应时间,因此成为了研究的热点.针对实际应用中数据图不变而模式图发生变化的情况,提出了一种面向模式图变化的增量图模式匹配算法PGC_IncGPM,在模式图匹配的过程中记录适当的中间结果作为索引,用于后续的模式匹配.提出了增强的图模式匹配算法GPMS,用于首次整个数据图上的模式匹配.该算法一方面能够建立后续增量匹配所需的索引,另一方面减少了整个数据图匹配的执行时间.设计实现了面向模式图增边和减边的两个核心子算法,通过子算法的组合,能够支持在模式图发生各种变化时进行增量图模式匹配.在真实数据集和合成数据集上进行实验,结果表明:与重新在整个数据图上进行匹配的ReComputing算法相比,当模式图中变化的边的数目不超过不变的边的数目时,PGC_IncGPM算法能够有效减少图模式匹配的执行时间;随着数据图规模的增大,PGC_IncGPM算法相对于ReComputing算法的执行时间的减少程度更加明显,对于大规模数据图具有更好的适用性.
2015, 26(11):2981-2993. DOI: 10.13328/j.cnki.jos.004904
摘要:协同过滤方法是当今大多数推荐系统的核心.传统的协同过滤方法专注于评分预测的准确性,然而实际推荐系统的推荐结果往往是项目的排序.针对这一问题,将排名学习领域的知识引入推荐算法,设计了一种基于评分矩阵局部低秩假设的成列协同排名算法.选择直接使用计算复杂度较低的成列损失函数来优化矩阵分解模型,并通过实验验证了其在运算速度上的显著提升.在3个实际推荐系统数据集上,与当下主流推荐算法的比较实验结果表明,该算法具有良好的性能.
2015, 26(11):2994-3009. DOI: 10.13328/j.cnki.jos.004906
摘要:对比序列模式能够表达序列数据集合间的差异,在商品推荐、用户行为分析和电力供应预测等领域有广泛的应用.已有的对比序列模式挖掘算法需要用户设定正例支持度阈值和负例支持度阈值.在不具备足够先验知识的情况下,用户难以设定恰当的支持度阈值,从而可能错失一些对比显著的模式.为此,提出了带间隔约束的top-k对比序列模式挖掘算法kDSP-Miner(top-k distinguishing sequential patterns with gap constraint miner).kDSP-Miner中用户只需设置期望发现的对比最显著的模式个数,从而避免了直接设置对比支持度阈值.相应地,挖掘算法更容易使用,并且结果更易于解释.同时,为了提高算法执行效率,设计了若干剪枝策略和启发策略.进一步设计了kDSP-Miner的多线程版本,以提高其对高维序列元素情况的处理能力.通过在真实世界数据集上的详实实验,验证了算法的有效性和执行效率.
2015, 26(11):3010-3025. DOI: 10.13328/j.cnki.jos.004900
摘要:随着产业界和科学界数据量的爆炸式增长,大数据技术和应用吸引了众多的关注.如何分析大数据,充分挖掘大数据的潜在价值,成为需要深入探讨的科学问题.计算智能是科学研究和工程实践中解决复杂问题的有效手段,是人工智能和信息科学的重要研究方向,应用计算智能方法进行大数据分析具有巨大的潜力.对大数据分析中的计算智能方法进行综述,结合大数据的特征,讨论了大数据分析中计算智能研究存在的问题和进一步的研究方向,阐述了数据源共享问题,并建议利用以天文学为代表的数据密集型基础科研领域的数据开展大数据分析研究.
2015, 26(11):3026-3042. DOI: 10.13328/j.cnki.jos.004887
摘要:教育数据挖掘(educational data mining,简称EDM)技术运用教育学、计算机科学、心理学和统计学等多个学科的理论和技术来解决教育研究与教学实践中的问题.在大数据时代背景下,EDM研究将迎来新的转折点.为方便读者了解EDM的研究进展或从事相关研究和实践,首先介绍EDM研究的概貌、特点和发展历程,然后重点介绍和分析了EDM近年来的研究成果.在成果介绍部分,选取的研究成果大部分发表于2013年以后,包括以往较少涉及的几种新型教育技术.在成果分析部分,对近年来的典型案例作了分类、统计和对比分析,对EDM研究的特点、不足及发展趋势进行了归纳和预测.最后讨论了大数据时代下EDM面临的机遇和挑战.