ObjectarrangementintoEuclideanspaceusinggeneticalgorithm资源-CSDN文库

论文

需积分: 9 185 浏览量 2021-06-29 16:52:46 上传评论收藏 230KB PDF 举报

资源推荐

资源详情

资源评论

Object Arrangement into Euclidean Space Using Genetic

Algorithm

Shinichiro Omachi, Hiroko Yokoyama, and Hirotomo Aso

Graduate School of Engineering, Tohoku University, Sendai, Japan 980-8579

SUMMARY

When only similarities or dissimilarities of two ob-

jects are given, visualization by arranging objects into

two-dimensional Euclidean space is effective in repre-

senting the relationship between more than two objects

intuitively. In this paper, an algorithm for arranging objects

into multidimensional Euclidean space with reflection of

the similarity or dissimilarity of two objects is proposed. As

an application of the proposed method, classification of

meanings of Japanese polysemous verbs is adopted. The

effectiveness of the proposed algorithm is shown by com-

Technica, Syst Comp Jpn, 31(13): 1118, 2000

Key words: Visualization; multidimensional scaling;

quantification theory IV; genetic algorithm.

1. Introduction

When we want to observe multiple objects and ana-

lyze them, it is important to understand their reciprocal

relationships. However, in the case that only similarities or

dissimilarities between two objects are observed, it is diffi-

cult to grasp reciprocal relationships between three or more

objects. In order to grasp reciprocal relationships intui-

tively, it is considered useful to arrange objects into two-di-

mensional Euclidean space. In that case, it is desired to

grasp intuitively not only the order of similarities or dis-

similarities, but also the magnitude of the similarities or

dissimilarities.

As methods of arranging objects into a Euclidean

space if similarities or dissimilarities between two objects

are given, multidimensional scaling [1] and quantification

theory IV [2] are known. Multidimensional scaling repre-

sents relationships between objects spatially. Its main pur-

pose is keeping the order of similarities or dissimilarities of

objects. In quantification theory IV, two vectors are consid-

ered. One is the vector whose elements are the similarities

of objects; the other is the vector whose elements are the

distance between two objects. Objects are arranged by

minimizing the angle between these vectors. These meth-

ods do not provide for keeping the magnitude of similarity

or dissimilarity itself. Moreover, multidimensional scaling

is effective only if the number of objects is relatively small

and the order can be kept to some extent. However, when

the number of objects is large, it is difficult to retain the

order relation. In quantification theory IV, objects tend to

concentrate at one point.

In this paper, we propose a method that arranges

objects into a Euclidean space by considering the magni-

tude of similarities or dissimilarities between two objects.

The proposed method makes it possible to visualize the

relationships between objects by arranging objects into

two-dimensional Euclidean space. Moreover, pattern rec-

ognition techniques under the assumption that the objects

are points in the Euclidean space can be used.

In order to confirm the effectiveness of the proposed

method, experiments that arrange objects into two-dimen-

sional Euclidean space when the dissimilarities between

two objects are given are carried out. As a concrete example,

Systems and Computers in Japan, Vol. 31, No. 13, 2000

Translated from Denshi Joho Tsushin Gakkai Ronbunshi, Vol. J82-D-II, No. 12, December 1999, pp. 21952202

classification of the meanings of a polysemous verb is

considered. There have been studies on obtaining the mean-

ings of words using collocational information extracted

from corpora [38]. Fukumoto and Tsujii proposed a

method of classifying verbs by representing each verb as a

vector whose element is the degree of co-occurrence with

a noun [6]. There are other methods to extract meanings of

a verb by clustering of nouns that co-occur with the verb

[7, 8]. In this paper, an algorithm that arranges nouns into

two-dimensional Euclidean space representing correlations

of each pair of nouns that co-occur with a polysemous verb

is considered. By arranging words into two-dimensional

Euclidean space, it becomes easy for people to grasp their

co-occurrence information intuitively. Moreover, novel ap-

proaches of analyzing words can be achieved, for example,

designing a hyperplane that separates clusters of meanings.

In this case, the algorithm is required to arrange two words

with small dissimilarity close together, and to arrange two

words with large dissimilarity apart. If the latter require-

ment is not satisfied, it is impossible to make clusters

according to meanings.

In this paper, first multidimensional scaling and

quantification theory IV are described. Then the proposed

method is described and compared with traditional methods

via experiments that arrange data made by corpora into

