Fuzzy clustering using multiple Gaussian kernels with optimized-parameters

In this paper, we propose a new kernel-based fuzzy clustering algorithm which tries to find the best clustering results using optimal parameters of each kernel in each cluster. It is known that data with nonlinear relationships can be separated using one of the kernel-based fuzzy clustering methods. Two common fuzzy clustering approaches are: clustering with a single kernel and clustering with multiple kernels. While clustering with a single kernel doesn’t work well with “multiple-density” clusters, multiple kernel-based fuzzy clustering tries to find an optimal linear weighted combination of kernels with initial fixed (not necessarily the best) parameters. Our algorithm is an extension of the single kernel-based fuzzy c-means and the multiple kernel-based fuzzy clustering algorithms. In this algorithm, there is no need to give “good” parameters of each kernel and no need to give an initial “good” number of kernels. Every cluster will be characterized by a Gaussian kernel with optimal parameters. In order to show its effective clustering performance, we have compared it to other similar clustering algorithms using different databases and different clustering validity measures.     

On an inequality by N. Trudinger and J. Moser and related elliptic equations

It has been shown by Trudinger and Moser that for normalized functions u of the Sobolev space ??^{1, N} (Ω), where Ω is a bounded domain in ?^N, one has ∫_Ω exp(α_N|u|^{N/(N ? 1)})dx ≤ C_N, where α_N is an explicit constant depending only on N, and C_N is a constant depending only on N and Ω. Carleson and Chang proved that there exists a corresponding extremal function in the case that Ω is the unit ball in ?^N. In this paper we give a new proof, a generalization, and a new interpretation of this result. In particular, we give an explicit sequence that is maximizing for the above integral among all normalized “concentrating sequences.” As an application, the existence of a nontrivial solution for a related elliptic equation with “Trudinger‐Moser” growth is proved. © 2002 John Wiley & Sons, Inc.     

Global minimization algorithms for concave quadratic programming problems

Abstract: In this article, we consider the concave quadratic programming problem which is known to be NP hard. Based on the improved global optimality conditions by [Dür, M., Horst, R. and Locatelli, M., 1998, Necessary and sufficient global optimality conditions for convex maximization revisited, Journal of Mathematical Analysis and Applications, 217, 637–649] and [Hiriart-Urruty, J.B. and Ledyav, J.S., 1996, A note in the characterization of the global maxima of a convex function over a convex set, Journal of Convex Analysis, 3, 55–61], we develop a new approach for solving concave quadratic programming problems. The main idea of the algorithms is to generate a sequence of local minimizers either ending at a global optimal solution or at an approximate global optimal solution within a finite number of iterations. At each iteration of the algorithms we solve a number of linear programming problems with the same constraints of the original problem. We also present the convergence properties of the proposed algorithms under some conditions. The efficiency of the algorithms has been demonstrated with some numerical examples.     

Un modéle d'lnspections optimales

We consider the following model: we inspect the motion of a Markov process with which an “evolution cost” is associated. We inspect the process at times T ₁…, T _n ,…. If when we inspect, its value is in a given set A, it continues its evolution, otherwise we kill it. At each inspection we associate an "inspection cost" and a "killing cost". The problem consists of finding a sequence of optimal inspections. After the modelization we construct the value function by an iterative procedure as in impulse control theory, by using the theory of analytic functions and theorems of section. Thanks to the criteria of optimality we get a sequence of optimal inspections under very general hypotheses.     

On the lower semicontinuity of optimal solution sets

We study the lower semicontinuity of the optimal solution set of a parametric optimization problem. Our results sharpen the main results of Zhao (1997, The lower semicontinuity of optimal solution sets. Journal of Mathematical Analysis and Applications, 207, 240–254. Ref. ). Namely, it is shown that the conclusion of Theorem 1 of is still valid under weaker assumptions, and the conditions on “ε-nontriviality” and uniform continuity of the objective function in Theorems 2 and 3 of can be omitted.     

Reachable solution set of a fuzzy relation equation

The largest element of the solution set of a fuzzy relation equation has been found by E. Sanchez (Inform. and Control30 (1976), 38–48) but the smallest element does not exist. It is difficult to expose the solution of the fuzzy relation equation. In the case of the determinate relation equations, complete consequences have been found by Wang Peizhuang and Yuan Meng (“Relation Equation and Relation Inequalities,” Selected papers on fuzzy subsets, Beijing Normal University, March 1980). In the case of the fuzzy relation equations, Wang and Yuan have given a class of special solutions which probably possesses some minimality characterizations. In this paper, the reachable solution set of the fuzzy relation equation is given. For the fuzzy relation equation on the finite sets, a neat and efficient method for solving it is given.     

Learning from imprecise and fuzzy observations: Data disambiguation through generalized loss minimization

