"1995多变量决策树研究：Brodley与Utgooff的合作探索"

需积分: 0 178 浏览量更新于2024-03-25 收藏 2.08MB PDF 举报

"Brodley and Utgoff (1995) introduced the concept of multivariate decision trees in their seminal paper published in the prestigious journal Machine Learning. This type of decision tree differs from traditional univariate decision trees in that it is not limited to splitting the data along a single feature. Instead, multivariate decision trees can consider multiple features simultaneously, allowing for more complex decision-making processes. The authors, Carla E. Brodley and Paul E. Utgoff, highlighted the advantages of using multivariate decision trees in machine learning tasks. By considering multiple variables at once, these trees can capture more intricate relationships within the data and make more informed decisions. This approach is particularly useful in scenarios where there are interactions between different features that may not be easily captured by univariate trees. The paper presented a detailed discussion of the algorithm for constructing multivariate decision trees, emphasizing the importance of considering all variables simultaneously during the splitting process. The authors also provided examples to illustrate how these trees can be used in practice, showcasing their ability to handle complex datasets with ease. Overall, Brodley and Utgoff's work on multivariate decision trees represents a significant advancement in the field of machine learning. By introducing a more flexible and powerful approach to decision tree construction, they have paved the way for more sophisticated data analysis techniques and have opened up new possibilities for improving the performance of machine learning algorithms."

BRODLEY

AND

UTGOFF

al., 1993; Murthy, Kasif, Salzberg

Beigel, 1993).

These

two

modifications decrease

the

chance

getting stuck

local minima when searching

for a set of

coefficients.

Another approach

is to use

linear programming (LP)

to find a set of

coefficients.

Re-

cently, Bennett

and

Mangasarian (1992) have created

linear programming approach that

minimizes

the

average error

of the

misclassified objects. Unlike other

methods, their

method always

finds an

optimal nondegenerate solution

in a

single linear program without

imposing

any

additional constraints.

2.5

Feature

selection

Which features should

selected

for a

linear combination test?

One

wants

eliminate

noisy

and

irrelevant features, minimize

the

number

features

in the

test

increase under-

standability,

and

decrease

the

number

features

in the

data that need

to be

evaluated.

addition,

one

wants

to find the

best combination with respect

some partition-merit crite-

rion.

For

most data sets

will

impossible

to try

every combination

features because

the

number

possible combinations

exponential

in the

number

features. Therefore,

some type

heuristic search procedure must

used.

Two

well-known greedy algorithms

for

selecting features

for a

linear combination test

are

Sequential Backward Elimination

(SBE)

and

Sequential Forward Selection (SFS) (Kittler, 1986).

An SEE

search begins with

all

features

and

removes those features that

do not

contribute

to the

effectiveness

of the

split.

SBE is

based

on the

assumption that

it is

better

for a

useful

projection onto

fewer

dimensions from

relatively well

informed

state than

it is to

for a

projection

onto more dimensions

from

relatively uninformed state (Breiman,

al.,

1984).

An SFS

search starts with

zero

features

and

sequentially adds

the

feature that contributes most

the

effectiveness

of the

split.

will

discuss these

two

approaches

detail

Section

Another factor

feature selection

is the

decision

whether

one is

willing

trade

accuracy

for

simplicity.

there

is a

cost associated with obtaining

the

value

of a

feature,

then

one can

bias

the

selection process

select less expensive features.

The

criterion

function

used

select

features

can be a

function

cost

and

quality.

For

example,

one can

restrict

the

number

features permitted

in a

test

when using

an SBE

search, continue

eliminate features

long

there

is not

more than some prespecified percentage drop

the

partition-merit criterion.

addition

searching

for the

best linear combination using some partition-merit crite-

rion,

one

must also

pay

attention

to the

number

instances

at a

node relative

to the

number

features

in the

test.

If the

number

unique instances

is not

more than several times

the

dimensionality

of the

number

features

in the

test, then

the

test will

underfit

the

training

instances (Duda

Hart, 1973).

other words, when there

are too few

instances, there

are

many possible orientations

for the

hyperplane defined

by the

test,

and

there

is no

basis

for

selecting

one

orientation over another.

these

cases

the

feature selection mechanism

should only consider tests that

will

not

underfit

the

training instances.

call this

selec-

tion

criterion

the

underfilling criterion. When this criterion

