基于多层次模糊关联算法的通用航空产业知识挖掘研究

为挖掘通用航空产业领域知识的类型与发展规律,明确产业规划、推动产业健康发展,利用采集的3869份通用航空产业主题相关的网页资料,根据主题信息的关键词对通用航空产业领域知识进行分类,并基于多层次模糊关联算法进行知识挖掘分析.结果表明,通用航空产业领域知识中的通用航空产业主体与通用航空产业产品存在着紧密的联系和规则,而且采...     

A sequential pattern mining algorithm using rough set theory

Sequential pattern mining is a crucial but challenging task in many applications, e.g., analyzing the behaviors of data in transactions and discovering frequent patterns in time series data. This task becomes difficult when valuable patterns are locally or implicitly involved in noisy data. In this paper, we propose a method for mining such local patterns from sequences. Using rough set theory, we describe an algorithm for generating decision rules that take into account local patterns for arriving at a particular decision. To apply sequential data to rough set theory, the size of local patterns is specified, allowing a set of sequences to be transformed into a sequential information system. We use the discernibility of decision classes to establish evaluation criteria for the decision rules in the sequential information system.     

A Model for Multi-timescaled Sequential Decision-making Processes with Adversary

Extending the multi-timescale model proposed by the author et al. in the context of Markov decision processes, this paper proposes a simple analytical model called M timescale two-person zero-sum Markov Games (MMGs) for hierarchically structured sequential decision-making processes in two players' competitive situations where one player (the minimizer) wishes to minimize their cost that will be paid to the adversary (the maximizer). In this hierarchical model, for each player, decisions in each level in the M-level hierarchy are made in M different discrete timescales and the state space and the control space of each level in the hierarchy are non-overlapping with those of the other levels, respectively, and the hierarchy is structured in a "pyramid" sense such that a decision made at level m (slower timescale) state and/or the state will affect the evolutionary decision making process of the lower-level m+1 (faster timescale) until a new decision is made at the higher level but the lower-level decisions themselves do not affect the transition dynamics of higher levels. The performance produced by the lower-level decisions will affect the higher level decisions for each player. A hierarchical objective function for the minimizer and the maximizer is defined, and from this we define "multi-level equilibrium value function" and derive a "multi-level equilibrium equation". We also discuss how to solve hierarchical games exactly.     

网站用户登录信息挖掘特征规则

本文首先研究了基本的面向属性归纳，提出了从网站用户登录信息中挖掘用户特征规则的思路。问题从解决多属性归纳着手，特点是首先建立概念树，然后用条件属性组合与约束的方法进行挖掘。实验表明，本文设计的模型能客观地描述客户行为，为从Web信息挖掘客户特征规则提出了一条有效的途径。     

Sequential heuristic for the two-dimensional bin-packing problem

A heuristic approach for the two-dimensional bin-packing problem is proposed. The algorithm is based on the sequential heuristic procedure that generates each pattern to produce some items and repeats until all items are produced. Both guillotine and non-guillotine patterns can be used. Each pattern is obtained from calling a pattern-generation procedure, where the objective is to maximize the pattern value. The item values are adjusted after the generation of each pattern using a value correction formula. The algorithm is compared with five published algorithms, using 50 groups of benchmark instances. The results indicate that the algorithm is the most efficient in improving solution quality.     

Art networks with geometrical distances

In this paper, ART networks (Fuzzy ART and Fuzzy ARTMAP) with geometrical norms are presented. The category choice of these networks is based on the L_p norm. Geometrical properties of these architectures are presented. Comparisons between this category choice and the category choice of the ART networks are illustrated. And simulation results on the databases taken from the UCI repository are performed. It will be shown that using the L_p norm is geometrically more attractive. It will operate directly on the input patterns without the need for doing any preprocessing. It should be noted that the ART architecture requires two preprocessing steps: normalization and complement coding. Simulation results on different databases show the good generalization performance of the Fuzzy ARTMAP with L_p norm compared to the performance of a typical Fuzzy ARTMAP.     

A multilevel programming approach to decentralized (or hierarchical) resource allocation systems

In many decision processes there is a hierarchy of decision-makers and decisions are taken at different levels in this hierarchy. In business (and many other practical activities) decision making has changed over the last decades. From a single person (the boss!) and a single criterion (e.g. profit), decision environments have developed increasingly to become multi-person and multi-criteria and even multi-level (or hierarchical) situations. In organization with hierarchical decision systems, the sequential and preemptive nature of the decision process makes the problem of selecting an optimum strategy and action very different from the usual operations research methods. Therefore, a multilevel programming approach is considered in modeling such problems. In particular a three-level mathematical programming model has been proposed for an optimal resource allocation problem in Ethiopian universities. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Model predictive control of nonlinear hybrid systems with discrete inputs employing a hybrid fuzzy model

The paper deals with model predictive control (MPC) of nonlinear hybrid systems with discrete inputs based on reachability analysis. In order to implement a MPC algorithm, a model of the process that we are dealing with is needed. In the paper, a hybrid fuzzy modelling approach is proposed. The hybrid system hierarchy is explained and the Takagi–Sugeno fuzzy formulation for hybrid fuzzy modelling purposes is tackled. An efficient method of identification of the hybrid fuzzy model is also discussed.