Methods for analyzing or learning from “fuzzy data” have attracted increasing attention in recent years. In many cases, however, existing methods (for precise, non-fuzzy data) are extended to the fuzzy case in an ad-hoc manner, and without carefully considering the interpretation of a fuzzy set when being used for modeling data. Distinguishing between an ontic and an epistemic interpretation of fuzzy set-valued data, and focusing on the latter, we argue that a “fuzzification” of learning algorithms based on an application of the generic extension principle is not appropriate. In fact, the extension principle fails to properly exploit the inductive bias underlying statistical and machine learning methods, although this bias, at least in principle, offers a means for “disambiguating” the fuzzy data. Alternatively, we therefore propose a method which is based on the generalization of loss functions in empirical risk minimization, and which performs model identification and data disambiguation simultaneously. Elaborating on the fuzzification of specific types of losses, we establish connections to well-known loss functions in regression and classification. We compare our approach with related methods and illustrate its use in logistic regression for binary classification.     

Embracing the giant component

Consider a game in which edges of a graph are provided a pair at a time, and the player selects one edge from each pair, attempting to construct a graph with a component as large as possible. This game is in the spirit of recent papers on avoiding a giant component, but here we embrace it. We analyze this game in the offline and online setting, for arbitrary and random instances, which provides for interesting comparisons. For arbitrary instances, we find that the competitive ratio (the best possible solution value divided by best possible online solution value) is large. For “sparse” random instances the competitive ratio is also large, with high probability (whp); If the instance has ¼(1 + ε)n random edge pairs, with 0 < ε ≤ 0.003, then any online algorithm generates a component of size O((log n)^3/2) whp , while the optimal offline solution contains a component of size Ω(n) whp . For “dense” random instances, the average‐case competitive ratio is much smaller. If the instance has ½(1 ? ε)n random edge pairs, with 0 < ε ≤ 0.015, we give an online algorithm which finds a component of size Ω(n) whp . © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

Randomness friendly graphs

We consider the two problems from extremal graph theory: 1. Given integer N, real p ϵ (0, 1) and a graph G, what is the minimum number of copies of G a graph H with N vertices and pN²/2 edges can contain? 2. Given an integer N and a graph G, what is the minimum number of copies of G an N-vertex graph H and its complement H¯ can contain altogether? In each of the problems, we say that G is “randomness friendly” if the number of its copies is nearly minimal when H is the random graph. We investigate how the two classes of graphs are related: the graphs which are “randomness friendly” in Problem 1 and those of Problem 2. In the latter problem, we discover new families of graphs which are “randomness friendly.” © 1996 John Wiley & Sons, Inc.     

The almost chebyshev property in linear semi-infinite programming

We consider a linear semi-infinite programming problem where the index set of the constraints is compact and the constraint functions are continuous on it. The set of all continuous functions on this index set as right hand sides are the parameter set. We investigate how large various unicity sets are.We state a condition on the objective function vector and the “matrix” of the problem which characterizes when the set of a parameters with a non-unique optimal point is a set of the first Baire category in the solvability set. This is the case if and only if the unicity set is a dense subset of the solvability set. Under the same assumptions it is even true that the interior of the strong unicity set is I also dense. If the index set of the constraints contains a dense subset with the property that each point1 is a G ₈-set, then the parameters of the strong unicity set, such that the optimal point satisfies the linear independence constraint qualification, are also dense.

We apply our results to a characterization of a unique continuous selection for the optimal set I mapping and to a one-sided L ₁-approximation problem     

On the convergence of some Procrustean averaging algorithms

Euclidean “(size-and-)shape spaces” are spaces of configurations of points in R ^N modulo certain equivalences. In many applications one seeks to average a sample of shapes, or sizes-and-shapes, thought of as points in one of these spaces. This averaging is often done using algorithms based on generalized Procrustes analysis (GPA). These algorithms have been observed in practice to converge rapidly to the Procrustean mean (size-and-)shape, but proofs of convergence have been lacking. We use a general Riemannian averaging (RA) algorithm developed in [Groisser, D. (2004) “Newton's method, zeroes of vector fields, and the Riemannian center of mass”, Adv. Appl. Math. 33, pp. 95–135] to prove convergence of the GPA algorithms for a fairly large open set of initial conditions, and estimate the convergence rate. On size-and-shape spaces the Procrustean mean coincides with the Riemannian average, but not on shape spaces; in the latter context we compare the GPA and RA algorithms and bound the distance between the averages to which they converge.     

Measuring the fuzziness of human thoughts: An application of fuzzy sets to sociological research

Conventionally, sociologists measure the membership of an individual to a group by a “0 or 1” characteristic function. But when the definition of that group is fuzzy and an individual is neither a full member nor a nonmember, this dichotomous characteristic function may distort the reality. Instead of the “0 or 1” characteristic function by classical set theory, fuzzy set theory introduces a membership function which is a gradation from 0 to 1 to measure the degree to which an object (an individual) belongs to a concept (a group). Based on the rationale of fuzzy set theory, we suggest some new methods of data collection and analysis. Among several noteworthy findings, two points are emphasized: 1) the fuzzy set is an appropriate way of measuring the fuzziness of human thought; and 2) it allows one to relax the conventional assumption that all individuals have identical distributions and deviations around their means.     

On fuzzy goals and maximizing decisions in stochastic optimal control

