不确定信息的层次描述资源-CSDN文库

118 浏览量 2021-03-28 02:52:58 上传评论收藏 982KB PDF 举报

资源推荐

资源详情

资源评论

Hierarchical description of uncertain information

Shu Zhao

a,b

, Ling Zhang

a,b

, Xiansheng Xu

a,b

, Yanping Zhang

a,b,

⇑

Key Laboratory of Intelligent Computing and Signal Processing, Ministry of Education, Anhui University, Hefei, Anhui Province 230039, PR China

School of Computer Science and Technology, Anhui University, Hefei, Anhui Province 230601, PR China

article info

Article history:

Received 20 July 2012

Received in revised form 8 January 2014

Accepted 15 January 2014

Available online 24 January 2014

Keywords:

Uncertain information

Hierarchical structure

Hierarchical coordinate

Granularity transformation

Optimal path

abstract

Humans have the innate ability to cope with and process incomplete and uncertain informa-

tion. Any intelligent system should also have such an ability built in. Incomplete and

uncertain information is formalized in different ways. By analyzing different methods for

representing uncertain information, we propose a new method that uses a hierarchical

coordinate to describe a total-order structure. This novel method describes information in

different granular spaces by using hierarchical coordinates. The relationships among these

spaces are constructed such that the transformation of information is possible. We extend

the fuzzy equivalence and tolerance relations to weighted equivalence and tolerance rela-

tions, respectively. The properties of those relations and the isomorphism discriminant of

information are described by using matrices. We develop a method for solving a complex

problem with hierarchical coordinates. Simulation experiments demonstrate that a hierar-

chical coordinate system can help us to efﬁciently determine the optimal paths of large-

scale networks.

1. Introduction

The complexity of the real world and the limitations of human intelligence require that we should be able to represent

and process uncertain, incomplete, or inconsistent information. Methods for dealing with uncertain information are there-

fore an important topic in computational intelligence.

Zhang and Zhang [33] considered a hierarchical framework for interpreting uncertain information; in this framework,

recognizing that any information is uncertain to some degree, uncertain information at a given level is expressed as certain

information at a coarser level, and conversely, certain information at a given level may become uncertain at a ﬁner level.

Based on these observations, the authors proposed a mathematical model, named the quotient space model, to describe

and analyze information at different levels of granularity. An underlying assumption of the quotient space theory is that

the uncertainty or certainty of information is related to the granularity. For example, we cannot determine whether

301 cm is certain or not. If the relevant scale is a meter, 3 m (301 cm) is certain information; however, if the relevant scale

is a millimeter, 3010 mm (301 cm) is uncertain information. If the relevant scale is a meter, 301 cm and 302 cm are consid-

ered to be the same; in contrast, if the relevant scale is a millimeter, 301 cm is considered to be smaller than 302 cm.

Li et al. [5] indicated that randomness and uncertainty are the two most important concepts in the description of informa-

tion. Uncertainty and certainty are not completely opposite concepts, and they can be transformed into each other to some de-

gree. Describing information at different levels of granularity and their relationships is crucial in designing intelligent systems.

http://dx.doi.org/10.1016/j.ins.2014.01.028

⇑

Corresponding author at: Key Laboratory of Intelligent Computing and Signal Processing, Ministry of Education, Anhui University, Hefei, Anhui Province

230039, PR China. Tel.: +86 13856002964.

E-mail addresses: zhangyp2@gmail.com, zhaoshuzs2002@hotmail.com (Y. Zhang).

Information Sciences 268 (2014) 133–146

Contents lists available at ScienceDirect

Information Sciences

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

A primary objective of this paper is to introduce a new method for representing and processing uncertain information based

on granular computing. There are several granular computing models used in uncertain information processing [2,14–17,21].

Rough set theory [1,4,8,11–13,18–20,22–25,28,35] focuses on the processing of the uncertainty caused by the indistinguish-

ability of objects, and fuzzy set theory [1,6,7,9,10,29,30] focuses on the uncertainty caused by the unsharp boundedness of a

concept. One of the key insights of rough set theory research is that the selection of different sets of features or variables will

yield different granulations, that is, by projecting a data set (value attribute system) onto different sets of variables, we recog-

nize alternative sets of equivalence-class ‘concepts’ in the data. Zadeh [29] suggests that granularities are fuzzy in human infer-

ence and concept formation. He indicated that computing with words based on fuzzy concepts is a primary process in granular

