一种基于规则的属性约简算法

Reduction of attributes is one of important topics in the research on rough set theory.Wong S K M and Ziarko W have proved that finding the minimal attribute reduction of decision table is a NP-hard problem.Algorithm A (the improved algorithm to Jelonek) choices optimal candidate attribute by using approximation quality of single attribute,it improves efficiency of attribute reduction,but yet exists the main drawback that the single atribute having maximum approxiamtion quality is probably optimal candidate attribute.Therefore,in this paper, we introduce the concept of compatible decision rule,and propose an attribute reduction algorithm based on rules (ARABR).Algorithm ARABR provides a new method that measures the relevance between extending attribute and the set of present attributes,the method assures that the optimal attribute is extended,and obviously reduces the search space.Theory analysis shows that algorithm ARABR is of lower computational complexity than Jelonek's algorithm,and overcomes effectively the main drawback of algorithm A.     

Studies on algorithms for self-stabilizing communication protocols

In this paper the algorithms for self-stabilizing communication protocols are studied.First some concepts and a formal method for describing the proposed algorithms are described,then an improved algorithm for achieving global states is presented.The study shows that the improved algorithm can be applied to obtain the global states in the case of a loss of cooperation of the different processes in th protocol,which can be used as a recovery point that will be used by the following recovery procdure.Thus,the improved algorithm can be used to self-stabilize a communication protocol.Meanwhile,a recovery algorithm for selastabilizing communication protocols is presented.After a failure is detected,all processes can eventually know the error.The recovery algorithm uses the contextual information exchanged during the progress of the protocol and recorded on the stable memory.The proof of correctness and analysis of complexity for these algorithms have been made.The availability and efficiency of the algorithms have been verified by illustrating the example protocols.Finally,some conclusions and remarks are given.     

考虑更新频率等因素的物化视图有效更新算法

For the materialized views in the fast LAN or computing grid environment, it is a very important problem that how to refresh them efficiently when data sources have changed. In this paper, we take the update frequencies and the size of source relations into account and present a partition strategy and an efficient algorithm by creating auxiliary views. Our algorithm may decrease the cost of join operation and communication on network as low aspossible.     

Path planning in complex 3D environments using a probabilistic roadmap method

This paper presents a 3D path planning algorithm for an unmanned aerial vehicle （UAV） in complex environments. In this algorithm, the environments are divided into voxels by octree algorithm. In order to satisfy the safety requirement of the UAV, free space is represented by free voxels, which have enough space margin for the UAV to pass through. A bounding box array is created in the whole 3D space to evaluate the free voxel connectivity. The probabilistic roadmap method （PRM） is improved by random sampling in the bounding box array to ensure a more efficient distribution of roadmap nodes in 3D space. According to the connectivity evaluation, the roadmap is used to plan a feasible path by using A＊ algorithm. Experimental results indicate that the proposed algorithm is valid in complex 3D environments.     

Anisotropic Diffusion Filtering for Reconstruction of Poisson Noisy Sinograms

Anisotropic diffusion filtering is a powerful tool for enhancing image while preserving edges not drifting or blurred. In the paper the tool is applied in rvconstruction of Poisson noisy sinograms which have not too many projections. The proposed algorithm has three steps： extending sinogram with interpolating operation, enhancing sinogram by anisotropic diffusion filtering and rvconstructing by filtered background projection （FBP）. It shows that the algorithm can get rvconstruction images which have much better in quality than the algorithm which only uses FBP. The algorithm is saliently morv efficient than statistical tomography algorithms as well. We illustrate the performance of the algorithm on the data generated by differvnt moralities.     

The motif tracking algorithm

