Каков наилучший способ вычислить сходство между строками в таблице на основе ассоциации?

Question

Предположим, у каждого человека есть коллекция любимых книг.

Итак, у меня есть таблица для:

• лицо
• Книга
• Ассоциация между человеком и книгой (объединенный стол для MxN)

Я хочу получить людей, похожих на человека1, на основе перекрытия любимых книг. То есть: чем больше у них общих книг, тем больше они похожи.

Мне не нужно использовать только SQL для решения этой проблемы. Я мог бы также использовать программирование. Я использую SQL Server 2008 и C #.

Какое решение вы бы использовали, эксперты?

Answer 1

Это может быть не самым эффективным, но это относительно просто:

WITH SimlarBookPrefs(person_id, similar_person_id, booksInCommon) AS
(
 Select p1.person_id, p2.person_id AS simlar_person_id,   
 /* Find the number of books p1 and p2 have in common */
   (SELECT COUNT(*) FROM PersonBook pb1, PersonBook pb2 
     JOIN pb1=book_id=pb2.book_id
   WHERE pb1.person_id=p1.person_id AND pb2.person_id=p2.person_id) As BooksInCommon
   FROM Person p1 CROSS JOIN Person p2
)

Это даст вам каждого человека, список других лиц и общее количество книг.

Чтобы получить наиболее похожего человека, добавьте (в том же запросе)

SELECT TOP 1 similar_person_id FROM SimilarBookPrefs 
   WHERE person_id = <person_to_match>
   ORDER By booksInCommon DESC;

Первая часть не обязательно должна быть CTE (т. Е. WITH ...), это может быть представление или даже производная таблица. Для краткости это CTE.

Answer 2

Если бы я делал это в C #, я мог бы заняться этим вот так

var query = from personBook in personBooks
            where personBook.PersonId != basePersonId // ID of person to match
            join bookbase in personBooks
            on personBook.BookId equals bookbase.BookId
            where bookbase.PersonId == basePersonId // ID of person to match
            join person in persons 
            on personBook.PersonId equals person.Id 
            group person by person into bookgroup
            select new
            {
                Person = bookgroup.Key, 
                BooksInCommon = bookgroup.Count()
            };

Скорее всего, это можно сделать с помощью структуры сущностей или Linq to SQL, или просто напрямую перевести на SQL.

Полный пример кода

class CommonBooks
{
    static void Main()
    {
        List<Person> persons = new List<Person>()
        {
            new Person(1, "Jane"), new Person(2, "Joan"), new Person(3, "Jim"), new Person(4, "John"), new Person(5, "Jill")
        };

        List<Book> books = new List<Book>()
        {
            new Book(1), new Book(2), new Book(3), new Book(4), new Book(5)
        };

        List<PersonBook> personBooks = new List<PersonBook>()
        {
            new PersonBook(1,1), new PersonBook(1,2), new PersonBook(1,3), new PersonBook(1,4), new PersonBook(1,5), 
            new PersonBook(2,2), new PersonBook(2,3), new PersonBook(2,5), 
            new PersonBook(3,2), new PersonBook(3,4), new PersonBook(3,5), 
            new PersonBook(4,1), new PersonBook(4,4),
            new PersonBook(5,1), new PersonBook(5,3), new PersonBook(5,5)
        };

        int basePersonId = 4; // person to match likeness

        var query = from personBook in personBooks
                    where personBook.PersonId != basePersonId
                    join bookbase in personBooks
                    on personBook.BookId equals bookbase.BookId
                    where bookbase.PersonId == basePersonId
                    join person in persons
                    on personBook.PersonId equals person.Id
                    group person by person into bookgroup
                    select new
                    {
                        Person = bookgroup.Key,
                        BooksInCommon = bookgroup.Count()
                    };

        foreach (var item in query)
        {
            Console.WriteLine("{0}\t{1}", item.Person.Name, item.BooksInCommon);
        }

        Console.Read();
    }
}

class Person
{
    public int Id { get; set; }
    public string Name { get; set; }
    public Person(int id, string name) { Id = id; Name = name; }
}

class Book
{
    public int Id { get; set; }
    public Book(int id) { Id = id; }
}

class PersonBook
{
    public int PersonId { get; set; }
    public int BookId { get; set; }
    public PersonBook(int personId, int bookId) { PersonId = personId; BookId = bookId; }
}

Answer 3

Проблема, которую вы описываете, обычно называется «коллективной фильтрацией» и решается с помощью «рекомендательных систем». Поиск в Google по любому из этих терминов должен привести к большому количеству полезной информации.