基于特征值的模板化库函数识别

逆编译是编译的逆过程,目的是将可执行的二进制机器代码变换为功能等价的高级语言代码,它在监控恶意代码,挖掘软件漏洞的工作中起着重要的作用。而在面向对象语言的逆编译过程中,模板化库函数识别的难度和复杂性非常大。通过分析现有的C++库函数识别方法,针对库函数模板识别中特征值冲突的关键问题,提出一种改进的特征值构造方法,它能够更完整的保存库函数信息,降低特征值冲突出现的概率,并通过识别部分C++标准模板库函数验证了该算法。     

一种基于图的关联规则挖掘改进算法

本文提出了一种基于图的关联规则挖掘的改进算法。首先介绍了基于图的关联规则挖掘算法;然后,在此基础上对原算法进行了修改,通过在图中查找完全子图来寻找频繁项集;最后,对原算法、改进算法和Apriori算法的优缺点进行了简单的比较分析。     

Incorporating topic transition in topic detection and tracking algorithms

Topics often transit among documents in a document collection. To improve the accuracy of the topic detection and tracking (TDT) algorithms in discovering topics or classifying documents, it is necessary to make full use of this kind of topic transition information. However, TDT algorithms usually find topics based on topic models, such as LDA, pLSI, etc., which are a kind of mixture model and make the topic transition difficult to be denoted and implemented. A topic transition model representation based on hidden Markov model is present, and learning the topic transition from documents is discussed. Based on the model, two TDT algorithms incorporating topic transition, i.e. topic discovering and document classifying, are provided to show the application of the proposed model. Experiments on two real-world document collections are done with the two algorithms, and performance comparison with other similar algorithm shows that the accuracy can achieve 93% for topic discovering in Reuters-21578, and 97.3% in document classifying. Furthermore, topic transition discovered by the algorithm on a dataset which was collected from a BBS website is consistent with the manual analysis results.     

关联规则挖掘中Apriori算法的研究与改进

经典的产生频繁项目集的Apriori算法存在多次扫描数据库可能产生大量候选及反复对候选项集和事务进行模式匹配的缺陷,导致了算法的效率较低。为此,对Apriori算法进行以下3方面的改进:改进由k阶频繁项集生成k+1阶候选频繁项集时的连接和剪枝策略;改进对事务的处理方式,减少Apriori算法中的模式匹配所需的时间开销;改进首次对数据库的处理方法,使得整个算法只扫描一次数据库,并由此提出了改进算法。实验结果表明,改进算法在性能上得到了明显提高。     

改进型遗传算法及其在数据挖掘中的应用

文中在简单遗传算法的基础上，利用改进的算法进行关联规则的发现和数据库中特征项权重的发现，通过对农业气象数据库的实验，力求解决遗传算法中的早熟等问题。     

A comparative study of some concurrency control algorithms for cluster-based communication networks

This paper presents a comparative study of some concurrency control algorithms for distributed databases of computer clusters which emphasize high availability and high performance requirements. For this purpose, we have analyzed some concurrency control algorithms which are used in commercial DBMSs, such as the pessimistic locking algorithm as it verifies transaction conflicts early in their execution phase, and the optimistic algorithm which investigates the presence of conflicts after the execution phase. A new algorithm is proposed and implemented by a simulation program. The three algorithms were tested using different configurations. Simulation results showed that the locking algorithm performed better than the optimistic method in presence of conflicts between transactions, while the optimistic algorithm provided better results in the absence of conflicts. Furthermore, in a distributed database with a certain probability of conflicts, the locking algorithm can be used to guarantee strong consistency and an acceptable level of performance. However, if this probability is negligible, the system performance can be improved by using the optimistic algorithm. The proposed algorithm offers improved performance in numerous cases. As a result, it can be used in a distributed database to guarantee a satisfactory level of performance in the presence of conflicts.     

社会语义网社区发现标签传递算法研究

针对在线社会网络的特性和现有社区发现算法的不足,提出一种基于语义网技术的在线社会网络社区发现算法ISLPA(Improved Semantic Label Propagation Algorithm),即一种适用于大规模在线社会网络的社区发现和标识算法。ISLPA算法对语义标签算法SemTagP进行改进,在社区划分过程中将在线社会网络视为有向加权图,通过语义网和社会化标签技术,充分结合在线社会网络丰富的语义信息和网络拓扑特征进行社区划分。ISLPA算法不需要预先设定社区数量和大小,就能实现社区发现,并能根据标签自动识别划分的社区。算法接近线性时间复杂度,具有较高的效率。通过实验表明,ISLPA算法能有效划分和标识真实在线社会网络。     

A modified augmented Lagrangian with improved grey wolf optimization to constrained optimization problems

This paper presents a novel constrained optimization algorithm named MAL-IGWO, which integrates the benefit of the improved grey wolf optimization (IGWO) capability for discovering the global optimum with the modified augmented Lagrangian (MAL) multiplier method to handle constraints. In the proposed MAL-IGWO algorithm, the MAL method effectively converts a constrained problem into an unconstrained problem and the IGWO algorithm is applied to deal with the unconstrained problem. This algorithm is tested on 24 well-known benchmark problems and 3 engineering applications, and compared with other state-of-the-art algorithms. Experimental results demonstrate that the proposed algorithm shows better performance in comparison to other approaches.

     