Fuzzy set theory has developed significantly in a mathematical direction during the past several years but few applications have emerged. This paper investigates the role of fuzzy set theory in certain optimal control formulations. In particular, it is shown that the well-known quadratic performance criterion in deterministic optimal control is equivalent to the exponential membership function of a certain fuzzy decision (set). In a stochastic setting, similar equivalences establish new definitions for “confluence of goals” and “maximizing decision” in fuzzy set theory. These and other definitions could lead to the development of a more applicable theory of fuzzy sets.     

N-邻域与N-Fuzzy有界集

本文研究了Fuzzy拓扑空间中的N-邻域与N-Fuzzy有界集问题.利用N-邻域引入N-Fuzzy有界集概念,讨论了其与另两种Fuzzy有界集的关系,获得了三种Fuzzy有界集的等价刻画及N-Fuzzy有界集的一些基本性质,推广了Fuzzy有界集的已有结果.     

Some Remarks on Normal Measures and Measurable Cardinals

We prove two theorems which in a certain sense show that the number of normal measures a measurable cardinal κ can carry is independent of a given fixed behavior of the continuum function on any set having measure 1 with respect to every normal measure over κ . First, starting with a model V ⊨ “ZFC + GCH + o(κ) = δ*” for δ* ≤ κ⁺ any finite or infinite cardinal, we force and construct an inner model N ⊆ V [G] so that N ⊨ “ZF + (∀δ < κ) [DC_δ] + ¬AC_κ + κ carries exactly δ* normal measures + 2^δ = δ⁺⁺ on a set having measure 1 with respect to every normal measure over κ”. There is nothing special about 2^δ = δ here, and other stated values for the continuum function will be possible as well. Then, starting with a modelV ⊨ “ZFC + GCH + κis supercompact”, we force and construct models of AC in which, roughly speaking, regardless of the specified behavior of the continuum function below κ on any set having measure 1 with respect to every normal measure over κ, κ can in essence carry any number of normal measures δ* ≥ κ⁺⁺.     

Reformulating the traffic equilibrium problem via a smooth gap function

This paper proposes an alternate formulation of the traffic assignment problem using route flows and the shortest Origin-Destination (OD) travel times as the decision variables. This is accomplished through defining a gap function to convert the Nonlinear Complementarity Problem (NCP) formulation to an equivalent Mathematical Program (MP). This formulation has two advantages:

• 1.(i) it can model assignment problems with general route costs which cannot be accomplished with existing formulations that use link-flow variables
• 2.(ii) the objective function is smooth, convex, and bounded, which permits efficient MP algorithms for its solution.

Two solution approaches are developed to solve the proposed formulation. The first is based on a set of working routes, which are modeled as “known a priori” based on travelers' preferences or interviews. The second approach uses a column generation procedure to generate a new route in each iteration on a need basis. For each approach, we use a Successive Quadratic Programming (SQP) algorithm to solve for the solutions.To show that the formulation is correct, we solve a small example with a general route cost and compare it to the classic traffic equilibrium problem which assumes an additive route cost function. Finally, numerical results for a medium-sized network are provided to demonstrate the feasibility of the solution approach.     

An Integral Simplex Algorithm for Solving Combinatorial Optimization Problems

In this paper a local integral simplex algorithm will be described which, starting with the initial tableau of a set partitioning problem, makes pivots using the pivot on one rule until no more such pivots are possible because a local optimum has been found. If the local optimum is also a global optimum the process stops. Otherwise, a global integral simplex algorithm creates and solves the problems in a search tree consisting of a polynomial number of subproblems, subproblems of subproblems, etc. The solution to at least one of these subproblems is guaranteed to be an optimal solution to the original problem. If that solution has a bounded objective then it is an optimal set partitioning solution of the original problem, but if it has an unbounded objective then the original problem has no feasible solution. It will be shown that the total number of pivots required for the global integral simplex method to solve a set partitioning problem having m rows, where m is an arbitrary but fixed positive integer, is bounded by a polynomial function of n.A method for programming the algorithms in this paper to run on parallel computers is discussed briefly.     

A Note on Fuzzy Relation Programming Problems with Max-Strict-t-Norm Composition

The fuzzy relation programming problem is a minimization problem with a linear objective function subject to fuzzy relation equations using certain algebraic compositions. Previously, Guu and Wu considered a fuzzy relation programming problem with max-product composition and provided a necessary condition for an optimal solution in terms of the maximum solution derived from the fuzzy relation equations. To be more precise, for an optimal solution, each of its components is either 0 or the corresponding component's value of the maximum solution. In this paper, we extend this useful property for fuzzy relation programming problem with max-strict-t-norm composition and present it as a supplemental note of our previous work.     

Asymptotics of Partial Density Functions for Divisors

We study the asymptotic behaviour of the partial density function associated to sections of a positive hermitian line bundle that vanish to a particular order along a fixed divisor Y. Assuming the data in question is invariant under an \(S^1\)-action (locally around Y) we prove that this density function has a distributional asymptotic expansion that is in fact smooth upon passing to a suitable real blow-up. Moreover we recover the existence of the “forbidden region” R on which the density function is exponentially small, and prove that it has an “error-function” behaviour across the boundary \(\partial R\). As an illustrative application, we use this to study a certain natural function that can be associated to a divisor in a Kähler manifold.