I want to create something like AMAZON: those who liked page A also liked page B

[windandwaves]

Hi Folk

I want to create something like AMAZON: those who liked page A also liked
page B (I am going to apply the concept to a few different selections, but
to keep it simple I will talk about page popularity here - like AMAZON talks
about purchase patterns: those who bought A also bought B, C and D).

In my mysql table, I record everytime a visitor looks at a particular page
(I keep track of people with sessions and they can only look at a page
once).

Next, what I want to do is to show a small list of similar likes. That is,
people who had an interest in page A also had an interest in page B.

The structure of my table is:
id
timestamp
session_id
page_name

There is a unique index on the combination of session_id and page_name.

To work out similar likes for page X, my idea was to make an array of all
the session ids that looked at page X and then select the top 10 of pages
that these folk looked at.

My question is, should I do this in PHP with a bunch of arrays, adding total
counts while looping through an array or shall I use SQL statements. I
could even make a really long string of WHERE session_id = A or session_id =
B, etc..... Although this seems really inefficient.

Another question I have is whether you think this will be a self-fulfilling
prophecy (e.g. if you say that page Y is also popular then people will check
it out and therefore make it more popular).

TIA

- Nicolaas

[ZeldorBlat]

This problem is actually more difficult than one might think -- if you
want to get accurate results. Companies with very large datasets like
Amazon spend a huge number of processor cycles to come up with those
types of rankings.

Do a search for "collaborat ive filtering" and "nearest neighbor." I
think you'll find that itll be much easier to implement any of the
several algorithms in a language other than SQL.

[Ian B]

The problem is actually not as difficult as you might think - and you
can get accurate results

:-)
First thing you need to realise is that you need your table in two
ways:

a) you need to look up id's which have accessed same page as the
current page
b) you need to look up the pages which those id's have accessed

also

c) you need to exclude the current page in b)
d) you need to count the number of times each related page occurs
e) you need to rank the results in order of popularity
This might sound like a programming problem, but it can be done in one
SQL statement

I'll build it up so you can see how I got there:

SELECT * FROM mytable AS t1

gets the whole table and lets you refer to it as "t1"
SELECT * FROM mytable AS t1
LEFT JOIN mytable AS t2 ON t1.session_id = t2.session_id

this gets you shedloads of results - one line for every combination
so if id#1 has visited pages a, b & c then you get

a-a
a-b
a-c
b-a
b-b
b-c
c-a
c-b
c-c

but we only want the ones for, say, page "a", and we only need
(from this data) the 'other' page

SELECT t2.page_name FROM mytable AS t1
LEFT JOIN mytable AS t2 ON t1.session_id = t2.session_id
WHERE t1.page_name = 'a'

this (for id#1)

would produce

b
c

running against all the data, would produce a whole list of pages - all
the pages that anyone who has visited page 'a' has also been to

If we group by page name, we'll get one line per page name
SELECT t2.page_name FROM mytable AS t1
LEFT JOIN mytable AS t2 ON t1.session_id = t2.session_id
WHERE t1.page_name = 'a'
AND t2.page_name <> 'a'
GROUP BY t2.page_name

g
d
e
f
b
c

If we add a count, we get the number of times that page turned up
SELECT t2.page_name,Co unt(t2.page_nam e) AS popularity FROM mytable AS
t1
LEFT JOIN mytable AS t2 ON t1.session_id = t2.session_id
WHERE t1.page_name = 'a'
AND t2.page_name <> 'a'
GROUP BY t2.page_name
g 10
d 27
e 19
f 41
b 110
c 83
And if we order by descending popularity, we're almost there

SELECT t2.page_name,Co unt(t2.page_nam e) AS popularity FROM mytable AS
t1
LEFT JOIN mytable AS t2 ON t1.session_id = t2.session_id
WHERE t1.page_name = 'a'
AND t2.page_name <> 'a'
GROUP BY t2.page_name
ORDER BY Count(t2.page_n ame) DESC

b 110
c 83
f 41
d 27
e 19
g 10

The last thing to do is limit the results to the top 5 results
SELECT t2.page_name,Co unt(t2.page_nam e) AS popularity FROM mytable AS
t1
LEFT JOIN mytable AS t2 ON t1.session_id = t2.session_id
WHERE t1.page_name = 'a'
AND t2.page_name <> 'a'
GROUP BY t2.page_name
ORDER BY Count(t2.page_n ame) DESC
LIMIT 5
b 110
c 83
f 41
d 27
e 19

And there's your list
....

Ian

[Ian B]

To answer your other question, it will be self-fulfilling (IMHO).
Amazon has the advantage of sales (which is the ultimate indicator of
whether the visitor wanted to go to that page) but you have no such
feedback, so everyone who goes to page a might then click through to
page b and hate it, but it will become more 'popular' in your rating
system.

You could try to balance this out by using the same SQL but with the
DESC removed and have a link "Almost no-one went to these pages - find
out why!"

:-)

