Seznam objektů, které by uživatele mohly zajímat

Školení, která pořádám

Na Internetových obchodech se mi velice líbí funkce „Lidé, kteří si koupili stejné zboží jako vy, si koupili také“. Tato funkce se dá zobecnit a použít nejen u zboží, ale třeba také u článků. Jak se taková funkce dá implementovat?

  1. Nejprve získáme seznam všech objektů, se kterými aktuální uživatel pracoval. („Pracovat s objektem“ může znamenat např. „koupit výrobek“ nebo „přečíst článek“.)
  2. Získáme seznam uživatelů, kteří pracovali s objekty na tomto seznamu. Průnik nemusí být absolutní, zajímají mě i uživatelé, kteří mají společných např. 90 % objektů, naopak mě moc nezajímají uživatelé, kteří pracovali se skoro všemi objekty.
  3. V objektech těchto uživatelů najdu ty, které se tam vyskytují nejčastěji a zároveň s nimi aktuální uživatel ještě nepracoval.

Implementace tohoto algoritmu v běžné relační databázi není právě jednoduchá a naopak bude výkonnostně poměrně náročná. Když se nad funkcí ale hlouběji zamyslíme, nutně nám to musí něco připomínat – vlastně jde o fulltextové vyhledávání tak, jak je implementované v MySQL. U každého uživatele si stačí ukládat v textovém poli seznam objektů, se kterými pracoval, a toto pole následně použít pro vyhledání podobných uživatelů. MySQL při fulltextovém vyhledávání netrvá na přítomnosti všech hledaných slov a zvýhodňuje texty, které hledanému výrazu co nejpřesněji odpovídají (nemají moc dalších slov).

Z takto získaného seznamu uživatelů a jejich objektů se už dá snadno získat seznam nejčastějších objektů, se kterými uživatel ještě nepracoval:

<?php
$zhlednuto = array_flip(explode(" ", mysql_result(mysql_query("SELECT zhlednuto FROM uzivatele WHERE id = " . intval($_COOKIE["uzivatel"])), 0)));
$zhlednuto[$_GET["id"]] = true;
$result = mysql_query("SELECT zhlednuto FROM uzivatele WHERE id != " . intval($_COOKIE["uzivatel"]) . " AND MATCH (zhlednuto) AGAINST ('+" . intval($_GET["id"]) . "' IN BOOLEAN MODE) AND MATCH (zhlednuto) AGAINST ('" . implode(" ", array_keys($zhlednuto)) . "') LIMIT 20");
$dalsi = array();
while ($row = mysql_fetch_assoc($result)) {
    foreach (explode(" ", $row["zhlednuto"]) as $id) {
        if (!isset($zhlednuto[$id])) {
            $dalsi[$id]++;
        }
    }
}
mysql_free_result($result);
if ($dalsi) {
    arsort($dalsi);
    echo "<h3>Mohlo by vás také zajímat</h3>\n";
    echo "<ul>\n";
    $result = mysql_query("SELECT url, nadpis FROM clanky WHERE id IN (" . implode(", ", array_keys($dalsi)) . ") ORDER BY FIELD(id, " . implode(", ", array_keys($dalsi)) . ") LIMIT 5");
    while ($row = mysql_fetch_assoc($result)) {
        echo "<li><a href='$row[url].php'>" . htmlspecialchars($row["nadpis"]) . "</a></li>\n";
    }
    mysql_free_result($result);
    echo "</ul>\n";
}
?>

Identifikátory uložené v poli zhlednuto musí mít délku alespoň ft_min_word_len (výchozí hodnota je 4), proto jim může být potřeba přidat nějaký textový doplněk.

Možné rozšíření

Zajímavým rozšířením této funkce by bylo doplnit také podobnost hodnocení. Např. na ČSFD by se mohly zobrazovat filmy setříděné podle hodnocení uživatelů, kteří podobně hodnotili filmy, které jsme viděli společně. Stejně tak u filmů, které jsem nehodnotil, by se nejprve mohlo zobrazovat hodnocení uživatelů, kteří mají podobný vkus jako já.

Jakub Vrána, Řešení problému, 4.4.2008, diskuse: 19 (nové: 0)

Diskuse

Pavel Šindelka:

Zajímavé a jako vždy originální řešení problému :) Tato "zjednodušení" vedou často k velkým úsporám na výpočetním čase s velmi slušnými výsledky. Jen se umět oprostit od toho, že svůj problém určitým způsobem "obcházím" :)

