GSP algorithm - Revision history

PEPSI697: Reverted 1 edit by 2409:40C1:300E:5B3A:8000:0:0:0 (talk): Non constructive edit

2024-11-19T05:38:21Z

Reverted 1 edit by 2409:40C1:300E:5B3A:8000:0:0:0 (talk): Non constructive edit

← Previous revision		Revision as of 05:38, 19 November 2024
Line 10:		Line 10:
	F<sub>1</sub> = the set of frequent 1-sequence		F<sub>1</sub> = the set of frequent 1-sequence
	k=2,		k=2,
	do while F<sub>k-1</sub> ~~om Bagthariya~~		do while F<sub>k-1</sub> != Null;
	= Null;
	Generate candidate sets C<sub>k</sub> (set of candidate k-sequences);		Generate candidate sets C<sub>k</sub> (set of candidate k-sequences);
	For all input sequences s in the database D		For all input sequences s in the database D

2409:40C1:300E:5B3A:8000:0:0:0: /* Algorithm */Gjkfvnm

2024-11-19T05:03:43Z

Algorithm: Gjkfvnm

← Previous revision		Revision as of 05:03, 19 November 2024
Line 10:		Line 10:
	F<sub>1</sub> = the set of frequent 1-sequence		F<sub>1</sub> = the set of frequent 1-sequence
	k=2,		k=2,
	do while F<sub>k-1</sub> != Null;		do while F<sub>k-1</sub> om Bagthariya
			= Null;
	Generate candidate sets C<sub>k</sub> (set of candidate k-sequences);		Generate candidate sets C<sub>k</sub> (set of candidate k-sequences);
	For all input sequences s in the database D		For all input sequences s in the database D

Bruce1ee: fixed lint errors – links in external links

2023-04-27T09:36:54Z

fixed lint errors – links in external links

