Decision rules for a hierarchical classifier

Two hierarchical classifier strategies which minimize the global and local probabilities of misclassification, respectively are presented. The modified version of the k-NN rule for a hierarchical classifier is proposed. Numerical examples are given.     

Parameterized complexity of candidate control in elections and related digraph problems

There are different ways for an external agent to influence the outcome of an election. We concentrate on “control” by adding or deleting candidates. Our main focus is to investigate the parameterized complexity of various control problems for different voting systems. To this end, we introduce natural digraph problems that may be of independent interest. They help in determining the parameterized complexity of control for different voting systems including Llull, Copeland, and plurality voting. Devising several parameterized reductions, we provide an overview of the parameterized complexity of the digraph and control problems with respect to natural parameters such as adding/deleting only a bounded number of candidates or having only few voters.     

Text document clustering based on neighbors

Clustering is a very powerful data mining technique for topic discovery from text documents. The partitional clustering algorithms, such as the family of k-means, are reported performing well on document clustering. They treat the clustering problem as an optimization process of grouping documents into k clusters so that a particular criterion function is minimized or maximized. Usually, the cosine function is used to measure the similarity between two documents in the criterion function, but it may not work well when the clusters are not well separated. To solve this problem, we applied the concepts of neighbors and link, introduced in [S. Guha, R. Rastogi, K. Shim, ROCK: a robust clustering algorithm for categorical attributes, Information Systems 25 (5) (2000) 345–366], to document clustering. If two documents are similar enough, they are considered as neighbors of each other. And the link between two documents represents the number of their common neighbors. Instead of just considering the pairwise similarity, the neighbors and link involve the global information into the measurement of the closeness of two documents. In this paper, we propose to use the neighbors and link for the family of k-means algorithms in three aspects: a new method to select initial cluster centroids based on the ranks of candidate documents; a new similarity measure which uses a combination of the cosine and link functions; and a new heuristic function for selecting a cluster to split based on the neighbors of the cluster centroids. Our experimental results on real-life data sets demonstrated that our proposed methods can significantly improve the performance of document clustering in terms of accuracy without increasing the execution time much.     

Hierarchical classifiers based on neighbourhood criteria with adaptive computational cost

Classifiers based on neighbourhood concept require a high computational cost when the Reference Patterns Set is large. In this paper, we propose the use of hierarchical classifiers to reduce this computational cost, maintaining the hit rate in the recognition of handwritten digits. The hierarchical classifiers reach the hit rate of the best individual classifier. We have used NIST Database to carry out the experimentation, and we have worked with two test sets: in Test 1 (SD3, SD19) the hit rate is 99.54%, with a speed-up of 40.6, and in Test 2 (SD7), the hit rate is 97.51% with a speed-up of 15.7.     

Information based data anonymization for classification utility

Anonymization is a practical approach to protect privacy in data. The major objective of privacy preserving data publishing is to protect private information in data whereas data is still useful for some intended applications, such as building classification models. In this paper, we argue that data generalization in anonymization should be determined by the classification capability of data rather than the privacy requirement. We make use of mutual information for measuring classification capability for generalization, and propose two k-anonymity algorithms to produce anonymized tables for building accurate classification models. The algorithms generalize attributes to maximize the classification capability, and then suppress values by a privacy requirement k (IACk) or distributional constraints (IACc). Experimental results show that algorithm IACk supports more accurate classification models and is faster than a benchmark utility-aware data anonymization algorithm.     

A linear-time algorithm for finding a sparsek-connected spanning subgraph of ak-connected graph

We show that anyk-connected graphG = (V, E) has a sparsek-connected spanning subgraphG = (V, E) with ¦E¦ =O(k¦V¦) by presenting anO(¦E¦)-time algorithm to find one such subgraph, where connectivity stands for either edge-connectivity or node-connectivity. By using this algorithm as preprocessing, the time complexities of some graph problems related to connectivity can be improved. For example, the current best time boundO(max{k ²¦V¦^1/2,k¦V¦}¦E¦) to determine whether node-connectivityK(G) of a graphG = (V, E) is larger than a given integerk or not can be reduced toO(max{k ³¦V¦^3/2,k ²¦V¦²}).The first author was partially supported by the Grant-in-Aid for Encouragement of Young Scientists of the Ministry of Education, Science and Culture of Japan and by the subvention to young scientists by the Research Foundation of Electrotechnology of Chubu.     

