Abstract Attribute-Based Prediction of File Properties(4)

Given a sample of?les,a decision tree learning algo-rithm attempts to recursively split the samples into clus-ters.The goal is to create clusters whose?les have sim-ilar attributes and similar classi?cations.Figure3illus-trates the ID3algorithm used by ABLE to induce a tree

ta

2. split attribute A

3. if leave nodes are "pure" done

4. else, if attributes remaining, goto 1

Figure3:Constructing a simple decision tree from the training data in Table2.

We present evidence that attributes that are known to the file system when a file is created, such as its name, permission mode, and owner, are often strongly related to future properties of the file such as its ultimate size, lifespan, and access pattern.

EECS03

MODE ABLE MODE

size=098.97%66.58%98.57%

0size16KB95.42%57.69%98.83%

lftmd1s(?le)88.16%58.80%72.95%

lftmd1s(direntry)96.96%52.80%77.66%

wronly91.17%46.98%81.83%

rdonly75.55%49.63%81.24%

Table3:A comparison of the accuracy of the ABLE and MODE predictors for several properties for the three traces. MODE always predicts the value that occurred most frequently in the training sample,without considering any at-tributes of the new?le.

We present evidence that attributes that are known to the file system when a file is created, such as its name, permission mode, and owner, are often strongly related to future properties of the file such as its ultimate size, lifespan, and access pattern.

against the ABLE(unconstrained)decision trees. MABLE:trees induced with only the inode attributes (mode,uid,gid).

NABLE:trees induced with only?le names.

Figure4compares the predication accuracies for ABLE,MABLE and NABLE.For the purpose of clarity, this?gure only shows the accuracy for three of our bi-nary properties(size,write-only,and?le name lifespan); the results for our other properties are similar.The?g-ure shows that ABLE usually outperforms both MABLE and NABLE.This tells that some multi-way associations exist between the?le name attributes and other attributes that allow us to make more accurate predictions when all are considered.An example of a multi-way association would be that the lifespan of a?le depends on both the ?le name and the user who created the?le.

However,the CAMPUS and EECS03results tell us that,in some situations,ABLE does worse than MABLE or NABLE.In these traces,some multi-way associations existed on Monday that did not generalize to new?les on Tuesday.This is a common problem of over-?tting the data with too many attributes,although the differences are not severe in our evaluation.

There are two important points to take away from our analysis of MABLE and NABLE.First,more attributes are not always better.We can fall into a trap known as the curse of dimensionality in which each attribute adds a new dimension to the sample space[6].Unless we see a suf?cient number of?les,our decision trees may get clouded by transient multi-way associations that do not apply in the long run.Second,NABLE and MABLE offer predictions roughly equivalent to ABLE.This is somewhat surprising,particularly in the case of MABLE, because it means that we can make accurate predictions even if we do not consider?le names at all.

Given enough training data,ABLE always outper-forms MABLE and NABLE.For the results presented in the paper,ABLE required an extra week of training to detect the false attribute associations,due in part to the small number of attributes.We anticipate that more training will be required for systems with larger attribute spaces,such as object-based storage with extended at-tributes[18]and non-UNIX?le systems such as CIFS or NTFS[29].Furthermore,irrelevant attributes may need to be pre-?ltered before induction of the decision tree[6] to prevent over-?tting.The automation of ABLE’s train-ing policies,including attribute?ltering,is an area for future work.

DEAS0303/24/2003

20

40

60

80

p

r

e

d

i

c

t

i

o

n

a

c

c

u

r

a

c

y

(

%

)

EECS0303/24/2003

p

r

e

d

i

c

t

i

o

n

a

c

c

u

r

a

c

y

(

%

)

CAMPUS

10/22/2001

20

40

60

80

p

r

e

d

i

c

t

i

o

n

a

c

c

u

r

a

c

y

(

%

)

Figure4:Comparing the prediction accuracy of ABLE, NABLE,and MABLE for the properties size=0,write-only,and lifetime1second.Prediction accuracy is measured as percentage correct.

We present evidence that attributes that are known to the file system when a file is created, such as its name, permission mode, and owner, are often strongly related to future properties of the file such as its ultimate size, lifespan, and access pattern.

?NABLE predicts “write-mostly" if

first=cache & last=gif [5742/94.0%]?MABLE predicts “size=0” if

mode=777 [4535/99.8%]?ABLE predicts “deleted within 1 sec” if

first = 01eb & last = 0004 & mode = 777 &

uid = 18abe [1148/99.7%] Figure5:Example rules for DEAS03discovered by NABLE,MABLE,and ABLE.The number of?les that match the attributes and the observed probability that these?les have the given property are shown on the right. For example,NABLE predicts that names whose name begins with cache and end in.gif will be“write-mostly”.This prediction is based on observations of 5742?les,94.0%of which have the“write-only”prop-erty.

We present evidenc …… 此处隐藏：5294字，全部文档内容请下载后查看。喜欢就下载吧 ……