Given a continuous stream of incoming data, a popular task is to determine whether a change has happened. For example, if the data is some atmospheric data, a change can happen to due sudden events such as hill fire, leakage of chemicals, etc; if the data is financial, a change can reflect big swings in the market. The problem can be modeled as an edge-weighted path graph that keeps growing on one end, and the task is to detect changes as the path graph grows. This project is to implement a method for determining the edge weights as the path graph grows, followed by adjusting the clustering of vertices in the path graph in order to detect changes.
The project will need three different things:
(1) implement a method designed by myself and others to incrementally build a good weighted path graph,
(2) design a good algorithm for clustering in the weighted path graph, possibly at multiple resolutions, for detecting changes,
(3) implement the change detecting algorithm in (2) and perform experiments to check effectiveness.
- Learn how the build a path weighted graph for clustering and change analysis.
- Learn clustering algorithms.