ikona David Grudl:

Rozhodně doporučuji přečíst tento článek http://johno.jsmf.net/archiv/spravanie-uzivatelov-…-datach.html

Ale obecně si myslím, že podobný algoritmus by třeba na blogu vůbec nefungoval. Uplatní se spíš v situacích, kdy „Pracovat s objektem“ = „koupit produkt“, ale i tak může být nalezení správných vah poměrně složité.

paranoiq:

tak nějak. základním problémem myslím bude, nemožnost zjistit zda uživatel článek skutečně četl.

ale ten nápad s fulltextem je super. díky

Mirek Dušín:

Jako rychlý hack dobré, ale jako inženýrské řešení příšerný nápad.

ikona Jakub Hejda:

Děkuji za vyřešení problému :-)
Mít tento blog ve čtečce RSS se prostě vyplatí. Díky díky díky.

ikona Zed:

Myslim, ze zajimave na tomto algoritmu je predevsim jeho uspornost. Jinak asi neni co resit. Skvely napad, z tve hlavy?:)

ikona Jakub Vrána OpenID:

Ano, nápad je z mé hlavy, nechal jsem se inspirovat pouze netradičním využitím fulltextového vyhledávání: http://www.mysqlperformanceblog.com/2007/…-text-search/.

johno:

Zdravim,

na pouzitie fulltext indexov na vyhladavanie/odporucanie treba dat pozor. Ono sa to nemusi vzdy spravat uplne tak, ako by clovek chcel. Fulltext v mysql totiz pouziva specializovanu TF-IDF schemu vahovania slov v dokumentoch, ktore vychadzaju z charakteristickych vlastnosti textov v dokumentoch. Nemusi to byt vhodne uplne v kazdej domene.

Viac do hlbky je to rozobrane na http://www.miislita.com/term-vector/term-vector-5-mysql.html

Co sa tyka rychlosti tak je mozne spravit klasicky invertovany index/tabulku so stlpcami term_id, document_id a potom nad tym vyhladavat. MySQL to myslim interne robi viac menej tak isto len tam pridava to vahovanie cez TF-IDF schemu.

Co sa tyka odporucania, tak taketo nieco je mozne dostatocne pouzit v pripade, ze ten vysledny graf uzivatelov a zhliadnuch clankov je dostatocne "husty".

Napriklad situacia:

Uzivatel A: clanky 1, 2, 4
Uzivatel B: clanky 2, 3, 4

Uzivatel C: clanok 3.

Co sa odporuci uzivatelovi C? Podla mna len 2 a 4. Aj ked je zrejme, ze by sa mu malo pacit do istej mieri aj 1, kedze uzivatelovi B sa paci aj 2,4 a to je velmi silny prekryv s uzivatelom A.

Problem je, ze udaje takehoto charakteru su v praxi velmi riedke a preto na to treba ist trochu inak.

ikona Jakub Vrána OpenID:

Já mám štěstí v tom, že data poměrně hustá mám. Dlouhodobě sleduji čtenost článků jednotlivými uživateli, abych jim mohl rozlišovat přečtené a nepřečtené příspěvky v diskusích.

Určitě by se to dalo vyřešit i přesněji, tento problém má ale tu výhodu, že stačí zobrazit jakž-takž relevantní data - stejně nevím, co se uživateli líbit bude a co ne, takže mu stačí nabídnout něco, co by možná jeho vkusu mohlo vyhovovat.

ikona Michal Aichinger:

Je pekne se inspirovat sphinxem, ktery vyhledava v GB dat ve zlomcich vteriny. Ale uz neni pekne to pasovat do mysql a vytezovat tim DB stroj. Pocet radku v teto tabulkce bude narustat vice nez cokoli jineho (snad krome tabulek s pocitanim pristupu, ale nad nimi se nedela fulltext) a prohledavani bude pomale. Myslim si ze vyuziti klasickych integer klicu (idcek objektu) a sql nad nimi bude daleko mene vykonove narocne.

ikona Jakub Vrána OpenID:

Můžeš to zkusit udělat konvenčním způsobem a změřit. Můj osobní odhad je, že to bude pomalejší, ale rád se nechám přesvědčit o opaku.

Já mám v tabulce uživatelů celkem 200 000 záznamů, průměrně jsou u každého 4 články a vyhledávání trvá (na tomto poměrně obyčejném stroji) kolem 0,1 s, což není málo, ale ani moc.

