- Python >= 3.4.*
Para rodar:
- python3 clustering.py --test
--test é um argumento opcional, para caso deseja ver alguma matriz de resultado --clean é um argumento opção que realiza a limpeza dos dados, tratando os atributos nominais.
Lembrar de instalar as bibliotecas necessárias (descritas no passo 3) como sudo (se não utilizar um ambiente virtual).
- Aline Laís Tavares
- Géssica Sodré
- João Paulo Araújo
Completo até o passo 4 do algoritmo. Falta fazer a partir do passo 5 (K-means)
A seguir, uma leve descrição do que é preciso ser feito para o projeto.
O conjunto de dados a ser estudado encontra-se em: https://archive.ics.uci.edu/ml/datasets/Flags Basicamente, são dados com informações de todas as bandeiras nacionais de cada país existente. Atributos incluem cores das bandeiras, língua do país, continente, etc. São 30 atributos no total e 194 instâncias (bandeiras).
-
Procurar dados em formato inconsistente e: (a) removê-los ou (b) prever seus reais valores pela média de todos os outros. No caso dos nosso conjunto de dados, não foram detectados dados inconsistentes.
-
Verificar se conjunto de dados possuem atributos nominais e tratá-los. No caso deste conjunto de dados, os atributos de cores predominantes e cores nos cantos esquerda-superior e direita-inferior foram convertidos em valores, representados por um identificador, como descrito na tabela a seguir:
| Cor | id |
|---|---|
| green | 0 |
| black | 1 |
| red | 2 |
| white | 3 |
| blue | 4 |
| gold | 5 |
| orange | 6 |
| brown | 7 |
Dado um conjunto de pontos (os n atributos para cada bandeira) , é preciso realizar os seguintes passos: [1]
-
Formar a matriz de afinidade
definido por:
Lembrando que deve se escolher o melhor valor de
, além de definir a distância [2] euclidiana para dois atributos. No caso, temos:
-
Definir a matriz diagonal onde o
é a soma dos valores de A na i-ésima linha. E com isso, construir a matriz
-
Achar
, maiores k autovetores de L (escolhidos para serem ortogonal um ao outro no caso de autovalores repetidos) e formar a matrix
através do empilhamento dos autovetores em colunas.
Achar autovetores e autovalores: https://stackoverflow.com/questions/6684238/whats-the-fastest-way-to-find-eigenvalues-vectors-in-python
Para usar a biblioteca SciPy, NumPy e plot gráfico, instalar as seguintes bibliotecas:
pip3 install --user numpy scipy matplotlib ipython jupyter pandas sympy nose sklearn
sudo apt-get install python3-tk-
Formar a matriz Y a partir de X através da renormalização de cada linha de X para ter uma unidade de largura( ex:
).
-
Tratar cada linha de Y como um ponto em
, agrupando-os em k grupos através do K-means ou outro algorítmo (na tentativa de minimizar distorções). Ou seja, escolher a quantidade de clusters k e aplicar algum algorítmo de K-means, da forma que se consiga obter dados satisfatórios. Comece por algum tamanho k=2 e pode ir aumentando até obter osmelhores grupos possíveis.
Possível algorítmo de K-means que pode ser utilizado: http://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html
- Finalmente, atribuir aos pontos originais
ao grupo j se e somente se a linha i da matriz Y foi atribuida ao grupo j. Em outras palavras, após realizar o K-means, associar um nome/significado a cada ponto de forma que estes representem os nomes das flags inicialmente sendo utilizadas. Por exemplo, se a linha Y[0] da matriz Y estiver em um cluster qualquer representada por um ponto, esse ponto especifico é o ponto Afghanistan.
[1] Ng, A., Jordan, M., Weiss, Y.: On Spectral Clustering: Analysis and an algorithm. In: Dietterich, T., Becker, S., Ghahramani, Z. (eds.) Advances in Neural Information Processing Systems 14, pp. 849–856. MIT Press, Cambridge (2002).
[2] Euclidean distance, 24 May 2017. In Wikipedia: The Free Encyclopedia. Wikimedia Foundation Inc. Encyclopedia on-line. Available from https://en.wikipedia.org/wiki/Euclidean_distance#n_dimensions. Retrieved at 21 June 2014.