A semi-supervised approach to sentiment analysis using revised sentiment strength based on SentiWordNet

Emergence of MapReduce (MR) framework for scaling data mining and machine learning algorithms provides for Volume, while handling of Variety and Velocity needs to be skilfully crafted in algorithms. So far, scalable clustering algorithms have focused solely on Volume, taking advantage of the MR framework. In this paper we present a MapReduce algorithm—data aware scalable clustering (DASC), which is capable of handling the 3 Vs of big data by virtue of being (i) single scan and distributed to handle Volume, (ii) incremental to cope with Velocity and (iii) versatile in handling numeric and categorical data to accommodate Variety. DASC algorithm incrementally processes infinitely growing data set stored on distributed file system and delivers quality clustering scheme while ensuring recency of patterns. The up-to-date synopsis is preserved by the algorithm for the data seen so far. Each new data increment is processed and merged with the synopsis. Since the synopsis itself may grow very large in size, the algorithm stores it as a file. This makes DASC algorithm truly scalable. Exclusive clusters are obtained on demand by applying connected component analysis (CCA) algorithm over the synopsis. CCA presents subtle roadblock to effective parallelism during clustering. This problem is overcome by accomplishing the task in two stages. In the first stage, hyperclusters are identified based on prevailing data characteristics. The second stage utilizes this knowledge to determine the degree of parallelism, thereby making DASC data aware. Hyperclusters are distributed over the available compute nodes for discovering embedded clusters in parallel. Staged approach for clustering yields dual advantage of improved parallelism and desired complexity in \(\mathcal {MRC}^0\) class. DASC algorithm is empirically compared with incremental Kmeans and Scalable Kmeans++ algorithms. Experimentation on real-world and synthetic data with approximately 1.2 billion data points demonstrates effectiveness of DASC algorithm. Empirical observations of DASC execution are in consonance with the theoretical analysis with respect to stability in resources utilization and execution time.     

An Algorithm to Determine Potential Systems in Mathematica

A symmetry analysis of differential equations plays an important role in discovering new solutions. In this article potential symmetries characterized by nonlocal transformations are introduced and an algorithm implemented in the computer algebra system Mathematica is presented which determines automatically potential systems and the corresponding potential symmetries. The possibilities of this algorithm are discussed by the examples of a nonlinear telegraph equation and the axial symmetric wave equation.     

遗传算法在NURBS曲线拟合精度的研究应用

为实现非均匀有理B样条(NURBS)曲线形态的精确控制,在权因子对NURBS曲线的拟合精度控制过程中,引入了遗传算法.分别对遗传算法的全局并行搜索方式和曲线拟合精度的控制方法进行了深入研究.通过遗传算法搜索到权因子变化空间中的最优个体组,应用最优权因子使NURBS参数化曲线具有较好的拟合精度,从而达到曲线形状的合理控制.试验数据表明,通过运用遗传算法对NURBS曲线的权因子进行优化,使得曲线的拟合精度有了较大的提高.     

社会网络中基于信任链的主题群组发现算法

针对社会网络中用户群组准确发现难题,提出了一种基于信任链的用户主题群组发现方法.该方法包括3个部分:主题空间发现、群组核心用户发现和主题群组发现.首先,给出了社会网络主题群组的相关形式化定义;然后,通过主题相关度计算发现主题空间,并给出主题空间上用户兴趣度计算方法;其次,提出原子、串联和并联信任链计算模型,并给出主题空间上的信任链计算方法;最后,分别给出主题空间发现算法、核心用户发现算法和主题群组发现算法.实验结果表明,提出的用户群组发现算法相比基于兴趣度的群组发现算法和边紧密度群组发现算法,平均准确率提升4.1%和11.3%,能够有效提升用户群组组织的准确度,在社会网络用户分类识别方面具有较好的应用价值.     

紧致密集Auto Store系统AGV路径规划与避碰策略

针对新兴紧致密集仓储系统Auto Store具有短途挪库作业多、顶层AGV冲突多、货架结构性角落多等特点,提出一种离线-在线两阶段AGV优化调度方法。离线路径规划阶段,给出改进双层A*算法,在拓扑图建模划分搜索区域基础上,上层通过考虑冲突的启发式函数和考虑转弯的代价函数寻求可行区域,下层在此区域基础上搜索最优路径。在线AGV运行阶段,针对两AGV冲突,扩充了回退策略和路线重规划策略;针对多AGV冲突,提出一种基于贪心算法的区域避碰决策策略,以控制问题规模。最后利用Flexsim仿真进行了验证,结果表明,较于标准A*算法,改进A*算法能在保证搜索效率的同时获得冲突较少的初始路径方案;较于优先级策略,区域避碰策略能减少AGV等待时间;将二者相结合,能缩短整体作业完成时间,且随着AGV数量和作业任务增多,优势越明显。     

Repeated detection of conjunctive predicates in distributed executions

