Aprenentatge no supervisat

L'aprenentatge no supervisat^[1] (unsupervised learning, en anglès) és un camp de l'aprenentatge automàtic format per algoritmes que aprenen patrons a partir de dades no etiquetades. A diferència de l'aprenentatge supervisat on hi ha un expert que etiqueta les dades, a l'aprenentatge no supervisat la idea és que els algoritmes siguin capaços de descobrir patrons o agrupacions en les dades sense la necessitat d'intervenció humana. La capacitat d'aquests algoritmes per descobrir similituds i diferències en les dades sense la necessitat d'un expert els converteixen en la solució ideal per a problemes d'anàlisi exploratòria de dades, estratègies de venda creuada, segmentació de clients i reconeixement d'imatges.

Els mètodes més utilitzats dins del camp de l'aprenentatge no supervisat són els algorismes d'agrupació,^[2] regles d'associació^[3] i la reducció de dimensionalitat.^[4]

Diferències entre diferents tipus d'aprenentatge

Sovint quan parlem de l'aprenentatge no supervisat també entra en conversa l'aprenentatge supervisat i el semisupervisat.^[5] La diferència entre aquests és principalment el nivell de participació de l'usuari i/o d'un agent extern en el procés d'etiquetatge de les dades.

Per un costat tenim els algorismes d'aprenentatge supervisat, que a diferència dels algorismes d'aprenentatge no supervisat, utilitzen dades etiquetades. A partir d'aquestes dades, prediuen els resultats futurs o assignen aquestes dades a categories específiques en funció de si problema que s'està intentant resoldre és de regressió o classificació. Generalment, els algorismes d'aprenentatge supervisat solen ser més precisos que els models d'aprenentatge no supervisat, però requereixen una intervenció humana inicial per etiquetar les dades de manera adequada. Els algorismes d'aprenentatge supervisat més habituals són la regressió lineal i logística, els naïve bayes, l'algoritme KNN i el bosc aleatori.^[6]

Per l'altra banda, tenim l'aprenentatge semisupervisat que es troba entre l'aprenentatge no supervisat i supervisat. Es produeix quan només s'han etiquetat una part de les dades d'entrada donades; és un cas de supervisió feble. Les dades no etiquetades, quan s'usen juntament amb una petita quantitat de dades etiquetades, poden produir una millora considerable en la precisió de l'aprenentatge.

Com hem comentat, l'adquisició de dades etiquetades per a un problema d'aprenentatge sovint requereix un agent humà especialitzat; el cost associat al procés d'etiquetatge pot fer que els conjunts d'entrenament grans i totalment etiquetats siguin inviables, mentre que l'adquisició de dades no etiquetades és relativament econòmica. En aquestes situacions, l'aprenentatge semisupervisat i no supervisat són de gran valor pràctic.

Algorismes d'agrupació

Els algoritmes d'agrupació (en anglès, "clustering") són els encarregats d'agrupar un conjunt d'objectes en diferents grups segons la seva distància o similitud amb la resta del grup.^[7] Aquesta distància pot ser calculada de diverses maneres, com per exemple utilitzant la distància euclidiana^[8] o altres que poden ser utilitzades amb variables discretes.

Podem trobar múltiples algoritmes d'agrupació dintre del grup dels algoritmes no supervisats:

K-Mitges

L'algoritme de K-Mitges^[9] (K-Means clustering en anglès), té l'objectiu de dividir un grup d'n objectes en k grups (o clústers) segons el seu valor mitjà. És un algoritme comunament utilitzat en segmentació del mercat,^[10] agrupació de documents, segmentació d'imatges^[11] i compressió d'imatges.

Segueix aquests passos:

Indiquem el valor de grups que voldrem (k)
Aleatòriament, es seleccionen k centroides per cada grup.
Per un punt del conjunt de dades, calculem la distància respecte cada un dels k centroides de cada grup i assignem el punt al clúster més proper.
Tornem a calcular els centroides de cada grup.
Repetim els passos 3 i 4 fins que no hi hagi canvi als centroides.

Agrupament Jeràrquic