ikona Zed:

Teprve ted, kdyz jsem pridal komentar, jsem si vsiml, ze se ke kazdemu webu prida i favicon.ico. Taky krasny napad!

jimx:

Takova rejpava poznamka, zhlednout je treba z hory do udoli, kdezto shlednout je treba televizni porad a nebo clanek ... v tomto pripade se jedna o druhy pripad a tak by se sloupec v tabulce a promenna meli jmenovat "shlednuto" :)

Ale nejlepsi ulet jsem stejne videl u jednoho inet prodejce automobilu, kde programator tvrdosijne pouzival promennou viska (misto vyska) :)

ikona Jakub Vrána OpenID:

Komentář přišel pozdě, článek byl opraven už v 9:08 :-).

Honza:

Je to přesně naopak:

zhlédnout - spatřit, uvidět
shlédnout - pohlédnout dolů

Čili v článku už je správně použito "zhlédnout"

ikona Jakub Vrána OpenID:

Aha, to jsem si ani nevšiml, že mi komentář radí, ať to vrátím zase zpátky :-).

ikona Marty:

@jimx: http://www.proofreading.cz/shlednout-nebo-zhlednout je to takto :-)

ikona marek:

Tyhle věci jsou jak ekonomika - nejde ani o to vymyslet algoritmus, ale spíš "nějaký" napasovat na naměřené hodnoty. Ono by se to pak krylo asi s nějakým seo vyhodnocováním, ale stálo by za to na jednom webu v padesáti procentech případů "doporučovat" náhodné články a v dalších padesáti používat tenhle algoritmus. A teď na co se bude klikat víc a jestli se to bude nějak lišit...  :)

ikona Robert Vlach:

Rád bych přispěl svou praktickou zkušeností s řešením jednoho problému:

V roce 2008 jsme na portále Na volné noze spustili novou verzi katalogu http://navolnenoze.cz/katalog/ s možností kombinování štítků (kategorií). Jednoduše si navolíte libovolnou kombinaci a projdete zobrazené prezentace, vše samozřejmě user&SEO-friendly. Nebudu zbytečně zacházet do podrobností, základní princip jsem popsal již dříve do diskuse pod jiným Jakubovým článkem tady na blogu:
http://php.vrana.cz/traverzovani-kolem-stromu-presuny-uzlu.php

Bohužel, samotné databázové řešení nebylo příliš dobré. Katalog se nám rychle rozrůstal, takže již v následujícím roce 2009 jsem narazil na výkonový strop. Doba zpracování všech dotazů u hlavních kategorií jako Jazyky nebo Počítače přesahovala 1 vteřinu, což je u špičkového profi webu naprosto nepřijatelné. Aniž bych zasahoval do původního databázového schématu, řešil jsem problém poměrně složitým kešováním, které však, jak jsem zjistil později, bylo extrémně náročné na počet záznamů ve vazebných tabulkách (až stovky tisíc řádků) a s rostoucím počtem prezentací v katalogu by bylo zcela neúnosné.

Trn z paty mi vytáhl až Jakub Vrána, který mi doporučil implementovat fulltextový index zhruba tak, jak je to popsáno výše v jeho příspěvku. Nejenže jsem se tím zbavil neohrabaného kešování, ale hlavně rychlost zpracování oproti původnímu návrhu databáze vzrostla místy až stonásobně! Stávající řešení je přitom funkčně plně totožné s původní verzí z roku 2008. V tak velký pokrok jsem ani nedoufal.

Jakube, vřelé díky, máš mé hluboké uznání :-)

Vložit komentář

Používejte diakritiku. Vstup se chápe jako čistý text, ale URL budou převedeny na odkazy a PHP kód uzavřený do <?php ?> bude zvýrazněn. Pokud máte dotaz, který nesouvisí s článkem, zkuste raději diskusi o PHP, zde se odpovědi pravděpodobně nedočkáte.

Jméno: URL:

avatar © 2005-2018 Jakub Vrána. Publikované texty můžete přetiskovat pouze se svolením autora. Ukázky kódu smíte používat s uvedením autora a URL tohoto webu bez dalších omezení Creative Commons. Můžeme si tykat. Skripty předpokládají nastavení: magic_quotes_gpc=Off, magic_quotes_runtime=Off, error_reporting=E_ALL & ~E_NOTICE a očekávají předchozí zavolání mysql_set_charset. Skripty by měly být funkční v PHP >= 4.3 a PHP >= 5.0.