OPTICS algorithm - Revision history

Citation bot: Added isbn. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar

2025-04-23T10:56:08Z

Added isbn. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar

← Previous revision		Revision as of 10:56, 23 April 2025
Line 130:		Line 130:
	\| title = Advances in Knowledge Discovery and Data Mining, 10th Pacific-Asia Conference, PAKDD 2006, Singapore, April 9-12, 2006, Proceedings		\| title = Advances in Knowledge Discovery and Data Mining, 10th Pacific-Asia Conference, PAKDD 2006, Singapore, April 9-12, 2006, Proceedings
	\| volume = 3918		\| volume = 3918
			\| year = 2006\| isbn = 978-3-540-33206-0
	~~\| year = 2006~~}}</ref> Density-Link-Clustering combines ideas from [[single-linkage clustering]] and OPTICS, eliminating the <math>\varepsilon</math> parameter and offering performance improvements over OPTICS.		}}</ref> Density-Link-Clustering combines ideas from [[single-linkage clustering]] and OPTICS, eliminating the <math>\varepsilon</math> parameter and offering performance improvements over OPTICS.

	HiSC<ref>{{cite conference		HiSC<ref>{{cite conference
Line 150:		Line 151:
	\| volume = 4213		\| volume = 4213
	\| year = 2006\| doi-access = free		\| year = 2006\| doi-access = free
			\| isbn = 978-3-540-45374-1
	}}</ref> is a hierarchical [[subspace clustering]] (axis-parallel) method based on OPTICS.		}}</ref> is a hierarchical [[subspace clustering]] (axis-parallel) method based on OPTICS.

Line 172:		Line 174:
	\| title = Advances in Databases: Concepts, Systems and Applications, 12th International Conference on Database Systems for Advanced Applications, DASFAA 2007, Bangkok, Thailand, April 9-12, 2007, Proceedings		\| title = Advances in Databases: Concepts, Systems and Applications, 12th International Conference on Database Systems for Advanced Applications, DASFAA 2007, Bangkok, Thailand, April 9-12, 2007, Proceedings
	\| volume = 4443		\| volume = 4443
	\| year = 2007}}</ref> is an improvement over HiSC that can find more complex hierarchies.		\| year = 2007\| isbn = 978-3-540-71702-7
			}}</ref> is an improvement over HiSC that can find more complex hierarchies.

	FOPTICS<ref>{{Cite journal \| last1 = Schneider \| first1 = Johannes \| last2 = Vlachos \| first2 = Michail \| year = 2013 \| title = Fast parameterless density-based clustering via random projections \| journal = 22nd ACM International Conference on Information and Knowledge Management(CIKM) }}</ref> is a faster implementation using random projections.		FOPTICS<ref>{{Cite journal \| last1 = Schneider \| first1 = Johannes \| last2 = Vlachos \| first2 = Michail \| year = 2013 \| title = Fast parameterless density-based clustering via random projections \| journal = 22nd ACM International Conference on Information and Knowledge Management(CIKM) }}</ref> is a faster implementation using random projections.

147.86.223.1 at 09:42, 16 April 2025

2025-04-16T09:42:30Z

