With the tremendous growth of shopping, banking, and other business transactions over computers network in the last two decades, The number of potential cyber-attacks by intruders has increased. Therefore the efforts are continually required in order to improve the effectiveness of detecting the network intruders. In this paper, a new network anomaly detection approach, which is based on outlier detection scheme, is presented. The frequent patterns are exploited for modeling the normal behavior of the traffic data and for calculating the deviation of the current traffic data points. The experimental results on KDD99 data set demonstrate the effectiveness of the propose approach in comparison with existing methods. © 2014 IEEE.