一种Spark环境下的高效率大规模图数据处理机制

本文针对现有的图处理和图管理框架存在的效率低下以及数据存储结构等问题,提出了一种适合于大规模图数据处理机制。首先分析了目前的一些图处理模型以及图存储框架的优势与存在的不足。其次,通过对分布式计算的特性分析采取适合大规模图的分割算法、数据抽取的优化以及缓存、计算层与持久层结合机制三方面来设计本文的图数据处理框架。最后通过PageRank和SSSP算法来设计实验与MapReduce框架和采用HDFS作持久层的Spark框架做性能对比。实验证明本文提出的框架要比MapReduce框架快90倍,比采用HDFS作持久层的Spark框架快2倍,能够满足高效率图数据处理的应用前景。     

基于分层概率图的动态网络在线异常检测方法

针对当前动态网络异常检测方法只能检测点异常、边异常和子图异常等局部异常事件的缺点,提出了基于分层概率图的在线异常检测方法。首先以窗口为单位将动态网络表征为树状图,然后运用概率分布的方法量化动态网络中连接关系的不确定性,最后结合统计假设检验的方法确定网络窗口是否发生异常。将该方法运用于AS级Internet的动态网络,实验结果表明,分层概率图模型不仅能够准确表征动态网络拓扑结构的演变,而且可以有效检测动态网络中的异常事件。     

基于空间纹理相似性的图像角点特征匹配算法

本文针对传统图像角点特征匹配算法的匹配速度慢且准确率低等问题,提出一种基于空间纹理相似性的图像角点特征匹配算法。首先,计算图像目标上角点对应的空间距离矩阵;然后,通过计算图像角点的空间距离矩阵在对应角点邻域LBP特征向量上的瑞利商,将角点在图像灰度特征空间内的度量问题转换为纹理特征空间内幅值的度量问题;最后,根据角点对应的瑞利商的大小,实现不同图像间的角点特征匹配。对不同条件下采集的图像进行角点特征匹配,得到的匹配结果表明本文算法不仅能够很好的适应图像光照、几何变化,得到的匹配正确率较高,同时与传统算法相比本文算法在运行时间上也有大幅度的降低,当处理特征数量较小时平均降低48ms,而匹配特征数量较多时能够降低2408ms。     

基于特征向量匹配的舞蹈实时姿态分析方法

针对人体运动姿态可自由编辑的特性,提取人体骨架模型,建立人体运动姿态模型库,分析了运动捕捉系统在舞蹈训练中的应用,提出基于特征平面间相似性匹配的方法来计算模型各部件间运动数据参数。经过验证,该方法对于人体姿态的分析具有较高的准确性、鲁棒性,使得舞蹈演员能够准确的对比出与标准舞蹈动作的差异,为舞蹈者进行科学舞蹈训练提供了理论支持。     

一种基于编码关联的快速多模式匹配算法

多模式匹配算法经常使用有限自动状态机来实现多个模式串的并行匹配。针对基于自动状态机的多模式匹配算法在应用于中文编码时存在的存储空间膨胀问题,使用中文字符的拆分编码构造自动状态机,以优化算法自动状态机的存储空间,并利用中文编码的编码关联性,设计了一种基于编码关联跳转的失效跳转表,使用启发式跳跃规则提升匹配算法的时间性能。最后通过实验证明,中文编码环境下,相比于其它使用自动状态机的多模式匹配算法,改良算法拥有更小的空间消耗与更快的运行速度。     

基于马氏距离的孪生多分类支持向量机

