---
# System prepended metadata

title: WEM
tags: [Master]

---

###### tags: `Master`
# WEM

Definition web Mining

Le potentiel d'extraction de connaissances à partir du web . Le Web Mining consiste à utiliser des technologies pour atteindre ce but.

Web Mining:
1. Web Content Mining
    - information des ressources d une page web (text, images, etc..)
3. Web Structure Mining
    - information de la structure des hyperliens connectant page et ressources web
5. Web Usage Mining
    - Information sur les données générées par les utilisateurs

## Web content mining (slide 19)
- Moteur de recherche
- Clustering des documents
- Classification des documents
- Personnalisation

## Web Structure Mining
Le web est un grand graphe (page = sommet, arc = hyperlien).

Analyse des hyperliens, structute du web
![](https://i.imgur.com/96085HJ.png)

### PageRank
Il assigne un poids à chaque page web pour faire un classification.
 
 
Une page qui est beaucouo pointé par des pages qui sont beaucoup pointé prend du poids

Plus il y a de lien sortant plus on perd de poids.

d = porbablité qu'on arrive sur une page sans passé par un lien.

Relation de renforcement réciproque.

- Un pivot: une page qui a beaucoup de liens sortant
- Une autorité: une page qui a beaucoup de liens qui pointent vers elle

Une communauté web: structure qui a beaucoup de lien entre eux (dans les deux sens) et tres peu à l'extrieur de la communauté.

![](https://i.imgur.com/fD494Ys.png)


## Web Usage Mining 
Genre youtube qui cible les videos que tu aimes
- Analyser les données de navigation sur le web pour:
    - comment le site est utilisé
    - comprendre le comportement des users
    - predire le comportement
    - cibler les users
    - augementer les ventes, le profit, la fidélité
- Défi
    - capturer quantitativement les interets communs des users du web.
- Personalisation:
- Commerce électronique:
- Web efficae
- Moteur de recherche

## Recherche d'information sur le web

- Adressage URL (portocole, localisation)
- Communication: HTTP/S
- formatage des données: HTML

### Mathématique
Le web est un graphe orienté avec des cycles, sommet = ressource, arc = hyperlien

Graphe orienté:
- puit = pas de chemin vers le reste du web
- sources = pas de chemin depuis le reste du web

Les defis du WEB pour la recherche d'information:
- Données dispersées
- Données volatiles
- Volume important
- Données redondantes et non structurées
- Qualité de données
- Données hétérogenes

Defis de demain:
- Reprendre le controle sur les données personnelles et choisir avec qui les partager.
- Lutter contre la desinformations
- La publicité politque en ligne doit etre transparente et comprise.

Piste d'action.
- Travailler avec les geants du web
- Nouveaux outils techno
- Lutter contre les lois trop invasisves et surveillance du gouv
- plus de transprence des algo
- regelementer les campagnes politiquesout


### Loi de zipf
- nombre de page par site
- nombre d'hyperliens entrants et sortant 
- le nombre de clic

Ils suivent tous une lois de zipf

==> Beacoup de site avec peu de page et très peu de sites avec un nombre considérable de pages


### anatomie des moteurs de recherche
- Spider
    - construit le corpus à partir du web
    - rassemble des données recursivement
    - soumission direct additionnelles de données par divers sources
    - les moteurs de recherche ont des politique différentes -> peu de correlation parmi les corpus
- L'indexeur
    - traiter les données et les representé
    - Divers politque de recherche
- le guichetier: répond aux requetes soumises

### Spider
- traverse les hypertextes en collectionnant les informstions des pages visitées
- utiliser pour indexer
- traditionnel
- périodique
- incrémental
- ciblé

On doit donnée un ensemble d'URL qu'il doit prendre pour commencer.

(slide 41)

Stratégie de recherche:
- parcours de l'arbre en largeur (FIFO), $O(b^d)$ mémoire
- pacrous de l'arbre en profondeur (LIFO), $O(bd)$ mémoire


:a:  **obeir aux restrictions de page-propriétaire**

Ciblage orienté:
- sujet
- hyperlien

Balise meta pour savoir s'il a eu des changements. reprendre la page si changement.

### Extraction des hyperliens

Le spider doit trouver tout les liens et en extraire les URLs

signet d'un url `#` endroit de la page 

### Canonicalisation des liens
- on enelve le / à la fin
- on enlever le # à la fin

### indexastion du texte d'ancrage
- extraire le texte d'ancrage
- stocker le texte associé à la page
- pas toujours utile `ici`
- lorsque image prendre le `alt`

### Exclusion des spiders

- Certaines pages indique qu'elles ne veulent pas de spider, donc on index pas
    -    spécification des répertoire qui ne sont pas visités
            -    Mettre un fichier robots.txt à la racine du serveur web avec des instructions
    -    balise META pour exclure
            -    ``` <meta name=“robots” content=“none”> ``` ou autres instructions

### Microformat

Utilisation des attributs HTML existant pour intégrer des tpes de données structurées. Abandonner car pas assez de divérsité

### Schema.org

Normalise les schémas de données structurées.

- Plus de 200 types définis
- Offre un vocabulaire plus varié que les microformats
- Plusieurs encodage
- invisible à à l'affichage
    - RDFa
    - Microdata
        - Fonctionnalité HTML5
        - Plus simple que RDFa
    - JSON-LD
        - Moyen simple de transformer des données existantes en JSON vers JSON-LD
    - OpenGraph

![](https://i.imgur.com/GnovS5r.png)
![](https://i.imgur.com/kR10JRc.png)

### OpenGraph

- CRéer par facebook
- Plus utilisé
- S'inspire des données srtucturées
- Utilisé par les principaux resaux sociaux

![](https://i.imgur.com/WMBILKl.jpg)

## Analyse des hyperliens

- Les premiers moteur comparait le contenu 
    - cosinus
    - TF-IDF

- Introduction des algorithmes basés sur les hyperliens
    - PageRank
        - alimente le moteur google
    - HITS

### Contenu

- Page de référence et page pivot

### Bibliométrique
- Référence en bas de page
- Fourni de la similitude avec la page visitée
- le corpus peut être vu comme un graphe

### Le facteur d'impacte
Combien de fois un article a été cité lors des deux dernières années

### Couplage bibliographique

- Mesure de similarité entre articles 
- Le couplage bibliographique de deux docs A et B est le nombre de documents cités par A et B ensemble
- Taille de l'intersection
- On ne peut pas normaliser par la taille bibbliographique

### Co-citation

- Mesure alternative sur les citations
- Le nombre de documents qu citent A et B
- On peut normaliser par le nombre total des documents citant soit A soit B

### Les liens web sont différents des citations

- Beaucoup de lien servent seulement à naviguer
- Beacoup pages sont justes des fournisseurs de contenu
- Concurrence


### Page de référence

Les pages de références sont des pages qui sont identifiées comme des pages contenant de l’information significative, digne confiance, et utile sur un sujet.

- In-degree: mesure simple pour referencer un page
    - donne à tous les liens le memes poids

### Page pivot

• Les pages pivot sont des pages qui fournissent un grand nombre de liens utiles vers des pages ayant un contenu relevant par rapport à un sujet (pages de références par rapport au sujet). 

### Exemple (slide 15, 16, ...)

### Activation propagée

Prends un fraction des documents qui sont liées avec un facteur $\lambda$

- Pas d'amélioration significative
- Mieux si on prends pas tous les voisins mais seulement le voisin le plus élvevé

### algorithme de Kleinberg
Tient compte de la similarité entre document et des liens

slide 24

### PageRank

Prend seulement les leins

Un utilisateur peut arriver sur une page en entrant directement dessus ou en suivant un chemin de lien. Il faut tenir compte de la manière de comment on arrive sur cette page. Le PageRank d'une page correspond à une estimation de la probabilité qu'un internaute la rencontre en naviguant de manière aléatoire. On prend en consideration l'importance des liens qui pointe sur nous.

**slide 34**
- On fait 5 itérations
- Il faut normaliser les valeurs "calcul"

#### Score initiaux
 $1\over N$
 N nombre de page
 
#### conclusion
 - Fonctionne et est utile
 - s'appuie sur le postulat que la présence d'un hyperlien dénote un appariement sémantique entre les deux pages
 - Cette hypothèse n'est pas toujours vérifiée


### Notation matricielle
- BC = Couplage bibliographique
- CC = Co-citation

- h = pivot = sont les vecteurs propres de la matrice $AA^t$
- a = référence = les vecteurs propres de la matrice $A^tA$

## Clustering

On découvre des nouvelles catégories de manièe **Non-supervisée** (aucune classe n'est fournie auparavant)

- Hiérarchique : analyse détaillées
- Non hiérarchique
    - Plus rapide
    - Itératif

### Méthode de partitionnement
- Alogrithme de soft clustering
    - Chaque objet possède un degré d'appartenance à chaque catégorie
- Alogrithmes de hard clustering
    - Chaque clusture appartient à une seul catégorie


### Clustering hiérarchique
Basé sur un arbre

#### Aglommerative
Au début chaque exemple est un cluster et on les fusionne de manière itérative pour former des clusters

#### Divisive
Un seul cluster au debut et on les sépare

### Similarité entre cluster
-  On calcule la distance 2 à 2 entre tous les documents (Matrice de similarité)
-  Fonction de similarité
    -  Cosinus
    -  euclide
-  Similarité entre deux clusers
-  Fonction de similarité
    -  Le saut minimum : ![](https://i.imgur.com/pCIISAn.png)
    -  Le saut maximum : ![](https://i.imgur.com/h4KSArD.png)

Exemple diamètre : On prends toujours au début la distance entre deux points (donc euclidienne ou cos) et ensuite la distance de cluster.

### Complexités
On peut garder la complexité en temps constant en faisant des observations et en utilisant la formule : 

![](https://i.imgur.com/BsUHYU1.png)
$O(1)$

Donc on reste en $O(n^2)$

### Clustering non hiérarchique
- On donne le nombre de cluster désirés k
- On choisit k graines
- On forme les clusters initiaux en se basant sur ces graines
- On redistribut itérativement
- On finit quand ca converge

### K_Moyennes (K-medoid)
- On suppose vecteurs réels
- On utlise le centre de gravité ou la moyenne
- On redistribut les exemples en cluster

### Métriques
- Norme eucidienne
- Manhattan
- Similiarité par cosinus

## Classification des documents

- Attribuer une classe à chaque document ou page Web
- Classification  manuel
- Classification automatique

### Automatique
- K plus proche voisin
- Bayesienne naive
- ...

### Attribut
- Eviter l'overfitting
- attribut pertient
- On peut combiner les méthodes utilisé (k-means,bayes)


### K plus proche voisin
- Inconvénient: on donne autant d'importance à un élement loin que proche


### Bayes
Slide 12-17 ou cours machine leraning

On peut compliqué la chose en tenant compte de l'apparition des mots dans le langage


### Arbre de decision
- Subidivision des noeuds
- Savoir si un noeud est terminal

On doit consistuer notre ensemble d'entrainement en se basant sur les mots

## Labo 2

Choisir dataset et lui envoyer un mail pour faire analyse de données

- Bourse
- Hopital
- Commentaire afficher sur un sujet
- 






