Analysis and efficient implementation of a linguistic fuzzy c-means

The paper is concerned with a linguistic fuzzy c-means (FCM) algorithm with vectors of fuzzy numbers as inputs. This algorithm is based on the extension principle and the decomposition theorem. It turns out that using the extension principle to extend the capability of the standard membership update equation to deal with a linguistic vector has a huge computational complexity. In order to cope with this problem, an efficient method based on fuzzy arithmetic and optimization has been developed and analyzed. We also carefully examine and prove that the algorithm behaves in a way similar to the FCM in the degenerate linguistic case. Synthetic data sets and the iris data set have been used to illustrate the behavior of this linguistic version of the FCM.     

Parallel implementation of fuzzy minimals clustering algorithm

Clustering aims to classify different patterns into groups called clusters. Many algorithms for both hard and fuzzy clustering have been developed to deal with exploratory data analysis in many contexts such as image processing, pattern recognition, etc. However, we are witnessing the era of big data computing where computing resources are becoming the main bottleneck to deal with those large datasets. In this context, sequential algorithms need to be redesigned and even rethought to fully leverage the emergent massively parallel architectures. In this paper, we propose a parallel implementation of the fuzzy minimals clustering algorithm called Parallel Fuzzy Minimal (PFM). Our experimental results reveal linear speed-up of PFM when compared to the sequential counterpart version, keeping very good classification quality.     

模糊序贯决策算法优化设计及Matlab实现

对模糊序贯决策算法进行了优化设计,构建了一种基于模糊关系矩阵的模糊序贯决策算法,并利用Matlab程序实现了算法,给出了源程序,通过实例分析说明了算法的简洁性。     

A fast and efficient clustering based fuzzy time series algorithm (FEFTS) for regression and classification

Forecasting fuzzy time series (FTS) methods are generally divided into two categories, one is based on intervals of universal set and the other is based on clustering algorithms. Since there are some challenging problems with the interval based algorithms such as the ideal interval length, clustering based FTS algorithms are preferred. Fuzzy Logical Relationships (FLRs) are usually used to establish relationships between input and output data in both interval based and clustering based FTS algorithms. Modeling complicated systems demands high number of FLRs that incurs high runtime to train FTS algorithms. In this study, a fast and efficient clustering based fuzzy time series algorithm (FEFTS) is introduced to handle the regression, and classification problems. Superiority of FEFTS algorithm over other FTS algorithms in terms of runtime and training and testing errors is confirmed by applying the algorithm to various benchmark datasets available on the web. It is shown that FEFTS reduces testing RMSE for regression data up to 40% with the least runtime. Also, FEFTS with the same accuracy as compared to Fuzzy-Firefly classification method, diminishes runtime moderately from 324.33 s to 0.0055 s.     

An efficient blocking-matching algorithm based on fuzzy reasoning

Due to the temporal and spatial correlation of image sequence, the motion vector of a reference block is highly related to the motion vectors of its adjacent blocks in the same image frame. By using that idea, we propose a novel efficient fuzzy search (EFS) algorithm for block motion estimation. The experimental results show that the EFS performs better than other fast search algorithms, such as TSS, CS, NTSS, FSS, BBGDS, SES, and PSA in terms of picture quality, accuracy, computational complexity, and coding efficiency.     

VLSI based orthogonal diagonal cross hair search (ODCHS) algorithm implementation for efficient image compression

In this paper, an efficient image codec is proposed using Magnetic Resonance Images (MRI). During the past few years, frequency domain analyzes such as Discrete Cosine Transform and Discrete Wavelet Transform (DWT) have been widely used in the field of image compression due to their well localized property of its coefficients in both frequency and space domain. This work also deals with image compression based on frequency domain transformation. As the medical images are very important for diagnosis, they require lossless compression to store them. However, the coefficients of DWT are real numbers; lossless compression cannot be achieved. To overcome this limitation, a variant of DWT named Lifting Wavelet Transform (LWT) is utilized in the proposed system. The proposed codec is applied on the decomposed image. The codec has also been synthesized using FPGA and the results are compared with simulation results and verified.     

一种高效二维小波分解算法的FPGA实现

针对现有二维提升小波变换实现过程中存在的大量过程数据存储及关键路径延时较长的问题,提出一种直接进行二维变换的VLSI架构.采用Altera公司Cyclone Ⅱ系列FPGA EP2C35F672C6对架构进行实现和验证,在纯计算逻辑下二维小波变换时钟频率可达到157.78 MHz.     