computing. Quotient space theory [31,33] focuses on not only the structure of elements at the same granular level, but also on

the structures observed at different granular levels. The quotient space model takes an approach, based on the ideas of Hobbs

[3], that involves our ability to conceptualize the world at different granularities and to translate from one abstraction level to

others easily, i.e., deal with them hierarchically. Quotient space theory emphasizes the description of information in different

granular spaces and the construction of relationships among these spaces to realize the transformation of information.

Yao [26] provided a comprehensive study of artiﬁcial intelligence perspectives on granular computing. He argued that

multiple/hierarchical granular structures are essential to both human and machine problem solving [26,27]. Note that the

hierarchical structures used by the quotient space are typical examples of granular structures. By using the hierarchical

structure, quotient space theory provides a practical way to make inferences based on fuzzy equivalence relations and fuzzy

tolerance relations [34].

In this paper, we extend the basic theory of the quotient space by using weighted equivalence relations and tolerance

relations and provide an effective tool for describing hierarchical structures. The remainder of the paper is organized as fol-

lows. Section 2 introduces related work. Section 3 provides a description of uncertain information, i.e., a total-order struc-

tural description called a hierarchical coordinate system, and discusses the relationships between the hierarchical coordinate

system and the membership functions in fuzzy set theory. Section 3.1 provides the sufﬁcient and necessary conditions of

isomorphic uncertain information described by a matrix. Experiments are described in Section 3.2 to illustrate how to use

hierarchical coordinates to obtain the optimal path in large-scale networks. Section 3.3 provides concluding remarks.

2. Related work

In quotient space theory, a triplet ðX; f ; TÞ is used to describe a problem-solving space, or a problem for short. The set X

that denotes the problem domain is also called the universe. f ðÞ indicates the attributes of domain X and is denoted by a

function f : X ! Y, where Y is the set of real numbers, a set of n-dimensional space R

, or a general space. f ðÞ is either sin-

gle-valued or multi-valued. For each element x 2 X; f ðxÞ corresponds to a certain attribute of x and is called an attribute func-

tion. T is the structure of domain X, i.e., the relationships among the elements in X. There are many methods for representing

structure, such as the Euclidean distance, inner product, semi-order, topology, and undirected or directed graph.

Deﬁnition 2.1 (Quotient Space). If X is a domain and R is an equivalence relation on X, then ½X is a quotient set under R.

Regarding ½X as a new domain, we have a new domain that is coarser than X. We say that X is granulated by R. The original

problem space is transformed into a new problem space at a new abstraction level. We call ð½X; ½f ; ½TÞ a quotient space of

ðX; f ; TÞ. We have a coarser space with a more coarse-grained domain ½X, attribute ½f , and structure ½T, called the quotient

set, quotient attribute, and quotient structure, respectively.

There are several ways to obtain a quotient space from domain X, attribute function f, and structure T [33]. We will use an

example to explain the concept of the quotient space and the process of granulation from the original space to the quotient

space by using the structure T.

Consider 10 cities. We use a triplet ðX; f ; TÞ to describe information about the cities, including information on the nodes

and information on the relationships between the nodes. Table 1 lists the relevant detailed information.

The attribute function is f : X ! Y. f ðÞ could be single-valued, e.g., f ðx

Þ¼big city; f ðx

Þ¼big city; ...;

f ðx

Þ¼middle city, or multi-valued f ¼ff

; f

; ...; f

g, e.g., f

ðx

Þ¼big city and f

ðx

Þ¼cultural city; ...; f

ðx

Þ¼

north city; f

ðx

Þ¼big city and f

ðx

Þ¼economic city; ...; f

ðx

Þ¼eastern city; ....

Structure T denotes the information about roads among the cities. Each road is categorized as one of various types: high-

way, national highway, provincial highway, etc.

To understand the structure T, an undirected weighted graph is used to express this problem space ðX; f ; TÞ. Here, X de-

notes the node set V in GðV; EÞ; f denotes nodes with information, attributes, or constraints; and T completely describes the

Table 1

An example of the detailed information of domain X.

Number Name ... Population

Beijing ... 20,000,000

Shanghai ... 23,000,000

... ... ... ...

Hefei ... 9,000,000

134 S. Zhao et al. / Information Sciences 268 (2014) 133–146

graph’s structures. The weight between two nodes denotes some measurement of the relationships between two nodes, i.e.,

the quality of the highway. Fig. 1 shows an example.