I've done this on a web site which searches for businesses, and no-one
stays at the bottom of the popularity list for long

Ian

[windandwaves]

Ian B wrote:

The problem is actually not as difficult as you might think - and you
can get accurate results

:-)
First thing you need to realise is that you need your table in two
ways:

a) you need to look up id's which have accessed same page as the
current page
b) you need to look up the pages which those id's have accessed

also

c) you need to exclude the current page in b)
d) you need to count the number of times each related page occurs
e) you need to rank the results in order of popularity
This might sound like a programming problem, but it can be done in one
SQL statement

I'll build it up so you can see how I got there:

SELECT * FROM mytable AS t1

gets the whole table and lets you refer to it as "t1"
SELECT * FROM mytable AS t1
LEFT JOIN mytable AS t2 ON t1.session_id = t2.session_id

this gets you shedloads of results - one line for every combination
so if id#1 has visited pages a, b & c then you get

a-a
a-b
a-c
b-a
b-b
b-c
c-a
c-b
c-c

but we only want the ones for, say, page "a", and we only need
(from this data) the 'other' page

SELECT t2.page_name FROM mytable AS t1
LEFT JOIN mytable AS t2 ON t1.session_id = t2.session_id
WHERE t1.page_name = 'a'

this (for id#1)

would produce

b
c

running against all the data, would produce a whole list of pages -
all the pages that anyone who has visited page 'a' has also been to

If we group by page name, we'll get one line per page name
SELECT t2.page_name FROM mytable AS t1
LEFT JOIN mytable AS t2 ON t1.session_id = t2.session_id
WHERE t1.page_name = 'a'
AND t2.page_name <> 'a'
GROUP BY t2.page_name

g
d
e
f
b
c

If we add a count, we get the number of times that page turned up
SELECT t2.page_name,Co unt(t2.page_nam e) AS popularity FROM mytable AS
t1
LEFT JOIN mytable AS t2 ON t1.session_id = t2.session_id
WHERE t1.page_name = 'a'
AND t2.page_name <> 'a'
GROUP BY t2.page_name
g 10
d 27
e 19
f 41
b 110
c 83
And if we order by descending popularity, we're almost there

SELECT t2.page_name,Co unt(t2.page_nam e) AS popularity FROM mytable AS
t1
LEFT JOIN mytable AS t2 ON t1.session_id = t2.session_id
WHERE t1.page_name = 'a'
AND t2.page_name <> 'a'
GROUP BY t2.page_name
ORDER BY Count(t2.page_n ame) DESC

b 110
c 83
f 41
d 27
e 19
g 10

The last thing to do is limit the results to the top 5 results
SELECT t2.page_name,Co unt(t2.page_nam e) AS popularity FROM mytable AS
t1
LEFT JOIN mytable AS t2 ON t1.session_id = t2.session_id
WHERE t1.page_name = 'a'
AND t2.page_name <> 'a'
GROUP BY t2.page_name
ORDER BY Count(t2.page_n ame) DESC
LIMIT 5
b 110
c 83
f 41
d 27
e 19

And there's your list
...

Ian

I never read a more indepth and clearer reply!!!!!

Thank you SO MUCH (a lot more than a million).

Nicolaas

[windandwaves]

Ian B wrote:

To answer your other question, it will be self-fulfilling (IMHO).
Amazon has the advantage of sales (which is the ultimate indicator of
whether the visitor wanted to go to that page) but you have no such
feedback, so everyone who goes to page a might then click through to
page b and hate it, but it will become more 'popular' in your rating
system.

You could try to balance this out by using the same SQL but with the
DESC removed and have a link "Almost no-one went to these pages - find
out why!"

:-)

I've done this on a web site which searches for businesses, and no-one
stays at the bottom of the popularity list for long

Ian

I can solve this by using a session variable that makes clicks from the
popularity list be excluded from the popularity list, thereby reducing some
of the self-fulfilling prophecy clicks lead to more clicks.

THANKS
- Nicolaas

[windandwaves]

Ian B wrote:

The problem is actually not as difficult as you might think - and you
can get accurate results

:-)
First thing you need to realise is that you need your table in two
ways:

a) you need to look up id's which have accessed same page as the
current page
b) you need to look up the pages which those id's have accessed

