AnimprovedFCMBPfuzzyclusteringmethodbasedonevolutionaryprogramming资源-CSDN文库

172 浏览量 2021-02-21 15:36:31 上传评论收藏 802KB PDF 举报

资源推荐

资源详情

资源评论

Computers and Mathematics with Applications 61 (2011) 1129–1144

Contents lists available at ScienceDirect

Computers and Mathematics with Applications

journal homepage: www.elsevier.com/locate/camwa

An improved FCMBP fuzzy clustering method based on

evolutionary programming

✩

Qing Tan

a,b

, Qing He

a,∗

, Weizhong Zhao

a,b

, Zhongzhi Shi

, E.S. Lee

Key Laboratory of Intelligent Information Processing, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China

Graduate School, Chinese Academy of Sciences, Beijing 100049, China

Department of Industrial Engineering, Kansas State University, Manhattan, KS 66506, USA

a r t i c l e i n f o

Article history:

Received 27 September 2010

Received in revised form 24 December 2010

Accepted 27 December 2010

Keywords:

Fuzzy clustering

FCMBP fuzzy clustering

Optimal fuzzy equivalent matrix

Evolutionary programming

a b s t r a c t

In current PC computing environment, the fuzzy clustering method based on perturbation

(FCMBP) is failed when dealing with similar matrices whose orders are higher than tens.

The reason is that the traversal process adopted in FCMBP is exponential complexity. This

paper treated the process of finding fuzzy equivalent matrices with smallest error from

an optimization point of view and proposed an improved FCMBP fuzzy clustering method

based on evolutionary programming. The method seeks the optimal fuzzy equivalent

matrix which is nearest to the given fuzzy similar matrix by evolving a population of

candidate solutions over a number of generations. A new population is formed from

an existing population through the use of a mutation operator. Better solutions survive

into next generation and finally the globally optimal fuzzy equivalent matrix could be

obtained or approximately obtained. Compared with FCMBP, the improved method has the

following advantages: (1) Traversal searching is avoided by introducing an evolutionary

programming based optimization technique. (2) For low-order matrices, the method

has much better efficiency in finding the globally optimal fuzzy equivalent matrix.

(3) Matrices with hundreds of orders could be managed. The method could quickly get

a more accurate solution than that obtained by the transitive closure method and higher

precision requirement could be achieved by further iterations. And the method is adaptable

for matrices of higher order. (4) The method is robust and not sensitive to parameters.

1. Introduction

The concept of fuzzy clustering analysis was firstly carried out by Ruspini in 1969 [1]. One of the fuzzy clustering methods

is fuzzy k-means clustering algorithm [2]. Another method in common use is transforming a fuzzy similar matrix R into a

fuzzy equivalent R

∗

= t(R) by finding the transitive closure of R; the final clustering is then made by R

∗

. However, since the

process of finding the transitive closure of R consists of making a series of transformations, it is not theoretically assured

whether the clustering result obtained by R

∗

really reflects the original clustering problem [3]. In order to deal with this

lack of fidelity problem, Li et al. [4] proposed the basic theory of resolution and parameter system then put forward a fuzzy

clustering method based on perturbation (FCMBP), whose main idea is to try to find a fuzzy equivalent R

, which is closest

to R by a certain distance. Thereafter, FCMBP is further studied and several important results are obtained in paper [5–8].

[5] proposed the concept of fuzzy equivalent normal form in order to express the solutions. Also the uniqueness of the

✩

This work is supported by the National Natural Science Foundation of China (No. 60933004, 60975039, 61035003, 60903141, 61072085), National

Basic Research Priorities Programme (No. 2007CB311004) and National Science and Technology Support Plan (No. 2006BAC08B06).

∗

Corresponding author. Tel.: +86 010 62600542.

E-mail address: heq@ics.ict.ac.cn (Q. He).

doi:10.1016/j.camwa.2010.12.063

1130 Q. Tan et al. / Computers and Mathematics with Applications 61 (2011) 1129–1144

parameter systems corresponding to standard resolution process was pointed out and the existence of optimal fuzzy

equivalence matrix was proved. In paper [6], based on the theory of distribution structure of fuzzy similar matrix equation

= X , the existence theorem and local uniqueness theorem of the optimal fuzzy equivalent matrix have been proved by

using the method of abstract analysis. And also the relation between local optimal fuzzy equivalent matrix and the given

fuzzy similar matrix had been pointed out. [7] proved that the FCMBP fuzzy clustering methods have smaller error than

transitive closure methods and gave examples to show their clustering results are not always the same. [8] provided a

systemic and detailed discussion about the theory of FCMBP fuzzy clustering method.

The FCMBP fuzzy clustering method in paper [8] provides a way to obtain the optimal fuzzy equivalent matrix. However,

it needs to run over all the combination possibilities of all classes of similar equivalent standard forms and all elements in

a symmetric group S

. The number of the equivalent matrices to be calculated grows exponentially as the order of the raw

similar matrix rises. It is computationally intractable when n, the order of the matrix, is high. For example, the method needs

to run over 2.3 × 10

possibilities when n = 12, and this number grows to 6.7 × 10