Given a conjunctive predicate ? over a distributed execution, this paper gives an algorithm to detect all interval sets, each interval set containing one interval per process, in which the local values satisfy the Definitely(?) modality. The time complexity of the algorithm is O(n³p), where n is the number of processes and p is the bound on the number of times a local predicate becomes true at any process. The paper also proves that unlike the Possibly(?) modality which admits O(pn) solution interval sets, the Definitely(?) modality admits O(np) solution interval sets. The paper also gives an on-line test to determine whether all solution interval sets can be detected in polynomial time under arbitrary fine-grained causality-based modality specifications.     

基于粗糙集的频繁项集挖掘算法

根据粗糙集中多属性的等价类求解方法,提出一种事务数据库频繁项集的挖掘算法,该算法只在发现1-频繁项集时需扫描数据库,算法效率比Apriori算法要高.     

Multiple Templates Access of Trees in Parallel Memory Systems

We study the problem of mapping theNnodes of a data structure onMmemory modules so that they can be accessed in parallel bytemplates, i.e., distinct sets of nodes. In literature several algorithms are available for arrays (accessed by rows, columns, diagonals, and subarrays) and trees (accessed by subtrees, root-to-leaf paths, levels, etc.). Although some mapping algorithms for arrays allow conflict-free access to several templates at once (for example rows and columns), no mapping algorithm is known for efficiently accessing subtree, path and level templates in complete binary trees. In our paper, we first prove that any mapping algorithm that is conflict-free for tree/level template has Ω(M/logM) conflicts when access is done according to path template and vice versa. Therefore, no mapping algorithm can be found that is conflict-free on both path and tree (or path and level) templates. Our main result is an algorithm for mapping complete binary trees withN= 2^M− 1 nodes onMmemory modules in such a way that:

• •the number of conflicts for accessing an-node subtree,adjacent nodes in the same level, orconsecutive nodes of a root-to-leaf path is(),
• •the load (i.e., the ratio between the maximum and minimum number of data items mapped on each module) is 1 + o(1),
• •the time complexity for retrieving the module where a given data item is stored is(1), if a preprocessing phase of space and time complexity(log) is executed, or(log log), if no preprocessing is allowed.

The algorithm can be easily generalized to complete binary trees of any size.     

Discovering interesting inclusion dependencies: application to logical database tuning

Inclusion dependencies together with functional dependencies form the most important data dependencies used in practice. Inclusion dependencies are important for various database applications such as database design and maintenance, semantic query optimization and efficient view maintenance of data warehouse. Existing approaches for discovering inclusion dependencies consist in producing the whole set of inclusion dependencies holding in a database, leaving the task of selecting the interesting ones to an expert user.In this paper, we take another look at the problem of discovering inclusion dependencies. We exploit the logical navigation, inherently available in relational databases through workloads of SQL statements, as a guess to automatically find out only interesting inclusion dependencies. This assumption leads us to devise a tractable algorithm for discovering interesting inclusion dependencies. Within this framework, approximate dependencies, i.e. inclusion dependencies which almost hold, are also considered.As an example, we present a novel application, namely self-tuning the logical database design, where the discovered inclusion dependencies can be used effectively.     

基于改进关联分类的两次学习方法

关联分类通常产生大量的分类规则,导致在分类新实例时经常产生规则冲突问题。针对这种规则冲突问题,提出了一种基于改进关联分类的两次学习框架。利用频繁且互关联的项集产生分类规则改进关联分类算法,有效减少了规则数。应用改进的关联分类算法产生的一级规则一次性分离出训练集中规则冲突的所有实例。然后,在冲突实例上应用改进的关联分类算法进行第二次学习得到二级规则。分类新实例时,首先利用第一级规则进行分类。如果出现规则冲突,则利用第二级规则分类该实例。实验结果表明,基于改进关联分类的两次学习方法降低了规则冲突比率,并且显著提高了分类准确率。     

Web使用挖掘中Apriori算法的改进研究

分析了挖掘频繁访问模式的过程和当前Apriori算法的缺陷,提出了一种Apriori算法的改进算法:BI_Apriori算法.改进的算法采用不规则数组来保存项集信息,有效省去了扫描数据库所耗费的大量时间.将项集有序性引入到该数组上,减少了候选项集的个数.并采用二进制来表示1阶频繁访问模式,提高了模式匹配和连接的效率.试验结果表明,该改进算法能更有效地发现各种长度不同的访问模式.     

航班滑行路径规划和停机位分配联合优化

针对机场的航班滑行路径规划和停机位分配的联合优化调度问题,构建基于冲突回避的滑行道与停机位联合调度模型,并提出改进的自适应差分进化算法求解问题。以最小化航班的滑行时间和旅客转机的行走时间为优化目标,建立非线性混合整数规划联合调度模型。设计考虑了滑行冲突的路径规划算法,完成航班的滑行路径分配,并通过自适应动态调整差分进化算法参数,引入个体位置边界的扰动策略,进一步改善了算法的搜索性能。对国内某枢纽机场的仿真结果表明,所提出的算法可以有效避免滑行冲突,缩短滑行时间,是能够兼顾旅客服务质量和航班场面滑行效率的有效方法。