An algorithm that is–due to its MPC nature–suitable for controlling a wide spectrum of systems (provided that they have discrete inputs only) is presented.

The benefits of the algorithm employing a hybrid fuzzy model are verified on a batch reactor example. The results suggest that by suitably determining the cost function, satisfactory control can be attained, even when dealing with complex hybrid–nonlinear–stiff systems such as the batch reactor.

Finally, a comparison between MPC employing a hybrid linear model and a hybrid fuzzy model is carried out. It has been established that the latter approach clearly outperforms the approach where a linear model is used.     

A mathematical programming viewpoint for solving the ultimate pit problem

In 1965 Helmut Lerchs and Ingo Grossmann presented to the mining community an algorithm to find the optimum design for an open pit mine. In their words, “the objective is to design the contour of a pit so as to maximize the difference between total mine value of the ore extracted and the total extraction cost of ore and waste”. They modeled the problem in graph theoretic terms and showed that an optimal solution of the ultimate pit problem is equivalent to finding the maximum closure of their graph based model. In this paper, we develop a network flow algorithm based on the dual to solve the same problem. We show how this algorithm is closely related to Lerchs and Grossmann's and how the steps in their algorithm can be viewed in mathematical programming terms. This analysis adds insight to the algorithm of Lerchs and Grossmann and shows where it can be made more efficient. As in the case Lerchs and Grossmann, our algorithm allows us to use very efficient data structures based on graphs that represent the data and constraints.. 1782 1528 V 3     

On the parallel complexity of hierarchical clustering and CC‐complete problems

Complex data sets are often unmanageable unless they can be subdivided and simplified in an intelligent manner. Clustering is a technique that is used in data mining and scientific analysis for partitioning a data set into groups of similar or nearby items. Hierarchical clustering is an important and well‐studied clustering method involving both top‐down and bottom‐up subdivisions of data. In this article we address the parallel complexity of hierarchical clustering. We describe known sequential algorithms for top‐down and bottom‐up hierarchical clustering. The top‐down algorithm can be parallelized, and when there are n points to be clustered, we provide an O(log n)‐time, n²‐processor Crew Pram algorithm that computes the same output as its corresponding sequential algorithm. We define a natural decision problem based on bottom‐up hierarchical clustering, and add this HIERARCHICAL CLUSTERING PROBLEM (HCP) to the slowly growing list of CC‐complete problems, thereby showing that HCP is one of the computationally most difficult problems in the COMPARATOR CIRCUIT VALUE PROBLEM class. This class contains a variety of interesting problems, and now for the first time a problem from data mining as well. By proving that HCP is CC‐complete, we have demonstrated that HCP is very unlikely to have an NC algorithm. This result is in sharp contrast to the NC algorithm which we give for the top‐down sequential approach, and the result surprisingly shows that the parallel complexities of the top‐down and bottom‐up approaches are different, unless CC equals NC. In addition, we provide a compendium of all known CC‐complete problems. © 2008 Wiley Periodicals, Inc. Complexity, 2008     

Interpretation of association rules in multi-tier structures

Dealing with the large amount of data resulting from association rule mining is a big challenge. The essential issue is how to provide efficient methods for summarizing and representing meaningful discovered knowledge from databases. This paper presents a new approach called multi-tier granule mining to improve the performance of association rule mining. Rather than using patterns, it uses granules to represent knowledge that is implicitly contained in relational databases. This approach also uses multi-tier structures and association mappings to interpret association rules in terms of granules. Consequently, association rules can be quickly assessed and meaningless association rules can be justified according to these association mappings. The experimental results indicate that the proposed approach is promising.     

A scheduling algorithm for open pit mines

An open pit (opencast) mine can be described by a three-dimensionalarray of blocks, each of which is assigned a number of valuesdefining its characteristics. Scheduling an open pit consistsin finding a sequence in which the blocks should be removedfrom the mine in order to maximize the total discounted profitfrom the mine subject to a variety of technical and economicconstraints. This paper proposes to model the mine-schedulingproblem as one of sequential optimization, and develops an algorithmfor its solution. To overcome the difficulty caused by an extremelylarge number of states in the problem at hand, we consider atechnique which is related to dynamic programming but avoidsthe complete enumeration of the state space. Our algorithm isa combination of this technique with powerful heuristics derivedfrom the specific properties of open pit mining.     

An efficient algorithm for mining high utility itemsets with negative item values in large databases