An efficient concurrent implementation of a neural network algorithm

The focus of this study is how we can efficiently implement the neural network backpropagation algorithm on a network of computers (NOC) for concurrent execution. We assume a distributed system with heterogeneous computers and that the neural network is replicated on each computer. We propose an architecture model with efficient pattern allocation that takes into account the speed of processors and overlaps the communication with computation. The training pattern set is distributed among the heterogeneous processors with the mapping being fixed during the learning process. We provide a heuristic pattern allocation algorithm minimizing the execution time of backpropagation learning. The computations are overlapped with communications. Under the condition that each processor has to perform a task directly proportional to its speed, this allocation algorithm has polynomial‐time complexity. We have implemented our model on a dedicated network of heterogeneous computers using Sejnowski's NetTalk benchmark for testing. Copyright © 2005 John Wiley & Sons, Ltd.     

模糊数据融合算法在设备状态监测中的应用

在对设备进行状态监测时,常采用传感器固定阈值检测法实现对设备的故障监测。为了克服该种方法所引起的信息损失问题,基于模糊集系统理论,提出一种应用多传感器模糊数据融合的融合监测方法,将监测设备的多个传感器所获取的信息模糊化,再将其融合,从而获取设备精确的状态估计。实验表明:该方法优于传统的设备故障监测方法。     

An efficient implementation algorithm for generating de Bruijn sequences

A nonsingular feedback shift register will generate pairwise disconnecting cycles. To get a de Bruijn cycle, we put a different mark on the states that are on the different cycle. This could help us find adjacent cycles easily and join them together. We modify the marks of the states that on the joined cycles to the same mark. At the same time, the feedback function is modified accordingly. Then a full cycle is obtained when the marks of all the states on different cycles are modified to the same mark. At the same time, the feedback function that could generate the de Bruijn sequences is also obtained.     

An efficient genetic algorithm for job-shop scheduling problems with fuzzy processing time and fuzzy duedate

In this paper, by considering the imprecise or fuzzy nature of the data in real-world problems, job-shop scheduling problems with fuzzy processing time and fuzzy duedate are formulated and a genetic algorithm which is suitable for solving the formulated problems is proposed. On the basis of the agreement index of fuzzy duedate and fuzzy completion time, the formulated fuzzy job-shop scheduling problems are interpreted so as to maximize the minimum agreement index. For solving the formulated fuzzy job-shop scheduling problems, an efficient genetic algorithm is proposed by incorporating the concept of similarity among individuals into the genetic algorithms using the Gannt chart. As illustrative numerical examples, both 6×6 and 10×10 job-shop scheduling problems with fuzzy duedate and fuzzy processing time are considered. Through the comparative simulations with simulated annealing, the feasibility and effectiveness of the proposed method are demonstrated.     

Analysis of an efficient parallel implementation of active-set Newton algorithm

The Journal of Supercomputing - This paper presents an analysis of an efficient parallel implementation of the active-set Newton algorithm (ASNA), which is used to estimate the nonnegative weights...     

一种有效的增量顺序学习模糊神经网络

利用误差下降率定义输入数据对系统输出的敏感性,并以此作为规则产生标准,提出一种有效增量顺序学习模糊神经网络。将修剪策略引入规则产生过程,因此该算法产生的模糊神经网络不需要进行修剪。通过仿真实验,本算法在达到与其他算法相当性能的情况下,能够获得更高的准确率和更简单的结构。     

An efficient single output fuzzy control algorithm for adaptive applications

A new single output fuzzy control algorithm which is simple and efficient is developed in the paper. Assuming standard type membership functions, a fuzzy set is characterized in this approach by that element in the fuzzy set with maximal membership. Fuzzy rules are then represented by a set of numbers. The algorithm uses a matrix representation of the rules in which the input part of the rule is used as an index, and the indexed element is the corresponding output. This is shown to allow for easy expansion of the output universe. Modification and introduction of new rules are further shown to be very simple and as a salient feature the efficiency of the algorithm is found to increase, when the number of rules increases. This new algorithm is therefore particularly useful and efficient when combined with a rule adaption mechanism. Because of simplicity and efficiency, this algorithm is very suitable for implementation even on small micro processor systems, making adaptive fuzzy control feasible for industrial applications, where a fast and nonlinear control is required.     

On efficient implementation of an approximation algorithm for the Steiner tree problem

