Abstract: To improve the performance of web cache,a new cache replacement algorithm named PGDSF-AI is proposed.The Algorithm is based on multi-Markov chains prediction model and characteristics of user browsing is used.Firstly,the Web users are classified according to browsing characteristics and a classified-Markov is built for a classified users,and then multi-Markov chains prediction model is constructed.Then,the prediction model is forecasted based on user access sequence and the target set of prediction is formed.When the cache has not enough space to accommodate new request,replace the key which is the smallest and does not belong to the target set of prediction.The average interval is used to avoid objects long time no access retaining in the cache.Experimental results have showed that the proposed algorithm had good performance.