Utility itemsets typically consist of items with different values such as utilities, and the aim of utility mining is to identify the itemsets with highest utilities. In the past studies on utility mining, the values of utility itemsets were considered as positive. In some applications, however, an itemset may be associated with negative item values. Hence, discovery of high utility itemsets with negative item values is important for mining interesting patterns like association rules. In this paper, we propose a novel method, namely HUINIV (High Utility Itemsets with Negative Item Values)-Mine, for efficiently and effectively mining high utility itemsets from large databases with consideration of negative item values. To the best of our knowledge, this is the first work that considers the concept of negative item values in utility mining. The novel contribution of HUINIV-Mine is that it can effectively identify high utility itemsets by generating fewer high transaction-weighted utilization itemsets such that the execution time can be reduced substantially in mining the high utility itemsets. In this way, the process of discovering all high utility itemsets with consideration of negative item values can be accomplished effectively with less requirements on memory space and CPU I/O. This meets the critical requirements of temporal and spatial efficiency for mining high utility itemsets with negative item values. Through experimental evaluation, it is shown that HUINIV-Mine outperforms other methods substantially by generating much less candidate itemsets under different experimental conditions.     

A modified fuzzy clustering for documents retrieval: application to document categorization

The paper advocates the use of a new fuzzy-based clustering algorithm for document categorization. Each document/datum will be represented as a fuzzy set. In this respect, the fuzzy clustering algorithm, will be constrained additionally in order to cluster fuzzy sets. Then, one needs to find a metric measure in order to detect the overlapping between documents and the cluster prototype (category). In this respect, we use one of the interclass probabilistic reparability measures known as Bhattacharyya distance, which will be incorporated in the general scheme of the fuzzy c-means algorithm for measuring the overlapping between fuzzy sets. This enables the introduction of fuzziness in the document clustering in the sense that it allows a single document to belong to more than one category. This is in line with semantic multiple interpretations conveyed by single words, which support multiple membership to several classes. Performances of the algorithms will be illustrated using a case study from the construction sector.     

Using data mining to identify structural rules in proteins

The progress in bioinformatics and biotechnology area has generated a huge amount of sequences that requires a detailed analysis. There are several data mining techniques that can be used to discovery patterns in large databases. This paper describes the development of a tool/methodology to extract hydrophobicity patterns/profiles that archives a specific secondary structure in proteins. The results indicate that association rules can be efficient method to investigate this kind of problem. This work contributes for two areas: prediction of protein structure and protein folding.     

A data parallel augmenting path algorithm for the dense linear many-to-one assignment problem

The purpose of this study is to describe a data parallel primal-dual augmenting path algorithm for the dense linear many-to-one assignment problem also known as semi-assignment. This problem could for instance be described as assigning n persons to m(n) job groups.The algorithm is tailored specifically for massive SIMD parallelism and employs, in this context, a new efficient breadth-first-search augmenting path technique which is found to be faster than the shortest augmenting path search normally used in sequential algorithms for this problem. We show that the best known sequential computational complexity of O(mn ² ) for dense problems, is reduced to the parallel complexity of O(mn), on a machine with n processors supporting reductions in O(1) time. The algorithm is easy to implement efficiently on commercially available massively parallel computers. A range of numerical experiments are performed on a Connection Machine CM200 and a MasPar MP-2. The tests show the good performance of the proposed algorithm.     

Dynamic Multi-level Overlay Graphs for Shortest Paths

Multi-level overlay graphs represent a speed-up technique for shortest paths computation which is based on a hierarchical decomposition of a weighted directed graph G. They have been shown to be experimentally efficient, especially when applied to timetable information. However, no theoretical result on the cost of constructing, maintaining and querying multi-level overlay graphs in a dynamic environment is known. In this paper, we show theoretical properties of multi-level overlay graphs that lead us to the definition of a new data structure for the computation and the maintenance of an overlay graph of G while weight decrease or weight increase operations are performed on G. Our solution is theoretically faster than the recomputation from scratch and allows queries that can be performed more efficiently than running Dijkstra’s shortest paths algorithm on G. This work was partially supported by the Future and Emerging Technologies Unit of EC (IST priority – 6th FP), under contract no. FP6-021235-2 (project ARRIVAL).     

Practical and flexible pattern matching over Ziv–Lempel compressed text

We address the problem of string matching on Ziv–Lempel compressed text. The goal is to search for a pattern in a text without uncompressing it. This is a highly relevant issue to keep compressed text databases where efficient searching is still possible. We develop a general technique for string matching when the text comes as a sequence of blocks. This abstracts the essential features of Ziv–Lempel compression. We then apply the scheme to each particular type of compression. We present an algorithm to find all the matches of a pattern in a text compressed using LZ77. When we apply our scheme to LZ78, we obtain a much more efficient search algorithm, which is faster than uncompressing the text and then searching it. Finally, we propose a new hybrid compression scheme which is between LZ77 and LZ78, being in practice as good to compress as LZ77 and as fast to search as LZ78. We show also how to search for some extended patterns on Ziv–Lempel compressed text, such as classes of characters and approximate string matching.     

Edge-Coloring Partialk-Trees

Many combinatorial problems can be efficiently solved for partialk-trees (graphs of treewidth bounded byk). The edge-coloring problem is one of the well-known combinatorial problems for which no efficient algorithms were previously known, except a polynomial-time algorithm of very high complexity. This paper gives a linear-time sequential algorithm and an optimal parallel algorithm which find an edge-coloring of a given partialk-tree with the minimum number of colors for fixedk.