Witam,

Zastanawiam sie nad takim problemem: mamy zbior powiedzmy 20 cech
ktorymi mozemy opisac jakis przedmiot np. jesli mamy obrazki to jego
cechami moga byc 'widac drzewa'(1), 'widac zwierzeta'(2), 'widac
morze'(3), 'widac statek'(4) itd. Mamy wiec taka 20-wymiarowa przestrzen
cech i kazdy obrazek mozemy opisac 20-sto wymiarowym wektorem. Dla
ulatwienia powiedzmy, ze obrazek moze albo miec ceche (1) albo jej nie
miec (0).

Mamy tez uzytkownika i mozemy stwierdzic, ze lubi on ogladac zdjecia z
drzewami i zwierzetami ([1 1 0 0 ...]) ale tez lubi zobaczyc statek na
morzu. ([0 0 1 1 ...]).

I teraz problem: w jaki sposob teraz znalezc w duzym zbiorze zdjecia,
ktore prawdopodobnie spodobaja sie uzytkownikowi?

Pierwsze co przychodzi na mysl to policzenie 'wektora preferencji
uzytkownika' (np. srednia arytmetyczna z ogladanych przez niego
obrazkow) i znalezienie najblizszych mu wektorow w przestrzeni cech. Ale
to raczej nie bedzie dzialac dobrze bo taki 'wektor preferencji' powie
nam tyle, ze 'uzytkownik troche lubi ogladac zdjecia z drzewami,
zwierzetami, morzem i statkiem [0.5 0.5 0.5 0.5...]'. Prawdopodobnie
nalezaloby jakos zachowac nie tylko informacje co user lubi ale tez w
jakich polaczeniach.

Macie jakies pomysly? W rozwiazaniu zalezy mi bardziej na predkosci niz
na dokladnosci ze wzgledu na bardzo duzy zbior zdjec.

Pewnie sa jakies algorytmy do tego, ale najwyrazniej nie potrafie zadac
odpowiedniego pytania guglowi.

pozdrawiam,
123

do góry

123 rzecze:

> Macie jakies pomysly? W rozwiazaniu zalezy mi bardziej na predkosci niz
> na dokladnosci ze wzgledu na bardzo duzy zbior zdjec.

Na pewno nie liczenie średniej z preferencji, bo jak ktoś lubi kolor żółty i
niebieski, to nie znaczy że lubi zielony. Gdybyś miał ustalone już na
starcie zestawy preferencji, to zapewne dałoby się zrobić odpowiednią
ekstrakcję cech z bazowej przestrzeni żeby wyszukiwanie było szybsze, ale
jeśli użytkownik może podawać nowe preferencje, to pozostaje chyba tylko
sekwencyjne sprawdzanie metryk dla każdego z zestawów preferencji.

Alternatywnie, możesz zamiast stosować metryki między obiektem i pojedynczym
zestawem preferencji zastosować metrykę maksimum od całego zbioru
preferencji użytkownika - złożonośc wzrośnie tak czy siak liniowo, ale
będzie to "ładniejsze".

Kwestia sprytnego oprogramowania wyliczania tych metryk za pomocą operacji
bitowych.
--
Omniscient, omnipotent, omnipresent, without judgment

Mateusz Ludwin mateuszl [at] gmail [dot] com

do góry

Mateusz Ludwin rzecze:

> Alternatywnie, możesz zamiast stosować metryki między obiektem i pojedynczym
> zestawem preferencji zastosować metrykę maksimum od całego zbioru
> preferencji użytkownika

Oczywiście błąd - minimum, a nie maksimum. Interesuje nas najmniejsza
odległość danego obrazka od kolejnych wektorów preferencji.
--
Omniscient, omnipotent, omnipresent, without judgment

Mateusz Ludwin mateuszl [at] gmail [dot] com

do góry

Dnia Mon, 05 Jan 2009 22:15:52 +0100, 123 napisał(a):

> Zastanawiam sie nad takim problemem: mamy zbior powiedzmy 20 cech
> ktorymi mozemy opisac jakis przedmiot np. jesli mamy obrazki to jego
> cechami moga byc
> 'widac drzewa'(1),

value = 0x0001

> 'widac zwierzeta'(2),

value = 0x0002

> 'widac morze'(3),

value = 0x0004

> 'widac statek'(4)

value = 0x0008
Wszystko powyzej szesnastkowo.

> Mamy tez uzytkownika i mozemy stwierdzic, ze lubi on ogladac zdjecia z
> drzewami i zwierzetami ([1 1 0 0 ...])

mask = 0x0003

> ale tez lubi zobaczyc statek na
> morzu. ([0 0 1 1 ...]).

mask = 0x000b

> I teraz problem: w jaki sposob teraz znalezc w duzym zbiorze zdjecia,
> ktore prawdopodobnie spodobaja sie uzytkownikowi?

