An u-shapelet is a sub-sequence of a time series used for clustering a time series dataset. The purpose of this paper is to discover u-shapelets on uncertain time series. To achieve this goal, we propose a dissimilarity score called FOTS whose computation is based on the eigenvector decomposition and the comparison of the autocorrelation matrices of the time series. This score is robust to the presence of uncertainty ; it is not very sensitive to transient changes ; it allows capturing complex relationships between time series such as oscillations and trends, and it is also well adapted to the comparison of short time series. The FOTS score is used with the Scalable Unsupervised Shapelet Discovery algorithm for the clustering of 17 datasets, and it has shown a substantial improvement in the quality of the clustering with respect to the Rand Index. This work defines a novel framework for the clustering of uncertain time series.
Un u-shapelet est une sous-séquence d’une série temporelle utilisée comme propriété pour séparer un groupe de séries temporelles en deux sous-groupes. Un sous-groupe de séries temporelles contenant le shapelet et un sousgroupe de série temporelles ne contenant pas le shapelet. Le but de cet article est de découvrir des u-shapelets sur des séries temporelles incertaines. Pour atteindre cet objectif, nous proposons un score de dissimilarité appelé FOTS dont le calcul est basé sur la comparaison des vecteurs propres des matrices d’autocorrélation des séries temporelles. Ce score est robuste à la présence d’incertitude ; il n’est pas très sensible aux changements transitoires ; il permet de capturer des relations complexes entre des séries temporelles telles que les oscillations et les tendances, et il est également bien adapté à la comparaison de séries temporelles courtes. Le score FOTS est utilisé avec l’algorithme Scalable Unsupervised Shapelet Discovery pour la classification non supervisée de 17 ensembles de données, et il a montré une amélioration substantielle de la qualité de la classification non supervisée par rapport au Rand Index. Ce travail définit un nouveau cadre pour la classification non supervisée de séries temporelles incertaines.
1
Toutes les mesures effectuées par un système mécanique
ont une incertitude. En effet, le principe d’incertitude met
en évidence les limites de la capacité des systèmes
mécaniques à effectuer des mesures sur un système sans les
perturber [1]. Ainsi, les séries temporelles des instruments de
mesure sont incertaines. Ces séries temporelles produites
par des capteurs constituent une vaste proportion des
séries temporelles utilisées en science, que ce soit en
médecine avec des Électrocardiogramme (enregistrement de
l’activité électrique du coeur), en physique avec des
mesures enregistrées par des télescopes, en informatique avec
l’Internet des objets, etc. Ignorer l’incertitude des données
au cours de leur analyse peut conduire à des conclusions
approximatives ou inexactes, d’où la nécessité de mettre en
oeuvre des techniques de gestion des données incertaines.
Plusieurs études récentes ont porté sur le traitement de
l’incertitude dans l’exploration de données. Deux approches
principales permettent de prendre en compte l’incertitude
dans les tâches de data mining : soit elle est prise en compte
lors de la comparaison en utilisant les fonctions de distance
appropriées [
État de l’art sur les u-shapelets Considérons un ensemble de données composé de 6 séries temporelles correspondant aux appels d’oiseaux : 3 séries temporelles correspondant à Moucherolle à côtés olive (séries temporelles vertes) et 3 séries temporelles correspondant aux appels de Moineau à couronne blanche (séries temporelles bleues). Lorsque ces séries temporelles sont classées en utilisant la distance euclidienne comme mesure de dissimilarité (Fig. 1 gauche), les groupes obtenus ne sont pas homogènes ; en d’autres termes, l’algorithme n’identifie pas l’oiseau à partir de ses cris. Cependant, si nous recherchons des sous-séquences caractéristiques (ushapelets) pour classer les séries temporelles, nous obtenons des groupes plus homogènes (Fig. 1 à droite). Une fois cette observation faite, la question naturelle est de savoir comment trouver des sous-séquences qui caractérisent un groupe de séries temporelles, c’est-à-dire des sous-séquences qui ne sont observées que dans un sousgroupe de séries temporelles. L’algorithme de découverte d’u-shapelet répond à cette question et procède comme suit : l’algorithme prend la longueur du motif comme paramètre. Sur chaque série temporelle de la base, on fait glisser une fenêtre de la même longueur que le motif, chaque nouvelle sous-séquence obtenue par ce processus est un ushapelet candidat.
Parmi les u-shapelets candidats, nous considérons comme un u-shapelet la sous-séquence capable de diviser l’ensemble de séries temporelles en deux sous-ensembles DA et DB de sorte que DA contient toutes les séries temporelles qui possèdent le u-shapelet et DB toutes celles qui ne contiennent pas l’u-shapelet. Deux autres contraintes sont prises en compte dans la découverte de motifs : La première est la capacité de l’u-shapelet à construire des sous-ensembles bien séparés. La deuxième est la capacité de l’u-shapelet à construire des sous-ensembles qui ne sont pas déséquilibrés. C’est-à-dire que la taille de DA doit être au plus k fois plus grande que celle de DB et vice versa. Definition 1 Deux jeux de données DA et DB sont dit réquilibré si et seulement si 1r < jjDDBAjj < (1 1r ); r > 1 Definition 2 Un u-shapelet est une sous-séquence qui a une longueur inférieur ou égale à la longueur de la plus petite série temporelle du jeu de données, et qui permet de diviser le jeux de données en deux sous-groupes r-équilibrées DA et DB ; où DA est le groupe de séries temporelles qui contiennent un motif similaire au u-shapelet et DB est le groupe de séries temporelles qui ne contiennent pas l’ushapelet.
La similarité entre une série temporelle et un u-shapelet est évaluée à l’aide d’une fonction de distance.
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
à utiliser pour sdist. En général, la distance euclidienne
omniprésente (ED) est utilisée, mais elle ne l’est pas
appropriée pour les séries temporelles incertaines [
Le calcul de la sdist entre un u-shapelet candidat et toutes les séries temporelles d’un jeux de données est appelé orderline.
Definition 4 Un orderline est un vecteur de distance entre un u-shapelet et toutes les séries temporelles d’un jeu de données.
Le calcul d’un orderline est coûteux en temps. Un orderline
pour un seul u-shapelet candidat a une complexité en temps
égale à O(N M log(M )) où N est le nombre de séries
temporelles du jeux de données, M est la longueur moyenne
des séries temporelles. L’algorithme force brute pour la
découverte de u-shapelet requiert K calculs d’orderline, où
K est le nombre de sous-séquences candidate. La stratégie
utilisée par [
L’évaluation de la qualité des u-shapelets est basée sur leur pouvoir de séparation qui est calculé comme suit : gap =
B
B ( A
A); (1) Où A (resp. B) représente la moyenne(sdist(S, DA)) (resp. moyenne(sdist(S, DB))), et A (resp. B) représente l’écart-type de sdist(S; DA) (resp. écart-type de sdist(S; DB)).
Si DA ou DB est constitué d’un seul élément (ou d’un nombre insuffisant de séries temporelles pour constituer un groupe), le gap prend la valeur zéro. Ceci assure qu’un gap élevé pour un u-shapelet correspond à une séparation réelle. 1.2
La classification non supervisée basée sur des u-shapelets
est une approche introduite par [
La classification non supervisée de séries temporelles avec
des u-shapelets présente plusieurs avantages.
Premièrement, la classification non supervisée basée sur les
ushapelets est définie pour les ensembles de données dans
lesquels les séries temporelles ont des longueurs
différentes, ce qui n’est pas le cas pour la plupart des
techniques décrites dans la littérature. En effet, dans de
nombreux cas, l’hypothèse de longueur égale est implicite, et
le découpage à longueur égale est effectué en exploitant
des compétences humaines coûteuses [
De plus, il est très approprié d’utiliser la classification non supervisée basée sur les u-shapelets avec des séries temporelles incertaines parce que la stratégie de comparaison d’un u-shapelet et d’une série temporelle ignore les données non pertinentes de la série temporelle et ainsi réduire les effets négatifs de la présence d’incertitudes dans celleci. Malgré cet avantage, il est hautement souhaitable de prendre en compte l’impact négatif de l’incertitude lors de la découverte des u-shapelets. 1.3
Les mesures traditionnelles de similarité comme la distance euclidienne (ED) ou la distorsion temporelle dynamique (DTW) ne fonctionnent pas toujours bien pour les séries temporelles incertaines. En effet, ces distances agrègent l’incertitude de chaque point de la série temporelle et amplifient ainsi l’impact négatif de l’incertitude. Cependant, ED joue un rôle fondamental dans la découverte des u-shapelets, car elle est utilisée pour calculer l’écart entre deux groupes formé par l’u-shapelet candidat. La découverte de u-shapelet sur des séries temporelles incertaines pourrait donc conduire à la sélection d’un mauvais candidat u-shapelet ou à l’assignation d’une série temporelle au mauvais groupe.
Dans cette étude, notre but n’est pas de définir un algorithme pour la découverte d’u-shapelets incertains, mais plutôt d’utiliser une fonction de dissimilarité robuste à l’incertitude pour améliorer la qualité des u-shapelets découverts et donc la qualité de clustering des séries temporelles incertaines. 1.4
Contributions — Nous faisons un état de l’art sur les mesures de dissimilarité incertaines et nous les évaluation leur pertinence pour la comparaison de séries temporelles incertaines de petite taille. — Nous introduisons une fonction de dissimilarité nommée correlation frobenius pour découverte d’ushapelets sur les séries temporelles incertaines (FOTS) ;qui posséde des propriétés intéressantes pour la comparaison de séries temporelles incertaines de petite taille et ne fait aucune hypothèse sur la distribution de probabilité de l’incertitude. — Nous mettons le code source à la disposition de la communauté scientifique pour permettre une extension de ce travail.
Une série temporelle incertaine (UTS) X =< X1; : : : ; Xn > est une séquence de variable aléatoire où Xi est une variable aléatoire modélisant une valeur réelle inconnue à l’instant i. Deux modèles sont principalement utilisés pour représenter les séries temporelles incertaines : le modèle ensembliste, et le modèle basé sur la fonction de densité de probabilité de l’incertitude.
Dans le modèle ensembliste, chaque élément Xi(1 i n) de l’UTS X =< X1; : : : ; Xn > est représenté par un ensemble fXi;1; : : : ; Xi;Ni g de valeurs observées et Ni représente le nombre d’observation à l’instant i.
Dans le modèle basé sur la distribution de probabilité, chaque élément Xi; (1 i n) de l’UTS X =< X1; : : : ; Xn > est représenté par une variable aléatoire Xi = xi + Xei , où xi est la valeur exacte qui est inconnue, et Xei est une variable aléatoire représentant l’erreur. C’est ce modèle que nous considérons tout au long de notre travail.
Plusieurs mesures de similarité ont été proposées pour les
séries temporelles incertaines. Elles peuvent être
regroupées en deux catégories principales : les mesures de
similarité traditionnelles et les mesures de similarité incertaines.
— les mesures de similarité traditionnelles telle que
la distance euclidienne sont celles
conventionnellement utilisées avec les séries temporelles. Elles
utilisent une seul valeur incertaine à chaque instant
comme approximation de la valeur réelle inconnue.
— les mesures de similarité incertaines utilisent des
informations statistiques additionnelles qui
mesurent l’incertitude associée à chaque
approximation de la valeur réelle. C’est le cas notamment de
DUST, PROUD, MUNICH [
sures de similarité traditionnelles, les mesures de similarité
déterministes renvoient un nombre réel représentant la
distance entre deux séries temporelles incertaines. DUST est
un exemple de mesure déterministe de similarité.
DUST [
'(jXi
Yij) = P r(dist(0; jXi
Yij) = 0): (2) cette fonction de similarité est par la suite utilisée par la fonction de dissimilarité dust : dust(Xi; Yi) = p log('(jXi
Yij)) + log('(0)): (3) La distance entre les séries temporelles incertaines X =< X1; : : : ; Xn > et Y =< Y1; : : : ; Yn > calculée à partir de DU ST est alors définie comme suit :
vu n DU ST (X; Y ) = tuX dust(Xi; Yi)2 : i=1 (4) Le problème avec les distances déterministes incertaines comme DU ST est que leur expression varie en fonction de la distribution de probabilité de l’incertitude, et la distribution de probabilité de l’incertitude n’est pas toujours disponible pour les jeux de données de séries temporelles.
milarités probabilistes n’exigent pas la connaissance de la distribution des probabilités d’incertitude. De plus, elles fournissent aux utilisateurs plus d’informations sur la fiabilité du résultat. Il existe plusieurs fonctions de similarité probabiliste, comme MUNICH, PROUD, PROUDS ou Corrélation Locale.
MUNICH [
PROUD [
Yi)2]; XV ar[(Xi i Une conséquence de cette caractéristique de la distance 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 :
P r(d(X; Y )norm ): (7) Un inconvénient majeur de PROUD est son inadéquation pour la comparaison de séries temporelles de petites longueurs comme les u-shapelets. En effet, le calcul de la probabilité que la distance PROUD soit inférieure à une valeur est basé sur l’hypothèse qu’elle suit asymptotiquement une distribution normale. Ainsi, cette probabilité sera d’autant plus précise que les séries temporelles comparées sont longues (plus de 30 points de données).
PROUDS [
Definition 5 La forme normalisée d’une série temporelle X =< X1; : : : ; Xn > est définie par X^ =< X^1; : : : ; X^n > tel que à chaque instant i (1 i n), nous avons : X^i =
Xi
SX
X ; X =Xn i=1
vu n Xi ; SX = tuX (Xi n (n i=1
X)2 1) : (8) PROUDS définit la distance entre deux séries temporelles normalisées X^ =< X^1:::X^n > and Y^ =< Y^1:::Y^n > (Définition 5) comme suit :
Eucl(X^ ; Y^ ) = 2(n n 1) + 2 X
X^iY^i i=1 (9) Pour les mêmes raisons que PROUD, PROUDS ne conviennent pas à la comparaison de séries temporelles courtes. Un autre inconvénient de PROUDS est qu’il suppose que les variables aléatoires sont indépendantes : cette hypothèse est forte et particulièrement inappropriée pour des séries temporelles courtes comme les u-shapelets. Une hypothèse plus réaliste avec les séries temporelles serait de considérer que les variables aléatoires constituant les séries temporelles sont M-dépendantes. Les variables aléatoires d’une série temporelle sont dites M-dépendantes si Xi; Xi+1; :::; Xi+M sont dépendantes (corrélées) et les variables Xi et Xi+M+1 sont indépendantes. Cependant, supposer que les variables aléatoires sont M-dépendantes complexifie l’écriture de PROUDS et rend son utilisation plus difficile car elle requiert dès lors d’affecter une valeur au paramètre M.
Corrélation incertaine [
X^iY^i=(n
1); i=1 (10) Où X^i et Y^i sont les formes normales de Xi et Yi (Définition 5) respectivement. Xi et Yi sont des variables aléatoires indépendantes et continues.
Si nous connaissons la distribution de probabilité des variables aléatoires, il est possible de déterminer la fonction de densité de probabilité associée à la corrélation, qui servira par la suite à calculer la probabilité que la corrélation entre deux séries temporelles soit supérieure à un seuil donné. La corrélation incertaine a cependant quelques inconvénients : — 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 les séries temporelles ; — Il faut connaître la fonction de distribution de probabilité de l’incertitude ou faire une hypothèse sur l’indépendance des variables aléatoires contenues dans les séries temporelles.
En raison de tous ces inconvénients, la corrélation incertaine ne peut pas être utilisée en l’état pour la découverte d’u-shapelet. Le paragraphe suivant présente une généralisation du coefficient de corrélation qui n’est pas une fonction de similarité incertaine mais qui reste intéressante pour la découverte des u-shapelets.
Corrélation locale [
Definition 7 (Auto-covariance, fenêtre glissante) Étant donnée une série temporelle X, un ensemble de fenêtre glissante w, l’estimateur de la matrice d’autocorrelation locale ^t utilisant une fenêtre glissante est définie à l’instant t 2 N tel que (Eq.11) :
t
X =t m+1 ^t(X; w; m) = x ;w x ;w: (11) Où x ;! est une sous-séquence de la série temporelle de longueur w et commençant à , x y = xyT est le produit 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 nombre de fenêtres à m = w. Étant donnée les estimations ^t(X) et ^t(Y ) pour les deux séries temporelles, la prochaine étape est de savoir comment les comparer et extraire un score de corrélation. Cet objectif est atteint en utilisant la décomposition spectrale ; les vecteurs propres des matrices d’auto-corrélations capturent les principales tendances apériodiques et oscillatoires, même sur des séries temporelles courtes. Ainsi, les sous-espaces couverts par les premiers (k) vecteurs propres sont utilisés pour caractériser localement le comportement de chaque série. La définition 8 formalise cette notion : Definition 8 (LoCo score) Étant donnée deux séries temporelles X et Y leur score LoCo est défini par
1 `t(X; Y ) = 2 (kU TX uY k + kU YT uX k) (12) Où U X et U Y sont les k premiers vecteurs propres des matrices d’auto-corrélation locales ^t(X) et ^t(Y ) respectivement, et uX et uY sont les vecteurs propres ayant la plus large valeur propre.
Intuitivement, deux séries temporelles X et Y seront considérées comme étant proches lorsque l’angle formé par l’espace portant les informations de la série temporelle X et de la série temporelle Y est nul. En d’autres termes, X et Y seront proches lorsque la valeur de cos( ) sera 1. La seule l’hypothèse faite pour le calcul de la similitude LoCo est que la moyenne des points de la série temporelle est nulle. Cette hypothèse peut facilement être vérifiée, il suffit pour cela de normaliser les séries temporelles en cours de comparaison. La fonction de similarité LoCo a de nombreuses propriétés intéressantes et ne nécessite pas : — de connaître la distribution de probabilité de l’incertitude, — de supposer l’indépendance des variables aléatoires ou de faire une hypothèse sur la longueur de l’ushapelet.
Elle est donc intéressante pour la découverte de motifs, mais nous avons encore besoin d’une dissimilarité pour pouvoir découvrir des u-shapelets. Dans le paragraphe suivant, nous allons définir une fonction de dissimilarité qui a les mêmes propriétés que LoCo et c’est-à-dire, qui est robuste à la présence d’incertitude. 3 3.1
La fonction de similarité LoCo définie sur deux séries temporelles multivariées X et Y correspond approximativement à la valeur absolue du cosinus de l’angle formé par les espaces propres de X et Y (jcos( )j). Une idée simple serait d’utiliser la valeur sin( ) ou comme fonction de dissimilarité mais cette approche ne fonctionne pas si bien ; le sinus et l’angle ne sont pas assez discriminants pour la comparaison de vecteurs propres à des fins de clustering. Nous proposons donc la mesure de dissimilarité suivante (Définition. 9).
Definition 9 (FOTS : Frobenius cOrrelation for uncertain Time series u-Shapelet discovery) Étant données deux séries X et Y , leur score FOTS est défini par vu m k UY kF = tuXX (UX i=1 j=1 F OT S(X; Y ) = kUX où kkF est la norme de Frobenius, m est la longueur de la série temporelle et k est le nombre de vecteurs propres. Comme le calcul FOTS est basé sur la comparaison des k-premiers vecteurs propres des matrices d’autocorrélation de la série temporelle, il a les mêmes propriétés souhaitables de la fonction de similarité LoCo, c’est-à-dire : — 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 hausse ou à la baisse) qui sont présentes ; — Il permet de réduire la sensibilité aux changements transitoires dans les séries temporelles ; — Il est approprié pour le comparison de séries temporelles courtes.
De plus, la fonction de dissimilarité FOTS est robust à
la présence d’incertitude due à la décomposition
spectrale des matrices d’autocorrélation des séries temporelles.
La robustesse du FOTS à l’incertitude est confirmée par le
théorème suivant :
Théorème 1 (HoffmanWielandt) [
Dans cette section, nous ne définissons pas un nouvel algorithme SUShapelet, mais nous expliquons comment nous utilisons l’algorithme SUShapelet avec le score FOTS (FOTS-SUSh) pour faire face à l’incertitude.
Le gap est un critère essentiel pour la sélection des ushapelets. Il est sujet à l’incertitude parce que son calcul est basé sur la distance euclidienne. Pour y remédier, nous proposons d’utiliser le score de FOTS au lieu d’une simple distance euclidienne lors du calcul du gap. L’algorithme 1 explique comment calculer l’orderline en utilisant le score de FOTS. L’algorithme 2 calcul l’orderline et trie les série temporelles en fonction de leur proximité au u-shapelet candidat (ligne 2 et 3). Un u-shapelet est considéré comme étant présent dans une série temporelle si sa distance à la série temporelle est inférieure ou égale à un seuil. Ainsi, l’algorithme de sélection de seuil construit un cluster DA UY )i2j (13) dont la taille varie entre lb et ub (ligne 5). L’algorithme cherche alors parmi les seuils sélectionnés celui ayant un gap maximal (ligne 6 et 11).
Definition 10 La fonction de dissimilarité sdf (S; T ) entre une série temporelle T et une sous-séquence S est le minimum des valeurs du score de FOTS entre la sousséquence S et toutes les sous-séquences possible de T de longueur égales à S.
Algorithme 1 : ComputeOrderline Input : u-shapeletCandidate : s, Jeu de données : D Output : Distance entre l’u-shapelet candidat et toutes
les séries temporelles du jeu de données 1 function ComputeOrderline(s; D) 2 dis fg s zN orm(s) 3 forall i 2 f1; 2; : : : ; jDjg do 4 ts D(i; :) 5 dis(i) sdf (s; ts) 6 return dis=jsj
Input : u-shapeletCandidate : s, Jeu de données : D, lb, ub : lower/upper bound : nombre minimum et maximum de séries temporelles par groupe Output : gap : distance entre deux groupes 1 function ComputeGap(s; D; lb; ub) 2 dis ComputeOrderline(s; D) 3 dis sort(dis) gap 0 4 for i lb to ub do 5 DA dis dis(i), DB 6 mA mean(DA), mB 7 sA std(DA), sB 8 currGap mB sB 9 if currGap > gap then 10 gap currGap dis > dis(i) mean(DB) std(DB) (mA + sA) 11
return gap 4 4.1
Il existe de nombreuses façons de regrouper les séries temporelles décrites par des u-shapelets. Dans cette expérience, l’algorithme divise itérativement le jeu de données à partir de chaque u-shapelet découvert : chaque u-shapelet divise l’ensemble de données en deux groupes DA et DB. Les séries temporelles qui appartiennent à DA sont celles contenant le u-shapelet et sont ensuite supprimées du jeu de données. Une nouvelle recherche de u-shapelet se poursuit avec le reste des données jusqu’à ce qu’il n’y ait plus de séries temporelles dans le jeu de données ou jusqu’à ce que l’algorithme ne soit plus capable de trouver d’ushapelet. En guise de critère d’arrêt, nous considérons la baisse du gap. L’algorithme s’arrête lorsque le gap de l’ushapelet nouvellement trouvé devient la moitié du gap du premier u-shapelet découvert. Cette approche est une mise en oeuvre directe de la définition d’u-shapelet.
Choisir la longueur N des u-shapelet : Le choix de la longueur de l’u-shapelet est guidé par la connaissance du domaine d’application duquel provient les séries temporelles. Dans le cadre de ces expériences, nous avons testé tous les nombres entre 4 et la moitié de la longueur des séries temporelles. Nous considérons comme longueur de l’u-shapelet celle permettant de mieux regrouper les séries temporelles.
fenêtres qui se chevauchent pour le calcul de la matrice d’auto-corrélation permet de capturer les oscillations présentes dans la série temporelle. Au cours de ces expériences, nous considérons que la taille de la fenêtre est égale à la moitié de la longueur de la forme en U. Choisir le nombre k de vecteurs propres : Un choix pratique est de fixer k à une petite valeur ; nous utilisons k = 4 tout au long de ces expériences. En effet, les tendances apériodiques clés sont capturées par un seul vecteurs propres, tandis que les principales tendances oscillatoires se manifestent dans une paire de vecteurs propres. 5
Différentes mesures de la qualité de classification non
supervisée de séries temporelles ont été proposées,
notamment le score Jaccard, l’indice Rand, l’indice Folkes et
l’indice Mallow, etc. Cependant, dans notre cas, nous avons
des étiquettes de classe pour les jeux de données, nous
pouvons donc utiliser cette information externe pour
évaluer la véritable qualité de la classification non supervisée
en utilisant l’indice Rand. De plus, l’indice Rand semble
être la mesure de la qualité des groupes couramment
utilisée [
De même que [
Data-set
50words
Adiac
Beef
Car
CBF
Coffee
ECG200
FaceFour
FISH
Gun_Point
Lighting2
Lighting7
OliveOil
OSULeaf
SwedishLeaf
synthetic_control
FaceAll
k-Shape et USLM sont deux algorithmes de clustering
basés sur les u-shapelets pour les séries temporelles
présentées dans [
TABLE 3 – Comparison entre k-Shape, USLM et FOTSUShapelet k-Shape
USLM
FOTS-UShapelet 5.3
L’utilisation du score FOTS associé à l’algorithme de
SUShapelet fait qu’il est possible de découvrir d’autres
ushapelets que ceux trouvés par la distance Euclidienne.
Le FOTS-SUSh améliore les résultats de la classification
des séries temporelles parce que le score FOTS prend en
compte les propriétés intrinsèques de la série temporelle et
est robuste à la présence d’incertitude. Cette amélioration
est particulièrement significative lorsque le score FOTS est
utilisé pour la classification non supervisée de séries
temporelles contenant plusieurs petites oscillations. En effet,
ces oscillations ne sont pas capturées par la distance
euclidienne mais par le score FOTS dont le calcul est basé sur
1. Nous considérons 5 jeux de données car se sont les jeux de données
pour lesquels nous avons les résultats des algorithmes k-shape et USLM.
la matrice d’autocorrélation. Cette observation est illustrée
par le résultat obtenu sur jeu de données SwedishLeaf.
Analyse de la complexité en temps. ED peut être
calculé en O(n) et le score FOTS est calculé en O(n!);
! ! 3 en raison de la complexité temporelle des
décompositions des vecteurs propres [
Le but de ce travail était de découvrir des u-shapelets sur des séries temporelles incertaines. Pour répondre à cette question, nous avons proposé un score de dissimilarité (FOTS) adapté à la comparaison de séries temporelles courtes, dont le calcul est basé sur la comparaison du vecteurs propres des matrices d’autocorrélation des séries temporelles. Ce score est robuste à la présence d’incertitude, il n’est pas très sensible aux changements transitoires, et il 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 Unsupervised Shapelet Discovery pour la classification non supervisée de 17 jeux de données de la littérature et a montré une amélioration de la qualité du regroupement évalué à l’aide de l’indice Rand. En combinant les avantages de l’algorithme des u-shapelets, qui réduit les effets néfastes de l’incertitude, et les avantages du score FOTS, qui est robuste à la présence de l’incertitude, ce travail définit un cadre original pour la classification non supervisée de séries temporelles incertaines. Dans la perspective de ce travail, nous prévoyons d’utiliser le score FOTS pour la classification non supervisée floue de séries temporelles incertaines.
Nous remercions cordialement le Ministère Français de l’enseignement supérieur et de la recherche qui a financé ce travail et nous remercions les reviewers pour leurs commentaires et leurs suggestions qui ont aidé à améliorer la qualité de ce travail.
[1] G. B. Folland and A. Sitaram, “The uncertainty principle : a mathematical survey,” Journal of Fourier analysis and applications, vol. 3, no. 3, pp. 207–238, 1997. [2] N. B. Rizvandi, J. Taheri, R. Moraveji, and A. Y.
Zomaya, “A study on using uncertain time series matching algorithms for MapReduce applications,” Concurrency and Computation : Practice and Experience, vol. 25, no. 12, pp. 1699–1718, aug 2013. [3] J. Hwang, Y. Kozawa, T. Amagasa, and H. Kitagawa, “GPU Acceleration of Similarity Search for Uncertain Time Series,” in 2014 17th International