Powiedzmy, że przydałby się nam do jakichś celów plik z liczbami losowymi. Np. chcemy 1000 liczb bez powtórzeń z przedziału 0 do 10^7:
s<-sample(1:10^7,10^3,replace=F)
Jak zapisać teraz otrzymane liczby do pliku?
write.table(s,file="liczby_losowe.txt", sep=" ",row.names=F, col.names=F)
Dzięki użyciu row.names i col.names F(ALSE) dostajemy do pliku czyste liczby, bez etykiet dla kolumn i wierszy.
d<-read.csv("http://users.pjwstk.edu.pl/~s8361/r/dane/tsp-berlin52.txt", header=FALSE, sep="")
head(d)
tail(d)
Mamy 3 kolumny o nazwach V1,V2,V3. Aby usunąć pojedynczą np. V2 wystarczy:
d[,-2]
należy podać z minusem indeks kolumny (indeksowanie „tradycyjnie” w R od 1). Oczywiście jeśli chcemy zmienić pierwotną postać d musimy zrobić przypisanie:
d<-d[,-2]
A co jeśli chcemy usunąć kilka kolumn, w dodatku nie sąsiadujących ze sobą? Wygodnym sposobem jest skorzystanie z polecenia subset:
d<-subset(d,select=c(V2,V3))
W poleceniu subset możemy odwoływać się po nazwach kolumn.
Porównywalnie do SQL-owego:
delete from nazwa_tabeli where nazwa_kolumny="wartosc";
w R dla data framu uzyskujemy przez:
nazwa_dfrejmu <- nazwa_dfrejmu[!nazwa_dfrejmu$nazwa_kolumny=="wartosc",]
Zakładając, że mamy graf g z poprzedniego wpisu.
Jeśli spojrzymy na wizualizacje grafu, zauważymy:
1) że jest niespójny
2) że są 3 skupiska odseparowane od reszty i 4 niepołączone z resztą ani między sobą osoby.
Pierwsze co zrobimy to:
is.connected(g) [1] FALSE
zgodnie z obserwacją 1) bez zaskoczenia nas zwróciło fałsz.
Zobaczmy jaka jest liczność naszych klastrów.
klasterki<-clusters(g, mode=c("weak", "strong")) table(klasterki$membership) 1 2 3 4 5 6 7 12 60 22 1 1 1 1
Stwórzmy sobie nowe obiekty klasy graf dla 3 najbardziej licznych
Korzystamy z induced.subgraph sprawdzając, czy dany wierzchołek należy do pożądanego klastra
g1<-induced.subgraph(g,klasterki$membership==1) ... g3 is.connected(g1) [1] TRUE
Możemy teraz porysować sobie wizualizacje, które z racji tego, że będą obejmować mniejszą liczbę węzłów i krawędzi będą bardziej czytelne.
DALSZE INFO:
a) subgraph
http://igraph.sourceforge.net/doc/R/subgraph.html
b) clusers
http://igraph.sourceforge.net/doc/R/clusters.html
Wcześniej pobrałem graf znajomych z Facebooka (robi się to bardzo łatwo korzystając z jednej z facebook’owych aplikacji). Szczegóły jak to zrobić wkrótce w oddzielnym wpisie.
Na podstawie tych danych przygotowałem sobie dwa pliki CSV. Jeden zawiera facebook’owe id, Imie Nazwisko; Drugi to zbiór par oznaczających relację bycia ze sobą znajomymi osób a i b. Zawiera po prostu: id_a, id_b.
Dane wczytujemy domyślnie do data frameów. (linie: 2-3)
(OPCJONALNE, niekonieczne linie 5-6) Zamieniamy zapis z notacji naukowej (ID są długie, więc domyślnie zobaczymy w R-ze je w notacji naukowej) na zwykłą.
Tworzymy sobie dodatkową kolumnę na inicjały (linia 7, inicjujemy 0), chociaż tak na prawdę wrzucimy tam całe imię oraz 3 pierwsze litery nazwiska bez spacji.(linie 8-14)
Biblioteka igraph z której będziemy korzystać nie poradzi sobie z tak dużymi liczbami jak ID, więc dokonamy przenumerowania, zamienimy unikalne ID na unikalne, ale bardzo krótkie reprezentacje. (linia 16 nadanie krótkich wersji)
Teraz dla data framu z danymi o parach również potrzebujemy dokonać podmiany długiego ID na wcześniej ustalone krótkie id. Piszemy w tym celu funkcję getShort().
Od 19-40 linii znajduje się funkcja realizująca wyszukiwanie binarne z bardzo satysfakcjonującą złożonością O(lgn). R posiada wiele bardzo dobrze zoptymalizowanych własnych metod, dlatego zamiast kodu w liniach 19-40 swobodnie można zaimplementować to jak w liniach: 58-62.
Ze stworzonej pętli skorzystamy w liniach 66-68 iterując po poszczególnych parach.
W liniach 70-78 piszemy sobie funkcję która zwróci nam informacje o relacjach znajomości w formie listy. Funkcja graph z biblioteki igraph oczekuje na wejściu właśnie listy wierzchołków, które są połączone krawędzią.
Lista a_0,a_1,a_2,a_3…. gdzie wierzchołki połączone krawędzią to pary: (a_0,a_1), (a_2,a_3)…
W linii 84 wreszcie tworzymy graf. Graf jest nieskierowany (ang. undirected) dlatego tworzymy go z parametrem directed=FALSE.
W lini 85 wiążemy z odpowiednimi wierzchołkami odpowiednie etykiety.
W lini 89 deklarujemy plik png będący naszym płótnem o celowo zadanych przez nas dużych wymiarach, na którym narysujemy graf: polecenie w linii 90. Precyzujemy kolor linii i wielkość wierzchołka.
setwd("~/Desktop/fb_graph")
ludzie<-read.csv("id_people.csv", header=FALSE)
relacje<-read.csv("relations.csv", header=FALSE)
for (i in 1:nrow(ludzie)){ ludzie$V1[i] <-format(ludzie$V1[i], scientific=FALSE)}
for (i in 1:nrow(relacje)){ relacje$V1[i]<-format(relacje$V1[i], scientific=FALSE); relacje$V2[i]<-format(relacje$V2[i], scientific=FALSE);}
ludzie$inicjaly<-0
for (i in 1:nrow(ludzie)) {
ludzie$inicjaly[i] <- paste(
(strsplit(as.character(ludzie$V2[i]), ' ')[[1]])[1] ,
substring(((strsplit(as.character(ludzie$V2[i]), ' ')[[1]])[2]),1,3)
,sep="")}
ludzie$short<-0
for (i in 1:nrow(ludzie)) {ludzie$short[i]=i}
getShort <-function(long) {
short<-0
L<- 1
R<- nrow(ludzie)
M<- floor((L+R)/2)
#for (i in L:R){
while (L<=R){
if(ludzie$V1[M]==long){
short<-ludzie$short[M]
break
} else
if(long < ludzie$V1[M] ){# szukany element < od wyznaczonego przez M
R<-(M-1)
M<-floor((L+R)/2)
} else { #szukany element > od wyznaczonego przez M
L<-(M+1)
M<-floor((L+R)/2)
}
}
return (short)
}
getShort <-function(long) {
short<-0
short<-ludzie$V1[long]
return (short)
}
getShort <-function(long) {
short<-0
short<-ludzie$short[ludzie$V1 == long]
return (short)
}
rl<-relacje
for (i in 1:nrow(rl)){
rl$V1[i]<-getShort(rl$V1[i]); rl$V2[i]<-getShort(rl$V2[i]);
}
getList<-function(){
l <-vector()
for (i in 1:nrow(rl)){
l<-c(l,rl$V1[i])
l<-c(l,rl$V2[i])
}
return(l)
}
v<-getList()
library(igraph)
g<-graph(v, directed=FALSE)
V(g)$label <- ludzie$inicjaly
p2<-png(filename="plocik.png",width=6500,height=6500,unit="px")
p2<-plot(g, vertex.size=1, edge.color="red")
Szukanie kliki.
Klika w grafie nieskierowanym G=(V,E) to podzbiór wierzchołków
w którym każda para wierzchołków jest połączona krawędzią należącą do E. Inaczej mówiąc klka to pełny podgraf grafu G. Rozmiar kliki to liczba wierzchołków, kótre zawiera. Problemy kliki to optymalizacyjny problem znalezieni w grafie kliki maksymalnego rozmiaru. W wersji decyzyjnej pytamy po prostu czy istnieje w grafie klika danego rzomiaru k. Formalna definicja to:CLIQUE = { <G,k> : G jest grafem zawierającym klikę rozmiaru k }
Problem kliki jest NP-zupełny. Algorytm „naiwny” stwierdza, czy graf G=(V,E) o |V| wierzchołkach zawiera klikę rozmiary k, polega naprzemierzeniu wszystkich k-podzbiorów zbioru V i sprawdzeniu każdego z nich, czy aby nie tworzy kliki. Czas działania algorytmy jest WIELOMIANOWY jeśli k jest stałą. Ogólnie jednak k może być bliskie |V|/2 a wówczas czas działania jest większy niż wielomianowy.
T. Cormen, Ch. Leiserson, R. Rivest, C. Stein,. Wprowadzenie do algorytmów.
a) wersja ~decyzyjna:
Szukanie kiliki o rozmiarze conajmniej k:
cliques(g, min=5)
b) wersja optymalizacyjna:
Szukanie największej kliki:
largest.cliques(g)
wiele więcej tutaj:
http://igraph.sourceforge.net/doc/R/cliques.html
W tym wpisie krótko przedstawię prosty algorytm służący do grupowania punktów w zadaną liczbę klastrów.
Idea: podzielić na zadaną liczbę grup elementów, tak by najbardziej podobne do siebie były w jednej grupie. Za taką miarę podobieństwa można uznać np. bliskość położenia punktów w przestrzeni. Punkty blisko siebie uznajemy za podobne.
Odległość w przestrzeni n-wymiarowej między dwoma punktami obliczamy z:
WAŻNA UWAGA: korzystamy z algorytmu uczenia bez nadzoru, czyli algorytm sam będzie musiał wychwycić pewne zależności, w tym podejściu nie posiada on żadnych przykładów uczących. NIE mówimy tu o klasyfikacji (bo przecież nie znamy klas <- brak przykładów uczących) lecz o grupowaniu na podstawie podobieństwa, które określiliśmy wcześniej.
Jak działa ten algorytm?
1. Dla zadanego k, losuje k z pośród n punktów. (te k punkty nazywamy centroidami – punktami średnimi klastra)
2. Oblicza odległość dla każdego z n punktów do każdego z k-centroidów i przypisuje go do najbliższego klastra.
3. Dla każdego z k-klastrów zostaje wyznaczony nowy centroid jako średnia przypisanych mu elementów.
4. W pętli wykonuj od kroku 2 dopóki nie dojdziemy do momentu, że nie następują już przesunięci punktów pomiędzy klastrami
Będziemy korzystać z R struktury danych: matrix, zbioru danych iris, oraz gotowej implementacji algorytmu kmeans.
Zbiór danych iris jest jednym z przykładowych zbiorów w R. Zawiera on 150 obserwacji dla 3 rodzajów kwiatków: setosa, versicolor, virginica. Po 50 obserwacji kwiatka każdego z 3 rodzajów. Te informacje to 4 liczby dla każdej z obserwacji charakteryzujące wymiary listków oraz informacja jakiego typu był to kwiatek. Jako, że kmeans to uczenie bez nadzoru, to będziemy korzystać tylko 4 pierwszych informacji o rozmiarach.
iris
Sepal.Length Sepal.Width Petal.Length Petal.Width Species
1 5.1 3.5 1.4 0.2 setosa
2 4.9 3.0 1.4 0.2 setosa
3 4.7 3.2 1.3 0.2 setosa
4 4.6 3.1 1.5 0.2 setosa
5 5.0 3.6 1.4 0.2 setosa
................................................................
summary(iris) Sepal.Length Sepal.Width Petal.Length Petal.Width Species Min. :4.300 Min. :2.000 Min. :1.000 Min. :0.100 setosa :50 1st Qu.:5.100 1st Qu.:2.800 1st Qu.:1.600 1st Qu.:0.300 versicolor:50 Median :5.800 Median :3.000 Median :4.350 Median :1.300 virginica :50 Mean :5.843 Mean :3.057 Mean :3.758 Mean :1.199 3rd Qu.:6.400 3rd Qu.:3.300 3rd Qu.:5.100 3rd Qu.:1.800 Max. :7.900 Max. :4.400 Max. :6.900 Max. :2.500
Do naszych działań poręczniej będzie korzystać z macierzy zawierającej te informacje, które nas interesują niż całym data.frame iris. Dlatego tworzymy macierz o nazwie ird wskazując, które kolumny z iris mają wejść w skład. Musimy zadać liczbę kolumn macierzy.
ird<-matrix(c(iris$Sepal.Length,iris$Sepal.Width, iris$Petal.Length,iris$Petal.Width), ncol=4)
Punkty reprezentujące poszczególne obserwacje możemy zobaczyć w 2D wywołując:
plot(ird)
Wywołajmy algorytm kmeans jako argumenty podając naszą macierz i wybrane przez nas k, np.k=3
rezultaty<-kmeans(ird,3)
Stwórzmy wykres pokazujący jak pogrupowane zostały punkty
plot(ird, col=rezultaty$cluster)
Jeśli chcemy zobaczyć wykres na którym zaznaczone zostaną nie tylko klastry, ale także finalne(z ostatniej iteracji) centroidy:
plot(ird, col=rezultaty$cluster) points(rezultaty$centers, col=6,pch=10,cex=3)
Gdybyśmy chcieli wiedzieć jakie są współrzędne każdego z 3 centroidów:
rezultaty$centers
[,1] [,2] [,3] [,4]
1 5.006000 3.428000 1.462000 0.246000
2 6.850000 3.073684 5.742105 2.071053
3 5.901613 2.748387 4.393548 1.433871
Jeśli chcemy wiedzieć ile punktów zostało przypisanych do poszczególnych grup:
table(rezultaty$cluster) 1 2 3 50 38 62
aby wywołać pomoc dla konkretnej biblioteki, funkcji, struktury danych po prostu wywołaj:
?igraph
?data.frame
Najprościej aby zainstalować nową bibliotekę:
1. Klikamy Packages&Data
2. Wybieramy Package Installer
3. Wybieramy źródło(serwer) np. R CRAN
4. Wpisujemy nazwę biblioteki której szukamy, np. igraph
5. Wybieramy z wyników tę która nas interesuje, klikamy Install Selected
6. Instalacja wykona się atuomatycznie
Aby korzystać z biblioteki, zaczynamy od komendy
library(igraph)
BARDZIEJ ZAAWANSOWANE WERSJE INSTALACJI BIBLIOTEK:
http://cran.r-project.org/doc/manuals/R-admin.html#Installing-packages
create file called x.R
today <- Sys.Date()
today <-format(today, format="%d-%m-%Y")
png(paste("raport-",today,".png",sep=""))
hist(rnorm(100))
dev.off()
to run from comand lines (e.g Terminal Unix/Macintosch)
R CMD BATCH x.R
Jak iterować po elementach naszego data.frame? Całkiem prosto:
for (i in 1:nrow(naszDataFrame)){
#tu akcja ktora ma sie wykonywac
}
Zwróć uwagę, że zanim zacząłem robić pierw dodałem nową kolumnę i ją zainicjowałem zerami.
Nie jest możliwe by zrobić to „w biegu” w pętli i od razu coś tam wpisywać.
> a<-c(1.4,1.8,2.2,2.6,3.0,3.4,3.8)
> b<-c+0.4
> c<-c(5,15,3,16,8,1,2)
> df2<-data.frame(a,b,c)
> df2$czest<-df2$c/sum(df2$c)
> df2$dis2<-0
> sum<-0; for (i in 1:nrow(df2)){sum<- sum + df2[i,]$czest; df2[i,]$dis2<-sum;}
> df2
a b c czest dist dis2
1 1.4 1.8 5 0.10 1 0.10
2 1.8 2.2 15 0.30 1 0.40
3 2.2 2.6 3 0.06 1 0.46
4 2.6 3.0 16 0.32 1 0.78
5 3.0 3.4 8 0.16 1 0.94
6 3.4 3.8 1 0.02 1 0.96
7 3.8 4.2 2 0.04 1 1.00
Kostanski's Blog 