also

c) you need to exclude the current page in b)
d) you need to count the number of times each related page occurs
e) you need to rank the results in order of popularity
This might sound like a programming problem, but it can be done in one
SQL statement

I'll build it up so you can see how I got there:

SELECT * FROM mytable AS t1

gets the whole table and lets you refer to it as "t1"
SELECT * FROM mytable AS t1
LEFT JOIN mytable AS t2 ON t1.session_id = t2.session_id

this gets you shedloads of results - one line for every combination
so if id#1 has visited pages a, b & c then you get

a-a
a-b
a-c
b-a
b-b
b-c
c-a
c-b
c-c

but we only want the ones for, say, page "a", and we only need
(from this data) the 'other' page

SELECT t2.page_name FROM mytable AS t1
LEFT JOIN mytable AS t2 ON t1.session_id = t2.session_id
WHERE t1.page_name = 'a'

this (for id#1)

would produce

b
c

running against all the data, would produce a whole list of pages -
all the pages that anyone who has visited page 'a' has also been to

If we group by page name, we'll get one line per page name
SELECT t2.page_name FROM mytable AS t1
LEFT JOIN mytable AS t2 ON t1.session_id = t2.session_id
WHERE t1.page_name = 'a'
AND t2.page_name <> 'a'
GROUP BY t2.page_name

g
d
e
f
b
c

If we add a count, we get the number of times that page turned up
SELECT t2.page_name,Co unt(t2.page_nam e) AS popularity FROM mytable AS
t1
LEFT JOIN mytable AS t2 ON t1.session_id = t2.session_id
WHERE t1.page_name = 'a'
AND t2.page_name <> 'a'
GROUP BY t2.page_name
g 10
d 27
e 19
f 41
b 110
c 83
And if we order by descending popularity, we're almost there

SELECT t2.page_name,Co unt(t2.page_nam e) AS popularity FROM mytable AS
t1
LEFT JOIN mytable AS t2 ON t1.session_id = t2.session_id
WHERE t1.page_name = 'a'
AND t2.page_name <> 'a'
GROUP BY t2.page_name
ORDER BY Count(t2.page_n ame) DESC

b 110
c 83
f 41
d 27
e 19
g 10

The last thing to do is limit the results to the top 5 results
SELECT t2.page_name,Co unt(t2.page_nam e) AS popularity FROM mytable AS
t1
LEFT JOIN mytable AS t2 ON t1.session_id = t2.session_id
WHERE t1.page_name = 'a'
AND t2.page_name <> 'a'
GROUP BY t2.page_name
ORDER BY Count(t2.page_n ame) DESC
LIMIT 5
b 110
c 83
f 41
d 27
e 19

And there's your list
...

Ian

The only thing one could probably add is to factor in how many places were
visited by someone in total. That is, a person who looked at alsmost all
pages should not have an influence as great as someone who only looked at
two pages (i.e. those links are meaningful).

How to do that in SQL as described above, I have no idea, but I may look
into this later.

[Gazornenplat]

How does this site work? Why do you need to exclude people from pages
that they have been to before? And why does it mean less if you visit
more pages? I'd be interested to know.

[windandwaves]

Gazornenplat wrote:

How does this site work? .
Here is how it works in mysql:

SELECT t2.page_name,Co unt(t2.page_nam e) AS popularity FROM mytable AS
t1
LEFT JOIN mytable AS t2 ON t1.session_id = t2.session_id
WHERE t1.page_name = 'a'
AND t2.page_name <> 'a'
GROUP BY t2.page_name
ORDER BY Count(t2.page_n ame) DESC
LIMIT 5

where mytable is a list of unique combinations of session IDs and pages
visited.
e.g. a table with the following fields:

ID, session_id, page_name

where you can only have unique combos of session_id and page_names

The sql will give you a list of the five most popular pages for people who
visited page "a"

Why do you need to exclude people from pages
that they have been to before?

If you publish this list with links to these "also popular" pages, then you
need to exclude these visits from my_table, otherwise it becomes a
self-fulfilling prophecy. That is, once a page is popular, it will become
more popular because it is popular, etc....

And why does it mean less if you visit
more pages?

People who visit many pages will have more influence on the "also popular"
list. However, the link for them between page a and b is less strong,
because there is also a link between page a and c, a and d, a and e, and so
on. While someone who only visits page a and b shows a clear link.

I am actually going to look at more than just page visits, I am going to
look at things like click-throughs to links from a page and email message as
these will be more meaningful than just page views.

HTH

- Nicolaas