A worldwide Internet usage growth rate of 380% over the period from 2000, the year of the dot-com bubble burst, until present indicates that Internet technology has become a cornerstone of our daily life. In the same period, cyber-crime has seen an incredible professionalization that makes sophisticated protection mechanisms for computers and networks an absolute necessity. Firewalls as the major defense of the last decade do not provide sufficient protection anymore. This fact has given rise to the development of intrusion detection and prevention systems. Traditional intrusion detection systems are reactive in the sense that they use a set of signatures, which grows at the same rate as new vulnerabilities are discovered, to identify malicious traffic patterns. Anomaly detection systems are another branch of intrusion detection systems that act more proactively. They derive a model of the normal system behavior and issue alerts whenever the behavior changes; making a subtle assumption that such changes are frequently caused by malicious or disruptive events. Anomaly detection has been a field of intensive research over the last years as it poses several challenging problems.In this thesis, we address three of these challenges. When working with large-scale network data from possibly multiple routers, the curse of dimensionality considerably complicates the problem of anomaly detection. Principal component analysis has been proposed to deal with it. However, as subsequent work has discovered several deficiencies in the proposed PCAmethod, there is room for improvement. A second challenge stems from the underlying assumption of anomaly detection mentioned above, which, unfortunately, does not always hold in practice.