We will illustrate how to obtain the quotient space ð½X; ½f ; ½TÞ of the original problem space ðX; f ; TÞ directly from the

structure T. From Fig. 1, we assign the connected nodes with some weight; for example, we can assign a weight of 10 to

the same granule. The maximum weight between two nodes in different granules is used as the weight of these two

granules. The equivalence relation R is deﬁned as xRy () x and y is connected to an edge whose weight is greater than

or equal to 10.

Statistical methods are used to obtain the quotient attribute ½f , such as the operator max, min, average, or sum. Many

others methods are discussed in the literature [33].

An undirected weighted graph used to express the quotient space ð½X; ½f ; ½TÞ as shown in Fig. 2.

3. Total-order structural representation

3.1. Hierarchical coordinate

Deﬁnition 3.1. Suppose X  X is a product space. WR # X  X is called a weighted equivalence relation if it is

(1) Reflexi

e :

x; y 2 X; WRðx; xÞ P maxWRðx; yÞ

(2) Symmetric :

x; y 2 X; WRðx; yÞ¼WRðy; xÞ

(3) Transiti

e :

x; y; z 2 X; WRðx; zÞ P sup

ðminðWRðx; yÞ; WRðy; zÞÞÞ

Deﬁnition 3.2. Suppose X  X is a product space. WR # X  X is called a weighted tolerance relation if it is

(1) Reflexi

e :

x; y 2 X; WRðx; xÞ P maxWRðx; yÞ

(2) Symmetric :

x; y 2 X; WRðx; yÞ¼WRðy; xÞ

Deﬁnition 3.3. Suppose WR is a weighted equivalence or a tolerance relation on X. Let WR

¼fðx; yÞjWRðx; yÞ P kg and

k 2fWRðx; yÞjx; y 2 Xg. WR

is a common equivalence or tolerance relation and is known as a cut relation of WR.

Proposition 3.1. Assume that f½XðkÞg is a hierarchical structure on X. A weighted equivalence or tolerance relation WR exists on X

such that ½XðkÞ is a quotient space with respect to WR

, where WR

is the cut relation of WR; k 2fWRðx; yÞjx; y 2 Xg.

Deﬁnition 3.4 (Quotient Chain). Deﬁne a ‘coarser than’ relation as ½X

< ½X

()½X

is coarser than ½X

.If½X

is the quotient

set of ½X

, denote ½X

< ½X

. A sequence ½X

< ½X

<  < ½X

¼ X is called a (Hierarchical) Quotient Chain.

Example 1.

10844

8104 4

4 4 10 6

44610

; WR

10854

8107 3

5 7 10 6

43610

Fig. 1. An undirected weighted graph with structure T.

S. Zhao et al. / Information Sciences 268 (2014) 133–146

135

剩余13页未读，继续阅读

评论收藏

内容反馈

weixin_38538585

粉丝: 3
资源: 956

不确定信息的层次描述

熵值法和层次分析法在权重确定中的应用

信息组织：第七章 元数据描述.ppt

《不确定性人工智能》课程教学全书导论.ppt

基于分布式偏好信息的不确定性多属性决策方法.pdf

不确定信息融合.zip_DS融合_信息融合_分类器 融合_数据分类_融合分类

java 层次分析法

论文研究-基于云模型的大坝安全多层次综合评价方法.pdf

层次分析法确定评价指标权重及Excel计算_曹茂林.pdf

信息化规划与管理之确定企业的信息结构 精品资料.pptx

在线市场产品不确定性对顾客退货行为的影响研究

Python-PyTorch实现多层次场景描述网络MSDN

信息系统安全加固描述.docx

电信新业务管理中的不确定性问题分析与综述

层次分析法案例.pdf

层次分析法原理(许树柏)

描述逻辑英文教程

01_层次分析法.pdf

模糊层次分析法软件-好软件

闽高校计算机等级考试信息技术选择题含答案确定书中页码版.doc

层次聚类分析,层次聚类分析热图解读,matlab

信息化规划与管理之确定企业的信息结构.pptx

描述逻辑综述.pdf

层次分析法报告.docx

模糊数学 教程 有层次分析法

需求不确定下应急医疗服务站鲁棒配置模型与算法.pdf

《不确定性人工智能》课程教学云变换.ppt

最新资源

信息组织：第七章元数据描述.ppt

不确定信息融合.zip_DS融合_信息融合_分类器融合_数据分类_融合分类

信息化规划与管理之确定企业的信息结构精品资料.pptx

模糊数学教程有层次分析法