仮想要素追加法による階層的クラスタリングの安定性の解析

全文

(1)社団法人情報処理学会研究報告 IPSJ SIG Technical Report. 2006−MPS−58（9） 2006／3／16. ઒ᗐⷐ⚛ㅊടᴺߦࠃࠆ㓏ጀ⊛ࠢ࡜ࠬ࠲࡝ࡦࠣߩ቟ቯᕈߩ⸃ᨆ ධ 㔕 ᜏ ᢪ ⮮ 㓉 ᢥ ች ᧛㧔ਛ ᧛㧕ᶈ ሶ ᧲੩ㄘᎿᄢቇ ᄢቇ㒮 ↢‛ࠪࠬ࠹ࡓᔕ↪⑼ቇᢎ⢒ㇱ ᧄႎ๔ߢߪ㧘㓏ጀ⊛ࠢ࡜ࠬ࠲࡝ࡦࠣ⚿ᨐߩ቟ቯᕈࠍ⸃ᨆߔࠆߚ߼ߩᢙℂࡕ࠺࡞ࠍឭ᩺ߔࠆ㧚ߎ ߩࡕ࠺࡞ߢߪ㧘ᓥ᧪ᚻᴺߩࠃ߁ߥ⛔⸘⊛ಣℂࠍ↪޿ߕߦ㧘઒ᗐⷐ⚛ߩㅊടߦࠃߞߡᐞ૗ቇ⊛ߦ ቟ቯᕈࠍ᷹ࠆߎߣ߇ߢ߈ࠆ㧚ឭ᩺ᴺࠍ 2 ᰴర࡙࡯ࠢ࡝࠶࠼ⓨ㑆ߢߩࠢ࡜ࠬ࠲࡝ࡦࠣߦㆡ↪ߒ㧘㓏ጀ቟ቯᐲࠍ᮸ᒻ࿑਄ߦนⷞൻߔࠆߎߣߢ㧘ߘߩ᦭ലᕈࠍᬌ⸽ߔࠆ㧚. Stability Analysis of Hierarchical Clustering by Adding a Temporary Element TAKU NAGUMO㧘TAKAFUMI SAITO㧘HIROKO NAKAMURA MIYAMURA Graduate School of Bio-Applications & Systems Engineering Tokyo University of Agriculture and Technology In this report, a mathematical model is proposed for analyzing the stability of hierarchical clustering results. In this model, the stability is measured geometrically by adding a temporary element, without using a statistical analysis. The proposed method is applied to clustering examples in 2-dimensional Euclidean space, and the effectiveness is verified by mapping the hierarchical stability onto the dendrogram.. 1. ✜⸒ ࠢ࡜ࠬ࠲ಽᨆᴺߪ㧘ⶄᢙߩ⋧㑐ࠍᜬߟ࠺࡯࠲ࠍߘ ߩ㘃ૃᕈߦၮߠ޿ߡᄖ⊛ၮḰߥߒߦ৻ᗧߦಽ㘃ߔࠆ ߚ߼ߩᚻᴺߢ޽ࠆ㧚ߎࠇ߹ߢߦߐ߹ߑ߹ߥᚻᴺ߇ឭ ᩺ߐࠇߡ߅ࠅ㧘↢‛ቇ߿␠ળ⑼ቇߥߤߩಽ㊁ߢ೑↪ ߐࠇߡ޿ࠆ [1]㧚․ߦㄭᐕߪ㧘ࡃࠗࠝࠗࡦࡈࠜࡑ࠹ ࠖࠢࠬಽ㊁ߦ߅޿ߡਇนᰳߥᛛⴚߣߥߞߡ޿ࠆ㧚 ࠢ࡜ࠬ࠲ಽᨆᴺߪ⚐☴ߦᢙቇ⊛ߥᚻᴺߢ޽ࠅ㧘ߘ ߩᕈ⾰߆ࠄ㧘࠺࡯࠲ߩࠊߕ߆ߥ㆑޿ߦࠃߞߡᓧࠄࠇ ࠆ⚿ᨐ߇ᄢ߈ߊ⇣ߥࠆߎߣ߇޽ࠆ㧚ߘߩߚ߼㧘ࠢ࡜ ࠬ࠲ಽᨆࠍ઒⺑ߩ⑼ቇ⊛ⵣઃߌߥߤߦ૶߁႐วߦߪ㧘 ࠢ࡜ࠬ࠲࡝ࡦࠣಽᨆ⚿ᨐߩ቟ቯᕈࠍ⠨ᘦߦ౉ࠇࠆߎ ߣ߇㊀ⷐߢ޽ࠆ㧚ߒ߆ߒ⃻ታߦߪ㧘ᓧࠄࠇߚ⚿ᨐߩ ቟ቯᕈߦኻߒߡ⠨ኤ߇ⴕࠊࠇࠆߎߣߪዋߥ޿㧚ߘߩ ℂ↱ߣߒߡ㧘ࠢ࡜ࠬ࠲ಽᨆᚻᴺߩ᥉෸ߦᲧߴߡ㧘ߘ ߩ቟ቯᕈߦ㑐ߔࠆ⎇ⓥ߇߹ߛචಽߣߪ޿߃ߕ㧘․ߦ ቟ቯᕈࠍᚻシߦ᳞߼ࠆᚻᴺ߇㐿ᜏߐࠇߡ޿ߥ޿ߎߣ ߇޽ߍࠄࠇࠆ㧚 ᧄႎ๔ߢߪ㧘ࠢ࡜ࠬ࠲ߩㆡಾߥಽഀᢙ߇ᧂ⍮ߩߣ ߈ߦ↪޿ࠄࠇࠆ㓏ጀ⊛ࠢ࡜ࠬ࠲࡝ࡦࠣࠍኻ⽎ߣߒߡ㧘 ߘߩ቟ቯᕈࠍ⸃ᨆߔࠆߚ߼ߩᢙℂࡕ࠺࡞ࠍឭ᩺ߔࠆ㧚 ቟ቯᕈߩᜰᮡߣߒߡ㧘ᓥ᧪ᚻᴺ߇రߩ࠺࡯࠲㓸ว߿ ߘߩㇱಽ㓸วߦ߅ߌࠆࠢ࡜ࠬ࠲ߩ㘃ૃᕈࠍ↪޿ߡ޿ ࠆߩߦኻߒ㧘ឭ᩺ᚻᴺߢߪ㧘రߩ࠺࡯࠲㓸วߦ઒ᗐ −31−. ⊛ߥⷐ⚛ࠍㅊടߒߚ႐วߩ㓏ጀ᭴ㅧߩᄌൻߩ᦭ήߦ ⌕⋡ߔࠆ㧚ߘࠇߦࠃࠅ㧘⛔⸘⊛ᚻᴺࠍ↪޿ࠆߎߣߥ ߊ୘‫ߩޘ‬㓏ጀߏߣߩ቟ቯᐲߩ▚಴߇น⢻ߣߥࠆ㧚ߐ ࠄߦ㧘㓏ጀ቟ቯᐲࠍ᮸ᒻ࿑਄ߦนⷞൻߔࠆᚻᴺߦߟ ޿ߡ߽ឭ᩺ߔࠆ㧚. 2. 㓏ጀ⊛ࠢ࡜ࠬ࠲࡝ࡦࠣߩ቟ቯᕈ ᧄ▵ߢߪ৻⥸⊛ߥ㓏ጀ⊛ࠢ࡜ࠬ࠲࡝ࡦࠣߦߟ޿ߡ ⸃⺑ߒ㧘቟ቯᕈߩ㑐ㅪ⎇ⓥߦߟ޿ߡㅀߴ㧘ߘߩ໧㗴 ὐࠍᜰ៰ߔࠆ㧚. 2.1 㓏ጀ⊛ࠢ࡜ࠬ࠲࡝ࡦࠣ. n ୘ߩⷐ⚛࠺࡯࠲ࠍ߽ߟ࠺࡯࠲㓸วߦኻߒߡ㧘ᦨ ߽ㄭ޿ 2 ୘ߩⷐ⚛㧔޽ࠆ޿ߪࠢ࡜ࠬ࠲㧕ࠍ⚿วߔࠆ ࠢ࡜ࠬ࠲ߩ᮸ ᠲ૞ࠍ n 1 ࿁➅ࠅ㄰ߔߎߣߦࠃߞߡ㧘 ᒻ࿑ࠍ૞ᚑߔࠆಽᨆᴺࠍ㧘㓏ጀ⊛ࠢ࡜ࠬ࠲࡝ࡦࠣߣ ޿߁㧚᮸ᒻ࿑ߩᨑߩ㐳ߐߪ㧘ⷐ⚛㧘޽ࠆ޿ߪࠢ࡜ࠬ ࠲㑆ߩ〒㔌ࠍ⴫ߒߡ޿ࠆ㧚㓏ጀ⊛ࠢ࡜ࠬ࠲࡝ࡦࠣߢ ߪ㧘޽ࠄ߆ߓ߼ࠢ࡜ࠬ࠲ಽഀᢙࠍቯ߼ߥߊߡ߽㧘ㆡ ᒰߥ〒㔌ߢಾᢿߔࠆߎߣߦࠃߞߡછᗧߩᢙߩࠢ࡜ࠬ ࠲ࠍᓧࠆߎߣ߇ߢ߈ࠆ㧚߹ߚ㧘᮸ᒻ࿑ߩ᭎ᒻ߆ࠄࠢ ࡜ࠬ࠲᭴ㅧ㧘ᄢ߹߆ߥⷐ⚛㑆ߩ㑐ଥߥߤࠍ⍮ࠆߎߣ ߽ߢ߈ࠆ㧚.