used with

the SBE

method,

features will

eliminated until

the

test

longer

underfits

the

training data. When used

with

the SFS

method, features will

added only

long

as the

addition

of a new

feature

will

not

cause

the

test

underfit

the

training data.

mentioned

Section 2.4, coefficient learning methods that seek

maximize accu-

racy

on the

training instances

may

fail

to find a

test

that discriminates

the

instances.

provide

partial solution

this dilemma,

one can add a

discrimination criterion

to the

MULTIVARIATE DECISION TREES

feature

selection method. Then

the

goal

of a

feature selection algorithm

is to find a

linear

combination

test based

on the

fewest features that maximizes

the

partition merit criterion,

discriminates

the

instances

and

does

not

underfit

the

training

instances.

2.6

Avoiding

overfilling

common approach

correcting

for

overfitting

in a

decision tree model

is to

prune back

the

tree

to an

appropriate level.

tree

grown, which classifies

all the

training

instances

correctly,

and

then

subtrees

are

pruned

back

reduce

future

classification

errors

(Breiman,

al., 1984; Quinlan, 1987). Quinlan (1987b)

and

Mingers (1989b) compare commonly

used

methods.

Traditional pruning methods examine

the

effect

eliminating entire nodes

subtrees

the

tree

determine

they should

pruned. However, although

multivariate test

may

overfit

the

training instances, pruning

the

entire node

may

result

even more classification

errors.

The

issue here

is the

granularity

of the

nodes

in a

multivariate decision tree;

the

granularity

can

vary

from

univariate test

at one end of the

spectrum

to a

multivariate test

based

on all n

features

at the

other end.

In the

case

where removing

multivariate test results

higher estimated error,

one can try to

reduce

the

error

eliminating features

from

the

multivariate test. Eliminating features generalizes

the

multivariate test;

multivariate test

based

on n — 1

features

more general than

one

based

on n

features.

Learning

the

coefficients

of a

linear combination test

this section

review

four

existing methods

for

learning

the

coefficients

of a

linear com-

bination

test

The first

method, Recursive Least Squares (RLS)

(Young,

1984),

minimizes

the

mean-squared error over

the

training data.

The

second method,

the

Pocket Algorithm

(Gallant, 1986), maximizes

the

number

correct classifications

on the

training

data.

The

third

method, Thermal Training (Frean, 1990), converges

to a set of

coefficients

pay-

ing

decreasing attention

large errors.

The

fourth

method, CART's

coefficient

learning

method (Breiman,

et al.

1984), explicitly searches

for a set of

coefficients

that minimizes

the

impurity

of the

partition created

by the

multivariate test.

The RLS and

CART methods

are

restricted

binary partitions

of the

data, whereas

the

Thermal

and

Pocket algorithms

produce multiway partitions.

3.1

Recursive Least Squares procedure

The

Recursive Least Squares Algorithm, invented

Gauss,

is a

recursive version

of the

Least Squares (LS) Algorithm.

procedure minimizes

the

mean squared error,

(

(y,

yi)

of the

training data, where

y, is the

true value

and y

is the

estimated value

of the

dependent variable,

y, for

instance

i. For

discrete

classification

problems,

the

true value

of the

dependent variable (the class)

either

c or

—

c. In our

implementation

of the RLS

procedure

we use c = 1.

To find the

coefficients

of the

linear

function

that

minimizes

the

mean-squared error,

the

RLS

algorithm incrementally updates

the

coefficients

using

the

error between

the

estimated

value

of the

dependent variable

and the

true value. Specifically,

after

instance

k is

observed,

剩余32页未读，继续阅读

白小俗

粉丝: 37

"1995多变量决策树研究：Brodley与Utgooff的合作探索"

MultivariateStats.jl：Julia包进行多变量统计与降维

探索多元交替决策树：ADTree的多元扩展及其在matlab中的应用

多元正态分布的JavaScript实现与Node.JS端口

多变量决策树算法的实现与比较

机器学习算法详解：决策树与随机森林

数据挖掘必备：CART决策树模型的实战应用与技巧

决策树优化技巧：利用信息增益提升分类准确率的秘诀

高级数据分析：信息增益在复杂决策树结构中的巧妙应用

【模型泛化能力评估】：交叉验证在决策树中的实际应用技巧

神经影像多变量分析：MLM技术解析

最新资源