for (po wszystkich zdjeciach)
if (value & mask != 0 ) /* value & mask znaczy logiczne and */
zdjecie podoba sie
endif
end

O(n) po calosci

--
Jarek

do góry

on 2009-01-05, 123 supposed :
> Pierwsze co przychodzi na mysl to policzenie 'wektora preferencji
> uzytkownika' (np. srednia arytmetyczna z ogladanych przez niego obrazkow) i
> znalezienie najblizszych mu wektorow w przestrzeni cech.

Wektor binarny jest przestrzenią niemetryczną. Wyciąganie tam średnich
nie ma zbyt wielkiego sensu.
Najprościej:
1. Stworzyć dla użytkownika wektor najczęściej oglądanych cech (np. 10
cech).
2. Wybrać X obrazków zawierających wektory cech najbliższe stworzonemu
dla użytkownika.

> statkiem [0.5 0.5 0.5 0.5...]'. Prawdopodobnie nalezaloby jakos zachowac nie
> tylko informacje co user lubi ale tez w jakich polaczeniach.
> Macie jakies pomysly? W rozwiazaniu zalezy mi bardziej na predkosci niz na
> dokladnosci ze wzgledu na bardzo duzy zbior zdjec.

Połączenia bym zignorował. Jest spora szansa, że cechy na obrazkach są
skorelowane. Tym bardziej, że zależy Ci na prędkości.

> Pewnie sa jakies algorytmy do tego, ale najwyrazniej nie potrafie zadac
> odpowiedniego pytania guglowi.

Google: binary vectors similarity, clustering binary data.

pozdrawiam,
Jakub

do góry

Jakub Debski wrote:
> on 2009-01-05, 123 supposed :
>> Pierwsze co przychodzi na mysl to policzenie 'wektora preferencji
>> uzytkownika' (np. srednia arytmetyczna z ogladanych przez niego
>> obrazkow) i znalezienie najblizszych mu wektorow w przestrzeni cech.
>
> Wektor binarny jest przestrzenią niemetryczną. Wyciąganie tam średnich
> nie ma zbyt wielkiego sensu.
> Najprościej:
> 1. Stworzyć dla użytkownika wektor najczęściej oglądanych cech (np. 10
> cech).
> 2. Wybrać X obrazków zawierających wektory cech najbliższe stworzonemu
> dla użytkownika.

Ale to bez sensu...

Jakby użytkownika interesował tak naprawdę jeden zestaw preferencji, to by sobie
pooznaczał jakieś checkboksy z warunkami, a tu wyraźnie chodzi o coś innego -
chce miec na przykład obrazki z czarnymi samochodami i białymi kobietami - ty mu
pokażesz obrazki z białymi lub czarnymi samochodami lub kobietami.
--
Mateusz Ludwin mateuszl [at] gmail [dot] com

do góry

Jarek wrote:

>> Mamy tez uzytkownika i mozemy stwierdzic, ze lubi on ogladac zdjecia z
>> drzewami i zwierzetami ([1 1 0 0 ...])
>
> mask = 0x0003
>
>> ale tez lubi zobaczyc statek na
>> morzu. ([0 0 1 1 ...]).
>
> mask = 0x000b
>
>> I teraz problem: w jaki sposob teraz znalezc w duzym zbiorze zdjecia,
>> ktore prawdopodobnie spodobaja sie uzytkownikowi?
>
> for (po wszystkich zdjeciach)
> if (value & mask != 0 ) /* value & mask znaczy logiczne and */
> zdjecie podoba sie
> endif
> end

Bardzo ciekawy sposób klasyfikacji. Rozumiesz w ogóle problem, czy tak sobie
tylko piszesz?
--
Mateusz Ludwin mateuszl [at] gmail [dot] com

do góry

Mateusz Ludwin submitted this idea :
> Jakub Debski wrote:
>> Wektor binarny jest przestrzenią niemetryczną. Wyciąganie tam średnich nie
>> ma zbyt wielkiego sensu.
>> Najprościej:
>> 1. Stworzyć dla użytkownika wektor najczęściej oglądanych cech (np. 10
>> cech).
>> 2. Wybrać X obrazków zawierających wektory cech najbliższe stworzonemu dla
>> użytkownika.
>
> Ale to bez sensu...
>
> Jakby użytkownika interesował tak naprawdę jeden zestaw preferencji, to by
> sobie pooznaczał jakieś checkboksy z warunkami, a tu wyraźnie chodzi o coś
> innego - chce miec na przykład obrazki z czarnymi samochodami i białymi
> kobietami - ty mu pokażesz obrazki z białymi lub czarnymi samochodami lub
> kobietami.