two-dimensional Euclidean space.



2. Arranging Algorithm

In this section, multidimensional scaling [1] and

quantification theory IV [2], which are related to the pro-

posed method, are described.

2.1. Multidimensional scaling

Multidimensional scaling is a method that represents

measurements of objects spatially, which is applied to many

fields, including psychology. Asymmetric data can also be

handled [9]. There are many multidimensional scaling

methods. The main idea of these methods is as follows.

Suppose dissimilarity e

of two objects i and j is given.

Let the coordinates of i and j that are arranged in the

Euclidean space be x

and x

. The distance d

is defined

If there is a monotonic increasing function f that satisfies

the order of e

can be represented strictly as the order of

distances of two points in the Euclidean space. In general,

however, function f that satisfies Eq. (2) does not exist.

Therefore, a nonlinear transformation T that revises the

order is defined:

Here, D and

are sets of d

and d

, respectively. It is

required that T is defined so that d

is similar to e

. Then

the loss function

is defined. We find {x

} that minimizes L by the steepest

descent method.

As the loss function, the following expression is used:

Typical transformations are the monotonic regression

method and rank-image method. In both methods, first,

} and {d

} are sorted. Then the ranks of the elements

whose indices are the same are compared. In the case that

the ranks of elements whose indices are (i, j) are the same,

itself is used as d

. If the ranks are different, in the

monotonic regression method, the mean value is used, and

in the rank-image method, the order is exchanged. For

example, suppose there are three objects and the set of

dissimilarities {e

} satisfies the following expression:

If the distances {d

} of the points in the Euclidean space

satisfy

then in the monotonic regression method,

, d

 d

and in the rank-image method,

, d

See Fig. 1.

In multidimensional scaling, arrangement can be

achieved using nonlinear transformation T by regarding the

order relation as important. If the number of objects is small

There are methods that represent characteristics of a word by co-occur-

rence vector. In this case, words are already arranged in the Euclidean

space. In this paper, it is assumed that dissimilarities between two words

are only given. The dissimilarity is different from the Euclidean distance.



Arrangement by the proposed method does not limit the dimensionality

of the space. In the experiments, two-dimensional space is used so that the

results can be evaluated intuitively.

In the case that similarity is given, a monotonic decreasing function is

used instead of Eq. (2).

(1)

(2)

(3)

(4)

(5)

剩余7页未读，继续阅读

评论收藏

内容反馈

weixin_38696090

粉丝: 4
资源: 874

Object arrangement into Euclidean space using genetic algorithm

最新资源

Object arrangement into Euclidean space using genetic algorithm

使用遗传算法将对象排列到欧几里得空间

Problem Arrangement zoj 3777

poj算法题目实现.zip_algorithm_arrangement4hv_conditionyis_poj problems

Quota Arrangement

Multi-phase Homing Optimal Control for Parafoil System

实验4_canny_matlab_arrangement4bm_

论文研究-Problems with Queuing Arrangement When Boarding.pdf

SAP Advance Purchase Function - Quota Arrangement

Parkinson_parkinson_arrangement154_machinelearning_

Arrangement - Actraiser [Birth of the people]_music_people_

A printer forensics method using halftone dot arrangement model

TV.zip_TV_TV滤波_arrangement5hy_图像处理_降噪

pca.rar_arrangement5qq_entirelyjek_matlab

jquery瀑布流排列样式代码.zip_arrangement_squarerze_waterfall

【船级社】 DNV Survey arrangement for machinery condition

Tsingtao arrangement

Digtal_Signal_数字滤波器_验证采样定理_arrangement8em_

Course_Arrangement用C++写的自动排课程序

Grammatical arrangement.txt

【船级社】 DNV-CG-0052 Survey arrangement for machinery.pdf

MUTUAL RECOGNITION ARRANGEMENT ON CONFORMITY SOM3SCSCJRAC016.pdf

【船级社】 BV Hull structure and arrangement for the classification

2013年湖南大学邀请赛H题bottles arrangement

【船级社】 BV NR 566 Hull arrangement, stability and systems for ship

DXJavaScript

【船级社】 566-NR_2022-07 Hull arrangement, stability and systems for

NX二次开发UF-ASSEM-set-default-arrangement 函数介绍

NX二次开发UF-ASSEM-set-used-arrangement 函数介绍

NX二次开发UF-ASSEM-set-active-arrangement 函数介绍

最新资源