The search for patterns or motifs in data represents a problem area of key interest to finance and economic researchers. In this paper, we introduce the motif tracking algorithm （MTA）, a novel immune inspired （IS） pattern identification tool that is able to identify unknown motifs of a non specified length which repeat within time series data. The power of the algorithm comes from the fact that it uses a small number of parameters with minimal assumptions regarding the data being examined or the underlying motifs. Our interest lies in applying the algorithm to financial time series data to identify unknown patterns that exist. The algorithm is tested using three separate data sets. Particular suitability to financial data is shown by applying it to oil price data. In all cases, the algorithm identifies the presence of a motif population in a fast and efficient manner due to the utilization of an intuitive symbolic representation. The resulting population of motifs is shown to have considerable potential value for other applications such as forecasting and algorithm seeding.     

Blind source separation algorithm based on support vector machines

This paper presents a novel blind source separation algorithm integrating the estimation of the probability density function with the fixed-point algorithm. Firstly, the kernel function is constructed by the radial basis function; then the sparse representation of the probability density function of the mixed signals are established, this sparse representation is based on the support vector machines recursion method of neural network theory, thus the closed form expression of the probability density function is obtained; finally, a new estimation method of the activation function is put forward, combining the Fast ICA with the estimation method, we can get a new algorithm of blind source separation. The simulation results have verified that the algorithm can successfully separate the mixed sub-Gaussian and super-Gaussian source signals, and the performance of the algorithm is excellent.     

A Heuristic Approach to Fast NOVCA （Near Optimal Vertex Cover Algorithm）

This paper describes an extremely fast polynomial time algorithm, the NOVCA （Near Optimal Vertex Cover Algorithm） that produces an optimal or near optimal vertex cover for any known undirected graph G （V, E）. NOVCA is based on the idea of（l） including the vertex having maximum degree in the vertex cover and （2） rendering the degree of a vertex to zero by including all its adjacent vertices. The three versions of algorithm, NOVCA-I, NOVCA-II, and NOVCA-random, have been developed. The results identifying bounds on the size of the minimum vertex cover as well as polynomial complexity of algorithm are given with experimental verification. Future research efforts will be directed at tuning the algorithm and providing proof for better approximation ratio with NOVCA compared to any available vertex cover algorithms.     

Research on scheduling algorithms in Web cluster servers

This paper analyzes quantitatively the impact of the load balance scheduling algorithms and the locality scheduling algorithms on the performance of Web cluster servers,and brings forward the Adaptive_LARD algorithm.Compared with the representative LARD algorithm,the advantages of the Adaptive_LARD are that:(1)it adjusts load distribution among the back-ends through the idea of load balancing to avoid learning steps in the LARD algorithm and reinforce its adaptability;(2)by distinguishing between TCP connections accessing disks and those accessing cache memory,it can estimate the impact of different connections on the back-ends‘load more precisely.Performance evaluations suggest that the proposed method outperforms the LARD algorithm by up to 14.7%.     

Efficient SVM Regression Training with SMO

The sequential minimal optimization algorithm (SMO) has been shown to be an effective method for training support vector machines (SVMs) on classification tasks defined on sparse data sets. SMO differs from most SVM algorithms in that it does not require a quadratic programming solver. In this work, we generalize SMO so that it can handle regression problems. However, one problem with SMO is that its rate of convergence slows down dramatically when data is non-sparse and when there are many support vectors in the solution—as is often the case in regression—because kernel function evaluations tend to dominate the runtime in this case. Moreover, caching kernel function outputs can easily degrade SMO's performance even more because SMO tends to access kernel function outputs in an unstructured manner. We address these problems with several modifications that enable caching to be effectively used with SMO. For regression problems, our modifications improve convergence time by over an order of magnitude.     

Improvements to the SMO algorithm for SVM regression

This paper points out an important source of inefficiency in Smola and Scholkopf's (1998) sequential minimal optimization (SMO) algorithm for support vector machine regression that is caused by the use of a single threshold value. Using clues from the Karush-Kuhn-Tucker conditions for the dual problem, two threshold parameters are employed to derive modifications of SMO for regression. These modified algorithms perform significantly faster than the original SMO on the datasets tried.     

回归支持向量机SMO算法的改进