孪生支持向量机(TWSVM)的研究是近来机器学习领域的一个热点。TWSVM具有分类精度高、训练速度快等优点,但训练时没有充分利用样本的统计信息。作为TWSVM的改进算法,基于马氏距离的孪生支持向量机(TMSVM)在分类过程中考虑了各类样本的协方差信息,在许多实际问题中有着很好的应用效果。然而TMSVM的训练速度有待提高,并且仅适用于二分类问题。针对这两个问题,将最小二乘思想引入TMSVM,用等式约束取代TMSVM中的不等式约束,将二次规划问题的求解简化为求解两个线性方程组,得到基于马氏距离的最小二乘孪生支持向量机(LSTMSVM),并结合有向无环图策略(DAG)设计出基于马氏距离的最小二乘孪生多分类支持向量机。为了减少DAG结构的误差累积,构造了基于马氏距离的类间可分性度量。人工数据集和UCI数据集上的实验均表明,所提算法不仅有效,而且相对于传统多分类SVM,其分类性能有明显提高。     

一种视频数据代表选择框架方法

为有效处理视频数据问题,提出一种识别海量数据集中代表子集的方法,即代表选择方法,经选择后的小容量的数据代表完全可以代表原始大数据集的结构特征。对于给定的大数据集,首先生成相应₁-norm非负稀疏图,然后利用一种谱聚类算法基于所生成的稀疏图将大数据反复划分直至形成聚类簇。代表选择过程中,将每个聚类看作Grassmann流形中的一个点,然后基于测地距衡量这些点间的距离,接着利用min-max算法分析距离以提取出较优的聚类子集。最后,通过分析被选集类的一个稀疏子图,利用主成分集中性方法探测出数据代表,称此过程为基于非负稀疏图与Grassmann流形测地距的代表选择框架。为验证所提出的框架,将之应用于视频分析中,从一长段的视频流中识别出少数的几个关键帧,实验效果通过人工判断与标准评价方法进行评价,并与现有的几种方法的效果进行比对,结果证明所提出的代表选择框架方法具有更好的效果与可行性。     

有监督的无参数核局部保持投影及人脸识别

针对发掘人脸图像中的高维非线性结构,将加核及构造无参数近邻图两种思想同时引入到局部保持投影算法中,在有监督的模式下,提出了一种新的有监督的无参数核局部保持投影(Parameter-less Supervised Kernel Locality Preserving Projection,PSKLPP)算法并给出了其推导过程。该算法通过将欧氏距离改为对离群数据更为鲁棒的余弦距离,构造无参数近邻图,利用核方法提取人脸图像中的非线性信息,并将其投影在一个高维非线性空间,运用局部保持投影算法得到一线性映射,有效避免了在计算相似矩阵过程中面临的复杂参数选择问题。在ORL和Yale人脸库上的仿真实验验证了所提算法的有效性。     

基于二分图的RDF关键词扩展查询方法

使用图表示RDF数据可以保持数据间的关联信息和语义信息,越来越多的关键词查询方法基于图结构实现RDF数据的查询处理。将二分图与RDF数据图相结合,定义RDF二分图模型,并提出一种基于二分图的RDF关键词扩展查询方法KERBG。该方法将文本信息封装在二分图顶点标签上,以支持对关系的查询;利用关键词同义词扩展技术对查询关键词进行语义扩展,有效解决同一对象的描述用词的多样性问题,进而提高查准率;利用RDF二分图的反对称邻接矩阵及其幂矩阵构造包含关键顶点的查询结果子图,实现关键词查询处理,并降低查询响应时间。实验结果表明,在查准率和查询响应时间方面,提出的KERBG方法优于当前主流方法。     

基于带标记的并发可达标识图的关键路径的求解方法

将AOE 网转换成有色时延Petri网模型,在模型转换过程中同时计算出各位置所对应的事件的最早开始时间,给出了模拟AOE 网的有色时延Petri网模型的带标记的并发可达标识图的构建算法;利用并发可达标识图中的标记序列直接得到关键路径并计算出完成所有活动所需的最短时间。实例与仿真实验结果表明,当AOE网中平均存在3个以上的并发活动时,所提方法执行效率优于传统的求解关键路径的算法,并发活动越多,所提算法效率越高。