Determinar locais através de um conjunto de pontos é uma tarefa de clusteringi. Aqui apresentam-
se duas maneiras diferentes que são as mais utilizadas para se determinar locais. Na secção 2.4.2.1, apresenta-se um método por partição e na secção 2.4.2.2 um método baseado em densi- dade.
2.4.2.1 Por partição
Ashbrook e Starner, em [AS03], usaram o conhecido algoritmo de clustering K-means para iden- tificar os locais importantes de um utilizador através do seu historial de locais. O K-means é um algoritmo iterativo de clustering bastante eficiente. Minimiza um termo de erro que consiste na soma dos quadrados das distâncias de cada ponto ao centro do seu grupo. Contudo, o algo- ritmo tem alguns aspectos negativos para agrupar os vários locais. Primeiro, o número de sítios tem de ser um parâmetro dado para o agrupamento, o que significa que este número tem de ser conhecido à partida. Segundo, todos os pontos são incluídos no resultado final dos grupos, o que torna este resultado muito sensível ao ruído. Um simples local que não seja importante longe dos outros pode puxar o centro de um grupo mais para perto dele do que aquilo que de- veria, pois o quadrado da distância do erro pesa bastante em pontos mais afastados. Terceiro e por último, este algoritmo não é determinístico. Ou seja, o resultado final depende da escolha inicial aleatória dos centros dos grupos.
O algoritmo X-means é uma evolução do K-means em que o número de grupos é descoberto de forma automática. No entanto, este continua a partilhar das restantes limitações do K-means. Detalhes sobre a implementação dos algoritmos K-means e X-means podem ser encontrados nas secções 2.5.2.1 e 2.5.2.2, respetivamente. Foram omitidas aqui as explicações para evitar repetições, uma vez que estes serão descritos mais à frente num contexto mais apropriado.
2.4.2.2 Baseada em densidade
A potencialidade dos algoritmos de clustering baseados em densidade torna-os bons candidatos para encontrar locais a partir dos pontos visitados. Zhou et al. [ZFL+04] desenharam o DJ-
Cluster para descobrir locais pessoais importantes, um algoritmo baseado em densidade que resolve muitas das limitações do K-means.
Figura 2.6: Grupo formado por algoritmo baseado em densidade. [ZFL+04]
iClusteringé uma técnica de Data Mining para fazer agrupamentos automáticos de dados segundo o seu grau
Primeiro, este permite descobrir grupos com formas arbitrarias, como demonstrado na fi- gura 2.6. Esta é uma melhoria significativa, uma vez que com o K-means todos os grupos são delimitados por um círculo, com um centro e um raio. Segundo, é menos sensível ao ruído, pontos muito afastados ou apenas pontos esporádicos têm menos probabilidade de participar no resultado final ou de afetar o restante resultado. Um utilizador pode, por exemplo, parar numa bomba de gasolina à qual nunca retorna ou parar em semáforos. Apropriadamente, estes acontecimentos geram poucos pontos que são descartados pois não preenchem o requisito de densidade. Terceiro, embora algoritmos baseados em densidade necessitem de alguns parâme- tros (E ps e MinPts) estes são bastante menos robustos que o número de locais. Por último, tem resultados determinísticos. Recebendo os mesmos dados de entrada e os mesmo parâmetros produzem sempre os mesmos grupos, ao contrário do K-means que depende da escolha inicial arbitrária dos centros dos grupos.
DBSCAN [EpKSX96, SEKX98] é representativo de um algoritmo baseado em densidade. Contudo, há evidência de que o DBSCAN é demasiado sensível aos parâmetros e que não ofe- rece nenhuma estratégia para trabalhar eficientemente com conjuntos de dados que não caibam na memória [ZFhLW02]. Devido a esses problema, o algoritmo DJ-Cluster foi desenvolvido [ZFL+04].
Algoritmo DJ-Cluster [ZBST07].
O algoritmo recebe um conjunto de pontos como entrada e para cada um calcula a sua vizinhança. A vizinhança de um ponto consiste nos pontos dentro de uma distância máxima representada por E ps, com a condição de que o número de pontos tem de ser no total, pelo menos, MinPts. Caso tal vizinhança não seja encontrada o ponto é marcado como ruído. Pelo contrário se for encontrado, os pontos fazem parte de um novo grupo. Se algum dos pontos já pertencer a outra localidade, estas são unificadas.
Figura 2.7: Agrupamento com base em densidade. (a) ilustra uma vizinhança N do ponto p; (b) ilustra que N(p) e N(q) são acopláveis por densidade; (c) ilustra o grupo final em cor vermelha. [ZBST07]
As definições que se seguem definem a vizinhança baseada em densidade de um ponto e a relação de junção por densidade.
2. TRABALHO RELACIONADO 2.4. Identificação e definição de locais
Vizinhança baseada na densidade de um ponto. A vizinhança N de um ponto p, denotada
por N(p), é definida pela equação (2.2),
N(p) = {q ∈ S|dist(p, q) <= E ps}, (2.2)
onde S é o conjunto de todos os pontos, q é qualquer ponto da amostra e E ps é o raio do círculo à volta de p que define a densidade. N(p) também necessita de satisfazer condição (2.3),
|N(p)| >= MinPts, (2.3)
onde MinPts é o número mínimo de pontos necessários numa vizinhança.
Junção por densidade. N(p)é densamente agrupável a N(q), denotado por J(N(p),N(q)), com
respeito a E ps e MinPts, se houver um ponto tal que ambos, N(p) e N(q), o contenham. A relação de junção por densidade é ilustrada na figura 2.7.
Algoritmo 2DJ-Cluster [ZBST07]
1: whilethere is at least one unprocessed point p in sample S do
2: Compute the density − based neighborhood N(p) with E ps and MinPts. 3: if N(p)is null then
4: Label p as noise. 5: else
6: if N(p)is density − joinable to an existing cluster then 7: Merge N(p) and all its density − joinable clusters.
8: else
9: Create a new cluster C based on N(p). 10: end if
11: end if 12: end while
O algoritmo DJ-Cluster é apresentado no Algoritmo 2. De notar que o algoritmo tem as seguintes propriedades:
• Todos os pontos fazem parte de algum grupo, ou então são ignorados e marcados como ruído;
• Existe sempre, pelo menos, um ponto em cada grupo;
• O algoritmo divide os dados de entrada em grupos não-hierárquicos; • Não existe sobreposição entre os grupos.
A complexidade computacional do algoritmo é de O(n2), mas pode ser melhorada usando
a indexação por R-Tree[Arg] para O(nlogn), sendo n o número de pontos contidos no conjunto de pontos dado como entrada do algoritmo.
Análises feitas com os parâmetros mostram que E ps deve ser um valor aproximado ao grau de precisão da posição a ser usada, sendo este cerca de 30 metros para dados do GPS, tal como explicado na secção 2.1.3.1. Diferentes escolhas para o parâmetro MinPts levam a resultados consideravelmente diferentes quanto ao número de locais importantes detetados [ZFL+04]. 2.4.3 Discussão
Os algoritmos para a deteção de locais apresentados na secção 2.4.1 não consideram a repetição dos mesmo locais. Cada vez que descobrem um local, assumem que é um novo local e não têm como o comparar com os já conhecidos.
Por outro lado, os algoritmos de clustering, abordados na secção 2.4.2, aplicados diretamente a todos os pontos dos ficheiros GPS, originam a perda de sítios importantes tais como a casa ou centros comerciais e em vez disso, algumas regiões como passadeiras em que um utiliza- dor passa bastantes vezes, mas não têm significado, são consideradas importantes (tal facto é ilustrado na figura 2.8).
Figura 2.8: Deteção de locais baseada em clustering. [LZX+08]
Assim um pré-processamento dos dados, como o de deteção de stay points explicado na secção 2.4.1.1, é importante para extrair alguns locais importantes dos dados e ignorar os que não interessam. Depois é utilizado um algoritmo de clustering por forma a agrupar os pontos pertencentes aos mesmos locais e assim definir os locais importantes. A computação do clus- teringé também mais pesada se não for previamente feita esta seleção dos dados, pois seriam um número consideravelmente maior de pontos para processar.
Foi escolhido o algoritmo de clustering baseado em densidade DJ-Cluster, para a tarefa de determinar os locais pelas vantagens já mencionadas. Este permite definir locais com forma arbitraria, é menos vulnerável ao ruído, não necessita do número de locais como parâmetro e é determinístico. Contudo, tem também ele um problema que é preciso ter em conta. O algo- ritmo depende demasiado da densidade, entenda-se frequência, e não dá importância ao tempo dispendido nos locais, duração. Por exemplo, se um utilizador ficar bastante tempo num local e nunca mais lá voltar, este não será considerado. Perdem-se assim locais que podem, também eles, ser importantes.
No caso do projeto Time Machine pretende-se que os locais sejam identificados como impor- tantes segundo estas duas varáveis: duração e frequência. Portanto a aproximação a este algo- ritmo terá de ter em conta que um local também pode ser importante mesmo que não tenha