=Paper=
{{Paper
|id=Vol-2133/rjcia-paper1
|storemode=property
|title=Découverte des u-shapelets basée sur la corrélation pour le clustering de séries temporelles incertaines(Frobenius correlation based u-shapelets discovery for time series clustering)
|pdfUrl=https://ceur-ws.org/Vol-2133/rjcia-paper1.pdf
|volume=Vol-2133
|dblpUrl=https://dblp.org/rec/conf/rjcia/FotsoNV18
}}
==Découverte des u-shapelets basée sur la corrélation pour le clustering de séries temporelles incertaines(Frobenius correlation based u-shapelets discovery for time series clustering)==
https://ceur-ws.org/Vol-2133/rjcia-paper1.pdf
Découverte des u-shapelets basée sur la corrélation pour le clustering de séries
temporelles incertaines.
Vanel Steve Siyou Fotso1 Engelbert Mephu Nguifo1 Philippe Vaslin 1
1
University Clermont Auvergne, CNRS, LIMOS, F-63000 Clermont-Ferrand, France
{siyou, mephu, vaslin}@isima.fr
Abstract de données, et il a montré une amélioration substantielle
de la qualité de la classification non supervisée par rap-
An u-shapelet is a sub-sequence of a time series used for
port au Rand Index. Ce travail définit un nouveau cadre
clustering a time series dataset. The purpose of this pa-
pour la classification non supervisée de séries temporelles
per is to discover u-shapelets on uncertain time series. To
incertaines.
achieve this goal, we propose a dissimilarity score cal-
led FOTS whose computation is based on the eigenvec- Mots Clef
tor decomposition and the comparison of the autocorre-
lation matrices of the time series. This score is robust to Classification non supervisée, UShapelet, Correlation, Sé-
the presence of uncertainty ; it is not very sensitive to tran- ries temporelles.
sient changes ; it allows capturing complex relationships
between time series such as oscillations and trends, and it
1 Introduction
is also well adapted to the comparison of short time series. Toutes les mesures effectuées par un système mécanique
The FOTS score is used with the Scalable Unsupervised ont une incertitude. En effet, le principe d’incertitude met
Shapelet Discovery algorithm for the clustering of 17 da- en évidence les limites de la capacité des systèmes méca-
tasets, and it has shown a substantial improvement in the niques à effectuer des mesures sur un système sans les per-
quality of the clustering with respect to the Rand Index. turber [1]. Ainsi, les séries temporelles des instruments de
This work defines a novel framework for the clustering of mesure sont incertaines. Ces séries temporelles produites
uncertain time series. par des capteurs constituent une vaste proportion des sé-
ries temporelles utilisées en science, que ce soit en mé-
Mots Clef decine avec des Électrocardiogramme (enregistrement de
Clustering, UShapelet, Correlation, time series. l’activité électrique du cœur), en physique avec des me-
sures enregistrées par des télescopes, en informatique avec
Résumé l’Internet des objets, etc. Ignorer l’incertitude des données
Un u-shapelet est une sous-séquence d’une série tempo- au cours de leur analyse peut conduire à des conclusions
relle utilisée comme propriété pour séparer un groupe de approximatives ou inexactes, d’où la nécessité de mettre en
séries temporelles en deux sous-groupes. Un sous-groupe œuvre des techniques de gestion des données incertaines.
de séries temporelles contenant le shapelet et un sous- Plusieurs études récentes ont porté sur le traitement de l’in-
groupe de série temporelles ne contenant pas le shape- certitude dans l’exploration de données. Deux approches
let. Le but de cet article est de découvrir des u-shapelets principales permettent de prendre en compte l’incertitude
sur des séries temporelles incertaines. Pour atteindre cet dans les tâches de data mining : soit elle est prise en compte
objectif, nous proposons un score de dissimilarité appelé lors de la comparaison en utilisant les fonctions de distance
FOTS dont le calcul est basé sur la comparaison des vec- appropriées [2–7], soit son impact est réduit par les trans-
teurs propres des matrices d’autocorrélation des séries formations effectuées sur les données. Cette dernière stra-
temporelles. Ce score est robuste à la présence d’incer- tégie est utilisée nativement par l’algorithme u-shapelet.
titude ; il n’est pas très sensible aux changements transi-
toires ; il permet de capturer des relations complexes entre
1.1 État de l’art sur les u-shapelets
des séries temporelles telles que les oscillations et les ten- Considérons un ensemble de données composé de 6 séries
dances, et il est également bien adapté à la comparaison temporelles correspondant aux appels d’oiseaux : 3 séries
de séries temporelles courtes. Le score FOTS est utilisé temporelles correspondant à Moucherolle à côtés olive (sé-
avec l’algorithme Scalable Unsupervised Shapelet Disco- ries temporelles vertes) et 3 séries temporelles correspon-
very pour la classification non supervisée de 17 ensembles dant aux appels de Moineau à couronne blanche (séries
Definition 3 La distance de sous-séquence sdist(S, T)
entre une série temporelle T et une sous-séquence S est le
minimum des distances entre la sous-séquence S et toutes
les sous-séquences de T de longueur égale à celle de S.
Cette définition ouvre la question de la mesure de distance
F IGURE 1 – Exemple de classification de séries temporelles utili- à utiliser pour sdist. En général, la distance euclidienne
sant d’une part la distance euclidienne (gauche), d’autre part des
omniprésente (ED) est utilisée, mais elle ne l’est pas ap-
sous-séquences caractéristiques appelées u-shapelet (droite). [8].
propriée pour les séries temporelles incertaines [5]. Dans
la section suivante, nous présentons une fonction de dissi-
temporelles bleues). Lorsque ces séries temporelles sont milarité plus adaptée à l’incertitude.
classées en utilisant la distance euclidienne comme me- Le calcul de la sdist entre un u-shapelet candidat et toutes
sure de dissimilarité (Fig. 1 gauche), les groupes obtenus les séries temporelles d’un jeux de données est appelé or-
ne sont pas homogènes ; en d’autres termes, l’algorithme derline.
n’identifie pas l’oiseau à partir de ses cris. Cependant, si
Definition 4 Un orderline est un vecteur de distance entre
nous recherchons des sous-séquences caractéristiques (u-
un u-shapelet et toutes les séries temporelles d’un jeu de
shapelets) pour classer les séries temporelles, nous obte-
données.
nons des groupes plus homogènes (Fig. 1 à droite).
Une fois cette observation faite, la question naturelle est
Le calcul d’un orderline est coûteux en temps. Un orderline
de savoir comment trouver des sous-séquences qui carac-
pour un seul u-shapelet candidat a une complexité en temps
térisent un groupe de séries temporelles, c’est-à-dire des
égale à O(N M log(M )) où N est le nombre de séries tem-
sous-séquences qui ne sont observées que dans un sous-
porelles du jeux de données, M est la longueur moyenne
groupe de séries temporelles. L’algorithme de découverte
des séries temporelles. L’algorithme force brute pour la dé-
d’u-shapelet répond à cette question et procède comme
couverte de u-shapelet requiert K calculs d’orderline, où
suit : l’algorithme prend la longueur du motif comme para-
K est le nombre de sous-séquences candidate. La stratégie
mètre. Sur chaque série temporelle de la base, on fait glis-
utilisée par [8] à filtrer les K sous-séquences candidates en
ser une fenêtre de la même longueur que le motif, chaque
considérant seulement celles permettant de construire deux
nouvelle sous-séquence obtenue par ce processus est un u-
groupes r-équilibrés. Cette sélection est faite efficacement
shapelet candidat.
grâce a un algorithme de hachage.
Parmi les u-shapelets candidats, nous considérons comme L’évaluation de la qualité des u-shapelets est basée sur leur
un u-shapelet la sous-séquence capable de diviser l’en- pouvoir de séparation qui est calculé comme suit :
semble de séries temporelles en deux sous-ensembles DA
et DB de sorte que DA contient toutes les séries tempo- gap = µB − σB − (µA − σA ), (1)
relles qui possèdent le u-shapelet et DB toutes celles qui ne
contiennent pas l’u-shapelet. Deux autres contraintes sont Où µA (resp. µB ) représente la moyenne(sdist(S, DA ))
prises en compte dans la découverte de motifs : (resp. moyenne(sdist(S, DB ))), et σA (resp. σB ) repré-
La première est la capacité de l’u-shapelet à construire des sente l’écart-type de sdist(S, DA ) (resp. écart-type de
sous-ensembles bien séparés. La deuxième est la capacité sdist(S, DB )).
de l’u-shapelet à construire des sous-ensembles qui ne sont Si DA ou DB est constitué d’un seul élément (ou d’un
pas déséquilibrés. C’est-à-dire que la taille de DA doit être nombre insuffisant de séries temporelles pour constituer
au plus k fois plus grande que celle de DB et vice versa. un groupe), le gap prend la valeur zéro. Ceci assure qu’un
gap élevé pour un u-shapelet correspond à une séparation
Definition 1 Deux jeux de données DA et DB sont dit r- réelle.
|DA |
équilibré si et seulement si 1r < |DB|
< (1 − 1r ), r > 1
1.2 U-shapelets pour la classification non su-
Definition 2 Un u-shapelet est une sous-séquence qui a pervisée de séries temporelles incertaines
une longueur inférieur ou égale à la longueur de la plus pe- La classification non supervisée basée sur des u-shapelets
tite série temporelle du jeu de données, et qui permet de di- est une approche introduite par [9] qui a suggéré de regrou-
viser le jeux de données en deux sous-groupes r-équilibrées per des séries temporelles à partir des propriétés locales de
DA et DB ; où DA est le groupe de séries temporelles qui leurs sous-séquences plutôt qu’utiliser les caractéristiques
contiennent un motif similaire au u-shapelet et DB est le globales de la série temporelle [10]. Dans ce but, le cluste-
groupe de séries temporelles qui ne contiennent pas l’u- ring basé sur les u-shapelets cherche d’abord un ensemble
shapelet. de sous-séquences caractéristiques des différentes catégo-
ries de séries temporelles et classe une série temporelle
La similarité entre une série temporelle et un u-shapelet est en fonction de la présence ou de l’absence de ces sous-
évaluée à l’aide d’une fonction de distance. séquences caractérisitiques.
La classification non supervisée de séries temporelles avec taines de petite taille et ne fait aucune hypothèse
des u-shapelets présente plusieurs avantages. Première- sur la distribution de probabilité de l’incertitude.
ment, la classification non supervisée basée sur les u- — Nous mettons le code source à la disposition de la
shapelets est définie pour les ensembles de données dans communauté scientifique pour permettre une exten-
lesquels les séries temporelles ont des longueurs diffé- sion de ce travail.
rentes, ce qui n’est pas le cas pour la plupart des tech-
niques décrites dans la littérature. En effet, dans de nom- 2 Définitions et travaux connexes
breux cas, l’hypothèse de longueur égale est implicite, et
le découpage à longueur égale est effectué en exploitant 2.1 Définitions
des compétences humaines coûteuses [8]. Deuxièmement, Une série temporelle incertaine (UTS) X =<
la classification non supervisée basée sur les u-shapelets est X1 , . . . , Xn > est une séquence de variable aléatoire
beaucoup plus expressive en ce qui concerne le pouvoir de où Xi est une variable aléatoire modélisant une valeur
représentation. En effet, une série temporelle n’est associé réelle inconnue à l’instant i. Deux modèles sont princi-
à un groupe que si elle contient l’u-shapelet caractéristique palement utilisés pour représenter les séries temporelles
de ce groupe. Ainsi, un une série temporelle pourrait n’être incertaines : le modèle ensembliste, et le modèle basé sur
associé à aucun groupe. la fonction de densité de probabilité de l’incertitude.
De plus, il est très approprié d’utiliser la classification non
Dans le modèle ensembliste, chaque élément Xi (1 ≤
supervisée basée sur les u-shapelets avec des séries tem-
i ≤ n) de l’UTS X =< X1 , . . . , Xn > est représenté par
porelles incertaines parce que la stratégie de comparaison
un ensemble {Xi,1 , . . . , Xi,Ni } de valeurs observées et Ni
d’un u-shapelet et d’une série temporelle ignore les don-
représente le nombre d’observation à l’instant i.
nées non pertinentes de la série temporelle et ainsi réduire
les effets négatifs de la présence d’incertitudes dans celle- Dans le modèle basé sur la distribution de probabilité,
ci. Malgré cet avantage, il est hautement souhaitable de chaque élément Xi , (1 ≤ i ≤ n) de l’UTS X =<
prendre en compte l’impact négatif de l’incertitude lors de X1 , . . . , Xn > est représenté par une variable aléatoire
la découverte des u-shapelets. Xi = xi + Xei , où xi est la valeur exacte qui est incon-
nue, et Xei est une variable aléatoire représentant l’erreur.
1.3 Incertitude et découverte des u-shapelets C’est ce modèle que nous considérons tout au long de notre
Les mesures traditionnelles de similarité comme la dis- travail.
tance euclidienne (ED) ou la distorsion temporelle dy- Plusieurs mesures de similarité ont été proposées pour les
namique (DTW) ne fonctionnent pas toujours bien pour séries temporelles incertaines. Elles peuvent être regrou-
les séries temporelles incertaines. En effet, ces distances pées en deux catégories principales : les mesures de simila-
agrègent l’incertitude de chaque point de la série tempo- rité traditionnelles et les mesures de similarité incertaines.
relle et amplifient ainsi l’impact négatif de l’incertitude. — les mesures de similarité traditionnelles telle que
Cependant, ED joue un rôle fondamental dans la décou- la distance euclidienne sont celles conventionnel-
verte des u-shapelets, car elle est utilisée pour calculer lement utilisées avec les séries temporelles. Elles
l’écart entre deux groupes formé par l’u-shapelet candidat. utilisent une seul valeur incertaine à chaque instant
La découverte de u-shapelet sur des séries temporelles in- comme approximation de la valeur réelle inconnue.
certaines pourrait donc conduire à la sélection d’un mau- — les mesures de similarité incertaines utilisent des
vais candidat u-shapelet ou à l’assignation d’une série tem- informations statistiques additionnelles qui me-
porelle au mauvais groupe. surent l’incertitude associée à chaque approxima-
Dans cette étude, notre but n’est pas de définir un algo- tion de la valeur réelle. C’est le cas notamment de
rithme pour la découverte d’u-shapelets incertains, mais DUST, PROUD, MUNICH [11]. [12] démontre que
plutôt d’utiliser une fonction de dissimilarité robuste à l’in- les performances des mesures de similarité incer-
certitude pour améliorer la qualité des u-shapelets décou- taines associées au pré-traitement sont meilleures
verts et donc la qualité de clustering des séries temporelles que les performances des mesures de similarité tra-
incertaines. ditionnelles sur des jeux de données contenant de
1.4 Contributions l’incertitude.
— Nous faisons un état de l’art sur les mesures de 2.2 État de l’art sur les mesures de similarité
dissimilarité incertaines et nous les évaluation leur incertaines
pertinence pour la comparaison de séries tempo-
Les mesures de similarité incertaines peuvent être regrou-
relles incertaines de petite taille.
pées en deux grandes catégories : les mesures de similarité
— Nous introduisons une fonction de dissimilarité
déterministes et les mesures de similarité probabilistes.
nommée correlation frobenius pour découverte d’u-
shapelets sur les séries temporelles incertaines Mesure de similarité déterministe. Tout comme les me-
(FOTS) ;qui posséde des propriétés intéressantes sures de similarité traditionnelles, les mesures de similarité
pour la comparaison de séries temporelles incer- déterministes renvoient un nombre réel représentant la dis-
tance entre deux séries temporelles incertaines. DUST est PROUD [15] Soient X =< X1 , ..., Xn > et Y =<
un exemple de mesure déterministe de similarité. Y1 , ..., Yn > deux UTS modélisées par des séquences de
variables aléatoires, la distance PROUD entre X et Y est
DUST [13] Etant donné deux séries temporelles incer- n
(Xi − Yi )2 . D’après le théorème central li-
P
taines X =< X1 , . . . , Xn > et Y =< Y1 , . . . , Yn >, d(X, Y ) =
i=1
la distance entre deux valeurs Xi , Yi est définie comme mite [16], la distribution cumulée approche asymptotique-
étant la distance entre leurs valeurs réelles inconnues r(Xi ), ment une loi normale
r(Yi ) : dist(Xi , Yi ) = |r(Xi ) − r(Yi )|. Cette distance est
utilisée pour mesurer la similarité de deux valeurs incer- X X
taines. d(X, Y ) ∝ N ( E[(Xi − Yi )2 ], V ar[(Xi − Yi )2 ]) (6)
ϕ(|Xi −Yi |) est la probabilité que les valeurs réelles à l’ins- i i
tant i soient égales, connaissant les valeurs réelles à l’ins-
Une conséquence de cette caractéristique de la distance
tant i.
PROUD est que le tableau de la loi réduite centrée normale
peut être utilisé pour calculer la probabilité que la distance
PROUD normalisée soit inférieure à un seuil :
ϕ(|Xi − Yi |) = P r(dist(0, |Xi − Yi |) = 0). (2)
cette fonction de similarité est par la suite utilisée par la P r(d(X, Y )norm ≤ ). (7)
fonction de dissimilarité dust :
p Un inconvénient majeur de PROUD est son inadéquation
dust(Xi , Yi ) = −log(ϕ(|Xi − Yi |)) + log(ϕ(0)). (3) pour la comparaison de séries temporelles de petites lon-
gueurs comme les u-shapelets. En effet, le calcul de la pro-
La distance entre les séries temporelles incertaines X =< babilité que la distance PROUD soit inférieure à une valeur
X1 , . . . , Xn > et Y =< Y1 , . . . , Yn > calculée à partir de est basé sur l’hypothèse qu’elle suit asymptotiquement
DU ST est alors définie comme suit : une distribution normale. Ainsi, cette probabilité sera d’au-
tant plus précise que les séries temporelles comparées sont
v longues (plus de 30 points de données).
u n
uX PROUDS [12] est une version amélioré de PROUD qui
DU ST (X, Y ) = t dust(Xi , Yi )2 . (4)
suppose que les variables aléatoires qui constituent la sé-
i=1
rie temporelle sont indépendantes et identiquement distri-
buées.
Le problème avec les distances déterministes incertaines
comme DU ST est que leur expression varie en fonction Definition 5 La forme normalisée d’une série tempo-
de la distribution de probabilité de l’incertitude, et la dis- relle X =< X1 , . . . , Xn > est définie par X̂ =<
tribution de probabilité de l’incertitude n’est pas toujours X̂1 , . . . , Xˆn > tel que à chaque instant i (1 ≤ i ≤ n),
disponible pour les jeux de données de séries temporelles. nous avons :
Mesure de similarité probabiliste. Les mesures des si-
milarités probabilistes n’exigent pas la connaissance de la v
n u n
distribution des probabilités d’incertitude. De plus, elles Xi − X̄ X Xi uX (Xi − X̄)2
X̂i = , X̄ = , SX = t . (8)
fournissent aux utilisateurs plus d’informations sur la fia- SX n (n − 1)
i=1 i=1
bilité du résultat. Il existe plusieurs fonctions de simila-
rité probabiliste, comme MUNICH, PROUD, PROUDS ou
Corrélation Locale.
PROUDS définit la distance entre deux séries temporelles
MUNICH [14]. Cette fonction de distance convient aux normalisées X̂ =< X̂1 ...X̂n > and Ŷ =< Ŷ1 ...Ŷn >
séries temporelles incertaines représentées par le modèle (Définition 5) comme suit :
ensembliste. La probabilité que la distance entre deux sé-
ries temporelles incertaines X et Y soit inférieure à un seuil n
ε est égale au nombre de distances entre X et Y, qui sont
X
Eucl(X̂, Ŷ ) = 2(n − 1) + 2 X̂i Ŷi (9)
inférieures à ε, sur le nombre possible de distances : i=1
Pour les mêmes raisons que PROUD, PROUDS ne
|{d ∈ dists(X, Y )|d ≤ ε}| conviennent pas à la comparaison de séries temporelles
P r(distance(X, Y )) ≤ ε = (5)
|dists(X, Y )| courtes. Un autre inconvénient de PROUDS est qu’il sup-
pose que les variables aléatoires sont indépendantes : cette
Le calcul de cette fonction de distance est très couteuse en hypothèse est forte et particulièrement inappropriée pour
temps. des séries temporelles courtes comme les u-shapelets. Une
hypothèse plus réaliste avec les séries temporelles serait de exemple, sinusoïdale) ainsi que les tendances apériodiques
considérer que les variables aléatoires constituant les sé- (par exemple, à la hausse ou à la baisse) qui sont présentes.
ries temporelles sont M-dépendantes. Les variables aléa- L’utilisation de matrices d’auto-corrélation qui sont calcu-
toires d’une série temporelle sont dites M-dépendantes si lées sur la base de fenêtres se chevauchant permet de ré-
Xi , Xi+1 , ..., Xi+M sont dépendantes (corrélées) et les va- duire la sensibilité aux changements transitoires dans
riables Xi et Xi+M +1 sont indépendantes. Cependant, sup- les séries temporelles.
poser que les variables aléatoires sont M-dépendantes com-
plexifie l’écriture de PROUDS et rend son utilisation plus Definition 7 (Auto-covariance, fenêtre glissante) Étant
difficile car elle requiert dès lors d’affecter une valeur au donnée une série temporelle X, un ensemble de fenêtre
paramètre M. glissante w, l’estimateur de la matrice d’autocorrelation
locale Γ̂t utilisant une fenêtre glissante est définie à l’ins-
Corrélation incertaine [7] : Les techniques d’analyse de
tant t ∈ N tel que (Eq.11) :
corrélation sont utiles pour la sélection de caractéristiques
dans des séries temporelles incertaines. Ces informations
permettent d’identifier les éléments redondants. La même t
X
stratégie peut être utile pour la découverte de u-shapelet. Γ̂t (X, w, m) = xτ,w ⊗ xτ,w . (11)
La corrélation incertaine est définie comme suit : τ =t−m+1
Definition 6 (Correlation sur les séries temporelles incer- Où xτ,ω est une sous-séquence de la série temporelle de
taines) Etant données deux UTS X =< X1 , . . . , Xn > et longueur w et commençant à τ , x ⊗ y = xy T est le produit
Y =< Y1 , . . . , Yn >, leur correlation est définie par extérieur de x et y. L’ensemble d’échantillons de m fenêtres
est centré autour du temps t. Nous fixons généralement le
Xn nombre de fenêtres à m = w.
Corr(X, Y ) = X̂i Ŷi /(n − 1), (10)
i=1 Étant donnée les estimations Γ̂t (X) et Γ̂t (Y ) pour les
deux séries temporelles, la prochaine étape est de savoir
Où X̂i et Ŷi sont les formes normales de Xi et Yi (Défi- comment les comparer et extraire un score de corrélation.
nition 5) respectivement. Xi et Yi sont des variables aléa- Cet objectif est atteint en utilisant la décomposition spec-
toires indépendantes et continues. trale ; les vecteurs propres des matrices d’auto-corrélations
capturent les principales tendances apériodiques et oscilla-
Si nous connaissons la distribution de probabilité des va- toires, même sur des séries temporelles courtes. Ainsi, les
riables aléatoires, il est possible de déterminer la fonction sous-espaces couverts par les premiers (k) vecteurs propres
de densité de probabilité associée à la corrélation, qui ser- sont utilisés pour caractériser localement le comportement
vira par la suite à calculer la probabilité que la corréla- de chaque série. La définition 8 formalise cette notion :
tion entre deux séries temporelles soit supérieure à un seuil
donné. La corrélation incertaine a cependant quelques in- Definition 8 (LoCo score) Étant donnée deux séries tem-
convénients : porelles X et Y leur score LoCo est défini par
— Il est trop sensible aux changements transitoires, ce
qui conduit souvent à des scores très fluctuants ;
— Il ne peut pas capturer les relations complexes dans 1
`t (X, Y ) = (kU TX uY k + kU TY uX k) (12)
les séries temporelles ; 2
— Il faut connaître la fonction de distribution de pro- Où U X et U Y sont les k premiers vecteurs propres des ma-
babilité de l’incertitude ou faire une hypothèse sur trices d’auto-corrélation locales Γ̂t (X) et Γ̂t (Y ) respecti-
l’indépendance des variables aléatoires contenues vement, et uX et uY sont les vecteurs propres ayant la plus
dans les séries temporelles. large valeur propre.
En raison de tous ces inconvénients, la corrélation incer- Intuitivement, deux séries temporelles X et Y seront consi-
taine ne peut pas être utilisée en l’état pour la découverte dérées comme étant proches lorsque l’angle formé par l’es-
d’u-shapelet. Le paragraphe suivant présente une générali- pace portant les informations de la série temporelle X et de
sation du coefficient de corrélation qui n’est pas une fonc- la série temporelle Y est nul. En d’autres termes, X et Y
tion de similarité incertaine mais qui reste intéressante pour seront proches lorsque la valeur de cos(α) sera 1. La seule
la découverte des u-shapelets. l’hypothèse faite pour le calcul de la similitude LoCo est
Corrélation locale [17] : La corrélation locale est une que la moyenne des points de la série temporelle est nulle.
généralisation de la corrélation. Elle calcule un score de Cette hypothèse peut facilement être vérifiée, il suffit pour
corrélation évolutif dans le temps qui suit une similarité cela de normaliser les séries temporelles en cours de com-
locale sur des séries temporelles multivariées basées sur paraison. La fonction de similarité LoCo a de nombreuses
une matrice d’auto-corrélation locale. La matrice d’auto- propriétés intéressantes et ne nécessite pas :
corrélation permet de capturer des relations complexes — de connaître la distribution de probabilité de l’in-
dans des séries temporelles comme l’oscillation clé (par certitude,
— de supposer l’indépendance des variables aléatoires
ou de faire une hypothèse sur la longueur de l’u-
n
shapelet. X
Elle est donc intéressante pour la découverte de motifs, (λi (X + E) − λi (X))2 ≤ ||E||2F . (14)
i=1
mais nous avons encore besoin d’une dissimilarité pour
pouvoir découvrir des u-shapelets. Dans le paragraphe sui-
où λi (X) est la plus grande valeur propre de X, et
vant, nous allons définir une fonction de dissimilarité qui
|||E|E||F
F 2. est le carré de la norme Frobenius de E.
a les mêmes propriétés que LoCo et c’est-à-dire, qui est
robuste à la présence d’incertitude.
La section suivante explique comment le FOTS est intégré
3 Notre approche dans l’algorithme de découverte d’u-shapelets.
3.1 Fonction de dissimilarité 3.2 Algorithme des u-shapelets avec score
La fonction de similarité LoCo définie sur deux séries tem- FOTS
porelles multivariées X et Y correspond approximative-
ment à la valeur absolue du cosinus de l’angle formé par Dans cette section, nous ne définissons pas un nouvel
les espaces propres de X et Y (|cos(α)|). Une idée simple algorithme SUShapelet, mais nous expliquons comment
serait d’utiliser la valeur sin(α) ou α comme fonction de nous utilisons l’algorithme SUShapelet avec le score FOTS
dissimilarité mais cette approche ne fonctionne pas si bien ; (FOTS-SUSh) pour faire face à l’incertitude.
le sinus et l’angle ne sont pas assez discriminants pour la Le gap est un critère essentiel pour la sélection des u-
comparaison de vecteurs propres à des fins de clustering. shapelets. Il est sujet à l’incertitude parce que son calcul
Nous proposons donc la mesure de dissimilarité suivante est basé sur la distance euclidienne. Pour y remédier, nous
(Définition. 9). proposons d’utiliser le score de FOTS au lieu d’une simple
distance euclidienne lors du calcul du gap. L’algorithme 1
Definition 9 (FOTS : Frobenius cOrrelation for uncertain explique comment calculer l’orderline en utilisant le score
Time series u-Shapelet discovery) de FOTS. L’algorithme 2 calcul l’orderline et trie les sé-
Étant données deux séries X et Y , leur score FOTS est rie temporelles en fonction de leur proximité au u-shapelet
défini par candidat (ligne 2 et 3). Un u-shapelet est considéré comme
étant présent dans une série temporelle si sa distance à la
v
um k série temporelle est inférieure ou égale à un seuil. Ainsi,
uXX l’algorithme de sélection de seuil construit un cluster DA
F OT S(X, Y ) = kUX − UY kF = t (UX − UY )2ij (13) dont la taille varie entre lb et ub (ligne 5). L’algorithme
i=1 j=1
cherche alors parmi les seuils sélectionnés celui ayant un
gap maximal (ligne 6 et 11).
où kkF est la norme de Frobenius, m est la longueur de la
série temporelle et k est le nombre de vecteurs propres.
Definition 10 La fonction de dissimilarité sdf (S, T )
Comme le calcul FOTS est basé sur la comparaison des entre une série temporelle T et une sous-séquence S est
k-premiers vecteurs propres des matrices d’autocorrélation le minimum des valeurs du score de FOTS entre la sous-
de la série temporelle, il a les mêmes propriétés souhai- séquence S et toutes les sous-séquences possible de T de
tables de la fonction de similarité LoCo, c’est-à-dire : longueur égales à S.
— Il permet de capturer des relations complexes
dans des séries temporelles comme les tendances
oscillatoires clés (par exemple, sinusoïdales) ainsi
que les tendances apériodiques (par exemple, à la Algorithme 1 : ComputeOrderline
hausse ou à la baisse) qui sont présentes ; Input : u-shapeletCandidate : s,
— Il permet de réduire la sensibilité aux change- Jeu de données : D
ments transitoires dans les séries temporelles ; Output : Distance entre l’u-shapelet candidat et toutes
— Il est approprié pour le comparison de séries tem- les séries temporelles du jeu de données
porelles courtes. 1 function ComputeOrderline(s, D)
De plus, la fonction de dissimilarité FOTS est robust à 2 dis ← {} s ← zN orm(s)
la présence d’incertitude due à la décomposition spec- 3 forall i ∈ {1, 2, . . . , |D|} do
trale des matrices d’autocorrélation des séries temporelles. 4 ts ← D(i, :)
La robustesse du FOTS à l’incertitude est confirmée par le 5 dis(i) ← sdf (s, ts)
théorème suivant :
6 return dis/|s|
Théorème 1 (HoffmanWielandt) [18] Si X et X +E sont
matrices n × n symétriques, alors :
Algorithme 2 : ComputeGap Choisir le nombre k de vecteurs propres : Un choix
Input : u-shapeletCandidate : s, pratique est de fixer k à une petite valeur ; nous utilisons
Jeu de données : D, k = 4 tout au long de ces expériences. En effet, les ten-
lb, ub : lower/upper bound : nombre minimum et dances apériodiques clés sont capturées par un seul vec-
maximum de séries temporelles par groupe teurs propres, tandis que les principales tendances oscilla-
Output : gap : distance entre deux groupes toires se manifestent dans une paire de vecteurs propres.
1 function ComputeGap(s, D, lb, ub)
2 dis ← ComputeOrderline(s, D)
5 Métriques d’évalutation
3 dis ← sort(dis) gap ← 0 Différentes mesures de la qualité de classification non su-
4 for i ← lb to ub do pervisée de séries temporelles ont été proposées, notam-
5 DA ← dis ≤ dis(i), DB ← dis > dis(i) ment le score Jaccard, l’indice Rand, l’indice Folkes et l’in-
6 mA ← mean(DA ), mB ← mean(DB ) dice Mallow, etc. Cependant, dans notre cas, nous avons
7 sA ← std(DA ), sB ← std(DB ) des étiquettes de classe pour les jeux de données, nous
8 currGap ← mB − sB − (mA + sA ) pouvons donc utiliser cette information externe pour éva-
9 if currGap > gap then luer la véritable qualité de la classification non supervisée
10 gap ← currGap en utilisant l’indice Rand. De plus, l’indice Rand semble
11 return gap être la mesure de la qualité des groupes couramment utili-
sée [8–10].
5.1 Comparaison avec u-shapelet
4 Evaluation expérimentale De même que [11], nous avons testé notre méthode sur
17 jeux de données du monde réel provenant des archives
4.1 Classification non supervisée avec les u- UCR [19] représentant un large éventail de domaines d’ap-
shapelets plication. Les ensembles de d’apprentissage et de test ont
été réunis pour obtenir des jeux de données plus impor-
Il existe de nombreuses façons de regrouper les séries tants. Le tableau 1 présente des informations détaillées sur
temporelles décrites par des u-shapelets. Dans cette expé- les ensembles de données testés.
rience, l’algorithme divise itérativement le jeu de données
à partir de chaque u-shapelet découvert : chaque u-shapelet Data-set Size of Length No. of Type
divise l’ensemble de données en deux groupes DA et DB . dataset Classes
50words 905 270 50 IMAGE
Les séries temporelles qui appartiennent à DA sont celles
Adiac 781 176 37 IMAGE
contenant le u-shapelet et sont ensuite supprimées du jeu
Beef 60 470 5 SPECTRO
de données. Une nouvelle recherche de u-shapelet se pour- Car 120 577 4 SENSOR
suit avec le reste des données jusqu’à ce qu’il n’y ait plus CBF 930 128 3 SIMULATED
de séries temporelles dans le jeu de données ou jusqu’à Coffee 56 286 2 SPECTRO
ce que l’algorithme ne soit plus capable de trouver d’u- ECG200 200 96 2 ECG
shapelet. En guise de critère d’arrêt, nous considérons la FaceFour 112 350 4 IMAGE
baisse du gap. L’algorithme s’arrête lorsque le gap de l’u- FISH 350 463 7 IMAGE
shapelet nouvellement trouvé devient la moitié du gap du Gun_Point 200 150 2 MOTION
premier u-shapelet découvert. Cette approche est une mise Lighting2 121 637 2 SENSOR
en oeuvre directe de la définition d’u-shapelet. Lighting7 143 319 7 SENSOR
OliveOil 60 570 4 SPECTRO
Choisir la longueur N des u-shapelet : Le choix de OSULeaf 442 427 6 IMAGE
la longueur de l’u-shapelet est guidé par la connaissance SwedishLeaf 1125 128 15 IMAGE
du domaine d’application duquel provient les séries tempo- synthetic_control 600 60 6 SIMULATED
FaceAll 2250 131 14 IMAGE
relles. Dans le cadre de ces expériences, nous avons testé
tous les nombres entre 4 et la moitié de la longueur des TABLE 1 – Jeux de données
séries temporelles. Nous considérons comme longueur de
l’u-shapelet celle permettant de mieux regrouper les séries
temporelles. Le tableau 2 présente une comparaison entre les deux algo-
rithmes.
Choisir la longueur w de la fenêtre : L’utilisation de
fenêtres qui se chevauchent pour le calcul de la matrice
5.2 Comparaison avec k-shape et USLM
d’auto-corrélation permet de capturer les oscillations pré- k-Shape et USLM sont deux algorithmes de clustering ba-
sentes dans la série temporelle. Au cours de ces expé- sés sur les u-shapelets pour les séries temporelles présen-
riences, nous considérons que la taille de la fenêtre est tées dans [10]. Dans cette section, nous comparons l’indice
égale à la moitié de la longueur de la forme en U. Rand index obtenu par FOTS-UShapelet et celui obtenu par
Datasets RI_SUSh RI_FOTS la matrice d’autocorrélation. Cette observation est illustrée
50words 0.811 0.877 par le résultat obtenu sur jeu de données SwedishLeaf.
Adiac 0.796 0.905
Analyse de la complexité en temps. ED peut être cal-
Beef 0.897 0.910
culé en O(n) et le score FOTS est calculé en O(nω ), ≤
Car 0.708 0.723
ω ≤ ω ≤≤ 3 en raison de la complexité temporelle des
CBF 0.578 0.909
décompositions des vecteurs propres [20]. Le calcul du
Coffee 0.782 0.896
score FOTS est alors plus coûteux que celui de ED. Ce-
ECG200 0.717 0.866
pendant, son utilisation reste pertinente pour la recherche
FaceFour 0.859 0.910
d’ u-shapelets, car ils sont souvent de petite taille.
FISH 0.775 0.899
Gun_Point 0.710 0.894 6 Conclusion et perspective
Lighting2 0.794 0.911
Lighting7 0.757 0.910 Le but de ce travail était de découvrir des u-shapelets
OliveOil 0.714 0.910 sur des séries temporelles incertaines. Pour répondre à
OSULeaf 0.847 0.905 cette question, nous avons proposé un score de dissimila-
SwedishLeaf 0.305 0.909 rité (FOTS) adapté à la comparaison de séries temporelles
synthetic_control 0.723 0.899 courtes, dont le calcul est basé sur la comparaison du vec-
FaceAll 0.907 0.908 teurs propres des matrices d’autocorrélation des séries tem-
porelles. Ce score est robuste à la présence d’incertitude, il
TABLE 2 – Comparison du Rand Index de SUSH (RI_SUSh) et n’est pas très sensible aux changements transitoires, et il
de FOTS-SUSh (RI_FOTS). Le meilleur Rand Index est en gras permet de capturer des relations complexes entre des sé-
ries temporelles telles que les oscillations et les tendances.
Le score FOTS a été utilisé avec l’algorithme Scalable Un-
k-Shape et USLM sur 5 jeux de données 1 (Tableau 3). Les supervised Shapelet Discovery pour la classification non
résultats de k-Shape et USLM ont été précédemment rap- supervisée de 17 jeux de données de la littérature et a mon-
portés dans [10]. Cette comparaison montre qu’en général, tré une amélioration de la qualité du regroupement évalué
FOTS-UShapelet donne de meilleurs résultats que k-Shape à l’aide de l’indice Rand. En combinant les avantages de
et USLM. l’algorithme des u-shapelets, qui réduit les effets néfastes
de l’incertitude, et les avantages du score FOTS, qui est
TABLE 3 – Comparison entre k-Shape, USLM et FOTS-
robuste à la présence de l’incertitude, ce travail définit un
UShapelet
cadre original pour la classification non supervisée de sé-
Rand ries temporelles incertaines. Dans la perspective de ce tra-
k-Shape USLM FOTS-UShapelet vail, nous prévoyons d’utiliser le score FOTS pour la clas-
Index
CBF 0.74 1 0.909 sification non supervisée floue de séries temporelles incer-
ECG200 0.70 0.76 0.866 taines.
Fac.F. 0.64 0.79 0.910
Lig2 0.65 0.80 0.911 Remerciements
Lig.7 0.74 0.79 0.910 Nous remercions cordialement le Ministère Français de
OSU L. 0.66 0.82 0.905 l’enseignement supérieur et de la recherche qui a financé
ce travail et nous remercions les reviewers pour leurs com-
mentaires et leurs suggestions qui ont aidé à améliorer la
5.3 Discussion qualité de ce travail.
L’utilisation du score FOTS associé à l’algorithme de SU-
Shapelet fait qu’il est possible de découvrir d’autres u-
Références
shapelets que ceux trouvés par la distance Euclidienne. [1] G. B. Folland and A. Sitaram, “The uncertainty prin-
Le FOTS-SUSh améliore les résultats de la classification ciple : a mathematical survey,” Journal of Fourier
des séries temporelles parce que le score FOTS prend en analysis and applications, vol. 3, no. 3, pp. 207–238,
compte les propriétés intrinsèques de la série temporelle et 1997.
est robuste à la présence d’incertitude. Cette amélioration [2] N. B. Rizvandi, J. Taheri, R. Moraveji, and A. Y.
est particulièrement significative lorsque le score FOTS est Zomaya, “A study on using uncertain time series
utilisé pour la classification non supervisée de séries tem- matching algorithms for MapReduce applications,”
porelles contenant plusieurs petites oscillations. En effet, Concurrency and Computation : Practice and Expe-
ces oscillations ne sont pas capturées par la distance eucli- rience, vol. 25, no. 12, pp. 1699–1718, aug 2013.
dienne mais par le score FOTS dont le calcul est basé sur
[3] J. Hwang, Y. Kozawa, T. Amagasa, and H. Kita-
1. Nous considérons 5 jeux de données car se sont les jeux de données gawa, “GPU Acceleration of Similarity Search for
pour lesquels nous avons les résultats des algorithmes k-shape et USLM. Uncertain Time Series,” in 2014 17th International
Conference on Network-Based Information Systems. [16] J. Hoffmann-Jørgensen and G. Pisier, “The law of
IEEE, sep 2014, pp. 627–632. large numbers and the central limit theorem in ba-
[4] K. Rehfeld and J. Kurths, “Similarity estimators for nach spaces,” The Annals of Probability, pp. 587–
irregular and age-uncertain time series,” Climate of 599, 1976.
the Past, vol. 10, no. 1, pp. 107–122, 2014. [17] S. Papadimitriou, J. Sun, and S. Y. Philip, “Local
correlation tracking in time series,” in Data Mining,
[5] M. Orang and N. Shiri, “An experimental evaluation
2006. ICDM’06. Sixth International Conference on.
of similarity measures for uncertain time series,” in
IEEE, 2006, pp. 456–465.
Proceedings of the 18th International Database Engi-
neering & Applications Symposium on - IDEAS ’14. [18] R. Bhatia and T. Bhattacharyya, “A generalization of
New York, New York, USA : ACM Press, 2014, pp. the Hoffman-Wielandt theorem,” Linear Algebra and
261–264. its Applications, vol. 179, pp. 11–17, jan 1993.
[6] W. Wang, G. Liu, and D. Liu, “Chebyshev Simila- [19] Y. Chen, E. Keogh, B. Hu, N. Begum, A. Bagnall,
rity Match between Uncertain Time Series,” Mathe- A. Mueen, and G. Batista, “The ucr time series clas-
matical Problems in Engineering, vol. 2015, pp. 1– sification archive,” July 2015.
13, 2015. [20] V. Y. Pan and Z. Q. Chen, “The complexity of the
[7] M. Orang and N. Shiri, “Correlation analysis tech- matrix eigenproblem,” in Proceedings of the thirty-
niques for uncertain time series,” Knowledge and In- first annual ACM symposium on Theory of compu-
formation Systems, vol. 50, no. 1, pp. 79–116, jan ting. ACM, 1999, pp. 507–516.
2017.
[8] L. Ulanova, N. Begum, and E. Keogh, “Scalable clus-
tering of time series with u-shapelets,” in Proceedings
of the 2015 SIAM International Conference on Data
Mining. SIAM, 2015, pp. 900–908.
[9] J. Zakaria, A. Mueen, and E. Keogh, “Clustering time
series using unsupervised-shapelets,” in Data Mining
(ICDM), 2012 IEEE 12th International Conference
on. IEEE, 2012, pp. 785–794.
[10] Q. Zhang, J. Wu, H. Yang, Y. Tian, and C. Zhang,
“Unsupervised feature learning from time series.” in
IJCAI, 2016, pp. 2322–2328.
[11] M. Dallachiesa, B. Nushi, K. Mirylenka, and T. Pal-
panas, “Uncertain time-series similarity : return to the
basics,” Proceedings of the VLDB Endowment, vol. 5,
no. 11, pp. 1662–1673, 2012.
[12] M. Orang and N. Shiri, “Improving performance of
similarity measures for uncertain time series using
preprocessing techniques,” in Proceedings of the 27th
International Conference on Scientific and Statistical
Database Management - SSDBM ’15. New York,
New York, USA : ACM Press, 2015, pp. 1–12.
[13] K. Murthy and S. R. Sarangi, “Generalized notion of
similarities between uncertain time series,” Mar. 26
2013, uS Patent 8,407,221.
[14] J. Aßfalg, H.-P. Kriegel, P. Kröger, and M. Renz,
“Probabilistic similarity search for uncertain time se-
ries.” in SSDBM. Springer, 2009, pp. 435–443.
[15] M.-Y. Yeh, K.-L. Wu, P. S. Yu, and M.-S. Chen,
“Proud : a probabilistic approach to processing simi-
larity queries over uncertain data streams,” in Procee-
dings of the 12th International Conference on Exten-
ding Database Technology : Advances in Database
Technology. ACM, 2009, pp. 684–695.