构建基于非加权图的推荐系统：数据结构与关系建模-java教程-PHP中文网

构建基于非加权图的推荐系统：数据结构与关系建模

本文详细阐述如何为推荐系统构建非加权图，重点解决数据捕获、存储及关系建模问题。通过将人员信息和活动数据有效组织成图结构，并结合“密切联系人”定义和隐私设置，实现高效的推荐逻辑。教程涵盖数据加载、使用邻接列表构建图、识别联系人关系以及处理隐私限制等关键步骤，旨在提供一个清晰、专业的指导框架。

1. 引言：图结构在推荐系统中的应用

在构建推荐系统时，有效地表示实体（如人）及其之间的复杂关系至关重要。对于需要识别“密切联系人”并基于共享属性（如社区、学校、雇主）进行推荐的场景，图（Graph）是一种极其合适的数据结构。图能够直观地将每个人视为一个节点（Vertex），将他们之间的特定关系视为边（Edge）。本教程将指导您如何从原始数据构建一个非加权图，并利用该图实现一个基础的推荐系统。

2. 数据捕获与初始存储

在构建图之前，首要任务是正确地从文件读取数据并将其存储在内存中。原始代码虽然实现了文件读取和对象创建，但缺少将这些创建的对象持久化存储的步骤。为了后续构建图结构，我们需要将每个 Person 和 Activity 对象存储到相应的集合中。

首先，定义 Person 和 Activity 类，它们应包含从CSV文件读取的相应属性。

// Person.java
public class Person {
    private String firstname;
    private String lastname;
    private String phone;
    private String email;
    private String community;
    private String school;
    private String employer;
    private String privacy; // "N" for no privacy, "Y" for privacy

    // 构造函数
    public Person(String firstname, String lastname, String phone, String email, 
                  String community, String school, String employer, String privacy) {
        this.firstname = firstname;
        this.lastname = lastname;
        this.phone = phone;
        this.email = email;
        this.community = community;
        this.school = school;
        this.employer = employer;
        this.privacy = privacy;
    }

    // Getters for all properties
    public String getFirstname() { return firstname; }
    public String getLastname() { return lastname; }
    public String getCommunity() { return community; }
    public String getSchool() { return school; }
    public String getEmployer() { return employer; }
    public String getPrivacy() { return privacy; }

    // 为了方便，可以添加一个获取全名的方法
    public String getFullName() {
        return firstname + " " + lastname;
    }

    // 重写 equals 和 hashCode 方法，确保 Person 对象的唯一性判断
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return firstname.equals(person.firstname) &&
               lastname.equals(person.lastname); // 假设名字组合唯一
    }

    @Override
    public int hashCode() {
        return java.util.Objects.hash(firstname, lastname);
    }

    @Override
    public String toString() {
        return "Person{" +
               "firstname='" + firstname + '\'' +
               ", lastname='" + lastname + '\'' +
               ", community='" + community + '\'' +
               ", school='" + school + '\'' +
               ", employer='" + employer + '\'' +
               ", privacy='" + privacy + '\'' +
               '}';
    }
}

// Activity.java
public class Activity {
    private String firstname;
    private String lastname;
    private String activityDescription;

    public Activity(String firstname, String lastname, String activityDescription) {
        this.firstname = firstname;
        this.lastname = lastname;
        this.activityDescription = activityDescription;
    }

    public String getFirstname() { return firstname; }
    public String getLastname() { return lastname; }
    public String getActivityDescription() { return activityDescription; }

    public String getPersonFullName() {
        return firstname + " " + lastname;
    }

    @Override
    public String toString() {
        return "Activity{" +
               "firstname='" + firstname + '\'' +
               ", lastname='" + lastname + '\'' +
               ", activityDescription='" + activityDescription + '\'' +
               '}';
    }
}

登录后复制