Aquest tipus d'algoritme, conegut també com a HCA (de les sigles en anglès, hierarchical cluster analysis) analitza grups puntuals, amb l'objectiu de construir una jerarquia de grups.^[12] Existeixen dos tipus:

- Aglomeratius: Cada observació comença amb el seu propi clúster, i els parells de clústers es fusionen a mesura que un puja per la jerarquia.

- Divisius: Totes les observacions comencen en un grup, i es realitzen divisions mentre un baixa en la jerarquia.

Hi ha diversos mètodes per mesurar la similitud entre dos grups diferents A i B, on els més utilitzats són:


Nom	Fórmula
Agrupament "Complete-Linkage"	$\max \,\{\,d(a,b):a\in A,\,b\in B\,\}.$
Agrupament "Single-Linkage"	$\min \,\{\,d(a,b):a\in A,\,b\in B\,\}..$
Enllaç mitjà pesat	$d(i\cup j,k)={\frac {d(i,k)+d(j,k)}{2}}.$
Enllaç mitjà sense pesar	${\frac {1}{\|A\|\cdot \|B\|}}\sum _{a\in A}\sum _{b\in B}d(a,b).$

On d és el tipus de distància utilitzat.

Models de mescles gaussianes

Conegut com a GMM (a partir del seu nom en anglès, "Gaussian Mixture Models"), és un algoritme probabilístic on es van agrupant les diferents dades segons si pertanyen a una de les diverses distribucions gaussianes que pertanyen a la barreja.^[13]

Per dur a terme l'algoritme, inicialment inicialitzem k punts aleatòriament, això es fa utilitzant els valors de la desviació estàndard i la mitjana. Després, agafem un punt del conjunt de dades i s'assigna a tots els clústers amb nivells de pertinença específics, per recalcular els paràmetres gaussians (mitjana i desviació estàndard). Repetirem això fins que hi hagi convergència, cosa que podrem comprovar examinant la probabilitat logarítmica de les dades existents.

Regles d'associació

Les regles d'associació són un tipus d'aprenentatge no supervisat on l'algoritme intenta trobar relacions o associacions interessants entre les variables d'un conjunt gran de dades. Es basa en diferents regles per descobrir aquestes relacions entre les variables de la base de dades, que se solen representar en forma de conjunts d'elements freqüents.