and 7.8 × 10

when n = 15 and

n = 20 correspondingly. So the method is out of work in current PC computing environment when dealing with high-order

similar matrices.

In order to make this exponential complexity algorithm still work on high-order situations, the traversal process adopted

in FCMBP must be break up. In this paper, we consider the problem of finding the optimal fuzzy equivalent matrix from an

optimization point of view. The optimization objective is to make the distance between the obtained fuzzy equivalent matrix

R and the raw fuzzy similar matrix R as small as possible, viz. make the lack of fidelity brought about by clustering according

to R as less as possible.

Traditional optimization techniques like gradient descent algorithm or direct, analytical methods have the advantages

of high computation efficiency and strong reliability. However, these methods always have strict constraint requirements

on the objective function such as single peak demands and continuously differentiable requirements. For the problem of

finding optimal fuzzy equivalent matrix, its objective function does not satisfy the single peak demands and even could

not be expressed as a corresponding expression. Therefore these traditional optimization methods cannot be applied to the

problem.

Evolutionary computation is a kind of useful method of optimization when other optimization methods fail in finding

the optimal solution [9]. It is suitable for difficult combinatorial and real-valued function optimization problems in which

the fitness landscapes are rugged and have many locally optimal solutions. These methods do not depend on the first- and

second-differentials of the objective function of the problem to be optimized and even have no demands on whether the

objective function has an explicit expression. All these features make it very suitable for solving the proposed optimization

problem. As a typical evolutionary algorithm, evolutionary programming (EP) [10] is a heuristic method based on simulating

the mechanics of natural selections. Compared with genetic algorithm (GA) [11], EP does not involve encoding the problem

solutions as fixed-length binary strings but directly represents them according to the problem to be optimized. Specific to

the problem of finding optimal fuzzy equivalent matrix, feasible solutions are represented by two factors: σ ∈ S

where S

a symmetric group and

X ∈

/≈ where

/≈ stores all classes of similar equivalent standard forms. Moreover, EP applies

mutation operators only while the classical GA uses crossover, mutation and other genetic operators. This mechanism avoids

the difficulty of defining a reasonable crossover operator in the proposed optimization problem. For the above reasons, we

introduce evolutionary programming based optimization technique to find the optimal fuzzy equivalent matrix and thus

propose an EP based FCMBP (EP-FCMBP) fuzzy clustering method. The method seeks the optimal solution by evolving a

population of candidate fuzzy equivalent matrices over a number of generations. A new population is formed from an

existing population through the use of a mutation operator. Through the use of a competition scheme, matrices with a

relatively less lack of fidelity have a greater chance of survival than the poorer solutions, which guarantees the population

evolves towards the global optimal point.

The rest of this paper is organized as follows: Section 2 introduces the basic idea of FCMBP and gives analysis of its

computational complexity. Then in Section 3, we present our EP-FCMBP fuzzy clustering method in detail. Experimental

results and analysis are given in Section 4, followed by our conclusions in Section 5.

2. Summary of FCMBP fuzzy clustering method

We shall follow the notations used in the earlier paper [8]. The main results in [8] are briefly summarized in the following.

Let Y

be the set of n-order fuzzy similar matrices, X

be the set of n-order fuzzy equivalent matrices, and S

be a symmetric

group. Then we have the following propositions.

Proposition 1 ([4]). For any X ∈ Y

, we have

X ∈ X

⇔ x

∧ x

≤ x

, ∀1 ≤ i = j = k ≤ n. (1)

Proposition 2 ([4]). For any σ ∈ S

, X = (x

)

n×n

, we have the following.

(1) If X ∈ Y

, then X

= (x

σ (i)σ (j)

)

n×n

∈ Y

(2) If X ∈ X

, then X

= (x

σ (i)σ (j)

)

n×n

∈ X

(3) If X ∈ X

, then X (I

) ∈ X

and X(I

) ∈ X

n−m

Q. Tan et al. / Computers and Mathematics with Applications 61 (2011) 1129–1144 1131

(4) Let X ∈ Y

. If there exist a t ∈ [0, 1] and X has a resolution satisfying the following conditions:

(a) X (I

) ∈ X

and X(I

) ∈ X

n−m

;

(b) X (I

) ≥ t and X (I

) ≥ t;

, I

) = (t)

m×(n−m)

and X(I

, I

) = (t)

(n−m)×m

;

then X ∈ X

and we say that X has a resolution structure, where X (I

, I

) = (x

)

m×(n−m)

denotes the matrix consisted of

the elements of x

, i ∈ I

, j ∈ I

, and others are similarly defined.

(5) If X ∈ Y

, then X ∈ X

⇔ X has a resolution structure.

(6) The solution of an n-order matrix equation X

= X can be represented by n − 1 parameters.

For any X ∈ X

, which has obtained the resolution structure for X , we have X(I

) ∈ X

and X(I

) ∈ X

n−m

and call these