在Smola 和Sch?觟lkopf的SMO算法中,由于使用了单一的极限值而使得算法的效果没有完全表现出来。使用KKT条件来检验二次规划问题,使用两个极限参量来对回归SMO算法进行改进。通过对比实验,这一改进算法在执行速度上表现出了非常好的性能。     

Rigorous proof of termination of SMO algorithm for support vector Machines

Sequential minimal optimization (SMO) algorithm is one of the simplest decomposition methods for learning of support vector machines (SVMs). Keerthi and Gilbert have recently studied the convergence property of SMO algorithm and given a proof that SMO algorithm always stops within a finite number of iterations. In this letter, we point out the incompleteness of their proof and give a more rigorous proof.     

一种改进的序贯最小优化算法

序贯最小优化(SMO)算法是目前解决支持向量机训练问题的一种十分有效的方法,但是当面对大样本数据时,SMO训练速度比较慢。本文分析了SMO迭代过程中目标函数值的变化情况,进而提出以目标函数值的改变量作为算法终止的判定条件。几个著名的数据集的试验结果表明,该方法可以大大缩短SMO的训练时间,特别适用于大样本数据。     

求解非正定核Huber-SVR的SMO算法

通过运用SMO分解思想和支持向量回归机SVR模型的约束条件,将SVR模型的求解问题转化成一系列的给定区间内抛物线的最小值求解问题,对于非正定核而言由于只改变其中部分抛物线的开口方向,因而可以求得其最小值.据此提出了一种可以求解非正定核的Huber-SVR的SMO方法,推导出了相应的迭代公式并设计了相应的算法.由于用该算法可以求解具有非正定核的SVR,因此可用具有非正定核的Huber-SVR进行回归和预测实验,并与正定核的Huber-SVR的实验结果进行比较.实验表明,对于Huber-SVR而言,某些非正定核比正定核有更好的回归和预测性能,这说明了求解非正定核的Huber-SVR的SMO算法的有效性和必要性.这一算法也可以推广到其它SVR中.     

噪声消除与SMO算法收敛性

近年来,随着序列最小优化分类算法SMO等一系列快速算法的推出,支持向量机在自动文本分类研究领域取得了很大的成功。大多数文本分类问题是线性可分的,使用线性核函数的SMO算法能够取得非常好的分类效果。但是文本向量是一种非常稀疏的向量,采用线性核函数的SMO算法对噪声样本非常敏感,容易产生发散的问题。文章分析证明了噪声如何影响SMO算法收敛性。为了解决训练样本中噪声样本影响SMO算法收敛的问题,设计了一个消除噪声样本的算法,取得了非常好的效果。     

基于样本取样的SMO算法

介绍了一种对样本集取样的方法 ,并在此基础上对序贯最小优化 (sequentialminimaloptimization ,SMO)算法进行了改进 ,提出了取样序贯最小优化 (S-SMO)算法 .S-SMO算法去掉了大部分非支持向量 ,将支持向量逐渐收集到工作集中 .实验结果表明 ,该方法提高了SMO算法的性能 ,缩短了支持向量机分类器的训练时间 .     

基于不同惩罚系数的SMO改进算法

为了解决Keerthi改进的序贯最小优化（SMO）算法在处理非平衡数据集时,整体分类性能较低、稳定性差等问题,对两个类别施加不同的惩罚系数的方法对算法作进一步改进,同时给出计算公式及算法步骤。实验结果表明,该算法不但提高了处理非平衡数据集的能力,也进一步提高了其稳定性。     

Global convergence of SMO algorithm for support vector regression

Global convergence of the sequential minimal optimization (SMO) algorithm for support vector regression (SVR) is studied in this paper. Given l training samples, SVR is formulated as a convex quadratic programming (QP) problem with l pairs of variables. We prove that if two pairs of variables violating the optimality condition are chosen for update in each step and subproblems are solved in a certain way, then the SMO algorithm always stops within a finite number of iterations after finding an optimal solution. Also, efficient implementation techniques for the SMO algorithm are presented and compared experimentally with other SMO algorithms.