Zaimplementuj procedurę MCL (Markov Chain Clustering) dla zadanej macierzy kwadratowej.
Program powinien być w postaci skryptu, który będzie pozwalał podać nazwę pliku i sposób reprezentacji macierzy M (tekstowy, binarny, macierz rzadka w pliku .mat) oraz parametry r, N i epsilon). Następnie powinien wykonywać iterację wg następującego planu:
- dopóki i<N oraz |M(i)-M(i+2)|>epsilon:
- M(i+1) = M(i)*M(i) #mnożenie macierzy
- M(i+2)= Inflate(M(i+1),r)
gdzie funkcja inflate wykonuje operację M[i,j]=M[i,j]**r (po elementach), a następnie normuje kolumny do 1.
Skrypt powinien wypisywać macierz w wybranym formacie (rzadkim, binarnym lub tekstowym) oraz na życzenie wykreślać wykres |M(i+2)-M(i)| względem i.
Warto dodać do programu funkcję, która zwraca spójne składowe grafu opisanego taką macierzą, czyli listy wierzchołków, pomiędzy którymi pozostają połączenia o niezerowej wadze.
Termin oddania prac – 30. maja, prace wysyłamy e-mailem do prowadzącego z dopiskiem ONA-2-2016 w tytule, w postaci pojedyńczego pliku pythona jako załącznik.
Przykładowe dane – macierz podobieństwa szczepów konopii (na podst. pracy Hakki et al, Electronic Journal of Biotechnology, Vol 10, No 4 (2007)) : cannabis4.npy, Dla tych danych sensownymi wartościami parametrów są N=20, epsilon = 0.5, r=1.1
Co dokładnie oznacza notacja |M(i)-M(i+2)|?
Jest to norma (np.suma wartości bezwględnych) macierzy będącej różnicą macierzy M(i) i M(i+2).
Czy gdy wczytujemy macierz rzadką to możemy zamienić ją na właściwą i na tej zamienionej macierzy wykonywać algorytm ?
Zasadniczo idea była taka, aby obliczenia mogły odbywać się bez konwersji na macierz “pełną”. Ze rozwiązania z “rozwinięciem” macierzy będę pewnie obcinał ~2 pkty.
A czy macierz rzadka która będzie wczytywana to bedzie .sparse.csr_matrix czy sparse.csc_matrix ?
To jest do wyboru. Jak Państwu wygodnie.