Według mnie cechą nie będzie kolor, ale tagi przypisywane przez autora
zdjęć lub moderatora, czyli głównie rzeczowniki, a nie przymiotniki.
Odpowiada to przykładowi OP (drzewa, zwięrzęta, morze, statek), czyli
problem jest z tych prostych.

Oczywiście jeżeli OP chce mieć pełne "market basket analysis", to
problem się komplikuje...

Checkboxy z warunkami to odpowiednik automatycznie wybranego wektora
preferencji użytkownika. Automatycznie wybrany wektor ma tę zaletę, że
nie angażuje w proces użytkownika :)

pozdrawiam,
Jakub

do góry

Jakub Debski wrote:

>> Jakby użytkownika interesował tak naprawdę jeden zestaw preferencji,
>> to by sobie pooznaczał jakieś checkboksy z warunkami, a tu wyraźnie
>> chodzi o coś innego - chce miec na przykład obrazki z czarnymi
>> samochodami i białymi kobietami - ty mu pokażesz obrazki z białymi lub
>> czarnymi samochodami lub kobietami.
>
> Według mnie cechą nie będzie kolor, ale tagi przypisywane przez autora
> zdjęć lub moderatora, czyli głównie rzeczowniki, a nie przymiotniki.
> Odpowiada to przykładowi OP (drzewa, zwięrzęta, morze, statek), czyli
> problem jest z tych prostych.

Nie.

"lubi on ogladac zdjecia z drzewami i zwierzetami ([1 1 0 0 ...]) ale tez lubi
zobaczyc statek na morzu. ([0 0 1 1 ...])."

To są dwa _wykluczające się_ zestawy preferencji. To że ktoś lubi zobaczyć
statek na morzy lub drzewa i zwierzęta nie znaczy, że lubi zobaczyć zwierzę na
statku. Jeżeli użytkownika będzie interesować operacja OR z kilku zestawów
preferencji, to po prostu doda sobie taki zestaw samodzielnie.

Kolor może być jak najbardziej jedną z cech. Np. "zdjęcie ma odcień zielony". I
ktos może lubić zielone pejzaże i czarno - białe portrety, ale czarno - białe
pejzaże go nie zainteresują. 0 w wektorze preferencji wcale nie jest słabsze od 1.

> Checkboxy z warunkami to odpowiednik automatycznie wybranego wektora
> preferencji użytkownika. Automatycznie wybrany wektor ma tę zaletę, że
> nie angażuje w proces użytkownika :)

To co proponujesz sprowadza się tak naprawdę do jednego wektora preferencji, a
tu uzytkownik może podać wiele. I powinno się sprawdzać każdy z wektorów z
osobna, a potem wziąć minimalną znalezioną odległość.
--
Mateusz Ludwin mateuszl [at] gmail [dot] com

do góry

It happens that Mateusz Ludwin formulated :
> To są dwa _wykluczające się_ zestawy preferencji. To że ktoś lubi zobaczyć
> statek na morzy lub drzewa i zwierzęta nie znaczy, że lubi zobaczyć zwierzę
> na statku.

Ale właśnie o tym pisałem odnośnie korelacji obrazków.
Szansa występowania zwierzęcia na statku jest mała, ponieważ cechy
występujące na obrazkach są zwykle silnie skorelowane.

> Jeżeli użytkownika będzie interesować operacja OR z kilku zestawów
> preferencji, to po prostu doda sobie taki zestaw samodzielnie.

Według mnie właśnie ten proces autor wątku chce zautomatyzować.

> Kolor może być jak najbardziej jedną z cech. Np. "zdjęcie ma odcień zielony".
> I ktos może lubić zielone pejzaże i czarno - białe portrety, ale czarno -
> białe pejzaże go nie zainteresują. 0 w wektorze preferencji wcale nie jest
> słabsze od 1.

Tu już by się musiał wypowiedzieć autor wątku, czego potrzebuje.
Jeżeli algorytm ma działać w ramach niewielkiej usługi bazodanowej, to
zaproponowane rozwiązanie będzie działać nawet dla dużej liczby
użytkowników i obrazków, choć nie w sposób optymalny.
Jeżeli wymagania biznesowe są większe i odpowiadają dostępnym środkom,
to dla każdego użytkownika można przeprowadzać pełną analizę asocjacji
jego preferencji, ale jest to problem zupełnie innej klasy...
Z wypowiedzi autora wątku wywnioskowałem zapotrzebowanie na coś
prostego.

> To co proponujesz sprowadza się tak naprawdę do jednego wektora preferencji,
> a tu uzytkownik może podać wiele. I powinno się sprawdzać każdy z wektorów z
> osobna, a potem wziąć minimalną znalezioną odległość.

To też dobry pomysł - można oceniać X ostatnio oglądanych obrazków i
szukać im podobnych. Uwzględni to zmianę preferencji użytkownika w
czasie.

pozdrawiam,
Jakub

do góry