On the weighted sensitivity minimization problem for delay systems

We consider the H^∞-optimal sensitivity problem for delay systems. In particular, we consider computation of μ:= inf {|W-φq|_∞ : q ε H^∞(j )} where W(s) is any function in RH^∞(j ), and φ in H^∞(j ) is any inner function. We derive a new explicit solution in the pure delay case where φ = e^−sh, h > 0.     

A hybrid medical decision making system based on principles component analysis, k-NN based weighted pre-processing and adaptive neuro-fuzzy inference system

Proper interpretation of the thyroid gland functional data is an important issue in diagnosis of thyroid disease. The primary role of the thyroid gland is to help regulation of the body's metabolism. Thyroid hormone produced by thyroid gland provides this. Production of too little thyroid hormone (hypo-thyroidism) or production of too much thyroid hormone (hyper-thyroidism) defines the types of thyroid disease. It is evident that usage of machine learning methods in disease diagnosis has been increasing gradually. In this study, diagnosis of thyroid disease, which is a very common and important disease, was conducted with such a machine learning system. In this study, we have detected on thyroid disease using principles component analysis (PCA), k-nearest neighbor (k-NN) based weighted pre-processing and adaptive neuro-fuzzy inference system (ANFIS). The proposed system has three stages. In the first stage, dimension of thyroid disease dataset that has 5 features is reduced to 2 features using principles component analysis. In the second stage, a new weighting scheme based on k-nearest neighbor (k-NN) method was utilized as a pre-processing step before the main classifier. Then, in the third stage, we have used adaptive neuro-fuzzy inference system to diagnosis of thyroid disease. We took the thyroid disease dataset used in our study from the UCI machine learning database. The obtained classification accuracy of our system was 100% and it was very promising with regard to the other classification applications in literature for this problem.     

Closed formulae for a parametric-mixed-sensitivity problem for Pritchard-Salamon systems

The parametric-mixed-sensitivity problem is posed for the class of irrational transfer matrices with a realization as a Pritchard-Salamon system. An exact solution is obtained in terms of two uncoupled, standard Riccati equations.     

Attribute reduction based on evidence theory in incomplete decision systems

Attribute reduction is a basic issue in knowledge representation and data mining. This paper deals with attribute reduction in incomplete information systems and incomplete decision systems based on Dempster-Shafer theory of evidence. The concepts of plausibility reduct and belief reduct in incomplete information systems as well as relative plausibility reduct and relative belief reduct in incomplete decision systems are introduced. It is shown that in an incomplete information system an attribute set is a belief reduct if and only if it is a classical reduct and a plausibility consistent set must be a classical consistent set. In a consistent incomplete decision system, the concepts of relative reduct, relative plausibility reduct, and relative belief reduct are all equivalent. In an inconsistent incomplete decision system, an attribute set is a relative plausibility reduct if and only if it is a relative reduct, a plausibility consistent set must be a belief consistent set, and a belief consistent set is not a plausibility consistent set in general.     

A geometric approach for shared secrets, a refinement

A refinement to the (k,n) threshold scheme proposed by Wu and He [1] is presented. It has been found that usable primes p need not be confined to the form p ≡ ±3 (mod 8) as suggested originally. Our constructive proof also lead to a different algorithm for implementation. This implementation dispenses with the directory file suggested in [1] which can be prohibitively large when the scheme is implemented with large p using the original proposal.     

Choice of approximator and design of penalty function for an approximate dynamic programming based control approach

This paper investigates the choice of function approximator for an approximate dynamic programming (ADP) based control strategy. The ADP strategy allows the user to derive an improved control policy given a simulation model and some starting control policy (or alternatively, closed-loop identification data), while circumventing the ‘curse-of-dimensionality’ of the traditional dynamic programming approach. In ADP, one fits a function approximator to state vs. ‘cost-to-go’ data and solves the Bellman equation with the approximator in an iterative manner. A proper choice and design of function approximator is critical for convergence of the iteration and the quality of final learned control policy, because an approximation error can grow quickly in the loop of optimization and function approximation. Typical classes of approximators used in related approaches are parameterized global approximators (e.g. artificial neural networks) and nonparametric local averagers (e.g. k-nearest neighbor). In this paper, we assert on the basis of some case studies and a theoretical result that a certain type of local averagers should be preferred over global approximators as the former ensures monotonic convergence of the iteration. However, a converged cost-to-go function does not necessarily lead to a stable control policy on-line due to the problem of over-extrapolation. To cope with this difficulty, we propose that a penalty term be included in the objective function in each minimization to discourage the optimizer from finding a solution in the regions of state space where the local data density is inadequately low. A nonparametric density estimator, which can be naturally combined with a local averager, is employed for this purpose.     