← Previous revision		Revision as of 09:42, 16 April 2025
Line 1:		Line 1:
	{{Short description\|Algorithm for finding density based clusters in spatial data}}		{{Short description\|Algorithm for finding density based clusters in spatial data}}
	{{Machine learning\|Clustering}}		{{Machine learning\|Clustering}}
	'''Ordering points to identify the clustering structure''' ('''OPTICS''') is an algorithm for finding density-based<ref>{{cite journal\|last1=Kriegel\|first1=Hans-Peter\|last2=Kröger\|first2=Peer\|last3=Sander\|first3=Jörg\|last4=Zimek\|first4=Arthur\|title=Density-based clustering\|journal=Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery\|date=May 2011\|volume=1\|issue=3\|pages=231–240\|doi=10.1002/widm.30\|s2cid=36920706 \|url=https://portal.findresearcher.sdu.dk/da/publications/be8fe7b9-d5e2-415c-91bc-5ac6fa00994b}}</ref> [[Cluster analysis\|clusters]] in spatial data. It was presented by Mihael Ankerst, Markus M. Breunig, [[Hans-Peter Kriegel]] and Jörg Sander.<ref name=":0">{{Cite conference		'''Ordering points to identify the clustering structure''' ('''OPTICS''') is an algorithm for finding density-based<ref>{{cite journal\|last1=Kriegel\|first1=Hans-Peter\|last2=Kröger\|first2=Peer\|last3=Sander\|first3=Jörg\|last4=Zimek\|first4=Arthur\|title=Density-based clustering\|journal=Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery\|date=May 2011\|volume=1\|issue=3\|pages=231–240\|doi=10.1002/widm.30\|s2cid=36920706 \|url=https://portal.findresearcher.sdu.dk/da/publications/be8fe7b9-d5e2-415c-91bc-5ac6fa00994b}}</ref> [[Cluster analysis\|clusters]] in spatial data. It was presented in 1999 by Mihael Ankerst, Markus M. Breunig, [[Hans-Peter Kriegel]] and Jörg Sander.<ref name=":0">{{Cite conference
	\|author=Mihael Ankerst \|author2=Markus M. Breunig \|author3=Hans-Peter Kriegel \|author3-link=Hans-Peter Kriegel \|author4=Jörg Sander		\|author=Mihael Ankerst \|author2=Markus M. Breunig \|author3=Hans-Peter Kriegel \|author3-link=Hans-Peter Kriegel \|author4=Jörg Sander
	\| title = OPTICS: Ordering Points To Identify the Clustering Structure		\| title = OPTICS: Ordering Points To Identify the Clustering Structure

Citation bot: Alter: pages. Add: authors 1-1. Removed parameters. Formatted dashes. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Corvus florensis | #UCB_webform 153/2499

2023-12-02T14:33:13Z

Alter: pages. Add: authors 1-1. Removed parameters. Formatted dashes. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Corvus florensis | #UCB_webform 153/2499

← Previous revision		Revision as of 14:33, 2 December 2023
Line 93:		Line 93:
	The image above illustrates this concept. In its upper left area, a synthetic example data set is shown. The upper right part visualizes the [[spanning tree]] produced by OPTICS, and the lower part shows the reachability plot as computed by OPTICS. Colors in this plot are labels, and not computed by the algorithm; but it is well visible how the valleys in the plot correspond to the clusters in above data set. The yellow points in this image are considered noise, and no valley is found in their reachability plot. They are usually not assigned to clusters, except the omnipresent "all data" cluster in a hierarchical result.		The image above illustrates this concept. In its upper left area, a synthetic example data set is shown. The upper right part visualizes the [[spanning tree]] produced by OPTICS, and the lower part shows the reachability plot as computed by OPTICS. Colors in this plot are labels, and not computed by the algorithm; but it is well visible how the valleys in the plot correspond to the clusters in above data set. The yellow points in this image are considered noise, and no valley is found in their reachability plot. They are usually not assigned to clusters, except the omnipresent "all data" cluster in a hierarchical result.

	Extracting clusters from this plot can be done manually by selecting ranges on the x-axis after visual inspection, by selecting a threshold on the y-axis (the result is then similar to a DBSCAN clustering result with the same <math>\varepsilon</math> and {{not a typo\|minPts}} parameters; here a value of 0.1 may yield good results), or by different algorithms that try to detect the valleys by steepness, knee detection, or local maxima. A range of the plot beginning with a steep descent and ending with a steep ascent is considered a valley, and corresponds to a contiguous area of high density. Additional care must be taken to the last points in a valley to assign them to the inner or outer cluster, this can be achieved by considering the predecessor.<ref>{{Cite conference \|~~last~~=Schubert \|~~first~~=Erich \|last2=Gertz \|first2=Michael \|date=2018-08-22 \|title=Improving the Cluster Structure Extracted from OPTICS Plots \|url=http://ceur-ws.org/Vol-2191/paper37.pdf \|conference=Lernen, Wissen, Daten, Analysen (LWDA 2018) \|volume=CEUR-WS 2191 \|pages=~~318-329~~ \|via=CEUR-WS}}</ref> Clusterings obtained this way usually are [[hierarchical clustering\|hierarchical]], and cannot be achieved by a single DBSCAN run.		Extracting clusters from this plot can be done manually by selecting ranges on the x-axis after visual inspection, by selecting a threshold on the y-axis (the result is then similar to a DBSCAN clustering result with the same <math>\varepsilon</math> and {{not a typo\|minPts}} parameters; here a value of 0.1 may yield good results), or by different algorithms that try to detect the valleys by steepness, knee detection, or local maxima. A range of the plot beginning with a steep descent and ending with a steep ascent is considered a valley, and corresponds to a contiguous area of high density. Additional care must be taken to the last points in a valley to assign them to the inner or outer cluster, this can be achieved by considering the predecessor.<ref>{{Cite conference \|last1=Schubert \|first1=Erich \|last2=Gertz \|first2=Michael \|date=2018-08-22 \|title=Improving the Cluster Structure Extracted from OPTICS Plots \|url=http://ceur-ws.org/Vol-2191/paper37.pdf \|conference=Lernen, Wissen, Daten, Analysen (LWDA 2018) \|volume=CEUR-WS 2191 \|pages=318–329 \|via=CEUR-WS}}</ref> Clusterings obtained this way usually are [[hierarchical clustering\|hierarchical]], and cannot be achieved by a single DBSCAN run.

	==Complexity==		==Complexity==

78.49.25.106: Replace {-} in citations by -, fix cite journal to cite conference.

2023-08-06T12:00:34Z

Replace {-} in citations by -, fix cite journal to cite conference.

← Previous revision		Revision as of 12:00, 6 August 2023
Line 93:		Line 93:
	The image above illustrates this concept. In its upper left area, a synthetic example data set is shown. The upper right part visualizes the [[spanning tree]] produced by OPTICS, and the lower part shows the reachability plot as computed by OPTICS. Colors in this plot are labels, and not computed by the algorithm; but it is well visible how the valleys in the plot correspond to the clusters in above data set. The yellow points in this image are considered noise, and no valley is found in their reachability plot. They are usually not assigned to clusters, except the omnipresent "all data" cluster in a hierarchical result.		The image above illustrates this concept. In its upper left area, a synthetic example data set is shown. The upper right part visualizes the [[spanning tree]] produced by OPTICS, and the lower part shows the reachability plot as computed by OPTICS. Colors in this plot are labels, and not computed by the algorithm; but it is well visible how the valleys in the plot correspond to the clusters in above data set. The yellow points in this image are considered noise, and no valley is found in their reachability plot. They are usually not assigned to clusters, except the omnipresent "all data" cluster in a hierarchical result.

	Extracting clusters from this plot can be done manually by selecting ranges on the x-axis after visual inspection, by selecting a threshold on the y-axis (the result is then similar to a DBSCAN clustering result with the same <math>\varepsilon</math> and {{not a typo\|minPts}} parameters; here a value of 0.1 may yield good results), or by different algorithms that try to detect the valleys by steepness, knee detection, or local maxima. A range of the plot beginning with a steep descent and ending with a steep ascent is considered a valley, and corresponds to a contiguous area of high density. Additional care must be taken to the last points in a valley to assign them to the inner or outer cluster, this can be achieved by considering the predecessor.<ref>{{Cite ~~journal~~ \|last=Schubert \|first=Erich \|last2=Gertz \|first2=Michael \|date=2018-08-22 \|title=Improving the Cluster Structure Extracted from OPTICS Plots \|url=http://ceur-ws.org/Vol-2191/paper37.pdf \|~~journal~~=Lernen, Wissen, Daten, Analysen (LWDA 2018) \|volume=2191 \|pages=318-329 \|via=CEUR-WS}}</ref> Clusterings obtained this way usually are [[hierarchical clustering\|hierarchical]], and cannot be achieved by a single DBSCAN run.		Extracting clusters from this plot can be done manually by selecting ranges on the x-axis after visual inspection, by selecting a threshold on the y-axis (the result is then similar to a DBSCAN clustering result with the same <math>\varepsilon</math> and {{not a typo\|minPts}} parameters; here a value of 0.1 may yield good results), or by different algorithms that try to detect the valleys by steepness, knee detection, or local maxima. A range of the plot beginning with a steep descent and ending with a steep ascent is considered a valley, and corresponds to a contiguous area of high density. Additional care must be taken to the last points in a valley to assign them to the inner or outer cluster, this can be achieved by considering the predecessor.<ref>{{Cite conference \|last=Schubert \|first=Erich \|last2=Gertz \|first2=Michael \|date=2018-08-22 \|title=Improving the Cluster Structure Extracted from OPTICS Plots \|url=http://ceur-ws.org/Vol-2191/paper37.pdf \|conference=Lernen, Wissen, Daten, Analysen (LWDA 2018) \|volume=CEUR-WS 2191 \|pages=318-329 \|via=CEUR-WS}}</ref> Clusterings obtained this way usually are [[hierarchical clustering\|hierarchical]], and cannot be achieved by a single DBSCAN run.

	==Complexity==		==Complexity==
Line 135:		Line 135:
	\| last1 = Achtert \| first1 = Elke		\| last1 = Achtert \| first1 = Elke
	\| last2 = Böhm \| first2 = Christian		\| last2 = Böhm \| first2 = Christian
	\| last3 = Kriegel \| first3 = Hans{-}Peter		\| last3 = Kriegel \| first3 = Hans-Peter
	\| last4 = Kröger \| first4 = Peer		\| last4 = Kröger \| first4 = Peer
	\| last5 = Müller{-}Gorman \| first5 = Ina		\| last5 = Müller-Gorman \| first5 = Ina
	\| last6 = Zimek \| first6 = Arthur		\| last6 = Zimek \| first6 = Arthur
	\| editor1-last = Fürnkranz \| editor1-first = Johannes		\| editor1-last = Fürnkranz \| editor1-first = Johannes
Line 157:		Line 157:
	\| last1 = Achtert \| first1 = Elke		\| last1 = Achtert \| first1 = Elke
	\| last2 = Böhm \| first2 = Christian		\| last2 = Böhm \| first2 = Christian
	\| last3 = Kriegel \| first3 = Hans{-}Peter		\| last3 = Kriegel \| first3 = Hans-Peter
	\| last4 = Kröger \| first4 = Peer		\| last4 = Kröger \| first4 = Peer
	\| last5 = Müller{-}Gorman \| first5 = Ina		\| last5 = Müller-Gorman \| first5 = Ina
	\| last6 = Zimek \| first6 = Arthur		\| last6 = Zimek \| first6 = Arthur
	\| editor1-last = Ramamohanarao \| editor1-first = Kotagiri		\| editor1-last = Ramamohanarao \| editor1-first = Kotagiri

78.49.25.106: Explain removal of artifacts using predecessor information, as implemented in sklearn, R and ELKI.

2023-08-06T11:58:20Z

Explain removal of artifacts using predecessor information, as implemented in sklearn, R and ELKI.

← Previous revision		Revision as of 11:58, 6 August 2023
Line 93:		Line 93:
	The image above illustrates this concept. In its upper left area, a synthetic example data set is shown. The upper right part visualizes the [[spanning tree]] produced by OPTICS, and the lower part shows the reachability plot as computed by OPTICS. Colors in this plot are labels, and not computed by the algorithm; but it is well visible how the valleys in the plot correspond to the clusters in above data set. The yellow points in this image are considered noise, and no valley is found in their reachability plot. They are usually not assigned to clusters, except the omnipresent "all data" cluster in a hierarchical result.		The image above illustrates this concept. In its upper left area, a synthetic example data set is shown. The upper right part visualizes the [[spanning tree]] produced by OPTICS, and the lower part shows the reachability plot as computed by OPTICS. Colors in this plot are labels, and not computed by the algorithm; but it is well visible how the valleys in the plot correspond to the clusters in above data set. The yellow points in this image are considered noise, and no valley is found in their reachability plot. They are usually not assigned to clusters, except the omnipresent "all data" cluster in a hierarchical result.

	Extracting clusters from this plot can be done manually by selecting ~~a range~~ on the x-axis after visual inspection, by selecting a threshold on the y-axis (the result is then similar to a DBSCAN clustering result with the same <math>\varepsilon</math> and {{not a typo\|minPts}} parameters; here a value of 0.1 may yield good results), or by different algorithms that try to detect the valleys by steepness, knee detection, or local maxima. Clusterings obtained this way usually are [[hierarchical clustering\|hierarchical]], and cannot be achieved by a single DBSCAN run.		Extracting clusters from this plot can be done manually by selecting ranges on the x-axis after visual inspection, by selecting a threshold on the y-axis (the result is then similar to a DBSCAN clustering result with the same <math>\varepsilon</math> and {{not a typo\|minPts}} parameters; here a value of 0.1 may yield good results), or by different algorithms that try to detect the valleys by steepness, knee detection, or local maxima. A range of the plot beginning with a steep descent and ending with a steep ascent is considered a valley, and corresponds to a contiguous area of high density. Additional care must be taken to the last points in a valley to assign them to the inner or outer cluster, this can be achieved by considering the predecessor.<ref>{{Cite journal \|last=Schubert \|first=Erich \|last2=Gertz \|first2=Michael \|date=2018-08-22 \|title=Improving the Cluster Structure Extracted from OPTICS Plots \|url=http://ceur-ws.org/Vol-2191/paper37.pdf \|journal=Lernen, Wissen, Daten, Analysen (LWDA 2018) \|volume=2191 \|pages=318-329 \|via=CEUR-WS}}</ref> Clusterings obtained this way usually are [[hierarchical clustering\|hierarchical]], and cannot be achieved by a single DBSCAN run.

	==Complexity==		==Complexity==
	Like [[DBSCAN]], OPTICS processes each point once, and performs one [[fixed-radius near neighbors\|<math>\varepsilon</math>-neighborhood query]] during this processing. Given a [[spatial index]] that grants a neighborhood query in <math>O(\log n)</math> runtime, an overall runtime of <math>O(n \cdot \log n)</math> is obtained. The authors of the original OPTICS paper report an actual constant slowdown factor of 1.6 compared to DBSCAN. Note that the value of <math>\varepsilon</math> might heavily influence the cost of the algorithm, since a value too large might raise the cost of a neighborhood query to linear complexity.		Like [[DBSCAN]], OPTICS processes each point once, and performs one [[fixed-radius near neighbors\|<math>\varepsilon</math>-neighborhood query]] during this processing. Given a [[spatial index]] that grants a neighborhood query in <math>O(\log n)</math> runtime, an overall runtime of <math>O(n \cdot \log n)</math> is obtained. The worst case however is <math>O(n^2)</math>, as with DBSCAN. The authors of the original OPTICS paper report an actual constant slowdown factor of 1.6 compared to DBSCAN. Note that the value of <math>\varepsilon</math> might heavily influence the cost of the algorithm, since a value too large might raise the cost of a neighborhood query to linear complexity.

	In particular, choosing <math>\varepsilon > \max_{x,y} d(x,y)</math> (larger than the maximum distance in the data set) is possible, but leads to quadratic complexity, since every neighborhood query returns the full data set. Even when no spatial index is available, this comes at additional cost in managing the heap. Therefore, <math>\varepsilon</math> should be chosen appropriately for the data set.		In particular, choosing <math>\varepsilon > \max_{x,y} d(x,y)</math> (larger than the maximum distance in the data set) is possible, but leads to quadratic complexity, since every neighborhood query returns the full data set. Even when no spatial index is available, this comes at additional cost in managing the heap. Therefore, <math>\varepsilon</math> should be chosen appropriately for the data set.

Citation bot: Alter: title. Add: chapter. Removed parameters. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox2 | #UCB_webform_linked 1244/2384

2023-07-24T17:59:56Z

Alter: title. Add: chapter. Removed parameters. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox2 | #UCB_webform_linked 1244/2384

← Previous revision		Revision as of 17:59, 24 July 2023
Line 152:		Line 152:
	}}</ref> is a hierarchical [[subspace clustering]] (axis-parallel) method based on OPTICS.		}}</ref> is a hierarchical [[subspace clustering]] (axis-parallel) method based on OPTICS.

	HiCO<ref>{{Cite book\| doi = 10.1109/SSDBM.2006.35\| isbn = 978-0-7695-2590-7~~\| title = Mining Hierarchies of Correlation Clusters~~\| year = 2006\| last1 = Achtert \| first1 = E.\| last2 = Böhm \| first2 = C.\| last3 = Kröger \| first3 = P.\| last4 = Zimek \| first4 = A.\| ~~pages~~ = ~~119–128\| journal = Proc.~~ 18th International Conference on Scientific and Statistical Database Management (SSDBM)\| citeseerx = 10.1.1.707.7872\| s2cid = 2679909}}</ref> is a hierarchical [[correlation clustering]] algorithm based on OPTICS.		HiCO<ref>{{Cite book\| doi = 10.1109/SSDBM.2006.35\| isbn = 978-0-7695-2590-7\| year = 2006\| last1 = Achtert \| first1 = E.\| last2 = Böhm \| first2 = C.\| last3 = Kröger \| first3 = P.\| last4 = Zimek \| first4 = A.\| title = 18th International Conference on Scientific and Statistical Database Management (SSDBM'06)\| chapter = Mining Hierarchies of Correlation Clusters\| pages = 119–128\| citeseerx = 10.1.1.707.7872\| s2cid = 2679909}}</ref> is a hierarchical [[correlation clustering]] algorithm based on OPTICS.

	DiSH<ref>{{cite conference		DiSH<ref>{{cite conference

OAbot: Open access bot: doi added to citation with #oabot.

2023-01-29T02:17:17Z

Open access bot: doi added to citation with #oabot.

← Previous revision		Revision as of 02:17, 29 January 2023
Line 149:		Line 149:
	\| title = Knowledge Discovery in Databases: PKDD 2006, 10th European Conference on Principles and Practice of Knowledge Discovery in Databases, Berlin, Germany, September 18-22, 2006, Proceedings		\| title = Knowledge Discovery in Databases: PKDD 2006, 10th European Conference on Principles and Practice of Knowledge Discovery in Databases, Berlin, Germany, September 18-22, 2006, Proceedings
	\| volume = 4213		\| volume = 4213
	\| year = 2006}}</ref> is a hierarchical [[subspace clustering]] (axis-parallel) method based on OPTICS.		\| year = 2006\| doi-access = free
			}}</ref> is a hierarchical [[subspace clustering]] (axis-parallel) method based on OPTICS.

	HiCO<ref>{{Cite book\| doi = 10.1109/SSDBM.2006.35\| isbn = 978-0-7695-2590-7\| title = Mining Hierarchies of Correlation Clusters\| year = 2006\| last1 = Achtert \| first1 = E.\| last2 = Böhm \| first2 = C.\| last3 = Kröger \| first3 = P.\| last4 = Zimek \| first4 = A.\| pages = 119–128\| journal = Proc. 18th International Conference on Scientific and Statistical Database Management (SSDBM)\| citeseerx = 10.1.1.707.7872\| s2cid = 2679909}}</ref> is a hierarchical [[correlation clustering]] algorithm based on OPTICS.		HiCO<ref>{{Cite book\| doi = 10.1109/SSDBM.2006.35\| isbn = 978-0-7695-2590-7\| title = Mining Hierarchies of Correlation Clusters\| year = 2006\| last1 = Achtert \| first1 = E.\| last2 = Böhm \| first2 = C.\| last3 = Kröger \| first3 = P.\| last4 = Zimek \| first4 = A.\| pages = 119–128\| journal = Proc. 18th International Conference on Scientific and Statistical Database Management (SSDBM)\| citeseerx = 10.1.1.707.7872\| s2cid = 2679909}}</ref> is a hierarchical [[correlation clustering]] algorithm based on OPTICS.

Citation bot: Add: s2cid. | Use this bot. Report bugs. | Suggested by Whoop whoop pull up | #UCB_webform 3288/3754

2022-12-20T06:19:30Z

Add: s2cid. | Use this bot. Report bugs. | Suggested by Whoop whoop pull up | #UCB_webform 3288/3754

88.126.31.229: /* Pseudocode */ ε instead of eps is nicer

2022-10-19T11:59:26Z

Pseudocode: ε instead of eps is nicer

← Previous revision		Revision as of 11:59, 19 October 2022
Line 52:		Line 52:
	The basic approach of OPTICS is similar to [[DBSCAN]], but instead of maintaining known, but so far unprocessed cluster members in a set, they are maintained in a [[priority queue]] (e.g. using an indexed [[Heap (data structure)\|heap]]).		The basic approach of OPTICS is similar to [[DBSCAN]], but instead of maintaining known, but so far unprocessed cluster members in a set, they are maintained in a [[priority queue]] (e.g. using an indexed [[Heap (data structure)\|heap]]).

	'''function''' OPTICS(DB, ~~eps~~, MinPts) '''is'''		'''function''' OPTICS(DB, ε, MinPts) '''is'''
	'''for each''' point p of DB '''do'''		'''for each''' point p of DB '''do'''
	p.reachability-distance = UNDEFINED		p.reachability-distance = UNDEFINED
	'''for each''' unprocessed point p of DB '''do'''		'''for each''' unprocessed point p of DB '''do'''
	N = getNeighbors(p, ~~eps~~)		N = getNeighbors(p, ε)
	mark p as processed		mark p as processed
	output p to the ordered list		output p to the ordered list
	'''if''' core-distance(p, ~~eps~~, MinPts) != UNDEFINED '''then'''		'''if''' core-distance(p, ε, MinPts) != UNDEFINED '''then'''
	Seeds = empty priority queue		Seeds = empty priority queue
	update(N, p, Seeds, ~~eps~~, MinPts)		update(N, p, Seeds, ε, MinPts)
	'''for each''' next q in Seeds '''do'''		'''for each''' next q in Seeds '''do'''
	N' = getNeighbors(q, ~~eps~~)		N' = getNeighbors(q, ε)
	mark q as processed		mark q as processed
	output q to the ordered list		output q to the ordered list
	'''if''' core-distance(q, ~~eps~~, MinPts) != UNDEFINED '''do'''		'''if''' core-distance(q, ε, MinPts) != UNDEFINED '''do'''
	update(N', q, Seeds, ~~eps~~, MinPts)		update(N', q, Seeds, ε, MinPts)

	In update(), the priority queue Seeds is updated with the <math>\varepsilon</math>-neighborhood of <math>p</math> and <math>q</math>, respectively:		In update(), the priority queue Seeds is updated with the <math>\varepsilon</math>-neighborhood of <math>p</math> and <math>q</math>, respectively:

	'''function''' update(N, p, Seeds, ~~eps~~, MinPts) '''is'''		'''function''' update(N, p, Seeds, ε, MinPts) '''is'''
	coredist = core-distance(p, ~~eps~~, MinPts)		coredist = core-distance(p, ε, MinPts)
	'''for each''' o in N		'''for each''' o in N
	'''if''' o is not processed '''then'''		'''if''' o is not processed '''then'''

David Eppstein: LNCS is not a journal

2022-04-27T05:23:33Z

LNCS is not a journal

@@ Line 115: / Line 115: @@
  |url=https://lirias.kuleuven.be/handle/123456789/125270 }}</ref> is an [[anomaly detection|outlier detection]] algorithm based on OPTICS. The main use is the extraction of outliers from an existing run of OPTICS at low cost compared to using a different outlier detection method. The better known version [[local outlier factor|LOF]] is based on the same concepts.
 HiCO<ref>{{Cite book| doi = 10.1109/SSDBM.2006.35| isbn = 978-0-7695-2590-7| title = Mining Hierarchies of Correlation Clusters| year = 2006| last1 = Achtert | first1 = E.| last2 = Böhm | first2 = C.| last3 = Kröger | first3 = P.| last4 = Zimek | first4 = A.| pages = 119–128| journal = Proc. 18th International Conference on Scientific and Statistical Database Management (SSDBM)| citeseerx = 10.1.1.707.7872}}</ref> is a hierarchical [[correlation clustering]] algorithm based on OPTICS.
 FOPTICS<ref>{{Cite journal | last1 = Schneider | first1 = Johannes | last2 = Vlachos | first2 = Michail | year = 2013 | title = Fast parameterless density-based clustering via random projections | journal = 22nd ACM International Conference on Information and Knowledge Management(CIKM) }}</ref> is a faster implementation using random projections.

← Previous revision		Revision as of 09:42, 16 April 2025
Line 1:		Line 1:
	{{Short description\|Algorithm for finding density based clusters in spatial data}}		{{Short description\|Algorithm for finding density based clusters in spatial data}}
	{{Machine learning\|Clustering}}		{{Machine learning\|Clustering}}
	'''Ordering points to identify the clustering structure''' ('''OPTICS''') is an algorithm for finding density-based<ref>{{cite journal\|last1=Kriegel\|first1=Hans-Peter\|last2=Kröger\|first2=Peer\|last3=Sander\|first3=Jörg\|last4=Zimek\|first4=Arthur\|title=Density-based clustering\|journal=Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery\|date=May 2011\|volume=1\|issue=3\|pages=231–240\|doi=10.1002/widm.30\|s2cid=36920706 \|url=https://portal.findresearcher.sdu.dk/da/publications/be8fe7b9-d5e2-415c-91bc-5ac6fa00994b}}</ref> [[Cluster analysis\|clusters]] in spatial data. It was presented by Mihael Ankerst, Markus M. Breunig, [[Hans-Peter Kriegel]] and Jörg Sander.<ref name=":0">{{Cite conference		'''Ordering points to identify the clustering structure''' ('''OPTICS''') is an algorithm for finding density-based<ref>{{cite journal\|last1=Kriegel\|first1=Hans-Peter\|last2=Kröger\|first2=Peer\|last3=Sander\|first3=Jörg\|last4=Zimek\|first4=Arthur\|title=Density-based clustering\|journal=Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery\|date=May 2011\|volume=1\|issue=3\|pages=231–240\|doi=10.1002/widm.30\|s2cid=36920706 \|url=https://portal.findresearcher.sdu.dk/da/publications/be8fe7b9-d5e2-415c-91bc-5ac6fa00994b}}</ref> [[Cluster analysis\|clusters]] in spatial data. It was presented in 1999 by Mihael Ankerst, Markus M. Breunig, [[Hans-Peter Kriegel]] and Jörg Sander.<ref name=":0">{{Cite conference
	\|author=Mihael Ankerst \|author2=Markus M. Breunig \|author3=Hans-Peter Kriegel \|author3-link=Hans-Peter Kriegel \|author4=Jörg Sander		\|author=Mihael Ankerst \|author2=Markus M. Breunig \|author3=Hans-Peter Kriegel \|author3-link=Hans-Peter Kriegel \|author4=Jörg Sander
	\| title = OPTICS: Ordering Points To Identify the Clustering Structure		\| title = OPTICS: Ordering Points To Identify the Clustering Structure

← Previous revision		Revision as of 12:00, 6 August 2023
Line 93:		Line 93:
	The image above illustrates this concept. In its upper left area, a synthetic example data set is shown. The upper right part visualizes the [[spanning tree]] produced by OPTICS, and the lower part shows the reachability plot as computed by OPTICS. Colors in this plot are labels, and not computed by the algorithm; but it is well visible how the valleys in the plot correspond to the clusters in above data set. The yellow points in this image are considered noise, and no valley is found in their reachability plot. They are usually not assigned to clusters, except the omnipresent "all data" cluster in a hierarchical result.		The image above illustrates this concept. In its upper left area, a synthetic example data set is shown. The upper right part visualizes the [[spanning tree]] produced by OPTICS, and the lower part shows the reachability plot as computed by OPTICS. Colors in this plot are labels, and not computed by the algorithm; but it is well visible how the valleys in the plot correspond to the clusters in above data set. The yellow points in this image are considered noise, and no valley is found in their reachability plot. They are usually not assigned to clusters, except the omnipresent "all data" cluster in a hierarchical result.

	Extracting clusters from this plot can be done manually by selecting ranges on the x-axis after visual inspection, by selecting a threshold on the y-axis (the result is then similar to a DBSCAN clustering result with the same <math>\varepsilon</math> and {{not a typo\|minPts}} parameters; here a value of 0.1 may yield good results), or by different algorithms that try to detect the valleys by steepness, knee detection, or local maxima. A range of the plot beginning with a steep descent and ending with a steep ascent is considered a valley, and corresponds to a contiguous area of high density. Additional care must be taken to the last points in a valley to assign them to the inner or outer cluster, this can be achieved by considering the predecessor.<ref>{{Cite ~~journal~~ \|last=Schubert \|first=Erich \|last2=Gertz \|first2=Michael \|date=2018-08-22 \|title=Improving the Cluster Structure Extracted from OPTICS Plots \|url=http://ceur-ws.org/Vol-2191/paper37.pdf \|~~journal~~=Lernen, Wissen, Daten, Analysen (LWDA 2018) \|volume=2191 \|pages=318-329 \|via=CEUR-WS}}</ref> Clusterings obtained this way usually are [[hierarchical clustering\|hierarchical]], and cannot be achieved by a single DBSCAN run.		Extracting clusters from this plot can be done manually by selecting ranges on the x-axis after visual inspection, by selecting a threshold on the y-axis (the result is then similar to a DBSCAN clustering result with the same <math>\varepsilon</math> and {{not a typo\|minPts}} parameters; here a value of 0.1 may yield good results), or by different algorithms that try to detect the valleys by steepness, knee detection, or local maxima. A range of the plot beginning with a steep descent and ending with a steep ascent is considered a valley, and corresponds to a contiguous area of high density. Additional care must be taken to the last points in a valley to assign them to the inner or outer cluster, this can be achieved by considering the predecessor.<ref>{{Cite conference \|last=Schubert \|first=Erich \|last2=Gertz \|first2=Michael \|date=2018-08-22 \|title=Improving the Cluster Structure Extracted from OPTICS Plots \|url=http://ceur-ws.org/Vol-2191/paper37.pdf \|conference=Lernen, Wissen, Daten, Analysen (LWDA 2018) \|volume=CEUR-WS 2191 \|pages=318-329 \|via=CEUR-WS}}</ref> Clusterings obtained this way usually are [[hierarchical clustering\|hierarchical]], and cannot be achieved by a single DBSCAN run.

	==Complexity==		==Complexity==
Line 135:		Line 135:
	\| last1 = Achtert \| first1 = Elke		\| last1 = Achtert \| first1 = Elke
	\| last2 = Böhm \| first2 = Christian		\| last2 = Böhm \| first2 = Christian
	\| last3 = Kriegel \| first3 = Hans{-}Peter		\| last3 = Kriegel \| first3 = Hans-Peter
	\| last4 = Kröger \| first4 = Peer		\| last4 = Kröger \| first4 = Peer
	\| last5 = Müller{-}Gorman \| first5 = Ina		\| last5 = Müller-Gorman \| first5 = Ina
	\| last6 = Zimek \| first6 = Arthur		\| last6 = Zimek \| first6 = Arthur
	\| editor1-last = Fürnkranz \| editor1-first = Johannes		\| editor1-last = Fürnkranz \| editor1-first = Johannes
Line 157:		Line 157:
	\| last1 = Achtert \| first1 = Elke		\| last1 = Achtert \| first1 = Elke
	\| last2 = Böhm \| first2 = Christian		\| last2 = Böhm \| first2 = Christian
	\| last3 = Kriegel \| first3 = Hans{-}Peter		\| last3 = Kriegel \| first3 = Hans-Peter
	\| last4 = Kröger \| first4 = Peer		\| last4 = Kröger \| first4 = Peer
	\| last5 = Müller{-}Gorman \| first5 = Ina		\| last5 = Müller-Gorman \| first5 = Ina
	\| last6 = Zimek \| first6 = Arthur		\| last6 = Zimek \| first6 = Arthur
	\| editor1-last = Ramamohanarao \| editor1-first = Kotagiri		\| editor1-last = Ramamohanarao \| editor1-first = Kotagiri

← Previous revision		Revision as of 06:19, 20 December 2022
Line 1:		Line 1:
	{{Short description\|Algorithm for finding density based clusters in spatial data}}		{{Short description\|Algorithm for finding density based clusters in spatial data}}
	{{Machine learning\|Clustering}}		{{Machine learning\|Clustering}}
	'''Ordering points to identify the clustering structure''' ('''OPTICS''') is an algorithm for finding density-based<ref>{{cite journal\|last1=Kriegel\|first1=Hans-Peter\|last2=Kröger\|first2=Peer\|last3=Sander\|first3=Jörg\|last4=Zimek\|first4=Arthur\|title=Density-based clustering\|journal=Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery\|date=May 2011\|volume=1\|issue=3\|pages=231–240\|doi=10.1002/widm.30\|url=https://portal.findresearcher.sdu.dk/da/publications/be8fe7b9-d5e2-415c-91bc-5ac6fa00994b}}</ref> [[Cluster analysis\|clusters]] in spatial data. It was presented by Mihael Ankerst, Markus M. Breunig, [[Hans-Peter Kriegel]] and Jörg Sander.<ref name=":0">{{Cite conference		'''Ordering points to identify the clustering structure''' ('''OPTICS''') is an algorithm for finding density-based<ref>{{cite journal\|last1=Kriegel\|first1=Hans-Peter\|last2=Kröger\|first2=Peer\|last3=Sander\|first3=Jörg\|last4=Zimek\|first4=Arthur\|title=Density-based clustering\|journal=Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery\|date=May 2011\|volume=1\|issue=3\|pages=231–240\|doi=10.1002/widm.30\|s2cid=36920706 \|url=https://portal.findresearcher.sdu.dk/da/publications/be8fe7b9-d5e2-415c-91bc-5ac6fa00994b}}</ref> [[Cluster analysis\|clusters]] in spatial data. It was presented by Mihael Ankerst, Markus M. Breunig, [[Hans-Peter Kriegel]] and Jörg Sander.<ref name=":0">{{Cite conference
	\|author=Mihael Ankerst \|author2=Markus M. Breunig \|author3=Hans-Peter Kriegel \|author3-link=Hans-Peter Kriegel \|author4=Jörg Sander		\|author=Mihael Ankerst \|author2=Markus M. Breunig \|author3=Hans-Peter Kriegel \|author3-link=Hans-Peter Kriegel \|author4=Jörg Sander
	\| title = OPTICS: Ordering Points To Identify the Clustering Structure		\| title = OPTICS: Ordering Points To Identify the Clustering Structure
Line 113:		Line 113:
	\| chapter-url = http://springerlink.metapress.com/content/76bx6413gqb4tvta/		\| chapter-url = http://springerlink.metapress.com/content/76bx6413gqb4tvta/
	\| series = Lecture Notes in Computer Science		\| series = Lecture Notes in Computer Science
	\|url=https://lirias.kuleuven.be/handle/123456789/125270 }}</ref> is an [[anomaly detection\|outlier detection]] algorithm based on OPTICS. The main use is the extraction of outliers from an existing run of OPTICS at low cost compared to using a different outlier detection method. The better known version [[local outlier factor\|LOF]] is based on the same concepts.		\|s2cid=27352458 \|url=https://lirias.kuleuven.be/handle/123456789/125270 }}</ref> is an [[anomaly detection\|outlier detection]] algorithm based on OPTICS. The main use is the extraction of outliers from an existing run of OPTICS at low cost compared to using a different outlier detection method. The better known version [[local outlier factor\|LOF]] is based on the same concepts.

	DeLi-Clu,<ref>{{cite conference		DeLi-Clu,<ref>{{cite conference
Line 151:		Line 151:
	\| year = 2006}}</ref> is a hierarchical [[subspace clustering]] (axis-parallel) method based on OPTICS.		\| year = 2006}}</ref> is a hierarchical [[subspace clustering]] (axis-parallel) method based on OPTICS.

	HiCO<ref>{{Cite book\| doi = 10.1109/SSDBM.2006.35\| isbn = 978-0-7695-2590-7\| title = Mining Hierarchies of Correlation Clusters\| year = 2006\| last1 = Achtert \| first1 = E.\| last2 = Böhm \| first2 = C.\| last3 = Kröger \| first3 = P.\| last4 = Zimek \| first4 = A.\| pages = 119–128\| journal = Proc. 18th International Conference on Scientific and Statistical Database Management (SSDBM)\| citeseerx = 10.1.1.707.7872}}</ref> is a hierarchical [[correlation clustering]] algorithm based on OPTICS.		HiCO<ref>{{Cite book\| doi = 10.1109/SSDBM.2006.35\| isbn = 978-0-7695-2590-7\| title = Mining Hierarchies of Correlation Clusters\| year = 2006\| last1 = Achtert \| first1 = E.\| last2 = Böhm \| first2 = C.\| last3 = Kröger \| first3 = P.\| last4 = Zimek \| first4 = A.\| pages = 119–128\| journal = Proc. 18th International Conference on Scientific and Statistical Database Management (SSDBM)\| citeseerx = 10.1.1.707.7872\| s2cid = 2679909}}</ref> is a hierarchical [[correlation clustering]] algorithm based on OPTICS.

	DiSH<ref>{{cite conference		DiSH<ref>{{cite conference
Line 175:		Line 175:
	FOPTICS<ref>{{Cite journal \| last1 = Schneider \| first1 = Johannes \| last2 = Vlachos \| first2 = Michail \| year = 2013 \| title = Fast parameterless density-based clustering via random projections \| journal = 22nd ACM International Conference on Information and Knowledge Management(CIKM) }}</ref> is a faster implementation using random projections.		FOPTICS<ref>{{Cite journal \| last1 = Schneider \| first1 = Johannes \| last2 = Vlachos \| first2 = Michail \| year = 2013 \| title = Fast parameterless density-based clustering via random projections \| journal = 22nd ACM International Conference on Information and Knowledge Management(CIKM) }}</ref> is a faster implementation using random projections.

	HDBSCAN*<ref>{{cite journal\|last1=Campello\|first1=Ricardo J. G. B.\|last2=Moulavi\|first2=Davoud\|last3=Zimek\|first3=Arthur\|last4=Sander\|first4=Jörg\|title=Hierarchical Density Estimates for Data Clustering, Visualization, and Outlier Detection\|journal=ACM Transactions on Knowledge Discovery from Data\|date=22 July 2015\|volume=10\|issue=1\|pages=1–51\|doi=10.1145/2733381}}</ref> is based on a refinement of DBSCAN, excluding border-points from the clusters and thus following more strictly the basic definition of density-levels by Hartigan.<ref>{{cite book\|author=J.A. Hartigan\|title=Clustering algorithms \|publisher=John Wiley & Sons\|year=1975}}</ref>		HDBSCAN*<ref>{{cite journal\|last1=Campello\|first1=Ricardo J. G. B.\|last2=Moulavi\|first2=Davoud\|last3=Zimek\|first3=Arthur\|last4=Sander\|first4=Jörg\|title=Hierarchical Density Estimates for Data Clustering, Visualization, and Outlier Detection\|journal=ACM Transactions on Knowledge Discovery from Data\|date=22 July 2015\|volume=10\|issue=1\|pages=1–51\|doi=10.1145/2733381\|s2cid=2887636 }}</ref> is based on a refinement of DBSCAN, excluding border-points from the clusters and thus following more strictly the basic definition of density-levels by Hartigan.<ref>{{cite book\|author=J.A. Hartigan\|title=Clustering algorithms \|publisher=John Wiley & Sons\|year=1975}}</ref>

	==Availability==		==Availability==