(2) 2.2 ቟ቯᕈߩ㑐ㅪ⎇ⓥ 㓏ጀ⊛ࠢ࡜ࠬ࠲࡝ࡦࠣߩ቟ቯᕈߦ㑐ߔࠆ⎇ⓥߣߒ ߡߪ㧘ⶄᢙߩ㓏ጀ⊛ࠢ࡜ࠬ࠲࡝ࡦࠣߩ⚿ᨐ㑆ߩ⋧㑐 ᷹ᐲࠍ೑↪ߔࠆᣇᴺ߇ઍ⴫⊛ߢ޽ࠆ[2]㧚ߚߣ߃߫㧘 Corneil ࠄߪ㧘Rand ߩಽ㘃㑆㘃ૃ᷹ᐲ[3]ࠍ቟ቯᕈߦ ↪޿ߡ޿ࠆ[4]㧚߹ߚ㧘Yu ߪࠣ࡜ࡈℂ⺰⊛ߦ቟ቯᕈ ࠍ᷹ࠆᚻᴺࠍឭ᩺ߒߡ޿ࠆ[5]㧚ㄭᐕࠃߊ↪޿ࠄࠇࠆ 㘃ૃ᷹ᐲߣߒߡ㧘Fowlkes ࠄߦࠃߞߡቯ⟵ߐࠇߚ᷹ ᐲ߇޽ࠆ[6]㧚ߎߩ᷹ᐲࠍታ㓙ߦ↪޿ߚ଀ߣߒߡ㧘 Ben-Hur ࠄߩᚻᴺ[7]߇޽ߍࠄࠇࠆ㧚ߎߩᚻᴺߢߪ㧘 రߩ࠺࡯࠲㓸วߩㇱಽ㓸วࠍ࡜ࡦ࠳ࡓߦ 2 ߟ૞ᚑߒ㧘 ߘࠇߙࠇߦߟ޿ߡ㓏ጀ⊛ࠢ࡜ࠬ࠲࡝ࡦࠣࠍⴕ߁㧚ߎ ߩߣ߈㧘2 ߟߩㇱಽ㓸วߩ౒ㅢㇱಽߦ฽߹ࠇࠆⷐ⚛ ߦᵈ⋡ߔࠆ㧚᮸ᒻ࿑ࠍࠢ࡜ࠬ࠲ߦಽഀߔࠆߎߣࠍ⠨ ߃㧘ߘࠇߙࠇߩಽഀߦߟ޿ߡ౒ㅢㇱಽߩⷐ⚛ߩᚲዻ ߒߡ޿ࠆࠢ࡜ࠬ࠲߇ᄌൻߒߡ޿ࠆ߆ุ߆ࠍ㘃ૃᐲߣ ߒߡᢙ୯ൻߒ㧘⛔⸘⊛ߥಣℂࠍⴕߞߡ቟ቯߥࠢ࡜ࠬ ࠲ಽഀࠍᓧࠆ㧚 ߎࠇࠄᣢሽᚻᴺߪಽ㘃㑆ߩ㘃ૃ᷹ᐲߦࠃࠆߚ߼㧘 ⛔⸘⊛ߦ↪޿ߥߌࠇ߫ߥࠄߥ޿ߣ޿߁ᰳὐ߇޽ࠆ㧚. 3. ઒ᗐⷐ⚛ㅊടᴺߦࠃࠆ቟ቯᕈࡕ࠺࡞ ᧄ▵ߢߪ㧘⛔⸘⊛ၮḰࠍ↪޿ߕߦ቟ቯᕈࠍ᷹ࠆᚻ ᴺࠍឭ᩺ߔࠆ㧚߹ߚ㧘ឭ᩺ᴺࠍ 2 ᰴర࡙࡯ࠢ࡝࠶࠼ ⓨ㑆ߦㆡ↪ߒߚ଀ࠍ␜ߔ㧚. 3.1 ઒ᗐⷐ⚛ㅊടᴺߦࠃࠆ቟ቯᕈߩࡕ࠺࡞ൻ ᧄᚻᴺߢߪ㧘రߩ࠺࡯࠲㓸วߦኻߒ㧘ⷐ⚛ࠍᣂߚߦ 1 ୘ㅊടߒߡ㓏ጀ⊛ࠢ࡜ࠬ࠲࡝ࡦࠣࠍⴕ޿㧘ߘߩ૏ ⟎ߦࠃࠆ㓏ጀ᭴ㅧߩᄌൻࠍᬌ಴ߔࠆ㧚ㅊടⷐ⚛ࠍട ߃ߡࠢ࡜ࠬ࠲࡝ࡦࠣߒ㧘ߘߩ߁߃ߢ᮸ᒻ࿑߆ࠄㅊട ⷐ⚛ࠍ೥㒰ߔࠆߎߣߢ㧘ㅊടⷐ⚛ߩࠢ࡜ࠬ࠲࡝ࡦࠣ ߳ߩᓇ㗀ࠍ⺞ߴࠆߎߣ߇ߢ߈ࠆ㧚 ㅊടⷐ⚛ߩ೥㒰ߪ㧘 ㅊടⷐ⚛ࠍߘߩ⚿วኻ⽎ߦหൻߐߖࠆߎߣߢታ⃻ߔ ࠆ㧚ᓧࠄࠇߚࠢ࡜ࠬ࠲᭴ㅧߣ㧘ⷐ⚛ㅊട೨ߩࠢ࡜ࠬ ࠲᭴ㅧࠍᲧセߒ㧘ห৻ߢߥ޿႐วߦߪ㧘ᧄ⾰⊛ߥ㓏 ጀ᭴ㅧߩᄌൻߣߺߥߔ㧚޿߹㧘࿑ 1(a)ߩࠃ߁ߥ 3 ⷐ ⚛߆ࠄߥࠆࠢ࡜ࠬ࠲᭴ㅧ߇޽ࠆߣ߈㧘ⷐ⚛ P ࠍㅊട ߒߡࠢ࡜ࠬ࠲࡝ࡦࠣࠍⴕ߁ߎߣࠍ⠨߃ࠆ㧚 ߎߩߣ߈㧘 ߚߣ߃߫(b)ߩࠃ߁ߥ᭴ㅧߦߥߞߚ႐วߪ㧘ㅊടⷐ⚛ ߢ޽ࠆ P ࠍ㒰ߊߣ㧘㓏ጀ᭴ㅧߪ(c)ߦ␜ߔࠃ߁ߦ(a) ߣᄌൻߒߡ޿ߥ޿㧚ߎࠇߦኻߒߡ㧘(d)ߩࠃ߁ߥ᭴ㅧ ߦߥߞߚ႐วߪ㧘P ࠍ㒰޿ߚᓟߩࠢ࡜ࠬ࠲᭴ㅧߪ(e) ߩࠃ߁ߦᄌൻߒߡ߅ࠅ㧘ᧄ⾰⊛ߥ㓏ጀ᭴ㅧᄌൻߢ޽ ࠆߎߣ߇ࠊ߆ࠆ㧚 ⷐ⚛ߩㅊടߦࠃߞߡ㧘਄⸥ߩࠃ߁ߥᧄ⾰⊛ߥ㓏 ጀ᭴ㅧᄌൻ߇⿠ߎࠆ߆ุ߆ߪ㧘ㅊടⷐ⚛ߩ୯ߦଐሽ ߔࠆ㧚ߎߩߣ߈㧘㓏ጀ᭴ㅧᄌൻࠍᒁ߈⿠ߎߔࠃ߁ߥ −32−. A. P. B C. (b) ଀1䋨Pㅊട䋩. A. B. A㵭. B. C. (c) ଀1䋨P೥㒰䋩. C. A (a) Pㅊട೨. P. B C. (d) ଀2䋨Pㅊട䋩. A㵭 B. C. (e) ଀2䋨P೥㒰䋩. ࿑ 1 ઒ᗐⷐ⚛ P ߩㅊട೥㒰ߦࠃࠆ㓏ጀ᭴ㅧߩᄌൻ ㅊടⷐ⚛୯ߩ▸࿐߇ᄢ߈޿߶ߤ㧘ߘߩࠢ࡜ࠬ࠲᭴ㅧ ߪਇ቟ቯߢ޽ࠆߣ⠨߃ࠆߎߣ߇ߢ߈ࠆ㧚 . 3.2. 㓏ጀ቟ቯᐲߩቯ⟵. ೨㗄ߢㅀߴߚㅊടⷐ⚛୯ߩ▸࿐ߦࠃࠆࠢ࡜ࠬ࠲᭴ ㅧߩ቟ቯߐࠍቯᑼൻߒ㧘㓏ጀ቟ቯᐲߣߒߡቯ⟵ߔࠆ㧚 ߎߎߢߪ㧘ㅊടⷐ⚛ P ߇ A㧘B㧘C ޿ߕࠇ߆ߩⷐ⚛ ߣవߦ⚿วߔࠆ႐วߛߌࠍኻ⽎ߣߒߡ⠨߃㧘ߘߩߣ ߈ߩ P ߩߣࠅ߁ࠆ୯ߩ▸࿐ࠍ㗔ၞ R(n)ߣߔࠆ㧚ߚߣ ߃߫㧘࿑ 1(b)㧘(d)ߣߥࠆ႐วߪ㧘޿ߕࠇ߽ P ߇ A ߣ ⚿วߔࠆߩߢ㧘 ߘߩߣ߈ߩ P ߩ୯ߪ R(n)ߦ฽߹ࠇࠆ㧚㗔ၞ R(n)ߪ㧘ᧄ⾰⊛ߥ㓏ጀ᭴ㅧᄌൻ߇⿠ߎࠆ㗔ၞ R(u)ߣ㧘⿠ߎࠄߥ޿㗔ၞ R(s)ߦಽߌࠄࠇࠆ㧚ߎߩߣ ߈㧘R(n)ߦභ߼ࠆ R(s)ߩ㗔ၞߩᄢ߈ߐߩഀว㧘ߔߥ ࠊߜ R(s)㧛R(n) ࠍ㧘A㧘B㧘C ߩ 3 ⷐ⚛߆ࠄߥࠆࠢ ࡜ࠬ࠲ߩ㓏ጀ቟ቯᐲߣቯ⟵ߔࠆ㧚 ߥ߅㧘A㧘B㧘C ߪ㧘ߘߩ৻ㇱ߽ߒߊߪోㇱ߇ࠢ࡜ ࠬ࠲ߢ޽ߞߡ߽㧘ߘߩઍ⴫୯ࠍ↪޿ࠆߎߣߢ㧘ห᭽ ߦ㓏ጀ቟ቯᐲࠍቯ⟵ߢ߈ࠆ㧚ߚߛߒ㧘◲නߩߚ߼㧘 ߘࠇߙࠇߩࠢ࡜ࠬ࠲ߪචಽ቟ቯߢ޽ࠅ઒ᗐⷐ⚛ߩㅊ ടߦࠃߞߡ፣უߒߥ޿ߣ޿߁઒ቯࠍ⸳ߌࠆ㧚. 3.3 2 ᰴర࡙࡯ࠢ࡝࠶࠼ⓨ㑆ߦ߅ߌࠆㆡ↪଀ ቟ቯᐲࠍታ㓙ߩⓨ㑆ߦኻߒߡㆡ↪ߒߚ⚿ᨐࠍ␜ߔ㧚 ߎߎߢߪ◲නߩߚ߼ 2 ᰴరⓨ㑆ࠍኻ⽎ߣߔࠆ㧚ⷐ⚛ 㑆ߩ〒㔌ዤᐲߪ࡙࡯ࠢ࡝࠶࠼〒㔌ߣߒ㧘ࠢ࡜ࠬ࠲㑆〒㔌ߪ㊀ᔃᴺߣߔࠆ㧚 3 ⷐ⚛ A㧘B㧘C ߩ㈩⟎ߣߒߡ㧘ฦⷐ⚛㑆〒㔌߇ |AB|:|AC|= 1 : 2 ߩ႐วߣ|AB|ѳ|AC|ѳ|BC|ߩ႐วߦ ߟ޿ߡ⠨߃ࠆ㧚ߘࠇߙࠇߩ઒ᗐⷐ⚛ㅊടᴺߦࠃࠆ቟ ቯᐲࠍ㧘ㄭૃ⊛ߦ⸘▚ߔࠆ㧚R(n) 㗔ၞౝㇱߩฦ↹⚛ ߦߟ޿ߡ㧘ᧄ⾰⊛ߥ㓏ጀ᭴ㅧᄌൻ߇⿠߈ࠆ߆ุ߆ࠍ ್ቯߔࠆߎߣߢ㧘R(s)㧘R(u) 㗔ၞߩ↹⚛ࠍᢙ߃਄ߍ ࠆ㧚R(u)㗔ၞߦ⌕⦡ߒߚ⚿ᨐࠍ࿑ 2 ߦ␜ߔ㧚(a)ߩ቟ ቯᐲߪ 0.88 ߢ޽ࠅ㧘(b)ߢߪ 0.34 ߣߥࠆ㧚.