Robust transient stabilisation problem for a synchronous generator in a power network

The robust transient stabilisation problem (with stability proof) of a synchronous generator in an uncertain power network with transfer conductances is rigorously formulated and solved. The generator angular speed and electrical power are required to be kept close, when mechanical and electrical perturbations occur, to the synchronous speed and mechanical input power, respectively, while the generator terminal voltage is to be regulated, when perturbations are removed, to its pre-fault reference constant value. A robust adaptive nonlinear feedback control algorithm is designed on the basis of a third-order model of the synchronous machine: only two system parameters (synchronous machine damping and inertia constants) along with upper and lower bounds on the remaining uncertain ones are supposed to be known. The conditions to be satisfied by the remote network dynamics for guaranteeing ?₂ and ?_∞ robustness and asymptotic relative speed and voltage regulation to zero are weaker than those required by the single machine-infinite bus approximation: dynamic interactions between the local deviations of the generator states from the corresponding equilibrium values and the remote generators states are allowed.     

A constant approximation algorithm for the densest k-subgraph problem on chordal graphs

The densest k-subgraph (DkS) problem asks for a k-vertex subgraph of a given graph with the maximum number of edges. The DkS problem is NP-hard even for special graph classes including bipartite, planar, comparability and chordal graphs, while no constant approximation algorithm is known for any of these classes. In this paper we present a 3-approximation algorithm for the class of chordal graphs. The analysis of our algorithm is based on a graph theoretic lemma of independent interest.     

Extended Nehari problem for time-variant discrete systems

In this paper a suboptimal solution to the time-variant discrete version of the extended Nehari problem is given. The main tool used to obtain such a solution, with prescribed tolerance, is the so-called anticausal stabilizing solution to the reverse discrete-time Riccati equation.     

An LMI solution to the robust synthesis problem for multi-rate sampled-data systems

In this paper we address the asynchronous multi-rate sampled-data H_∞ synthesis problem. Necessary and sufficient conditions are given for the existence of a controller achieving the desired performance, and the problem is shown to be equivalent to a convex optimization problem expressed in the form of linear operator inequalities. In the case where the sample and hold rates are synchronous, these operator inequalities reduce to linear matrix inequalities, for which standard numerical software is available.     

GH 2 control for uncertain discrete-time-delay fuzzy systems based on a switching fuzzy model and piecewise Lyapunov function

Generalized H2 （GH2） stability analysis and controller design of the uncertain discrete-time Takagi-Sugeno （T-S） fuzzy systems with state delay are studied based on a switching fuzzy model and piecewise Lyapunov function. GH2 stability sufficient conditions are derived in terms of linear matrix inequalities （LMIs）. The interactions among the fuzzy subsystems are considered. Therefore, the proposed conditions are less conservative than the previous results. Since only a set of LMIs is involved, the controller design is quite simple and numerically tractable. To illustrate the validity of the proposed method, a design example is provided.     

大规模散乱点的k邻域快速搜索算法

针对大规模散乱点数据k最近邻域搜索速度慢和稳定性差的问题,提出一种新的k邻域快速搜索算法.首先,引入空间分块策略将数据集中的点归入不同的子空间;其次,动态控制搜索步长的改变量,根据点到其自身小立方体边界的最小距离保证搜索结果的准确性;最后,通过改变预筛选点数量的右侧控制阈值来消除已有算法中由于初始数值不当引起的死循环.实验结果表明该算法对初始搜索步长、搜索步长增量、采样密度和不同的拓扑结构具有较强的稳定性,并且能更快地完成k邻域搜索.     

Some remarks on Hamiltonians and the infinite-dimensional one block H problem

In this note, a simple proof is given for the Hamiltonian solution to the H^∞ optimal sensitivity for plants with arbitrary inner transfer function. The approach combines skew Toeplitz theory and state-space representations, and gives rise to a straightforward and basis-free methodology.