Séance 3 : Différents Filtres et Segmentations
3 Février
I. Présentation de la séance
A. Objectifs
Les objectifs définis à la dernière séance étaient :
- Commencer à identifier des modes de transport grâce aux vitesses
- Calculer l'angle de la direction pour détecter les centres d'interets
- Changer de jeu de données pour avoir de meilleurs données
- Travailler sur une approche vitesse pour reconnaitre les points aberrants
Cette séance nous avons décidé de travailler sur :
- Sélection d'un certain nombre de trajectoires intéressantes
- Début du travail sur la segmentation des trajectoires
- Evaluation de différents filtres, calcul d'erreur
B. Analyse technique
Filtrage¶
Average & Median¶
Une première approche pour nettoyer les données serait d'appliquer un filtre sur l'ensemble des données. L'objectif de ce filtre serait de réduire les variations haute-fréquences (assimilables au bruit) et d'amoidrir l'importance des acquisitions aberrantes.
Nous pouvons alors distinguer deux filtres :
- Average filter
- Median filter
Que nous définissons comme suit:
$$x_{n} = {\sum\limits_{i=-k}^k x_{n+i} \over 2k+1}.$$
Median filter : $$x_{n} = median [x_{n-k}:x_{n+k}] $$
Dans la suite, nous choisirons $k$=2
Chacun de ces filtres recalcule une position pour chaque point. Pour chaque coordonée (longitude et lattitude), le filtre remplace la valeur initiale par la valeur moyenne (ou médiane) sur l'ensemble constitué du point à filtrer, des k points précédents et des k points suivants.
On constate que ces deux filtres se comportent différemment vis-à-vis des points aberrants, qui garderont une influence plus ou moins importante avec l'average filter (puisque leurs coordonnées seront utilisées dans le calcul des moyennes) qui lissera donc les trajectoires en gardant les tendances. En revanche le median filter ne renvoie que des coordonnées de points d'origine, et sera donc plus fidèle aux données de départ, et en ignorant les points aberrants.
Heuristics Based Outlier Detection¶
Plutot que de recalculer l'ensemble des points, comme avec les filtres précédents, nous pouvons établir un certain nombre de tests que chaque point doit vérifier pour ne pas être considéré comme un point aberrant.
C'est la démarche des Heuristics Based Outlier Detection. Nous allons établir une valeur seuil sur la vitesse ou sur l'accélération, si cette valeur pour le point considéré est supérieure au seuil choisi, alors ce point sera éliminé.
Une application pourrait être par exemple, d'effacer les points avec une vitesse supérieure à 9km/h sur un parcours de marche.
On peut noter que cette démarche laisse intacte les variations hautes fréquences, mais qu'elle peut traiter efficacement les points aberrants.
Kalmon et filtre à particules¶
Cette méthode s'appuie sur un mélange d'une approche baysienne et des filtres de Markov pour prédire la position probable du point suivant. Si ce dernier se retrouve trop éloigné de la zone de prédiction, il sera corrigé ou considéré comme aberrant.
Dans un premier temps, nous avons choisi de ne pas explorer cette méthode : elle semble trop complexe pour notre niveau d'avancement actuel.
Evaluation des filtres¶
Pour évaluer la qualité des filtres, on peut faire des parcours vraiment déterminé dans Lyon pour évaluer la qualité du débruitage.
Segmentation des trajectoires¶
Définition¶
La segmentation des trajectoires correspond au calcul, sur l'ensemble des points enregistrés le long d'une journée, des trajets distincts entrepris par la personne.
Pour être satisfaisant, le trajet calculé doit être :
- réel : la personne doit s'être déplacé effectivement de ce point là
- précis : les localisations de la personne ne doivent pas être corrompus par du bruit
- discriminant : les points utilisés pour décrire un trajet, doivent correspondre au déplacement réel pour ce trajet. Et non pas par exemple à l'attente en fin de trajet.
Approche délai¶
Une première approche pour segmenter les trajectoires est d'exploiter les délais entre l'acquisition des différents points. Nous pouvons en effet corréler un délai plus long à plusieurs évenements :
- arrêt au sein d'un batiment (travail, domicile,...)
- arrêt de l'utilisation du gps car la personne a atteint le centre d'intéret
- présence d'un tunnel
Les deux premiers évenements peuvent s'assimiler à des coupures entre différents trajets. En revanche, la présence d'un tunnel ne renvoie pas du tout à la fin du trajet.
Algorithme¶
On regarde la distance orthogonal entre chaque point et le vol d'oiseau entre les 2 points extremes de la trajectoire. Si la distance est trop grande, c'est qu'on peut pas expliquer la trajectoire par une seulement une ligne droite.
Evaluation moyen de transport¶
Pour évaluer les différents trajets, il pourrait être efficace de déterminer les différents modes de transport utilisés par une personne. Pour ce faire, une première étape serait de distinguer la marche de l'ensemble des autres modes de transport.
II. Code
Imports¶
import gmplot
import parser
import filters
import matplotlib.pyplot as plt
from IPython.display import IFrame
A. Choix des données
IPhone ou Android ?¶
Dans un premier temps, nous avons cherché à obtenir une journée avec un grand nombre de points, en effet la journée du 21 sept 2015 avait très peu de points. (moins de 5 points pour le trajet du matin et idem pour le trajet du soir)
Pour cela nous avons pris deux ensemble des données Google Takeout :
- Un jeu de données d'un téléphone Android de mi-2015 à debut-1018 (dataset #1)
- Un jeu de données d'un iPhone de mi-2016 à debut-2018 (dataset #2)
# C'est très long
android_df = parser.importJson("data/android.json")
iphone_df = parser.importJson("data/iphone.json")
android_df.head()
On crée une fonction qui retourne le nombre de points par jour pour un dataframe donné.
def compute_points_per_day(df) :
points_per_day = []
current_day = ""
j = -1
for i in range(df["date"].size) :
if (df["date"][i] == current_day) :
points_per_day[j] += 1
else :
j += 1
current_day = df["date"][i]
points_per_day.append(1)
return points_per_day
android_points = compute_points_per_day(android_df)
iphone_points = compute_points_per_day(iphone_df)
plt.figure(figsize=(12,8))
plt.plot(android_points, '-',label='Android Points Count')
plt.plot(iphone_points, 'r-',label='iPhone Points Count')
plt.grid(True)
plt.ylabel('Number of points')
plt.xlabel('Days')
plt.ylim((0, 3500))
plt.legend(loc='upper right')
plt.show()
Sélection de la journée¶
day_df = parser.selectDate("17-08-2017", android_df)
day_df.head()
gmap = gmplot.GoogleMapPlotter(45.757589, 4.831689, 14, apikey="AIzaSyDsYwvF3UUxTx8RB40wd4SnUVzfnbW66LM")
gmap.plot(day_df["latitude"],day_df["longitude"], 'cornflowerblue', edge_width=2)
gmap.draw("figure/3-day-android.html")
IFrame('figure/3-day-android.html', width=990, height=500)
Cette journée comporte beaucoup de déplacements dans le centre de Lyon.
Plus précisément, nous savons que l'ensemble de ces déplacements a été réalisé à pied.
Analyse des données¶
plt.figure(figsize=(12,8))
plt.subplot(211)
plt.hist(day_df["velocity"], 100)
plt.grid(True)
plt.xlabel('Vitesse (km/h)')
plt.ylabel('Nombre d\'échantillons')
plt.xlim([0,40])
plt.subplot(212)
plt.hist(day_df["acceleration"], 100)
plt.xlim([0,5])
plt.grid(True)
plt.xlabel('Acceleration (km/h^2)')
plt.ylabel('Nombre d\'échantillons')
plt.show()
La vitesse et l'accélération sont la plupart du temps très proches de 0.7
La vitesse est comprise globalement entre 0 et 5 km/h, ce qui est cohérent avec une journée de marche.
L'accélération est comprise entre 0 et 1 km/h²; ce qui est également cohérent pour de la marche.
On constate dans les deux cas, la présence de résidus dans les hautes valaurs.
plt.figure(figsize=(12,8))
plt.hist(day_df["delay"], 1000)
plt.grid(True)
plt.xlabel('Delai entre deux échantillons (secondes)')
plt.xlim([0,100])
plt.ylabel('Echantillons au cours de la journée')
plt.show()
Les echantillons sont échantillonnés pour la plupart toutes les 20 secondes.
B. Filtrage des données : Average & Median
Dans cette partie on se propose de comparer les trajectoires filtrées avec les average et median filters avec la trajectoire initiales en calculant la distance entre chaque point avant et après filtrage.
day_df = parser.selectDate("17-08-2017", android_df)
Average filter¶
day_df_filtered = filters.meanFilter(day_df)
gmap = gmplot.GoogleMapPlotter(45.757589, 4.831689, 15, apikey="AIzaSyDsYwvF3UUxTx8RB40wd4SnUVzfnbW66LM")
gmap.plot(day_df_filtered['latitude'],day_df_filtered['longitude'], 'cornflowerblue', edge_width=3)
gmap.plot(day_df_filtered['lat_mean_filt'],day_df_filtered['lng_mean_filt'], 'red', edge_width=2)
gmap.draw("figure/3-mean-filter.html")
IFrame('figure/3-mean-filter.html', width=990, height=500)
Les trajets rouges sont ceux filtrés et les bleux sont les données originelles.
On peut évaluer l'amplitude de la correction appliquée par le filtre en calculant la distance pour chaque point entre sa position initiale et sa position après filtrage, distance qui correspond à "l'erreur" du GPS selon le filtre.
errorMean = filters.errorDistances(day_df_filtered, "lat_mean_filt", "lng_mean_filt")
plt.figure(figsize=(12,4))
plt.grid(True)
plt.xlabel('Numéro du point')
plt.ylabel('Distance entre le point d\'origine et le point filtré (m)')
plt.plot(errorMean)
plt.show()
plt.figure(figsize=(12,4))
plt.hist(errorMean, 500)
plt.grid(True)
plt.xlabel('Distance entre point d\'origine et point filtré (m)')
plt.ylabel('Nombre d\'échantillons')
plt.xlim([0,100])
plt.show()
On remarque que certaines séquences ne subissent que des corrections minimes (notamment pour les points 100 à 500) mais que la différence peut atteindre les 400 mètres dans le pire cas.
Median filter¶
day_df_filtered = filters.medianFilter(day_df_filtered)
gmap = gmplot.GoogleMapPlotter(45.757589, 4.831689, 15, apikey="AIzaSyDsYwvF3UUxTx8RB40wd4SnUVzfnbW66LM")
gmap.plot(day_df_filtered['latitude'],day_df_filtered['longitude'], 'cornflowerblue', edge_width=3)
gmap.plot(day_df_filtered['lat_med_filt'],day_df_filtered['lng_med_filt'], 'red', edge_width=2)
gmap.draw("figure/3-median-filter.html")
IFrame('figure/3-median-filter.html', width=990, height=500)
Les trajets bleux sont issues des données originelles, les trajets rouges des données filtrées.
De même on peut afficher la distance entre les points filtrés et originels.
errorMed = filters.errorDistances(day_df_filtered, "lat_med_filt", "lng_med_filt")
plt.figure(figsize=(12,4))
plt.grid(True)
plt.xlabel('Numéro du point')
plt.ylabel('Distance entre le point d\'origine et le point filtré (m)')
plt.plot(errorMed)
plt.show()
plt.figure(figsize=(12,4))
plt.hist(errorMed, 500)
plt.grid(True)
plt.xlabel('Distance entre point d\'origine et point filtré (m)')
plt.ylabel('Nombre d\'échantillons')
plt.xlim([0,100])
plt.show()
Par rapport au filtre précédent, on a moins de pics mais ceux ici sont plus grands. En effet puisqu'on utilise les points médians, il arrive souvent que le poitfiltré soit exactement celui d'origine, en revanche lorsqu'on corrige, on ne moyenne pas et donc le point corrigier ne participe pas à sa correction, elle est d'autant plus importante. Cela montre que le median filter est moins sensible aux point aberrants.
Comparaison des filtres¶
Pour comparer les filtres on commence par afficher les deux trajectoires filtrées : celle du mean filter est en bleu et celle du median filter en rouge.
gmap = gmplot.GoogleMapPlotter(45.757589, 4.831689, 15, apikey="AIzaSyDsYwvF3UUxTx8RB40wd4SnUVzfnbW66LM")
gmap.plot(day_df_filtered['lat_mean_filt'],day_df_filtered['lng_mean_filt'], 'cornflowerblue', edge_width=2)
gmap.plot(day_df_filtered['lat_med_filt'],day_df_filtered['lng_med_filt'], 'red', edge_width=2)
gmap.draw("figure/3-both-filters.html")
IFrame('figure/3-both-filters.html', width=990, height=500)
On constate d'une part que les trajectoires du mean filter sont plus courbées là où celles du median filter présentent des angles droits plus en accords avec le tracé des rues. De plus on voit bien que le median filter est plus robuste face aux outliers, notamment au niveau du pont Wilson. Dans l'ensemble le median filter semble donner des résultats plus satisfaisants.
On peut également comparer la fidélité aux données d'origine en comparant la médiane des distances de correction sur l'ensemble des points pour chaque filter :
errorMeanSorted = sorted(errorMean)
errorMedSorted = sorted(errorMed)
print("Ecart médian pour : ")
print("- mean filter : "+str(errorMeanSorted[int(len(errorMean)/2)])[0:5]+' mètres.')
print("- median filter : "+str(errorMedSorted[int(len(errorMed)/2)])[0:5]+' mètres.')
Comme on s'y attendait le median filter est plus fidèle aux données d'origine.
C. Filtrage des données : Heuristics Based Outliners
Speed Thereshold¶
Centres d'interet¶
Une première application des filtres heuristiques, pourrait être de localiser les points d'interets: ces derniers sont les points où la vitesse de la personne est très faible. En pratique, on a choisi un vitesse inférieure à 2 km/h.
filteredData = day_df[day_df.velocity < 2]
gmap = gmplot.GoogleMapPlotter(45.757589, 4.831689, 14.5, apikey="AIzaSyDsYwvF3UUxTx8RB40wd4SnUVzfnbW66LM")
gmap.heatmap(filteredData['latitude'], filteredData['longitude'])
gmap.draw("figure/3-immobility.html")
IFrame('figure/3-immobility.html', width=990, height=500)
La projection de ces points sur une heatmap permet de facilement repérer les points d'arrets dans la journée.
Filtrage¶
Nous avons vu plus haut que la vitesse était globalement répartie entre 0 et 5 km/h. Nous avons également noté la présence de points exceptionnels avec une vitesse très importante. Ces vitesses anormalement élevées sont certainement dûes à des erreurs lors de l'acquisition. Enlever ces points permettrait donc de débruiter le parcours.
filteredData = day_df[day_df.velocity < 6]
gmap = gmplot.GoogleMapPlotter(45.757589, 4.831689, 15, apikey="AIzaSyDsYwvF3UUxTx8RB40wd4SnUVzfnbW66LM")
gmap.plot(day_df['latitude'],day_df['longitude'], 'cornflowerblue', edge_width=5)
gmap.plot(filteredData['latitude'],filteredData['longitude'], 'red', edge_width=2)
gmap.draw("figure/3-low-speed.html")
IFrame('figure/3-low-speed.html', width=990, height=500)
Nous constatons que cette approche fournit un certain nombre de résultats intéressants. Les passages sur les points suivants sont plus lisibles et semblent plus réels :
- la traversée de la passerrelle du Palais de la Justice
- la passage place Bellecour
Plusieurs points aberrants uniques ont également été enlevé avec succès.
Toutefois, ce débruitage n'est pas parfait. Dans certaines zones, les hautes fréquences persistent :
- garre Perrache
- place des Terreaux
Pour corriger ces points, il faut descendre le seuil au-delà des valeurs pertinentes : soit 1 ou 2 km/h. Un tel filtrage dégrade trop la trajectoire.
Acceleration Thereshold¶
L'accélération présente un comportement très semblable à la vitesse.
accFilteredData = day_df[day_df.acceleration < 1]
gmap = gmplot.GoogleMapPlotter(45.757589, 4.831689, 15, apikey="AIzaSyDsYwvF3UUxTx8RB40wd4SnUVzfnbW66LM")
gmap.plot(day_df['latitude'],day_df['longitude'], 'cornflowerblue', edge_width=5)
gmap.plot(accFilteredData['latitude'],accFilteredData['longitude'], 'red',edge_width=2)
gmap.draw("figure/3-low-acceleration.html")
IFrame('figure/3-low-acceleration.html', width=990, height=500)
D. Première segmentation des trajets
On va essayer de segmenter cette journée. On commence par l'approche naïve :
Hypothèse : Entre deux trajets, l'utilisateur rentre à intérieur d'un batiment, ce qui augmente le délai entre deux mesures (à cause des difficultés à recevoir le signal gps en intérieur)
On découpe donc les segments de manière à ce que deux segments soient séparés par des delay élevés. On cherche à fixer arbitrairement une limite de délai. Pour cela, on affiche les délais sur la journée :
max(day_df["delay"])
plt.figure(figsize=(12,8))
plt.plot(day_df["delay"])
plt.grid(True)
plt.ylabel('Delay')
plt.xlabel('Numéro de Mesure')
plt.show()
Un des délai est d'environs 4 heures. Il s'agit probablement du fait que le téléphone s'est éteint. On limite l'axe des y à des délai inférieur à 400 secondes.
plt.figure(figsize=(12,8))
plt.plot(day_df["delay"])
plt.grid(True)
plt.ylabel('Delay')
plt.xlabel('Numéro de Mesure')
plt.ylim((0, 200))
plt.show()
On remarque que Google Maps tente de prendre des mesures toutes les 20 secondes avec parfois :
- des temps plus court que 20 sec (probablement lorsque l'application Google Maps est en premier plan)
- des temps plus longs que 20 sec (probablement à cause d'une mauvaise réception dans un batiment)
On s'intéresse également à une approche basée sur la vitesse pour créer des segments :
plt.figure(figsize=(12,8))
plt.plot(day_df["velocity"])
plt.grid(True)
plt.ylabel('Velocity')
plt.xlabel('Numéro de Mesure')
plt.ylim((0,150))
plt.show()
La trajectoire n'étant pas encore filtrée, la vitesse semble très volatile, donc peu utilisable pour la segmentation.
On crée une fonction permettant de segmenter un dataframe. Dès qu'un delay est supérieur à 100 secondes (choisi par rapport au graphique des délais), un nouveau segment est créé.
def delay_segment_dataframe(df, limit) :
segnum = 0
segments = []
for i in range(df["time"].size) :
if (df["delay"][i] > limit) :
segments.append(segnum)
segnum += 1;
else :
segments.append(segnum)
df["segment"] = segments
return df
day_df = delay_segment_dataframe(day_df, limit=100)
segment_count = max(day_df['segment'])
segment_count
On a 25 segments pour la journée. Cela semble beaucoup mais on pourra considérer supprimer les segments trop court.
On cherche à afficher la carte de la journée, mais avec une couleur différente par trajet.
import colors
colors_list = []
for key in colors.color_codes.keys():
colors_list.append(colors.color_codes[key])
gmap = gmplot.GoogleMapPlotter(45.757589, 4.831689, 14, apikey="AIzaSyDsYwvF3UUxTx8RB40wd4SnUVzfnbW66LM")
for i in range(segment_count) :
start_index = day_df[day_df['segment'] == i].index.tolist()[0]
end_index = day_df[day_df['segment'] == i + 1].index.tolist()[0]
segment_df = day_df.loc[start_index:(end_index - 1),]
gmap.plot(segment_df["latitude"], segment_df["longitude"], colors_list[i], edge_width=2)
gmap.draw("figure/3-segments.html")
IFrame('figure/3-segments.html', width=990, height=500)
La segmentation semble cohérente. Certaines trajets restent très étranges (aller-retour au dessus de la Saone).
Cependant l'approche que nous avons utiisé (limite sur les délais) ne fonctionne que si la personne rentre dans un batiment, et la limite que nous avons fixée est arbitraire. On peut réfléchir à une autre méthode basée sur la vitesse filtrée, ou les points d'intérêts.
III. Conclusion
A. Bilan
Concernant la partie segmentation :
- Nous avons remarqué qu'en général sur des trajets très peu de points sont présents, ainsi un certains nombre de question se pose : que peut-on vraiment tirer comme information de ces trajets ? Cela a t-il du sens de les filtrer ? (un filtrage considère beaucoup de points comme abérants, alors qu'ils ne le sont pas)
- L'approche naïve de la segmentation basée sur la limite sur les delays semble bien fonctionner, il serait intéressant de pouvoir fixer cette limite de manière moins arbitraire et de travailler sur d'autres algorithmes de segmentation.
B. Travail à faire de la prochaine séance
Pour la prochaine séance nous devons :
- faire tourner nos algorithmes sur un plus grand nombre de trajets
- améliorer la segmentation
- proposer d'autres algorithmse de segmentation
- adapter les filtres aux segments
- filtrer les données, puis étudier la vitesse sur les données filtrées, et regarder en particulier si on peut en déduire le mode de transport
- discussion du nom des notebooks