Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| en:iot-reloaded:dbscan [2024/09/25 12:43] – agrisnik | en:iot-reloaded:dbscan [2024/12/10 20:44] (current) – pczekalski | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ===== DBSCAN ===== | ===== DBSCAN ===== | ||
| - | {{: | ||
| - | |||
| DBSCAN (Density-Based Spatial Clustering of Applications with Noise) employs density measures to mark points in high-density regions and those in low-density regions – the noise. Because of this natural behaviour of the algorithm, it is particularly useful in signal processing and similar application domains. | DBSCAN (Density-Based Spatial Clustering of Applications with Noise) employs density measures to mark points in high-density regions and those in low-density regions – the noise. Because of this natural behaviour of the algorithm, it is particularly useful in signal processing and similar application domains. | ||
| Line 8: | Line 6: | ||
| One of the essential concepts is the point' | One of the essential concepts is the point' | ||
| - | <figure Point' | + | {{ : |
| - | {{ : | + | |
| - | < | + | |
| - | </ | + | |
| - | , where: | + | where: |
| - | * **p** – the point of interest; | + | * **p** – the point of interest. |
| - | * **N(p)** – neighbourhood of the point p; | + | * **N(p)** – neighbourhood of the point p. |
| - | * **q** – any other point; | + | * **q** – any other point. |
| - | * **distance(p, | + | * **distance(p, |
| - | * **eps** – epsilon – user-defined distance constant; | + | * **eps** – epsilon – user-defined distance constant. |
| - | * **D** – the initial set of points available for the algorithm; | + | * **D** – the initial set of points available for the algorithm. |
| The algorithm treats different points differently depending on density and neighbouring points distribution around the point – its neighbourhood: | The algorithm treats different points differently depending on density and neighbouring points distribution around the point – its neighbourhood: | ||
| Line 32: | Line 27: | ||
| * Points that are not core and are not reachable from any core point are considered noise or outliers. | * Points that are not core and are not reachable from any core point are considered noise or outliers. | ||
| - | < | + | < |
| - | {{ : | + | {{ : |
| - | < | + | < |
| </ | </ | ||
| * **The main steps in DBSCAN:** | * **The main steps in DBSCAN:** | ||
| - | * Selects a point from the data set – it might be the first in the data set or any randomly selected; | + | * Selects a point from the data set – it might be the first in the data set or any randomly selected. |
| * If it is a core point, form a cluster by grouping it with all directly density-reachable points. | * If it is a core point, form a cluster by grouping it with all directly density-reachable points. | ||
| * Move to the next unvisited point and return to step 1. | * Move to the next unvisited point and return to step 1. | ||
| - | * Border points are added to the nearest cluster, and points | + | * Border points are added to the nearest cluster, and points not reachable from any core point are marked as noise. |
| Line 53: | Line 48: | ||
| * It struggles with clusters of varying densities since eps is fixed. | * It struggles with clusters of varying densities since eps is fixed. | ||
| - | DBSCAN is great for discovering clusters in data with noise, especially when clusters are not circular or spherical. | + | DBSCAN is excellent |
| - | Some application examples: | + | Some application examples |
| - | < | + | < |
| - | {{ : | + | {{ : |
| - | < | + | < |
| </ | </ | ||
| - | < | + | < |
| - | {{ : | + | {{ : |
| - | < | + | < |
| </ | </ | ||
| - | A typical application in signal processing: | + | A typical application in signal processing |
| - | < | + | < |
| - | {{ : | + | {{ : |
| - | < | + | < |
| </ | </ | ||
| Line 77: | Line 72: | ||
| Usually, MinPts is selected using some prior knowledge of the data and its internal structure. If it is done, the following steps might be applied: | Usually, MinPts is selected using some prior knowledge of the data and its internal structure. If it is done, the following steps might be applied: | ||
| - | * Unordered List ItemCalculate | + | * Calculate |
| * The average distances are sorted and depicted on a chart, where x – is the index of the sorted average distance, y – is the distance value. | * The average distances are sorted and depicted on a chart, where x – is the index of the sorted average distance, y – is the distance value. | ||
| - | * The optimal eps value is when y increases rapidly, as shown in the following picture on artificial sample data. | + | * The optimal eps value is when y increases rapidly, as shown in the following picture |
| - | < | + | < |
| {{ : | {{ : | ||
| < | < | ||