接下来，修改 InfoReader 类，使用 ArrayList 来存储读取到的 Person 和 Activity 对象。

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class InfoReader {

    private List<Person> persons = new ArrayList<>();
    private List<Activity> activities = new ArrayList<>();

    public void readInfo() {
        // 读取 Person 数据
        try {
            String fileLocation = File.separator + "Users" + File.separator + "user" + File.separator + "Downloads" + File.separator + "SamplefilePersons2022Oct31text.csv";
            File personListFile = new File(fileLocation);
            Scanner personScanner = new Scanner(personListFile);

            while (personScanner.hasNextLine()) {
                String nextLine = personScanner.nextLine();
                String[] personComponents = nextLine.split(",");

                // 确保数据完整性，防止数组越界
                if (personComponents.length < 8) {
                    System.err.println("Skipping malformed person line: " + nextLine);
                    continue;
                }

                String firstname = personComponents[0].trim();
                String lastname = personComponents[1].trim();
                String phone = personComponents[2].trim();
                String email = personComponents[3].trim();
                String community = personComponents[4].trim();
                String school = personComponents[5].trim();
                String employer = personComponents[6].trim();
                String privacy = personComponents[7].trim();

                Person newPerson = new Person(firstname, lastname, phone, email, community, school, employer, privacy);
                persons.add(newPerson); // 将 Person 对象添加到列表中
            }
            personScanner.close();
        } catch (FileNotFoundException e) {
            System.err.println("Person file not found: " + e.getMessage());
            throw new RuntimeException(e);
        }

        // 读取 Activity 数据
        try {
            String fileLocation = File.separator + "Users" + File.separator + "user" + File.separator + "Downloads" + File.separator + "SamplefileActivities2022Oct31text.csv";
            File activityListFile = new File(fileLocation);
            Scanner activityScanner = new Scanner(activityListFile);

            while (activityScanner.hasNextLine()) {
                String nextLine = activityScanner.nextLine();
                String[] activityComponents = nextLine.split(",");

                if (activityComponents.length < 3) {
                    System.err.println("Skipping malformed activity line: " + nextLine);
                    continue;
                }

                String firstname = activityComponents[0].trim();
                String lastname = activityComponents[1].trim();
                String activityDescription = activityComponents[2].trim();

                Activity newActivity = new Activity(firstname, lastname, activityDescription);
                activities.add(newActivity); // 将 Activity 对象添加到列表中
            }
            activityScanner.close();
        } catch (FileNotFoundException e) {
            System.err.println("Activity file not found: " + e.getMessage());
            throw new RuntimeException(e);
        }
    }

    public List<Person> getPersons() {
        return persons;
    }

    public List<Activity> getActivities() {
        return activities;
    }
}

登录后复制

注意事项：

trim() 方法用于移除字符串两端的空白字符，避免数据匹配问题。
添加了简单的错误处理，以防CSV行格式不正确。
Person 类中的 equals() 和 hashCode() 方法被重写，这对于在 HashMap 或 HashSet 中使用 Person 对象作为键或元素至关重要，确保每个 Person 对象被正确识别。这里假设姓和名的组合可以唯一标识一个人。在实际应用中，通常会使用唯一的ID。

3. 构建非加权图：邻接列表表示

图的表示方法有多种，对于稀疏图（边相对较少）和需要快速查找某个节点所有邻居的场景，邻接列表（Adjacency List）是高效且常用的选择。我们将使用 Map<Person, List<Person>> 来表示图，其中 Person 对象是图中的节点，List<Person> 存储与该节点直接相连的所有邻居节点。

3.1 定义“密切联系人”关系

根据问题描述，“密切联系人”定义为共享相同社区、学校或雇主的任何人。这意味着如果两个人至少在一个这些属性上匹配，他们之间就存在一条边。

即构数智人

即构数智人是由即构科技推出的AI虚拟数字人视频创作平台，支持数字人形象定制、短视频创作、数字人直播等。

查看详情

3.2 实现图构建逻辑

以下是构建图的步骤和示例代码：