Summary This paper studies the design and implementation of an approximation algorithm for the Steiner tree problem. Given any undirected distance graph G and a set of Steiner points S, the algorithm produces a Steiner tree with total weight on its edges no more than 2(1–1/L) times the total weight on the optimal Steiner tree, where L is the number of leaves in the optimal Steiner tree. Our implementation of the algorithm, in the worst case, makes it run in 0(¦E _g¦+¦V _g–S¦log¦V _g–S¦+¦S¦log ¦S¦) time for general graph G and in 0(¦S¦ log¦S¦+M log (M,¦V _g–S¦)) time for sparse graph G, where E _g is the set of edges in G, V_g is the set of vertices in G, M = min {¦E _g, (¦V _g–S¦–1)²/2} and (x,y) = min {i¦log⁽ⁱ⁾ y x/y}.The implementation is not likely to be improved significantly without the improvement of the shortest paths algorithm and the minimum spanning tree algorithm as the algorithm essentially composes of the computation of the multiple sources shortest paths of a graph with ¦V _g¦ vertices and ¦E _g¦ edges and the minimum spanning tree of a graph with ¦V _g–S¦ vertices and M edges.     

An efficient hardware implementation of parallel EBCOT algorithm for JPEG 2000

With the augmentation in multimedia technology, demand for high-speed real-time image compression systems has also increased. JPEG 2000 still image compression standard is developed to accommodate such application requirements. Embedded block coding with optimal truncation (EBCOT) is an essential and computationally very demanding part of the compression process of JPEG 2000 image compression standard. Various applications, such as satellite imagery, medical imaging, digital cinema, and others, require high speed and performance EBCOT architecture. In JPEG 2000 standard, the context formation block of EBCOT tier-1 contains high complexity computation and also becomes the bottleneck in this system. In this paper, we propose a fast and efficient VLSI hardware architecture design of context formation for EBCOT tier-1. A high-speed parallel bit-plane coding (BPC) hardware architecture for the EBCOT module in JPEG 2000 is proposed and implemented. Experimental results show that our design outperforms well-known techniques with respect to the processing time. It can reach 70 % reduction when compared to bit plane sequential processing.     

An efficient implementation of the equilibrium algorithm for housing markets with duplicate houses

We propose an asymptotically optimal implementation of the equilibrium algorithm for housing markets with duplicate houses and strict preferences. It is based on Tarjan?s depth-first search algorithm for strongly connected components of a digraph.     

基于遗传优化的张力模糊控制

针对张力系统实时性的要求, 同时为了保证控制系统可靠性, 提出了在线和离线遗传优化的张力系统模糊控制方法. 首先, 离线部分采用遗传算法优化输入输出量的隶属度函数, 获得控制量输出表, 供在线调用. 然后, 在线部分采用超代遗传算法(HGGA)优化输入量化因子和输出比例因子, 缩短算法运行时间, 加快收敛速度. 同时为了补偿系统的时滞, 调整了被调量的当前误差和误差变化率. 最后在张力平台上验证了上述算法. 结果表明, 上述控制方法实现了张力实时控制.     

A convergence theorem for the fuzzy subspace clustering (FSC) algorithm

We establish the convergence of the fuzzy subspace clustering (FSC) algorithm by applying Zangwill's convergence theorem. We show that the iteration sequence produced by the FSC algorithm terminates at a point in the solution set S or there is a subsequence converging to a point in S. In addition, we present experimental results that illustrate the convergence properties of the FSC algorithm in various scenarios.     

A highly efficient implementation of a backpropagation learning algorithm using matrix ISA

BackPropagation (BP) is the most famous learning algorithm for Artificial Neural Networks (ANN). BP has received intensive research efforts to exploit its parallelism in order to reduce the training time for complex problems. A modified version of BP based on matrix–matrix multiplication was proposed for parallel processing. In this paper, we present the implementation of Matrix BackPropagation (MBP) using scalar, vector, and matrix Instruction Set Architectures (ISAs). Besides this, we show that the performance of the MBP is improved by switching from scalar ISA to vector ISA. It is further improved by switching from vector ISA to matrix ISA. On a practical application, speech recognition, the speedup of training a neural network using unrolling scalar ISA over scalar ISA is 1.83. On eight parallel lanes, the speedups of using vector, unrolling vector, and matrix ISAs are respectively 10.33, 11.88, and 15.36, where the maximum theoretical speedup is 16. The results obtained show that the use of matrix ISA gives a performance close to optimal, because of reusing the loaded data, decreasing the loop overhead, and overlapping the memory operations with arithmetic operations.