(3) ߎߎߢ઒ߦ㧘(b)ߩ႐วߢ|AB|=|AC|=|BC|ߣߒߡ࿑ 3 ߩࠃ߁ߦ R(n)ࠍಽഀߔࠆߎߣࠍ⠨߃ࠆߣ㧘R(At)㧘 R(Bt)㧘R(Ct)ߩ㕙Ⓧߪߘࠇߙࠇ╬ߒߊ㧘߹ߚ R(Al)㧘 R(Ar)㧘R(Bl)㧘R(Br)㧘R(Cl)㧘R(Cr)ߩ㕙Ⓧ߽ߘࠇߙ ࠇ╬ߒ޿㧚ߎߎ߆ࠄ㓏ጀ቟ቯᐲߩ୯ၞߪᰴߩࠃ߁ߦ ߥࠆ㧚 1 d 㓏ጀ቟ቯᐲ d 1 3 వߦㅀߴߚ࿑ 2(b)ߩ႐วߩ቟ቯᐲ 0.34 ߪ㧘ᦨ߽ਇ቟ ቯߥߣ߈ߩℂ⺰୯ 1/3 ߦㄭ޿୯ߣߥߞߡ޿ࠆ㧚 ߐࠄߦ⹦ߒߊ቟ቯᐲߦߟ޿ߡ⷗ࠆߚ߼ߦ㧘వߦ⚿ วߔࠆ 2 ⷐ⚛ A㧘B ࠍ࿕ቯߒ㧘3 ୘⋡ߩⷐ⚛ࠍ A㧘B ߘࠇߙࠇࠍਛᔃߣߔࠆඨᓘ|AB|ߩᄖㇱߢേ߆ߒ㧘቟ ቯᐲߩಽᏓࠍ⺞ߴࠆ㧚ߎߩ⚿ᨐࠍ࿑ 4 ߦ␜ߔ㧚ߎߎ ߢ㧘⊕㗔ၞߪ⿛ᩏ▸࿐ᄖߢ޽ࠆߎߣࠍ␜ߒߡ޿ࠆ㧚3 ⷐ⚛㑆ߩ〒㔌߇߶߷╬ߒߊߥࠆ 2 ౞ߩ੤ὐㄭㄝߢ㧘 ቟ቯᐲߪ․ߦૐߊߥࠅ㧘〒㔌Ꮕ߇ᄢ߈ߊߥࠆߦߟࠇ ߡ቟ቯᐲ߇㜞ߊߥߞߡ޿ࠆߎߣ߇⺒ߺขࠇࠆ㧚. (a)|AB|:|AC|=1 : 2 (0.88) (b)|AB|ѳ|AC|ѳ|BC| (0.34). ࿑ 2 ᭴ㅧᄌൻ㗔ၞ (᜝ᒐౝߪ቟ቯᐲ). R(At) R(At). A R(Al) R(Br). R(Bt) R(Bt). R(Ar) R(Cl). R(Bl). B. R(Cr). R(Ct)) R(Ct. C. ࿑ 3 ኻ⽎㗔ၞ. 4. ታ㛎࡮⠨ኤ ᧄ▵ߢߪ࡜ࡦ࠳ࡓߦ૞ᚑߒߚ࠺࡯࠲⟲ࠍ଀ߣߒߡ㧘 ઒ᗐⷐ⚛ㅊടᴺߦࠃࠆ቟ቯᐲߦࠃߞߡ᦭ലߦ⴫⃻ߐ ࠇࠆᖱႎ㧘߅ࠃ߮⴫⃻ߐࠇߥ޿ᖱႎߣߘߩ⸃᳿╷ߦ ߟ޿ߡㅀߴࠆ㧚߹ߚ㧘ᓥ᧪ᚻᴺߣߩᲧセߦߟ޿ߡ߽ ⠨ኤߔࠆ㧚. A. B 0.33... 1.0. ࿑ 4 ቟ቯᐲಽᏓ. 4.1 ឭ᩺ᚻᴺߩ᦭ലᕈ ឭ᩺ᴺߢߪ㧘઒ᗐⷐ⚛ߩㅊടߦࠃࠆ㓏ጀ᭴ㅧߩᄌ ൻࠍਇ቟ቯߣߒߡ޿ࠆ߇㧘ߎࠇߪߔߢߦᒻᚑߐࠇߚ ࠢ࡜ࠬ࠲ߦኻߒߡߘߩౝㇱߩⷐ⚛߿ઁࠢ࡜ࠬ࠲ߩⷐ ⚛߇ᓸዊߥᄌേࠍߒߚ႐วࠍ઒ᗐⷐ⚛ߦ⷗┙ߡࠆߎ ߣࠍᗧ๧ߒߡ޿ࠆ㧚 ߎߩ᭽ሶࠍ⏕߆߼ࠆߚ߼㧘⋥ⷰ⊛ߦℂ⸃ߒ߿ߔ޿ 2 ᰴర࠺࡯࠲ࠍ଀ߣߒߡ㧘ታ㓙ߩ࠺࡯࠲ߣ᮸ᒻ࿑߆ ࠄឭ᩺ᴺߩ᦭ലᕈࠍ⏕߆߼ࠆ㧚 ⷐ⚛ᢙࠍ 20 ߣߒ࡜ࡦ ࠳ࡓߦ૞ᚑߒߚ଀ߦߟ޿ߡ㧘࿑ 5 ߦᐳᮡ㧘࿑ 6 ߦ㓏 ጀ⊛ࠢ࡜ࠬ࠲࡝ࡦࠣᓟߦ቟ቯᐲࠍ᳞߼㧘ߘࠇࠍノᐲ ୯ߢ␜ߒߚ᮸ᒻ࿑ࠍ␜ߔ㧚ߎߎߢ㧘቟ቯᐲߩノᐲ୯ ߳ߩࡑ࠶ࡇࡦࠣߦߪ࿑ 4 ߣหߓ߽ߩࠍ↪޿ࠆ㧚߹ߚ ⸘▚ኻ⽎ߣߥࠆ 3 ࠢ࡜ࠬ࠲ߪ㧘⚿ว㗅ᐨߦߒߚ߇޿ వߦ⚿วߒߡ޿ࠆࠢ࡜ࠬ࠲ߩઍ⴫୯ߣ㧘ᓟߦ⚿วߔ ࠆࠢ࡜ࠬ࠲ߩ 2 ߟߩሶߩઍ⴫୯ߣߔࠆ㧚቟ቯᐲߪ㧘 ߘߩ୯ࠍᜬߟࡁ࡯࠼߆ࠄ㧘ߘߩሶߢ޽ࠆᓟߦ⚿วߔ ࠆࠢ࡜ࠬ࠲߹ߢߩ▸࿐ߩ⍱ᒻࠍ቟ቯᐲߦኻᔕߔࠆノ ᐲ୯ߢႣࠅߟ߱ߒߡ⴫⃻ߔࠆ㧚 ߎࠇࠄߩⷐ⚛ߩ߁ߜ㧘 ࿑5 ฝ஥ߦ޽ࠆ{(4, 16), (6, (5, 15))}߆ࠄߥࠆࠢ࡜ࠬ࠲ߦ⌕⋡ߔࠆ(࿑ 7)㧚(4, 16)ߣ(6, (5, 15))㑆ߦߪචಽߥ〒㔌߇޽ࠆࠃ߁ߦ⷗߃ࠆ㧚ߎߎ −33−. ࿑ 5 2 ᰴర࠺࡯࠲㓸ว㧔ⷐ⚛ᢙ㧦20㧕. ࿑ 6 㓏ጀ቟ቯᐲࠍนⷞൻߒߚ᮸ᒻ࿑㧔ⷐ⚛ᢙ㧦20㧕.

(4) 4. 16. 16. 5 15. 4. 4. 16. 5. 5 15. 15. 6 6 (a) ᄌൻ೨ (b) ਄߳ᄌൻᓟ (c) ਅ߳ᄌൻᓟ ࿑ 7 ⷐ⚛ 15 ߇ᓸዊߦᄌൻߔࠆ႐ว 6. ߢⷐ⚛ 15 ߇਄ᣇะߦᓸዊ⒖േߔࠆߣ㧘ࠢ࡜ࠬ࠲(5㧘 15)ߩઍ⴫୯ߣⷐ⚛ 6 ߣߩ〒㔌ࠃࠅ߽(4, 16)ߣߩ〒㔌 ߇⍴ߊߥࠅవߦ⚿วߒ㧘ࠢ࡜ࠬ࠲{(4, 16), (5, 15)}ߣ ߥߞߡߒ߹߁㧚߹ߚਅᣇะ߳ᓸዊ⒖േߔࠆߣⷐ⚛ 6 ߣⷐ⚛ 15 ߩ〒㔌߇ⷐ⚛ 5 ߣࠢ࡜ࠬ࠲(4, 16)ߣߩ〒㔌 ࠃࠅ߽ዊߐߊߥࠅࠢ࡜ࠬ࠲᭴ㅧ߇ᄌൻߔࠆ㧚 ᧄᚻᴺߪ㧘ߔߢߦࠢ࡜ࠬ࠲࡝ࡦࠣߐࠇߚ⚿ᨐߢ޽ࠆ ᮸ᒻ࿑ߦኻߒߡ㓏ጀ቟ቯᐲࠍ⸘▚ߔࠆ㧚ߟ߹ࠅ቟ቯ ᐲ⸘▚ኻ⽎ࠍฦࡁ࡯࠼ߦኻߒߡߘߩਅ૏ 3 ࡁ࡯࠼ߦ ቯ߼ߡ޿ࠆߚ߼㧘⸘▚ኻ⽎߆ࠄṳࠇࠆⷐ⚛࡮ࠢ࡜ࠬ ࠲㑆ߩㅒォน⢻ᕈߪ␜ߔߎߣ߇ߢ߈ߥ޿㧚ߎߩߎߣ ߳ߩኻᔕߣߒߡ㧘ߔߢߦ⚿วߒߡ޿ࠆࡁ࡯࠼ߛߌߢ ߥߊ㧘⚿วߔࠆน⢻ᕈߩ޽ࠆㄭறࡁ࡯࠼ߔߴߡߦኻ ߒߡ቟ቯᐲࠍ⸘▚ߔࠆߎߣ߇⠨߃ࠄࠇࠆ㧚ߒ߆ߒ㧘 ⸘▚㊂߿นⷞൻᚻᴺߥߤߩ໧㗴ߪᱷࠆ㧚. ࠢ࡜ࠬ࠲࡝ࡦࠣߩ቟ቯᕈࠍᐞ૗ቇ⊛ߦ⸃ᨆߔࠆᣂߒ ޿ᢙℂࡕ࠺࡞ࠍឭ᩺ߒߚ㧚ᧄᚻᴺߢߪ㧘࡜ࡦ࠳ࡓࠨ ࡦࡊ࡝ࡦࠣߦࠃࠆ⛔⸘⊛ᚻᴺࠍ↪޿ࠆߎߣߥߊ㧘ฦ 㓏ጀߢߩ቟ቯᐲࠍ▚಴ߢ߈ࠆ㧚߹ߚ㧘㓏ጀ቟ቯᐲࠍ ᮸ᒻ࿑਄ߦนⷞൻߔࠆߎߣߢ㧘ᓥ᧪ߩ᮸ᒻ࿑ߢߪᄬ ࠊࠇߡ޿ߚᖱႎࠍឭ␜ߢ߈ߚ㧚 ੹ᓟߩ⺖㗴ߣߒߡ㧘⃻ታߩࠕࡊ࡝ࠤ࡯࡚ࠪࡦߦㆡ ↪ߒ㧘 ᦭ലᕈࠍᬌ⸽ߔࠆߎߣ߇޽ߍࠄࠇࠆ㧚 ੹࿁ߪ㧘 2 ᰴర࡙࡯ࠢ࡝࠶࠼ⓨ㑆ߢ㊀ᔃᴺࠍ↪޿ߚ႐วߦ㒢 ቯߒߡ㧘㓏ጀ቟ቯᕈࠍ▚಴ߒߚ㧚ߒ߆ߒ㧘⒳‫ࠕߩޘ‬ ࡊ࡝ࠤ࡯࡚ࠪࡦ࠺࡯࠲ߦㆡ↪ߔࠆߦߪ㧘ᄙᰴరⓨ㑆 ߢ㧘⒳‫〒ߩޘ‬㔌ዤᐲ㧘⒳‫࠲ࠬ࡜ࠢߩޘ‬㑆〒㔌ࠍ↪޿ ߚ႐วߦኻߒߡ߽㧘ኻᔕ߇ᔅⷐߢ޽ࠆ㧚 ߐࠄߦ㧘㓏ጀ቟ቯᐲߩ㜞ㅦ⸘▚㧘㓏ጀࠍ⿧߃ߚ቟ ቯᕈߩ⸃ᨆࠍⴕ߁ߚ߼ߩ⸘▚ᴺߣนⷞൻᴺ㧘ࠢ࡜ࠬ ࠲ಽഀᢙߩ᳿ቯᴺ㧘ࠃࠅ⋥ⷰ⊛ߥนⷞൻᚻᴺߩ㐿ᜏ ߥߤߦ߽㧘㗅ᰴขࠅ⚵ߺߚ޿㧚. ⻢ㄉ ᧄ⎇ⓥߩ৻ㇱߪ㧘⑼ቇ⎇ⓥ⾌⵬ഥ㊄㧔⪚⧘ 17650024㧕ߩេഥࠍฃߌߡ޿ࠆ㧚. ෳ⠨ᢥ₂ [1]㩷 A. K. Jain, M. N. Murty, and P. J. Flynn, “Data clustering: a. 4.2 ᣢሽᚻᴺߣߩᲧセ. review,” ACM Computing Surveys, Vol. 31, No. 3, pp.. ᧄᚻᴺߪ࠺࡯࠲㓸วߩㇱಽ㓸วࠍ↪޿ࠆᚻᴺߥߤ ߣᲧߴߡ⛔⸘⊛ߦᛒ߁ᔅⷐ߇ߥ޿ߚ߼㧘⸘▚㊂ߪ⪺. 264-323, 1999. [2] 㩷 V. V. Ranghavan and M. Y. L. IP, “Techniques for measuring the stability of clustering : a comparative. ߒߊᷫዋߔࠆ㧚㓏ጀ቟ቯᐲߪ㧘⃻ᤨὐߢߪ↹⚛ߩᢙ ߃਄ߍߢ▚಴ߒߡ޿ࠆ߇㧘ኻ⽎ 3 ࠢ࡜ࠬ࠲ߩࠢ࡜ࠬ ࠲㑆〒㔌ߛߌ߆ࠄ⸘▚ߢ߈ࠆߚ߼㧘⴫ᒁ߈ߣ⵬㑆ߦ ࠃࠅߐࠄߦ㜞ㅦߥㄭૃ⸘▚߇น⢻ߣ⠨߃ࠄࠇࠆ㧚 ᧄᚻᴺߩఝ૏ὐߣߒߡ㧘࠺࡯࠲ᢙ߇ዋߥ޿႐วߦ ߽ㆡ↪ߢ߈ࠆߎߣ߇޽ߍࠄࠇࠆ㧚ㇱಽ㓸วࠍ↪޿ࠆ ᚻᴺߢߪ㧘࠺࡯࠲ᢙ߇৻ቯએ਄ߥ޿႐วߦߪචಽߥ ା㗬ᕈࠍᓧࠄࠇߥ޿ߩߦኻߒ㧘ᧄᚻᴺߪࠊߕ߆ 3 ୘ ߩⷐ⚛߆ࠄߥࠆࠢ࡜ࠬ࠲ߦኻߒߡ߽㧘቟ቯᐲࠍ⸘▚ ߢ߈ࠆ㧚 ߹ߚᧄᚻᴺࠍࠢ࡜ࠬ࠲ಽഀᢙ᳿ቯߩᜰᮡߣߒߡ೑ ↪ߔࠆߎߣ߽⠨߃ࠄࠇࠆ㧚ᓥ᧪㧘ಽഀᢙࠍ᳿ቯߔࠆ ߚ߼ߦߪ⚿ว〒㔌ࠍ↪޿ߡ޿ࠆ߇㧘ߎࠇߦฦ㓏ጀߦ ߅ߌࠆ቟ቯᐲࠍട๧ߒߡ⠨ᘦߔࠆߎߣߢ㧘ࠃࠅㆡߒ ߚࠢ࡜ࠬ࠲ಽഀ߇ᓧࠄࠇࠆߣ⠨߃ࠄࠇࠆ㧚. study, ” ACM SIGIR 1982, pp. 209-237, 1982. [3]㩷 W. M. Rand, “Objective criteria for the evaluation of clustering, ” Journal of American Statistical Association, Vol. 66, No. 336, pp. 846-850, 1971. [4]㩷 D. G. Corneil and M. E. Woodward, “A comparison and evaluation of graph theoretical clustering techniques,” INFOR, Canadian Journal of Operational Research and Information Processing, Vol. 16, No. 1, pp. 74-89, 1978. [5]㩷 C. T. Yu, “The Stability of two common matching functions in classification with respect to a proposed measure,” Journal of the American society for Information Science, Vol. 27, No. 4, pp. 248-255, 1976. [6] 㩷 E. B. Fowlkes, and C. L. Mallows, “A method for comparing two hierarchical clusterings,” Journal of the American Statistical Association, Vol. 78, No. 78, pp. 553-584, 1983.. 5. ⚿⸒. [7]㩷 A. Ben-Hur, A. Elisseeff, and I. Guyon, “A stability based method for discovering structure in clustered data,” Pacific. ᧄႎ๔ߢߪ㧘઒ᗐⷐ⚛ࠍㅊടߔࠆߎߣߢ㧘㓏ጀ⊛. Symposium on Biocomputing, Vol. 7, pp. 6-17, 2002.. −34−.

(5)