初始化图结构： 创建一个 Map<Person, List<Person>> 来存储邻接列表。
遍历所有人员： 对于列表中的每一个人 p1。
比较人员关系： 将 p1 与列表中的所有其他人 p2 进行比较。
判断密切联系： 如果 p1 和 p2 满足“密切联系人”的条件（共享社区、学校或雇主），则在它们之间添加一条无向边。由于是非加权图，只需记录连接关系。

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class RecommendationSystem {

    private Map<Person, Set<Person>> graph; // 使用Set来存储邻居，避免重复

    public RecommendationSystem(List<Person> persons) {
        this.graph = new HashMap<>();
        buildGraph(persons);
    }

    /**
     * 构建非加权图，识别密切联系人。
     * 
     * @param persons 所有人员列表
     */
    private void buildGraph(List<Person> persons) {
        // 初始化每个人的邻居列表
        for (Person person : persons) {
            graph.put(person, new HashSet<>());
        }

        // 遍历所有人员对，建立关系
        for (int i = 0; i < persons.size(); i++) {
            Person p1 = persons.get(i);
            for (int j = i + 1; j < persons.size(); j++) { // 避免重复比较和自连接
                Person p2 = persons.get(j);

                if (isCloseContact(p1, p2)) {
                    // 添加无向边
                    graph.get(p1).add(p2);
                    graph.get(p2).add(p1);
                }
            }
        }
    }

    /**
     * 判断两个人是否是密切联系人。
     * 
     * @param p1 第一个人
     * @param p2 第二个人
     * @return 如果是密切联系人则返回 true，否则返回 false
     */
    private boolean isCloseContact(Person p1, Person p2) {
        // 共享社区
        if (!p1.getCommunity().isEmpty() && p1.getCommunity().equals(p2.getCommunity())) {
            return true;
        }
        // 共享学校
        if (!p1.getSchool().isEmpty() && p1.getSchool().equals(p2.getSchool())) {
            return true;
        }
        // 共享雇主
        if (!p1.getEmployer().isEmpty() && p1.getEmployer().equals(p2.getEmployer())) {
            return true;
        }
        return false;
    }

    /**
     * 获取指定人员的推荐列表。
     * 推荐逻辑：获取其所有密切联系人，但排除请求隐私的人员。
     * 
     * @param targetPersonName 目标人员的全名 (firstname lastname)
     * @return 推荐人员列表
     */
    public List<Person> getRecommendations(String targetPersonName) {
        Person targetPerson = null;
        // 找到目标 Person 对象
        for (Person p : graph.keySet()) {
            if (p.getFullName().equals(targetPersonName)) {
                targetPerson = p;
                break;
            }
        }

        if (targetPerson == null) {
            System.out.println("Target person not found: " + targetPersonName);
            return new ArrayList<>();
        }

        List<Person> recommendations = new ArrayList<>();
        Set<Person> closeContacts = graph.get(targetPerson);

        if (closeContacts != null) {
            for (Person contact : closeContacts) {
                // 检查联系人是否请求了隐私
                if (!"Y".equalsIgnoreCase(contact.getPrivacy())) { // "N" 表示没有隐私，"Y" 表示有隐私
                    recommendations.add(contact);
                }
            }
        }
        return recommendations;
    }

    // 可选：打印图结构以进行调试
    public void printGraph() {
        System.out.println("Graph Structure:");
        for (Map.Entry<Person, Set<Person>> entry : graph.entrySet()) {
            System.out.print(entry.getKey().getFullName() + " -> ");
            for (Person neighbor : entry.getValue()) {
                System.out.print(neighbor.getFullName() + ", ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        InfoReader reader = new InfoReader();
        reader.readInfo(); // 读取数据

        List<Person> allPersons = reader.getPersons();
        // List<Activity> allActivities = reader.getActivities(); // 活动数据目前未用于图构建

        RecommendationSystem recommender = new RecommendationSystem(allPersons);
        recommender.printGraph(); // 打印构建的图

        // 示例：获取 Rajay Mccalla 的推荐
        List<Person> rajayRecommendations = recommender.getRecommendations("Rajay Mccalla");
        System.out.println("\nRecommendations for Rajay Mccalla:");
        if (rajayRecommendations.isEmpty()) {
            System.out.println("No recommendations or all contacts requested privacy.");
        } else {
            for (Person p : rajayRecommendations) {
                System.out.println("- " + p.getFullName() + " (Community: " + p.getCommunity() + ")");
            }
        }

        // 假设有一个人Winston William，并且他有联系人
        // 需要确保测试数据中包含Winston William及其联系人
        // List<Person> winstonRecommendations = recommender.getRecommendations("Winston William");
        // System.out.println("\nRecommendations for Winston William:");
        // for (Person p : winstonRecommendations) {
        //     System.out.println("- " + p.getFullName());
        // }
    }
}

登录后复制

4. 推荐逻辑与隐私处理

在 getRecommendations 方法中，我们实现了核心的推荐逻辑：

查找目标人员： 根据全名找到对应的 Person 对象。
获取直接联系人： 从图的邻接列表中获取目标人员的所有直接邻居（即密切联系人）。
隐私过滤： 遍历这些联系人，只将 privacy 属性不是 "Y"（即未请求隐私）的人员添加到推荐列表中。

5. 总结与注意事项

通过上述步骤，我们成功地将人员数据转化为一个非加权图，并基于此图实现了基础的推荐功能。

总结：

数据存储是基础： 确保从文件读取的数据被正确存储在 ArrayList 等集合中，是后续处理的前提。
图结构选择： 邻接列表对于表示稀疏图和快速查找邻居非常有效。
关系建模： 明确定义实体之间的关系（如“密切联系人”的条件），是构建有效图的关键。
隐私处理： 将业务规则（如隐私设置）融入到推荐逻辑中，确保推荐的合规性。

注意事项：

唯一标识符： 在实际应用中，应为每个人分配一个唯一的ID（例如，数据库主键），而不是仅仅依赖姓名组合。这可以避免同名问题，并提高数据处理效率。
图的遍历算法： 对于更复杂的推荐需求（如“朋友的朋友”推荐），可能需要使用广度优先搜索（BFS）或深度优先搜索（DFS）等图遍历算法。
性能优化： 对于非常大的数据集，图的构建和遍历可能需要优化，例如使用更高效的数据结构或并行处理。
数据清洗： 真实世界的数据往往不规范，可能包含空值、格式错误等。在读取和处理数据时，应增加更健壮的错误检查和数据清洗机制。
活动数据利用： 当前的图只基于“密切联系人”关系。活动数据（Activities）可以用于构建更丰富的推荐，例如基于共同兴趣或行为的推荐，这可能需要构建多模态图或加权图。
可扩展性： 随着系统复杂度的增加，可以考虑使用专门的图数据库（如Neo4j）来管理和查询图数据。