the first resolution structure. Then, for X (I

) and X(I

), we can similarly obtain the resolution structure of X(I

) and X(I

This process is continued until the submatrices become one-order submatrices. Since every resolving process is carried out

according to some parameter t, we can illustrate the resolving process by a diagram as follows:

X(I

) : t

↑

X : t

→ X (I

) : t

simplified as:

↑

→ t

After the matrix has been completely resolved in a step-by-step fashion, we obtain a completed parameter system of X.

The resolution structure of X obtained by the following process is called a standard resolution of X, and the process is called

a standard resolution process [4].

(1) Let t = ∧{x

: 1 ≤ i = j ≤ n}.

(2) If t = 1, then X = (1)

n×n

and let I

= {1} and I

= {2, 3, . . . , n}; if t < 1, then find the first column (or row) which

contains the most t. Suppose that the column is the j

th column. Let x

= x

= · · · = x

n−m

= t (i

< i

< · · · <

n−m

), and let I

= {i

, i

, . . . , i

n−m

} and I

= {1, 2, 3, . . . , n} \ I

(3) Carry out the resolution structure by referring to I

and I

defined in above step. Thus, the first standard resolution

structure (X(I

), X(I

, I

), X(I

, I

)) was obtained.

In X

, we define an equivalent relation ‘‘∼’’ as follows: ∀X, Y ∈ X

, X ∼ Y ⇔ ∃σ ∈ S

, s.t. Y = X

Definition 1 ([8]). Let X ∈ X

, X is called a fuzzy equivalent standard form if its lower triangular matrix has the following

form of blocks.

(1) For each block, all the elements of the block are equal and the up-right elements are closest to the diagonal elements 1.

(2) The elements in the upper blocks are bigger than the ones in the lower blocks.

(3) The elements in the right blocks are bigger than or equal to the ones in the left blocks.

(4) Each block has more rows than columns or the rows and columns are equal.

(5) The lower triangular is divided into n − 1 blocks.

Proposition 3 ([8]). Let X ∈ X

. If X has a standard resolution structure (X (I

), X(I

, I

), X(I

, I

)), then the following

block statements are true.

(1) ∃σ ∈ S

, s.t. X

has the following block matrix form:

[

X(I

) X(I

, I

)

X(I

, I

) X(I

)

]

. (2)

(2) X (I

, I

) = (t)

m×(n−m)

, X (I

, I

) = (t)

(n−m)×m

(3) If t = 1, then X = (1)

n×n

. If t < 1, then

(a) m ≤ n − m,

(b) X (I

) > (t)

m×m

) ≥ (t)

(n−m)×(n−m)

, or there exist t in X(I

) and s ≤ n − 2m, where s is the number of t in the column of X(I

)

which has the most t.

(d) The up-right element of X(I

, I

) is nearest to the diagonal element 1.

Theorem 1 ([8]). For any X ∈ X

, ∃σ ∈ S

s.t. X

is a fuzzy equivalent standard form.

Theorem 2 ([8]). For any X, Y ∈ X

, X ∼ Y ⇔ X and Y have the same equivalent standard form.

Let X ∈ X

, and [X ] is the equivalent class of X. Then [X] can be represented by the equivalent standard form.

Theorem 3 ([8]). If X ∈ X

, then X ∼ Y ⇔ X and Y have the same standard parameter system.

Two standard parameter systems are called similar if they have the same diagram, but their parameters may not be equal.

We introduce another relation ‘‘≈’’ in X

as: X ≈ Y ⇔ X and Y have similar standard parameter systems, whose relation is

an equivalent relation in X

and will be called a translation equivalent relation. All of the equivalent standard forms together

form a set denoted by

. It is obvious that |

| = |X

/∼|. Obviously, ‘‘≈’’ is also an equivalent relation in

剩余15页未读，继续阅读

评论收藏

内容反馈

weixin_38534352

粉丝: 5
资源: 982

An improved FCMBP fuzzy clustering method based on evolutionary ...

最新资源

An improved FCMBP fuzzy clustering method based on evolutionary ...

基于进化规划的FCMBP模糊聚类改进方法

论文研究-基于进化规划的FCMBP模糊聚类改进方法.pdf

fuzzy clustering code

An improved kernel regression method based on Taylor expansion

An improved iterative back projection algorithm based on ringing artifacts suppression

An improved method for calculating the no-fit polygon

An improved image mosaic based on Canny edge and an 18-dimensional descriptor

An Improved Uniform Identity Authentication Method.pdf

An Improved Algorithm of Slotted-ALOHA based on.zip

An improved rotor speed estimation method of IPMSM

An Improved MAC Scheme of HORNET Based on Node Structure with Variable Optical Buffer

Design and Realization of Position Controller Based on Characteristic Model

An improved neuro-dynamics-based approach to online path planning for multi-robots in unknown dynamic environments

AN IMPROVED NICHE GENETIC ALGORITHM

An improved FCM medical image segmentation algorithm based on MMTD

An improved algorithm for spectral

An improved EEMD method based on the adjustable cubic trigonometric cardinal spline interpolation

An improved collaborative recommendation algorithm based on optimized user similarity

09067568.pdf

An Evaluation Study on Maturity of China's Modern Marine Industry System Based on Improved Catastrophe Progression Method

An improved topic detection method for Chinese microblog based on incremental clustering

最新资源