Describe the potential time complexity of anomaly detection approaches based on the following approaches: model-based using clustering, proximity- based, and density. No knowledge of specific techniques is required. Rather, focus on the basic computational requirements of each approach, such as the time required to compute the density of each object.

Question

What will be an ideal response?

Answer 1

If K-means clustering is used, then the complexity is dominated by finding
the clusters. This requires time proportional to the number of objects, i.e.,
O(m). The distance and density based approaches, usually require computing
all the pairwise proximities, and thus the complexity is often O(m2). In
some cases, such as low dimensional data, special techniques, such as the R?
tree or k-d trees can be used to compute the nearest neighbors of an object
more efficiently, i.e., O(m log m), and this can reduce the overall complexity
when the technique is based only on nearest neighbors. Also, a grid-based
approach to computing density can reduce the complexity of density-based
anomaly detection to O(m), but such techniques are not as accurate and are
only effective for low dimensions.