本文详细阐述了如何在推荐系统中构建和利用无权重图来识别“密切联系人”。通过解析用户和活动数据，将数据结构化为图，其中个人作为节点，共享社区、学校或雇主的联系则构成边。文章提供了数据读取、存储的优化方案，并展示了如何构建邻接列表表示的图，以高效地发现并管理用户间的关系，同时考虑隐私设置，为构建基于社交关系的推荐系统奠定基础。
1. 理解图数据结构在推荐系统中的应用
在构建基于人际关系的推荐系统时，图数据结构是一种极其有效且直观的建模工具。它允许我们将系统中的实体（例如人）表示为图的节点（Vertices），将实体之间的关系（例如“密切联系人”）表示为图的边（Edges）。对于本场景，识别“密切联系人”的定义是：共享相同社区、学校或雇主的人。这是一个典型的无权重图问题，因为我们只关心是否存在关系，而不关心关系的强度。
2. 数据捕获与结构化存储
首先，我们需要从提供的CSV文件中准确地读取并存储人员（Person）和活动（Activity）数据。原始代码在循环中读取数据但未将其存储到任何集合中，这导致数据丢失。正确的做法是在读取每个对象后，将其添加到相应的列表中。
2.1 定义数据模型
为了更好地组织数据，我们假设存在 Person 和 Activity 类，它们分别封装了人员和活动的信息。
// 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; // "Y" for privacy requested, "N" for no privacy
// 构造函数、getter和setter方法
public Person() {}
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;
}
public String getFirstname() { return firstname; }
public void setFirstname(String firstname) { this.firstname = firstname; }
public String getLastname() { return lastname; }
public void setLastname(String lastname) { this.lastname = lastname; }
public String getPhone() { return phone; }
public void setPhone(String phone) { this.phone = phone; }
public String getEmail() { return email; }
public void setEmail(String email) { this.email = email; }
public String getCommunity() { return community; }
public void setCommunity(String community) { this.community = community; }
public String getSchool() { return school; }
public void setSchool(String school) { this.school = school; }
public String getEmployer() { return employer; }
public void setEmployer(String employer) { this.employer = employer; }
public String getPrivacy() { return privacy; }
public void setPrivacy(String privacy) { this.privacy = privacy; }
@Override
public String toString() {
return firstname + " " + lastname;
}
// 为了在Map中使用Person作为键，需要重写equals和hashCode方法
@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);
}
}
// Activities.java (简化，仅为示例)
public class Activities {
private String firstname;
private String lastname;
private String activity;
// 构造函数、getter和setter方法
public Activities() {}
public String getFirstname() { return firstname; }
public void setFirstname(String firstname) { this.firstname = firstname; }
public String getLastname() { return lastname; }
public void setLastname(String lastname) { this.lastname = lastname; }
public String getActivity() { return activity; }
public void setActivity(String activity) { this.activity = activity; }
}2.2 优化数据读取与存储
修改 InfoReader 类，在读取文件时将 Person 和 Activities 对象存储到 ArrayList 中。
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 persons = new ArrayList<>();
private List activities = new ArrayList<>();
public void ReadInfo() {
// 读取人员数据
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;
}
Person newPerson = new Person(
personComponents[0].trim(), // firstname
personComponents[1].trim(), // lastname
personComponents[2].trim(), // phone
personComponents[3].trim(), // email
personComponents[4].trim(), // community
personComponents[5].trim(), // school
personComponents[6].trim(), // employer
personComponents[7].trim() // privacy
);
persons.add(newPerson); // 存储Person对象
}
personScanner.close();
} catch (FileNotFoundException e) {
System.err.println("Person file not found: " + e.getMessage());
throw new RuntimeException("Error reading person data", e);
}
// 读取活动数据
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;
}
Activities newActivity = new Activities();
newActivity.setFirstname(activityComponents[0].trim());
newActivity.setLastname(activityComponents[1].trim());
newActivity.setActivity(activityComponents[2].trim());
activities.add(newActivity); // 存储Activity对象
}
activityScanner.close();
} catch (FileNotFoundException e) {
System.err.println("Activity file not found: " + e.getMessage());
throw new RuntimeException("Error reading activity data", e);
}
}
public List getPersons() {
return persons;
}
public List getActivities() {
return activities;
}
} 3. 构建无权重图
有了存储在 persons 列表中的所有 Person 对象后，我们可以开始构建图。在本例中，我们将使用邻接列表（Adjacency List）来表示图，因为它对于稀疏图（即边相对较少的图）来说空间效率更高。
3.1 图的表示
图可以表示为一个 Map
3.2 构建图的算法
遍历 persons 列表中的每一个人，然后将当前人与列表中的其他所有人进行比较。如果他们符合“密切联系人”的定义（共享社区、学校或雇主），则在图的邻接列表中添加一条边。
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class RecommendationGraph {
private Map> adjacencyList; // 使用Set避免重复边
public RecommendationGraph() {
this.adjacencyList = new HashMap<>();
}
/**
* 根据人员列表构建无权重图。
* 节点是Person对象，边表示“密切联系人”关系。
* @param persons 所有人员的列表
*/
public void buildGraph(List persons) {
// 确保所有人员都作为节点存在于邻接列表中
for (Person person : persons) {
adjacencyList.putIfAbsent(person, new HashSet<>());
}
// 遍历所有人员对，建立关系
for (int i = 0; i < persons.size(); i++) {
Person person1 = persons.get(i);
for (int j = i + 1; j < persons.size(); j++) { // 避免重复和自环
Person person2 = persons.get(j);
// 判断是否为密切联系人
boolean isCloseContact = false;
if (!person1.getCommunity().isEmpty() && person1.getCommunity().equals(person2.getCommunity())) {
isCloseContact = true;
}
if (!person1.getSchool().isEmpty() && person1.getSchool().equals(person2.getSchool())) {
isCloseContact = true;
}
if (!person1.getEmployer().isEmpty() && person1.getEmployer().equals(person2.getEmployer())) {
isCloseContact = true;
}
if (isCloseContact) {
// 如果是密切联系人，则在两者之间添加无向边
adjacencyList.get(person1).add(person2);
adjacencyList.get(person2).add(person1);
}
}
}
}
/**
* 获取指定人员的密切联系人列表。
* @param person 目标人员
* @return 密切联系人列表，如果不存在则返回空Set
*/
public Set getCloseContacts(Person person) {
return adjacencyList.getOrDefault(person, new HashSet<>());
}
/**
* 打印图的结构（可选，用于调试）
*/
public void printGraph() {
for (Map.Entry> entry : adjacencyList.entrySet()) {
System.out.print(entry.getKey().toString() + " -> ");
for (Person neighbor : entry.getValue()) {
System.out.print(neighbor.toString() + ", ");
}
System.out.println();
}
}
} 4. 生成推荐和隐私处理
在构建了图并能够查询一个人的密切联系人之后，下一步是根据这些关系生成推荐。同时，我们必须严格遵守用户的隐私设置。
4.1 隐私筛选
如果一个人请求了隐私（privacy 属性为 "Y"），那么不应向该人发送任何推荐，也不应将该人推荐给其他人。这意味着在生成推荐时，我们需要过滤掉这些用户。
4.2 推荐生成示例
假设我们要为 targetPerson 推荐活动，我们可以查看其密切联系人的活动，但要排除那些设置了隐私的联系人。
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;
public class RecommendationSystem {
private RecommendationGraph graph;
private List allActivities; // 所有活动数据
public RecommendationSystem(RecommendationGraph graph, List allActivities) {
this.graph = graph;
this.allActivities = allActivities;
}
/**
* 为目标人员生成活动推荐。
* 推荐基于其未设置隐私的密切联系人所参与的活动。
* @param targetPerson 目标人员
* @return 推荐的活动列表
*/
public List generateRecommendations(Person targetPerson) {
Set recommendedActivities = new HashSet<>();
// 1. 获取目标人员的密切联系人
Set closeContacts = graph.getCloseContacts(targetPerson);
// 2. 筛选出未设置隐私的联系人
Set publicContacts = closeContacts.stream()
.filter(p -> "N".equalsIgnoreCase(p.getPrivacy())) // 假设"N"表示未设置隐私
.collect(Collectors.toSet());
// 3. 收集这些联系人参与的活动
for (Person contact : publicContacts) {
// 查找该联系人参与的所有活动
allActivities.stream()
.filter(activity -> activity.getFirstname().equals(contact.getFirstname()) &&
activity.getLastname().equals(contact.getLastname()))
.map(Activities::getActivity)
.forEach(recommendedActivities::add);
}
// 4. 可以进一步过滤掉targetPerson自己已经参与的活动，或进行排序等
// (此示例中未实现，根据具体需求添加)
return new ArrayList<>(recommendedActivities);
}
public static void main(String[] args) {
// 1. 读取并存储数据
InfoReader reader = new InfoReader();
reader.ReadInfo();
List persons = reader.getPersons();
List activities = reader.getActivities();
// 2. 构建图
RecommendationGraph graph = new RecommendationGraph();
graph.buildGraph(persons);
System.out.println("--- 图结构 ---");
graph.printGraph();
// 3. 初始化推荐系统并生成推荐
RecommendationSystem recSystem = new RecommendationSystem(graph, activities);
// 示例：为 Rajay Mccalla 生成推荐
Person rajay = persons.stream()
.filter(p -> "Rajay".equals(p.getFirstname()) && "Mccalla".equals(p.getLastname()))
.findFirst()
.orElse(null);
if (rajay != null) {
System.out.println("\n--- 为 " + rajay + " 生成推荐 ---");
List recommendations = recSystem.generateRecommendations(rajay);
if (recommendations.isEmpty()) {
System.out.println("没有可用的推荐。");
} else {
recommendations.forEach(System.out::println);
}
} else {
System.out.println("未找到 Rajay Mccalla。");
}
// 示例：为 Winston William 生成推荐 (假设他有联系人)
Person winston = persons.stream()
.filter(p -> "Winston".equals(p.getFirstname()) && "William".equals(p.getLastname()))
.findFirst()
.orElse(null);
if (winston != null) {
System.out.println("\n--- 为 " + winston + " 生成推荐 ---");
List recommendations = recSystem.generateRecommendations(winston);
if (recommendations.isEmpty()) {
System.out.println("没有可用的推荐。");
} else {
recommendations.forEach(System.out::println);
}
}
}
} 5. 注意事项与总结
- 数据清洗与验证： 实际应用中，CSV文件中的数据可能不规范，例如缺少字段、包含额外空格等。在解析时应进行更严格的验证和清洗（例如 trim() 方法的使用）。
-
效率考量： buildGraph 方法的时间复杂度为 O(N^2)，其中 N 是人员数量。对于非常庞大的数据集，这可能成为性能瓶颈。可以考虑使用更高效的数据结构或算法来优化关系匹配过程，例如为 community、school、employer 创建索引（Map
>），然后通过索引来查找共同点，将复杂度降低到 O(N * M)，M 为平均每个属性的共享人数。 - 图的类型： 本教程构建的是无向无权重图。如果需要表示关系的强度（例如，共享两个或三个共同点的人联系更紧密），则需要构建有权重图。
- 隐私保护： 隐私字段的处理至关重要。确保在任何推荐逻辑中都尊重用户的隐私设置。
- 推荐多样性与新颖性： 简单的基于共同联系人活动的推荐可能导致推荐同质化。实际系统中需要结合更多算法（如协同过滤、内容推荐）来提高推荐的多样性和新颖性。
通过以上步骤，我们成功地将人员关系建模为无权重图，并在此基础上实现了基于密切联系人和隐私设置的初步推荐系统。这种图方法为理解和利用复杂的人际关系提供了一个坚实的基础。
