Storage device performance prediction with CART models(18)

Storage device performance prediction is a key element of self-managed storage systems and application planning tasks, such as data assignment. This work explores the application of a machine learning tool, CART models, to storage device modeling. Our appr

AppendixA:ConstructingCARTModels

ACARTmodelisapiecewise-constantfunctiononamulti-dimensionalspace.Thisappendixgivesabriefdescriptionofthemodelconstructionalgorithm.Pleasereferto[4]foracompletediscussionofCARTmodels.

TheCARTmodelhasabinarytreestructurebuiltbyrecursivebinarysplits.SupposewehaveNobser-vations,Xii12N,withcorrespondingoutputsYii12N.Eachobservationconsistsofpinputfeatures,Xixi1xip).Theconstructionalgorithmstartswithatreewithonlyarootnodeandgrowsthetreedownwardbysplittingonenodeatime.Thechosensplitoffersthemostbene tinreducingthemeansquarederror.TheaverageYiforalltheXisinaleafnodeisusedasthepredictivevaluefortheleafnode.Thealgorithmcontinuesuntilcertaincriteriaaremet.

Wedescribehowthesplitischosenindetailnext.Thealgorithmevaluatesallthepossibledistinctsplitsonalltheleafnodesofthetree(ortherootnodeinthe rststep).Anodecorrespondstoahyer-rectangleregionoftheinputvectorspace,andasplitdecidesalongwhichfeatureandatwhatvaluetheregionshouldbedividedintotwo.Forexample,atnodet,asplitonfeaturejatvaluevde nestwonodes,nodet1andnodet2.

Xi

nodet1

Xixij

v

Xi

nodet

Xi

nodet2

Xixij

v

Xinodet

IfwedenotethenumberofobservationsinnodetasNtandthepredictivevalueasYt,themeansquarederroratnodetbeforethesplitis

MSEt

i:Xinodet

∑

1

Nt1

Yi

¯t1Y

2

i:Xinodet2

∑

1