การจัดกลุ่มหลายสัมพันธ์ (Multi-relational Clustering) คืออะไร?

การจัดกลุ่มหลายสัมพันธ์ (Multi-relational clustering) เป็นกระบวนการแบ่งวัตถุข้อมูลเป็นชุดของกลุ่มตามความคล้ายคลึง โดยใช้ข้อมูลในหลายสัมพันธ์ (relations) ในส่วนนี้จะแนะนำ CrossClus (Cross-relational Clustering with user guidance) อัลกอริทึมสำหรับการจัดกลุ่มหลายสัมพันธ์ที่สำรวจวิธีใช้คำแนะนำจากผู้ใช้ในการจัดกลุ่มและการแพร่กระจาย ID ของ tuple เพื่อหลีกเลี่ยงการ join แบบจริง (physical joins)

ความท้าทายหลักหนึ่งของการจัดกลุ่มหลายสัมพันธ์คือมีแอตทริบิวต์มากเกินไปในสัมพันธ์ต่างๆ และปกติแล้วมีเพียงส่วนเล็กน้อยที่เกี่ยวข้องกับงานจัดกลุ่มเฉพาะ

พิจารณาฐานข้อมูลแผนกวิทยาการคอมพิวเตอร์ เพื่อจัดกลุ่มนักศึกษา แอตทริบิวต์ครอบคลุมหลายด้านข้อมูล เช่น วิชาที่นักศึกษาเรียน, ผลงานตีพิมพ์, ที่ปรึกษาและกลุ่มวิจัยของนักศึกษา ฯลฯ

ผู้ใช้มักสนใจจัดกลุ่มนักศึกษาโดยใช้ด้านข้อมูลเฉพาะ (เช่น จัดกลุ่มตาม lĩnh vựcวิจัย) ผู้ใช้มักเข้าใจความต้องการของแอปพลิเคชันและความหมายของข้อมูลดี ดังนั้น การควบคุมของผู้ใช้ในโครงสร้างคิวรีที่เรียบง่าย สามารถนำมาเพิ่มประสิทธิภาพและคุณภาพของการจัดกลุ่มหลายสัมพันธ์มิติสูงได้

CrossClus รับคิวรีจากผู้ใช้ที่มีสัมพันธ์เป้าหมาย (target relation) และแอตทริบิวต์ที่เกี่ยวข้องหนึ่งหรือหลายตัว ซึ่งร่วมกันระบุเป้าหมายการจัดกลุ่มของผู้ใช้ CrossClus กำหนดแอตทริบิวต์หลายสัมพันธ์ (multi-relational attributes) แอตทริบิวต์หลายสัมพันธ์ A' ถูกกำหนดโดยเส้นทาง join R_t ⋈ R₁ … ⋈ R_k และแอตทริบิวต์ R_k.A และอาจมีออเปอเรเตอร์รวม (aggregation operator) เช่น average, count, max

A' ถูกแทนอย่างเป็นทางการด้วย [A'.join path, A'.attr, A'.aggr] โดย A'.aggr เป็นตัวเลือก แอตทริบิวต์หลายสัมพันธ์ A' เป็นคุณลักษณะเชิงหมวดหมู่ (categorical) หรือตัวเลข (numerical) ขึ้นอยู่กับว่า R_k.A เป็น categorical หรือ numerical หาก A' เป็นคุณลักษณะเชิงหมวดหมู่ สำหรับ tuple เป้าหมาย t, t.A' แสดงการกระจายค่าใน tuples ใน R_k ที่ join กับ t ได้

ในกระบวนการจัดกลุ่มหลายสัมพันธ์ CrossClus ต้องค้นหาแอตทริบิวต์ที่เกี่ยวข้องข้ามหลายสัมพันธ์ CrossClus ต้องจัดการสองความท้าทายหลักในการค้นหา: ข้อแรก สัมพันธ์เป้าหมาย R_t มัก join กับสัมพันธ์ที่ไม่ใช่เป้าหมาย R ได้หลายเส้นทาง join และแต่ละแอตทริบิวต์ใน R สามารถเป็นแอตทริบิวต์หลายสัมพันธ์ได้ ไม่สามารถค้นหาแบบทุกกรณี (exhaustive search) ในพื้นที่ค้นหาที่ใหญ่โตนี้ได้ ข้อที่สอง ในจำนวนแอตทริบิวต์มหาศาล บางตัวเกี่ยวข้องกับคิวรีผู้ใช้ (เช่น ที่ปรึกษาของนักศึกษาเกี่ยวกับสาขาวิจัย) ในขณะที่อีกมากมายไม่เกี่ยวข้อง (เช่น ข้อมูลส่วนตัวของเพื่อนร่วมชั้น)