← Previous revision		Revision as of 09:36, 27 April 2023
Line 32:		Line 32:
	== References ==		== References ==
	* R. Srikant and R. Agrawal. 1996. [http://www.rakesh.agrawal-family.com/papers/edbt96seq_rj.pdf Mining Sequential Patterns: Generalizations and Performance Improvements]. In Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology (EDBT '96), Peter M. G. Apers, Mokrane Bouzeghoub, and Georges Gardarin (Eds.). Springer-Verlag, London, UK, UK, 3–17.		* R. Srikant and R. Agrawal. 1996. [http://www.rakesh.agrawal-family.com/papers/edbt96seq_rj.pdf Mining Sequential Patterns: Generalizations and Performance Improvements]. In Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology (EDBT '96), Peter M. G. Apers, Mokrane Bouzeghoub, and Georges Gardarin (Eds.). Springer-Verlag, London, UK, UK, 3–17.
	* ~~{{Google books\|dH2KQhJboSYC\|~~ {{cite book\|title=Data Mining Techniques\|first=Arun K. \|last=Pujari		* {{cite book \|title=Data Mining Techniques \|first=Arun K. \|last=Pujari \|publisher=Universities Press \|year=2001 \|ISBN=81-7371-380-4 \|pages=256–260 \|url={{Google books \|dH2KQhJboSYC \|plainurl=yes}}}}
	\|publisher=Universities Press\|year=2001\|ISBN=81-7371-380-4}} (pp. 256-260)\|page=256}}
	* [https://doi.org/10.1023/A:1007652502315 Zaki, M.J. Machine Learning (2001) 42: 31].		* [https://doi.org/10.1023/A:1007652502315 Zaki, M.J. Machine Learning (2001) 42: 31].

I dream of horses: Random page patrol with AutoWikiBrowser, typo(s) fixed: 3-17 → 3–17

2022-01-06T05:00:32Z

Random page patrol with AutoWikiBrowser, typo(s) fixed: 3-17 → 3–17

← Previous revision		Revision as of 05:00, 6 January 2022
Line 20:		Line 20:
	End do		End do
	Result = Set of all frequent sequences is the union of all F<sub>k</sub>'s		Result = Set of all frequent sequences is the union of all F<sub>k</sub>'s


	The above algorithm looks like the [[Apriori algorithm]]. One main difference is however the generation of candidate sets. Let us assume that:		The above algorithm looks like the [[Apriori algorithm]]. One main difference is however the generation of candidate sets. Let us assume that:
Line 32:		Line 31:

	== References ==		== References ==
	* R. Srikant and R. Agrawal. 1996. [http://www.rakesh.agrawal-family.com/papers/edbt96seq_rj.pdf Mining Sequential Patterns: Generalizations and Performance Improvements]. In Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology (EDBT '96), Peter M. G. Apers, Mokrane Bouzeghoub, and Georges Gardarin (Eds.). Springer-Verlag, London, UK, UK, ~~3-17~~.		* R. Srikant and R. Agrawal. 1996. [http://www.rakesh.agrawal-family.com/papers/edbt96seq_rj.pdf Mining Sequential Patterns: Generalizations and Performance Improvements]. In Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology (EDBT '96), Peter M. G. Apers, Mokrane Bouzeghoub, and Georges Gardarin (Eds.). Springer-Verlag, London, UK, UK, 3–17.
	* {{Google books\|dH2KQhJboSYC\| {{cite book\|title=Data Mining Techniques\|first=Arun K. \|last=Pujari		* {{Google books\|dH2KQhJboSYC\| {{cite book\|title=Data Mining Techniques\|first=Arun K. \|last=Pujari
	\|publisher=Universities Press\|year=2001\|ISBN=81-7371-380-4}} (pp. 256-260)\|page=256}}		\|publisher=Universities Press\|year=2001\|ISBN=81-7371-380-4}} (pp. 256-260)\|page=256}}

Jarble: linking

2021-10-19T01:24:08Z

linking

← Previous revision		Revision as of 01:24, 19 October 2021
Line 32:		Line 32:

	== References ==		== References ==
	* R. Srikant and R. Agrawal. 1996. Mining Sequential Patterns: Generalizations and Performance Improvements. In Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology (EDBT '96), Peter M. G. Apers, Mokrane Bouzeghoub, and Georges Gardarin (Eds.). Springer-Verlag, London, UK, UK, 3-17.		* R. Srikant and R. Agrawal. 1996. [http://www.rakesh.agrawal-family.com/papers/edbt96seq_rj.pdf Mining Sequential Patterns: Generalizations and Performance Improvements]. In Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology (EDBT '96), Peter M. G. Apers, Mokrane Bouzeghoub, and Georges Gardarin (Eds.). Springer-Verlag, London, UK, UK, 3-17.
	* {{Google books\|dH2KQhJboSYC\| {{cite book\|title=Data Mining Techniques\|first=Arun K. \|last=Pujari		* {{Google books\|dH2KQhJboSYC\| {{cite book\|title=Data Mining Techniques\|first=Arun K. \|last=Pujari
	\|publisher=Universities Press\|year=2001\|ISBN=81-7371-380-4}} (pp. 256-260)\|page=256}}		\|publisher=Universities Press\|year=2001\|ISBN=81-7371-380-4}} (pp. 256-260)\|page=256}}

RathanKalluri at 06:20, 18 October 2019

2019-10-18T06:20:47Z

← Previous revision		Revision as of 06:20, 18 October 2019
Line 1:		Line 1:
	{{More citations needed\|date=May 2007}}		{{More citations needed\|date=May 2007}}

	'''GSP algorithm''' (''Generalized Sequential Pattern'' algorithm) is an [[algorithm]] used for [[sequence mining]]. The algorithms for solving sequence mining problems are mostly based on the ''[[apriori algorithm\|~~a priori~~]]'' (level-wise) algorithm. One way to use the level-wise paradigm is to first discover all the frequent items in a level-wise fashion. It simply means counting the occurrences of all singleton elements in the database. Then, the [[transaction (database)\|transactions]] are filtered by removing the non-frequent items. At the end of this step, each transaction consists of only the frequent elements it originally contained. This modified database becomes an input to the GSP algorithm. This process requires one pass over the whole [[database]].		'''GSP algorithm''' (''Generalized Sequential Pattern'' algorithm) is an [[algorithm]] used for [[sequence mining]]. The algorithms for solving sequence mining problems are mostly based on the ''[[apriori algorithm\|apriori]]'' (level-wise) algorithm. One way to use the level-wise paradigm is to first discover all the frequent items in a level-wise fashion. It simply means counting the occurrences of all singleton elements in the database. Then, the [[transaction (database)\|transactions]] are filtered by removing the non-frequent items. At the end of this step, each transaction consists of only the frequent elements it originally contained. This modified database becomes an input to the GSP algorithm. This process requires one pass over the whole [[database]].

	GSP algorithm makes multiple database passes. In the first pass, all single items (1-sequences) are counted. From the frequent items, a set of candidate 2-sequences are formed, and another pass is made to identify their frequency. The frequent 2-sequences are used to generate the candidate 3-sequences, and this process is repeated until no more frequent sequences are found. There are two main steps in the algorithm.		GSP algorithm makes multiple database passes. In the first pass, all single items (1-sequences) are counted. From the frequent items, a set of candidate 2-sequences are formed, and another pass is made to identify their frequency. The frequent 2-sequences are used to generate the candidate 3-sequences, and this process is repeated until no more frequent sequences are found. There are two main steps in the algorithm.

StraussInTheHouse: /* top */has at least one reference, see info

2018-12-31T10:58:20Z

top: has at least one reference, see info

← Previous revision		Revision as of 10:58, 31 December 2018
Line 1:		Line 1:
	{{~~unreferenced~~\|date=May 2007}}		{{More citations needed\|date=May 2007}}

	'''GSP algorithm''' (''Generalized Sequential Pattern'' algorithm) is an [[algorithm]] used for [[sequence mining]]. The algorithms for solving sequence mining problems are mostly based on the ''[[apriori algorithm\|a priori]]'' (level-wise) algorithm. One way to use the level-wise paradigm is to first discover all the frequent items in a level-wise fashion. It simply means counting the occurrences of all singleton elements in the database. Then, the [[transaction (database)\|transactions]] are filtered by removing the non-frequent items. At the end of this step, each transaction consists of only the frequent elements it originally contained. This modified database becomes an input to the GSP algorithm. This process requires one pass over the whole [[database]].		'''GSP algorithm''' (''Generalized Sequential Pattern'' algorithm) is an [[algorithm]] used for [[sequence mining]]. The algorithms for solving sequence mining problems are mostly based on the ''[[apriori algorithm\|a priori]]'' (level-wise) algorithm. One way to use the level-wise paradigm is to first discover all the frequent items in a level-wise fashion. It simply means counting the occurrences of all singleton elements in the database. Then, the [[transaction (database)\|transactions]] are filtered by removing the non-frequent items. At the end of this step, each transaction consists of only the frequent elements it originally contained. This modified database becomes an input to the GSP algorithm. This process requires one pass over the whole [[database]].

Cedar101:

2018-09-13T09:25:38Z

<sub>

← Previous revision		Revision as of 09:25, 13 September 2018
Line 4:		Line 4:

	GSP algorithm makes multiple database passes. In the first pass, all single items (1-sequences) are counted. From the frequent items, a set of candidate 2-sequences are formed, and another pass is made to identify their frequency. The frequent 2-sequences are used to generate the candidate 3-sequences, and this process is repeated until no more frequent sequences are found. There are two main steps in the algorithm.		GSP algorithm makes multiple database passes. In the first pass, all single items (1-sequences) are counted. From the frequent items, a set of candidate 2-sequences are formed, and another pass is made to identify their frequency. The frequent 2-sequences are used to generate the candidate 3-sequences, and this process is repeated until no more frequent sequences are found. There are two main steps in the algorithm.
	* Candidate Generation. Given the set of frequent (k-1)-frequent sequences F(k-1), the candidates for the next pass are generated by joining F(k-1) with itself. A pruning phase eliminates any sequence, at least one of whose subsequences is not frequent.		* Candidate Generation. Given the set of frequent (k-1)-frequent sequences F<sub>k-1</sub>, the candidates for the next pass are generated by joining F(k-1) with itself. A pruning phase eliminates any sequence, at least one of whose subsequences is not frequent.
	* Support Counting. Normally, a [[Hash tree (persistent data structure)\|hash tree]]–based search is employed for efficient support counting. Finally non-maximal frequent sequences are removed.		* Support Counting. Normally, a [[Hash tree (persistent data structure)\|hash tree]]–based search is employed for efficient support counting. Finally non-maximal frequent sequences are removed.

	== Algorithm ==		== Algorithm ==
	F1 = the set of frequent 1-sequence		F<sub>1</sub> = the set of frequent 1-sequence
	k=2,		k=2,
	do while F(k-1)!= Null;		do while F<sub>k-1</sub> != Null;
	Generate candidate sets Ck (set of candidate k-sequences);		Generate candidate sets C<sub>k</sub> (set of candidate k-sequences);
	For all input sequences s in the database D		For all input sequences s in the database D
	do		do
	Increment count of all a in Ck if s supports a		Increment count of all a in C<sub>k</sub> if s supports a
	End do		End do
	Fk = {a ∈ Ck such that its frequency exceeds the threshold}		Fk = {a ∈ C<sub>k</sub> such that its frequency exceeds the threshold}
	k = k+1;		k = k+1;
	End do		End do
	Result = Set of all frequent sequences is the union of all ~~Fks~~		Result = Set of all frequent sequences is the union of all F<sub>k</sub>'s


Line 29:		Line 29:

	==See also==		==See also==
	[[Sequence mining]]		* [[Sequence mining]]

	== References ==		== References ==
	* R. Srikant and R. Agrawal. 1996. Mining Sequential Patterns: Generalizations and Performance Improvements. In Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology (EDBT '96), Peter M. G. Apers, Mokrane Bouzeghoub, and Georges Gardarin (Eds.). Springer-Verlag, London, UK, UK, 3-17.		* R. Srikant and R. Agrawal. 1996. Mining Sequential Patterns: Generalizations and Performance Improvements. In Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology (EDBT '96), Peter M. G. Apers, Mokrane Bouzeghoub, and Georges Gardarin (Eds.). Springer-Verlag, London, UK, UK, 3-17.
	* {{Google books\|dH2KQhJboSYC\| {{cite book\|title=Data Mining Techniques\|first=Arun K. \|last=Pujari		* {{Google books\|dH2KQhJboSYC\| {{cite book\|title=Data Mining Techniques\|first=Arun K. \|last=Pujari
	\|publisher=Universities Press\|year=2001\|ISBN=81-7371-380-4}} (pp. 256-260)\|page=256}}		\|publisher=Universities Press\|year=2001\|ISBN=81-7371-380-4}} (pp. 256-260)\|page=256}}
	*Zaki, M.J. Machine Learning (2001) 42: 31. ~~https://doi.org/10.1023/A:1007652502315~~		* [https://doi.org/10.1023/A:1007652502315 Zaki, M.J. Machine Learning (2001) 42: 31].

	==External links==		==External links==

KoGro: Edited the pseudocode, as the for and while loop ends were wrong. Added a reference to a paper by Zaki, that proposes a different algorithm, but gives a good summary of GSP including the correct pseudocode nonetheless.

2018-09-13T09:07:54Z

Edited the pseudocode, as the for and while loop ends were wrong. Added a reference to a paper by Zaki, that proposes a different algorithm, but gives a good summary of GSP including the correct pseudocode nonetheless.

← Previous revision		Revision as of 09:07, 13 September 2018
Line 12:		Line 12:
	do while F(k-1)!= Null;		do while F(k-1)!= Null;
	Generate candidate sets Ck (set of candidate k-sequences);		Generate candidate sets Ck (set of candidate k-sequences);
	For all input sequences s in the database D		For all input sequences s in the database D
	do		do
	Increment count of all a in Ck if s supports a		Increment count of all a in Ck if s supports a
	Fk = {a ∈ Ck such that its frequency exceeds the threshold}		End do
			Fk = {a ∈ Ck such that its frequency exceeds the threshold}
	k = k+1;		k = k+1;
⚫	Result = Set of all frequent sequences is the union of all Fks
	End do
	End do		End do
		⚫	Result = Set of all frequent sequences is the union of all Fks


	The above algorithm looks like the [[Apriori algorithm]]. One main difference is however the generation of candidate sets. Let us assume that:		The above algorithm looks like the [[Apriori algorithm]]. One main difference is however the generation of candidate sets. Let us assume that:
Line 34:		Line 35:
	* {{Google books\|dH2KQhJboSYC\| {{cite book\|title=Data Mining Techniques\|first=Arun K. \|last=Pujari		* {{Google books\|dH2KQhJboSYC\| {{cite book\|title=Data Mining Techniques\|first=Arun K. \|last=Pujari
	\|publisher=Universities Press\|year=2001\|ISBN=81-7371-380-4}} (pp. 256-260)\|page=256}}		\|publisher=Universities Press\|year=2001\|ISBN=81-7371-380-4}} (pp. 256-260)\|page=256}}
			*Zaki, M.J. Machine Learning (2001) 42: 31. https://doi.org/10.1023/A:1007652502315

	==External links==		==External links==

58.60.1.29: /* References */

2018-08-10T04:49:23Z

References

← Previous revision		Revision as of 04:49, 10 August 2018
Line 31:		Line 31:

	== References ==		== References ==
			* R. Srikant and R. Agrawal. 1996. Mining Sequential Patterns: Generalizations and Performance Improvements. In Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology (EDBT '96), Peter M. G. Apers, Mokrane Bouzeghoub, and Georges Gardarin (Eds.). Springer-Verlag, London, UK, UK, 3-17.
	* {{Google books\|dH2KQhJboSYC\| {{cite book\|title=Data Mining Techniques\|first=Arun K. \|last=Pujari		* {{Google books\|dH2KQhJboSYC\| {{cite book\|title=Data Mining Techniques\|first=Arun K. \|last=Pujari
	\|publisher=Universities Press\|year=2001\|ISBN=81-7371-380-4}} (pp. 256-260)\|page=256}}		\|publisher=Universities Press\|year=2001\|ISBN=81-7371-380-4}} (pp. 256-260)\|page=256}}