Aquests mètodes s'utilitzen sovint per a l'anàlisi de cistella de mercat^[14] (quins articles es compren junts, quines botigues acostumen a visitar juntes, l'agrupació de preus, la venda encreuada, etc.), que permet a les empreses entendre millor els seus clients i les relacions entre diferents productes. Els tres algorismes més usats per generar regles d'associació són l'algorisme Eclat, l'algorisme de creixement F-P, i l'algorisme a priori;^[15] sent l'últim d'aquests el més usat.

Algorisme a priori

Aquest algorisme utilitza conjunts de dades freqüents per generar regles d'associació.^[16] Està dissenyat per treballar amb les bases de dades que contenen transaccions i fa ús d'una cerca en amplitud juntament amb un arbre hash per calcular el conjunt d'elements de manera eficient.

S'usa principalment per a l'anàlisi de cistella de mercat i ajuda a entendre els productes que es poden comprar junts. També és utilitzat en l'àmbit sanitari per trobar les reaccions a cert fàrmac pels pacients.

Algorisme Eclat^[17]

Aquest algorisme usa una tècnica de cerca en profunditat per aconseguir conjunts d'elements freqüents en una base de dades de transaccions. Realitza una execució més ràpida que l'algoritme a priori.

Algorisme de creixement F-P

És la versió millorada de l'algoritme a priori. Representa la base de dades amb estructura d'arbre que es coneix com a patró o arbre freqüent. L'objectiu d'aquest arbre freqüent és extreure els patrons més freqüents.^[18]

Reducció de dimensió

Encara que, normalment, tenir més dades implica millors resultats, tenir massa informació també pot afectar negativament els diferents algorismes (per exemple, provocant overfitting), i pot també dificultar la visualització dels sets de dades. Per aquest motiu, podem utilitzar tècniques de reducció de dimensió quan creiem que la quantitat de dades és massa gran. Aquests algorismes pretenen de reduir la quantitat d'informació a una mida més assequible, preservant la integritat d'aquesta el màxim possible.^[19]

Existeixen diferents mètodes per reduir la dimensió d'un conjunt de dades donat:

Anàlisi de components principals

L'anàlisi de components principals (ACP, PCA en anglès), utilitza una transformació lineal per a crear un nou set de dades, basat en el que ja tenim, que només ens quedem amb les components principals. La variància de major mida del conjunt de dades és capturada en el primer eix, primera component principal. La segona variància més gran és el segon eix, segona component principal, i així successivament, segons el nombre de dimensions que tinguem a les dades.^[20]

Descomposició en valors singulars

La descomposició en valors singulars (DVS) consisteix a factoritzar una matriu (real o complexa) en matrius de rang més baix. Aquesta factorització és causada per la fórmula:

$M=U\Sigma V'$

on U és una matriu unitària de dimensió m×m real o complexa, Σ és una matriu diagonal rectangular de dimensió m×n amb entrades reals no-negatives a la diagonal, i V* (la matriu transposada conjugada de V) és una matriu unitària real o complexa de dimensió n×n.

Aquesta tècnica és comunament utilitzada per a reduir el soroll de les dades, o per a la compressió d'informació.

Autoencoder^[21]

L'Autoencoder és un tipus de xarxa neuronal que té el mateix nombre de nodes tant a l'entrada com a la sortida, format per capes intermèdies amb nombre de nodes inferior. L'objectiu de l'Autoencoder és replicar a l'última capa els valors inicials de la primera capa. Com les capes intermèdies tenen una dimensió inferior, la xarxa neuronal aprèn a representar les dades amb una dimensió també menor.

Referències

↑ «aprenentatge no supervisat». Cercaterm. TERMCAT, Centre de Terminologia.
↑ Tsekouras, George E.; Trygonis, Vasilis; Rigos, Anastasios; Chatzipavlis, Antonios; Tsolakis, Dimitrios. Neuro-Fuzzy Network for Modeling the Shoreline Realignment of the Kamari Beach, Santorini, Greece. Cham: Springer International Publishing, 2017, p. 229–241. ISBN 978-3-319-65171-2.
↑ Cios, Krzysztof J.; Swiniarski, Roman W.; Pedrycz, Witold; Kurgan, Lukasz A. Unsupervised Learning: Association Rules (en anglès). Boston, MA: Springer US, 2007, p. 289–306. DOI 10.1007/978-0-387-36795-8_10. ISBN 978-0-387-33333-5.
↑ Pena, J.M.; Lozano, J.A.; Larranaga, P.; Inza, I. «Dimensionality reduction in unsupervised learning of conditional Gaussian networks». IEEE Transactions on Pattern Analysis and Machine Intelligence, 23, 6, 6-2001, pàg. 590–603. DOI: 10.1109/34.927460.
↑ Chapelle, O.; Scholkopf, B.; Zien, Eds., A. «Semi-Supervised Learning (Chapelle, O. et al., Eds.; 2006) [Book reviews]». IEEE Transactions on Neural Networks, 20, 3, 3-2009, pàg. 542–542. DOI: 10.1109/TNN.2009.2015974. ISSN: 1045-9227.
↑ Caruana, Rich; Niculescu-Mizil, Alexandru An empirical comparison of supervised learning algorithms. Association for Computing Machinery [New York, NY, USA], 25-06-2006, pàg. 161–168. DOI: 10.1145/1143844.1143865.
↑ Singh, Seema. «An Introduction To Clustering» (en anglès), 08-06-2018. [Consulta: 27 juny 2022].
↑ Bouhmala, Noureddine How Good is the Euclidean Distance Metric for the Clustering Problem, 7-2016, pàg. 312–315. DOI: 10.1109/IIAI-AAI.2016.26.
↑ J. Garbade, Dr. Michael Understanding K-means Clustering in Machine Learning, 12-09-2018.
↑ Dolnicar, Sara «A Review of Unquestioned Standards in Using Cluster Analysis for Data-Driven Market Segmentation». Faculty of Commerce - Papers (Archive), 02-12-2002.
↑ Coleman, G.B.; Andrews, H.C. «Image segmentation by clustering». Proceedings of the IEEE, 67, 5, 5-1979, pàg. 773–785. DOI: 10.1109/PROC.1979.11327. ISSN: 1558-2256.
↑ Nielsen, Frank. Hierarchical Clustering (en anglès). Cham: Springer International Publishing, 2016, p. 195–211. DOI 10.1007/978-3-319-21903-5_8. ISBN 978-3-319-21903-5.
↑ Yang, Miin-Shen; Lai, Chien-Yo; Lin, Chih-Ying «A robust EM clustering algorithm for Gaussian mixture models» (en anglès). Pattern Recognition, 45, 11, 01-11-2012, pàg. 3950–3961. DOI: 10.1016/j.patcog.2012.04.031. ISSN: 0031-3203.
↑ Kaur, Manpreet; Kang, Shivani «Market Basket Analysis: Identify the Changing Trends of Market Data Using Association Rule Mining». Procedia Computer Science, 85, 2016, pàg. 78–85. DOI: 10.1016/j.procs.2016.05.180. ISSN: 1877-0509.
↑ Heaton, Jeff Comparing dataset characteristics that favor the Apriori, Eclat or FP-Growth frequent itemset mining algorithms. IEEE [Norfolk, VA, USA], 3-2016, pàg. 1–7. DOI: 10.1109/SECON.2016.7506659.
↑ Hegland, Markus. The apriori algorithm ? a tutorial. Volume 11. WORLD SCIENTIFIC, 2007-10-01, p. 209–262. DOI 10.1142/9789812709066_0006. ISBN 978-981-270-905-9.
↑ Li, Zhi Fang; Liu, Xiu Fang; Cao, Xu «A Study on Improved Eclat Data Mining Algorithm». Advanced Materials Research, 328-330, 9-2011, pàg. 1896–1899. DOI: 10.4028/www.scientific.net/amr.328-330.1896. ISSN: 1662-8985.
↑ Borgelt, Christian (en anglès) An implementation of the FP-growth algorithm. ACM Press [Chicago, Illinois], 2005, pàg. 1–5. DOI: 10.1145/1133905.1133907.
↑ «What is Unsupervised Learning?» (en anglès americà). [Consulta: 27 juny 2022].
↑ «A Tutorial on Principal Component Analysis». Jonathon Shlens, 15-02-2010. Arxivat de l'original el 2013-11-10. [Consulta: 27 juny 2022].
↑ Kramer, Mark A. «Nonlinear principal component analysis using autoassociative neural networks» (en anglès). AIChE Journal, 37, 2, 2-1991, pàg. 233–243. DOI: 10.1002/aic.690370209. ISSN: 0001-1541.

[1] «aprenentatge no supervisat». Cercaterm. TERMCAT, Centre de Terminologia.

[2] Tsekouras, George E.; Trygonis, Vasilis; Rigos, Anastasios; Chatzipavlis, Antonios; Tsolakis, Dimitrios. Neuro-Fuzzy Network for Modeling the Shoreline Realignment of the Kamari Beach, Santorini, Greece. Cham: Springer International Publishing, 2017, p. 229–241. ISBN 978-3-319-65171-2.

[3] Cios, Krzysztof J.; Swiniarski, Roman W.; Pedrycz, Witold; Kurgan, Lukasz A. Unsupervised Learning: Association Rules (en anglès). Boston, MA: Springer US, 2007, p. 289–306. DOI 10.1007/978-0-387-36795-8_10. ISBN 978-0-387-33333-5.

[4] Pena, J.M.; Lozano, J.A.; Larranaga, P.; Inza, I. «Dimensionality reduction in unsupervised learning of conditional Gaussian networks». IEEE Transactions on Pattern Analysis and Machine Intelligence, 23, 6, 6-2001, pàg. 590–603. DOI: 10.1109/34.927460.

[5] Chapelle, O.; Scholkopf, B.; Zien, Eds., A. «Semi-Supervised Learning (Chapelle, O. et al., Eds.; 2006) [Book reviews]». IEEE Transactions on Neural Networks, 20, 3, 3-2009, pàg. 542–542. DOI: 10.1109/TNN.2009.2015974. ISSN: 1045-9227.

[6] Caruana, Rich; Niculescu-Mizil, Alexandru An empirical comparison of supervised learning algorithms. Association for Computing Machinery [New York, NY, USA], 25-06-2006, pàg. 161–168. DOI: 10.1145/1143844.1143865.

[7] Singh, Seema. «An Introduction To Clustering» (en anglès), 08-06-2018. [Consulta: 27 juny 2022].

[8] Bouhmala, Noureddine How Good is the Euclidean Distance Metric for the Clustering Problem, 7-2016, pàg. 312–315. DOI: 10.1109/IIAI-AAI.2016.26.

[9] J. Garbade, Dr. Michael Understanding K-means Clustering in Machine Learning, 12-09-2018.

[10] Dolnicar, Sara «A Review of Unquestioned Standards in Using Cluster Analysis for Data-Driven Market Segmentation». Faculty of Commerce - Papers (Archive), 02-12-2002.

[11] Coleman, G.B.; Andrews, H.C. «Image segmentation by clustering». Proceedings of the IEEE, 67, 5, 5-1979, pàg. 773–785. DOI: 10.1109/PROC.1979.11327. ISSN: 1558-2256.

[12] Nielsen, Frank. Hierarchical Clustering (en anglès). Cham: Springer International Publishing, 2016, p. 195–211. DOI 10.1007/978-3-319-21903-5_8. ISBN 978-3-319-21903-5.

[13] Yang, Miin-Shen; Lai, Chien-Yo; Lin, Chih-Ying «A robust EM clustering algorithm for Gaussian mixture models» (en anglès). Pattern Recognition, 45, 11, 01-11-2012, pàg. 3950–3961. DOI: 10.1016/j.patcog.2012.04.031. ISSN: 0031-3203.

[14] Kaur, Manpreet; Kang, Shivani «Market Basket Analysis: Identify the Changing Trends of Market Data Using Association Rule Mining». Procedia Computer Science, 85, 2016, pàg. 78–85. DOI: 10.1016/j.procs.2016.05.180. ISSN: 1877-0509.

[15] Heaton, Jeff Comparing dataset characteristics that favor the Apriori, Eclat or FP-Growth frequent itemset mining algorithms. IEEE [Norfolk, VA, USA], 3-2016, pàg. 1–7. DOI: 10.1109/SECON.2016.7506659.

[16] Hegland, Markus. The apriori algorithm ? a tutorial. Volume 11. WORLD SCIENTIFIC, 2007-10-01, p. 209–262. DOI 10.1142/9789812709066_0006. ISBN 978-981-270-905-9.

[17] Li, Zhi Fang; Liu, Xiu Fang; Cao, Xu «A Study on Improved Eclat Data Mining Algorithm». Advanced Materials Research, 328-330, 9-2011, pàg. 1896–1899. DOI: 10.4028/www.scientific.net/amr.328-330.1896. ISSN: 1662-8985.

[18] Borgelt, Christian (en anglès) An implementation of the FP-growth algorithm. ACM Press [Chicago, Illinois], 2005, pàg. 1–5. DOI: 10.1145/1133905.1133907.

[19] «What is Unsupervised Learning?» (en anglès americà). [Consulta: 27 juny 2022].

[20] «A Tutorial on Principal Component Analysis». Jonathon Shlens, 15-02-2010. Arxivat de l'original el 2013-11-10. [Consulta: 27 juny 2022].

[21] Kramer, Mark A. «Nonlinear principal component analysis using autoassociative neural networks» (en anglès). AIChE Journal, 37, 2, 2-1991, pàg. 233–243. DOI: 10.1002/aic.690370209. ISSN: 0001-1541.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]