Single-linkage clustering
ಅಂಕಿಅಂಶಗಳಲ್ಲಿ, ಏಕ-ಸಂಪರ್ಕ ಕ್ಲಸ್ಟರಿಂಗ್ ಶ್ರೇಣೀಕೃತ ಕ್ಲಸ್ಟರಿಂಗ್ನ ಹಲವಾರು ವಿಧಾನಗಳಲ್ಲಿ ಒಂದಾಗಿದೆ. ಇದು ಬಾಟಮ್-ಅಪ್ ಶೈಲಿಯಲ್ಲಿ (ಅಗ್ಲೋಮೆರೇಟಿವ್ ಕ್ಲಸ್ಟರಿಂಗ್) ಸಮೂಹಗಳ ಗುಂಪನ್ನು ಆಧರಿಸಿದೆ, ಪ್ರತಿ ಹಂತದಲ್ಲೂ ಎರಡು ಸಮೂಹಗಳನ್ನು ಸಂಯೋಜಿಸುತ್ತದೆ, ಅದು ಪರಸ್ಪರ ಒಂದೇ ಸಮೂಹಕ್ಕೆ ಇನ್ನೂ ಸೇರಿರದ ಹತ್ತಿರದ ಜೋಡಿ ಅಂಶಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಈ ವಿಧಾನವು ಉದ್ದವಾದ ತೆಳುವಾದ ಸಮೂಹಗಳನ್ನು ಉತ್ಪಾದಿಸುತ್ತದೆ, ಇದರಲ್ಲಿ ಒಂದೇ ಸಮೂಹದ ಹತ್ತಿರದ ಅಂಶಗಳು ಸಣ್ಣ ಅಂತರವನ್ನು ಹೊಂದಿರುತ್ತವೆ, ಆದರೆ ಸಮೂಹದ ವಿರುದ್ಧ ತುದಿಗಳಲ್ಲಿರುವ ಅಂಶಗಳು ಇತರ ಸಮೂಹಗಳ ಎರಡು ಅಂಶಗಳಿಗಿಂತ ಪರಸ್ಪರ ಹೆಚ್ಚು ದೂರದಲ್ಲಿರಬಹುದು. ದತ್ತಾಂಶದ ಕೆಲವು ವರ್ಗಗಳಿಗೆ, ಇದು ದತ್ತಾಂಶವನ್ನು ಉಪಯುಕ್ತವಾಗಿ ಉಪವಿಭಾಗಗೊಳಿಸಬಹುದಾದ ವರ್ಗಗಳನ್ನು ವ್ಯಾಖ್ಯಾನಿಸುವಲ್ಲಿ ತೊಂದರೆಗಳಿಗೆ ಕಾರಣವಾಗಬಹುದು. ಆದಾಗ್ಯೂ, ಇದು ಗ್ಯಾಲಕ್ಸಿ ಸಮೂಹಗಳನ್ನು ವಿಶ್ಲೇಷಿಸಲು ಖಗೋಳಶಾಸ್ತ್ರದಲ್ಲಿ ಜನಪ್ರಿಯವಾಗಿದೆ, ಇದು ಸಾಮಾನ್ಯವಾಗಿ ದ್ರವ್ಯದ ಉದ್ದನೆಯ ತಂತಿಗಳನ್ನು ಒಳಗೊಂಡಿರಬಹುದು; ಈ ಅಪ್ಲಿಕೇಶನ್ನಲ್ಲಿ, ಇದನ್ನು ಫ್ರೆಂಡ್ಸ್-ಆಫ್-ಫ್ರೆಂಡ್ಸ್ ಅಲ್ಗಾರಿದಮ್ ಎಂದೂ ಕರೆಯಲಾಗುತ್ತದೆ. ಅಗ್ಲೋಮೆರೇಟಿವ್ ಕ್ಲಸ್ಟರಿಂಗ್ ವಿಧಾನಗಳ ಅವಲೋಕನ ಅಗ್ಲೋಮೆರೇಟಿವ್ ಕ್ಲಸ್ಟರಿಂಗ್ ಪ್ರಕ್ರಿಯೆಯ ಆರಂಭದಲ್ಲಿ, ಪ್ರತಿಯೊಂದು ಅಂಶವು ತನ್ನದೇ ಆದ ಕ್ಲಸ್ಟರ್ನಲ್ಲಿರುತ್ತದೆ. ಎಲ್ಲಾ ಅಂಶಗಳು ಒಂದೇ ಸಮೂಹದಲ್ಲಿ ಕೊನೆಗೊಳ್ಳುವವರೆಗೆ ಸಮೂಹಗಳನ್ನು ಅನುಕ್ರಮವಾಗಿ ದೊಡ್ಡ ಸಮೂಹಗಳಾಗಿ ಸಂಯೋಜಿಸಲಾಗುತ್ತದೆ. ಪ್ರತಿ ಹಂತದಲ್ಲೂ, ಕಡಿಮೆ ಅಂತರದಿಂದ ಬೇರ್ಪಟ್ಟ ಎರಡು ಸಮೂಹಗಳನ್ನು ಸಂಯೋಜಿಸಲಾಗುತ್ತದೆ. ಎರಡು ಸಮೂಹಗಳ ನಡುವಿನ ಅಂತರವನ್ನು ನಿರ್ಧರಿಸಲು ಬಳಸುವ ಕಾರ್ಯವು, ಲಿಂಕೇಜ್ ಫಂಕ್ಷನ್ ಎಂದು ಕರೆಯಲ್ಪಡುತ್ತದೆ, ಇದು ಒಟ್ಟುಗೂಡಿಸುವ ಕ್ಲಸ್ಟರಿಂಗ್ ವಿಧಾನಗಳನ್ನು ಪ್ರತ್ಯೇಕಿಸುತ್ತದೆ. ಸಿಂಗಲ್-ಲಿಂಕೇಜ್ ಕ್ಲಸ್ಟರಿಂಗ್ನಲ್ಲಿ, ಎರಡು ಸಮೂಹಗಳ ನಡುವಿನ ಅಂತರವನ್ನು ಒಂದೇ ಜೋಡಿ ಅಂಶಗಳಿಂದ ನಿರ್ಧರಿಸಲಾಗುತ್ತದೆಃ ಆ ಎರಡು ಅಂಶಗಳು (ಪ್ರತಿ ಸಮೂಹದಲ್ಲಿ ಒಂದು) ಪರಸ್ಪರ ಹತ್ತಿರದಲ್ಲಿರುತ್ತವೆ. ಯಾವುದೇ ಹಂತದಲ್ಲಿ ಉಳಿದಿರುವ ಈ ಜೋಡಿವಾರು ದೂರಗಳಲ್ಲಿ ಅತ್ಯಂತ ಕಡಿಮೆ ಅಂತರವು ಎರಡು ಸಮೂಹಗಳನ್ನು ವಿಲೀನಗೊಳಿಸಲು ಕಾರಣವಾಗುತ್ತದೆ, ಅದರ ಅಂಶಗಳು ಒಳಗೊಂಡಿರುತ್ತವೆ. ಈ ವಿಧಾನವನ್ನು ಹತ್ತಿರದ ನೆರೆಯ ಕ್ಲಸ್ಟರಿಂಗ್ ಎಂದೂ ಕರೆಯಲಾಗುತ್ತದೆ. ಕ್ಲಸ್ಟರಿಂಗ್ನ ಫಲಿತಾಂಶವನ್ನು ಡೆಂಡ್ರೋಗ್ರಾಮ್ನಂತೆ ದೃಶ್ಯೀಕರಿಸಬಹುದು, ಇದು ಕ್ಲಸ್ಟರ್ಗಳನ್ನು ವಿಲೀನಗೊಳಿಸಿದ ಅನುಕ್ರಮವನ್ನು ಮತ್ತು ಪ್ರತಿ ವಿಲೀನವು ನಡೆದ ದೂರವನ್ನು ತೋರಿಸುತ್ತದೆ. ಗಣಿತಶಾಸ್ತ್ರದ ಪ್ರಕಾರ, X ಮತ್ತು Y ಸಮೂಹಗಳ ನಡುವಿನ ಡಿ (X, Y) ದೂರವನ್ನು, X ಮತ್ತು Y ಅನ್ನು ಸಮೂಹಗಳೆಂದು ಪರಿಗಣಿಸಲಾಗುವ ಯಾವುದೇ ಎರಡು ಘಟಕಗಳ ಗುಂಪುಗಳು ಮತ್ತು d (x, y) ಅನ್ನು x ಮತ್ತು y ಎಂಬ ಎರಡು ಅಂಶಗಳ ನಡುವಿನ ಅಂತರವನ್ನು ಸೂಚಿಸುವ ಅಭಿವ್ಯಕ್ತಿಯಿಂದ ವಿವರಿಸಲಾಗುತ್ತದೆ. ನೈವ್ ಅಲ್ಗಾರಿದಮ್ ಈ ಕೆಳಗಿನ ಅಲ್ಗಾರಿದಮ್ ಒಂದು ಒಟ್ಟುಗೂಡಿಸುವ ಯೋಜನೆಯಾಗಿದೆ, ಇದು ಹಳೆಯ ಸಮೂಹಗಳನ್ನು ಹೊಸ ಗುಂಪುಗಳಾಗಿ ವಿಲೀನಗೊಳಿಸುವುದರಿಂದ ಸಾಮೀಪ್ಯ ಮ್ಯಾಟ್ರಿಕ್ಸ್ನಲ್ಲಿರುವ ಸಾಲುಗಳು ಮತ್ತು ಕಾಲಮ್ಗಳನ್ನು ಅಳಿಸಿಹಾಕುತ್ತದೆ. ಸಾಮೀಪ್ಯ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಎಲ್ಲಾ ದೂರಗಳನ್ನು ಒಳಗೊಂಡಿದೆ. ಕ್ಲಸ್ಟರಿಂಗ್ಗಳಿಗೆ ಅನುಕ್ರಮ ಸಂಖ್ಯೆಗಳನ್ನು ನಿಗದಿಪಡಿಸಲಾಗಿದೆ ಮತ್ತು ಇದು-th ಕ್ಲಸ್ಟರಿಂಗ್ನ ಮಟ್ಟವಾಗಿದೆ. ಅನುಕ್ರಮ ಸಂಖ್ಯೆ m ಹೊಂದಿರುವ ಸಮೂಹವನ್ನು (m) ಎಂದು ಸೂಚಿಸಲಾಗುತ್ತದೆ ಮತ್ತು ಸಮೂಹಗಳ ನಡುವಿನ ಸಾಮೀಪ್ಯವನ್ನು ಸೂಚಿಸಲಾಗುತ್ತದೆ. ಸಿಂಗಲ್ ಲಿಂಕೇಜ್ ಅಲ್ಗಾರಿದಮ್ ಈ ಕೆಳಗಿನ ಹಂತಗಳಿಂದ ಕೂಡಿದೆಃ ಮಟ್ಟ ಮತ್ತು ಅನುಕ್ರಮ ಸಂಖ್ಯೆಯನ್ನು ಹೊಂದಿರುವ ಡಿಸ್ಜಾಯಿಂಟ್ ಕ್ಲಸ್ಟರಿಂಗ್ನೊಂದಿಗೆ ಪ್ರಾರಂಭಿಸಿ. ಪ್ರಸ್ತುತ ಕ್ಲಸ್ಟರಿಂಗ್ನಲ್ಲಿನ ಎಲ್ಲಾ ಜೋಡಿ ಕ್ಲಸ್ಟರ್ಗಳ ಮೇಲೆ ಕನಿಷ್ಠವು ಎಲ್ಲಿದೆ ಎಂಬುದರ ಪ್ರಕಾರ, ಪ್ರಸ್ತುತ ಕ್ಲಸ್ಟರಿಂಗ್ನಲ್ಲಿ ಅತ್ಯಂತ ಹೋಲುವ ಜೋಡಿ ಕ್ಲಸ್ಟರ್ಗಳನ್ನು ಹುಡುಕಿ. ಅನುಕ್ರಮ ಸಂಖ್ಯೆಯನ್ನು ಹೆಚ್ಚಿಸಿಃ ಮುಂದಿನ ಕ್ಲಸ್ಟರಿಂಗ್ ಅನ್ನು ರೂಪಿಸಲು ಕ್ಲಸ್ಟರ್ಗಳನ್ನು ಮತ್ತು ಒಂದೇ ಕ್ಲಸ್ಟರ್ ಅನ್ನು ವಿಲೀನಗೊಳಿಸಿ. ಕ್ಲಸ್ಟರ್ಗಳಿಗೆ ಅನುಗುಣವಾದ ಸಾಲುಗಳು ಮತ್ತು ಕಾಲಮ್ಗಳನ್ನು ಅಳಿಸುವ ಮೂಲಕ ಮತ್ತು ಹೊಸದಾಗಿ ರೂಪುಗೊಂಡ ಕ್ಲಸ್ಟರ್ಗೆ ಅನುಗುಣವಾದ ಸಾಲು ಮತ್ತು ಕಾಲಮ್ ಅನ್ನು ಸೇರಿಸುವ ಮೂಲಕ ಸಾಮೀಪ್ಯ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಅನ್ನು ನವೀಕರಿಸಲು ಈ ಕ್ಲಸ್ಟರಿಂಗ್ನ ಮಟ್ಟವನ್ನು ಹೊಂದಿಸಿ. ಸೂಚಿಸಲಾದ ಹೊಸ ಸಮೂಹ ಮತ್ತು ಹಳೆಯ ಸಮೂಹದ ನಡುವಿನ ಸಾಮೀಪ್ಯವನ್ನು ಹೀಗೆ ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ. ಎಲ್ಲಾ ವಸ್ತುಗಳು ಒಂದೇ ಗುಂಪಿನಲ್ಲಿದ್ದರೆ, ನಿಲ್ಲಿಸಿ. ಇಲ್ಲದಿದ್ದರೆ, ಹಂತ 2ಕ್ಕೆ ಹೋಗಿ. ಕಾರ್ಯನಿರತ ಉದಾಹರಣೆ ಈ ಕಾರ್ಯನಿರತ ಉದಾಹರಣೆಯು ಐದು ಬ್ಯಾಕ್ಟೀರಿಯಾಗಳ 5S ರೈಬೋಸೋಮಲ್ ಆರ್ಎನ್ಎ ಅನುಕ್ರಮ ಜೋಡಣೆಯಿಂದ ಗಣಿಸಲಾದ ಜೆಸಿ69 ಜೆನೆಟಿಕ್ ಡಿಸ್ಟೆನ್ಸ್ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಅನ್ನು ಆಧರಿಸಿದೆಃ ಬ್ಯಾಸಿಲಸ್ ಸಬ್ಟಿಲಿಸ್ (β), ಬ್ಯಾಸಿಲಸ್ ಸ್ಟಿಯರೋಥರ್ಮೊಫಿಲಸ್ (β), ಲ್ಯಾಕ್ಟೋಬಾಸಿಲಸ್ ವೈರಿಡೆಸೆನ್ಸ್ (β), ಅಕೋಲೆಪ್ಲಾಸ್ಮಾ ಮೋಡಿಕಮ್ (β), ಮತ್ತು ಮೈಕ್ರೋಕೊಕಸ್ ಲ್ಯುಟಿಯಸ್ (β). ಮೊದಲ ಹೆಜ್ಜೆ ಮೊದಲ ಕ್ಲಸ್ಟರಿಂಗ್ ನಾವು ಐದು ಅಂಶಗಳನ್ನು ಹೊಂದಿದ್ದೇವೆ ಮತ್ತು ಅವುಗಳ ನಡುವೆ ಜೋಡಿಯಾಗಿ ಅಂತರಗಳ ಈ ಕೆಳಗಿನ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಅನ್ನು ಹೊಂದಿದ್ದೇವೆ ಎಂದು ಭಾವಿಸೋಣಃ ಈ ಉದಾಹರಣೆಯಲ್ಲಿ, ಇದು ಅತ್ಯಂತ ಕಡಿಮೆ ಮೌಲ್ಯವಾಗಿದೆ, ಆದ್ದರಿಂದ ನಾವು ಅಂಶಗಳನ್ನು ಕ್ಲಸ್ಟರ್ ಮಾಡುತ್ತೇವೆ ಮತ್ತು. ಮೊದಲ ಶಾಖೆಯ ಉದ್ದದ ಅಂದಾಜು ಯಾವ ಮತ್ತು ಈಗ ಸಂಪರ್ಕಗೊಂಡಿರುವ ನೋಡ್ ಅನ್ನು ಸೂಚಿಸೋಣ. ಸೆಟ್ಟಿಂಗ್ ಅಂಶಗಳು ಮತ್ತು ಅವು ಸಮಾನ ದೂರದಲ್ಲಿರುವುದನ್ನು ಖಾತ್ರಿಪಡಿಸುತ್ತದೆ. ಇದು ಅಲ್ಟ್ರಾಮೆಟ್ರಿಸಿಟಿ ಊಹೆಯ ನಿರೀಕ್ಷೆಗೆ ಅನುರೂಪವಾಗಿದೆ. ಶಾಖೆಗಳು ಸೇರುತ್ತವೆ ಮತ್ತು ನಂತರ ಉದ್ದವನ್ನು ಹೊಂದಿರುತ್ತವೆ (ಅಂತಿಮ ಡೆಂಡ್ರೋಗ್ರಾಮ್ ನೋಡಿ) ಮೊದಲ ದೂರ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ನವೀಕರಣ ನಾವು ನಂತರ ಆರಂಭಿಕ ಸಾಮೀಪ್ಯ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಅನ್ನು ಹೊಸ ಸಾಮೀಪ್ಯ ಮ್ಯಾಟ್ರಿಕ್ಸ್ಗೆ ನವೀಕರಿಸಲು ಮುಂದುವರಿಯುತ್ತೇವೆ (ಕೆಳಗೆ ನೋಡಿ), ಒಂದು ಸಾಲು ಮತ್ತು ಒಂದು ಕಾಲಮ್ನಿಂದ ಗಾತ್ರದಲ್ಲಿ ಕಡಿಮೆಯಾಗುತ್ತದೆ. ಬೋಲ್ಡ್ ಮೌಲ್ಯಗಳು ಹೊಸ ದೂರಗಳಿಗೆ ಅನುಗುಣವಾಗಿರುತ್ತವೆ, ಮೊದಲ ಕ್ಲಸ್ಟರ್ನ ಪ್ರತಿಯೊಂದು ಅಂಶ ಮತ್ತು ಉಳಿದ ಪ್ರತಿಯೊಂದು ಅಂಶಗಳ ನಡುವಿನ ಕನಿಷ್ಠ ಅಂತರವನ್ನು ಉಳಿಸಿಕೊಳ್ಳುವ ಮೂಲಕ ಲೆಕ್ಕ ಹಾಕಲಾಗುತ್ತದೆಃ ಮೊದಲ ಕ್ಲಸ್ಟರ್ನಲ್ಲಿ ಒಳಗೊಂಡಿರದ ಅಂಶಗಳ ನಡುವಿನ ಅಂತರಕ್ಕೆ ಅನುಗುಣವಾಗಿರುವುದರಿಂದ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ನವೀಕರಣದಿಂದ ಇಟಾಲಿಕ್ ಮಾಡಲಾದ ಮೌಲ್ಯಗಳು ಪರಿಣಾಮ ಬೀರುವುದಿಲ್ಲ. ಎರಡನೇ ಹಂತ ಎರಡನೇ ಕ್ಲಸ್ಟರಿಂಗ್ ನಾವು ಈಗ ಹೊಸ ದೂರ ಮ್ಯಾಟ್ರಿಕ್ಸ್ನಿಂದ ಪ್ರಾರಂಭವಾಗುವ ಹಿಂದಿನ ಮೂರು ಕ್ರಿಯೆಗಳನ್ನು ಪುನರುಚ್ಚರಿಸುತ್ತೇವೆಃ ಇಲ್ಲಿ, ಮತ್ತು ಕಡಿಮೆ ಮೌಲ್ಯಗಳಾಗಿವೆ, ಆದ್ದರಿಂದ ನಾವು ಕ್ಲಸ್ಟರ್ ಅನ್ನು ಅಂಶದೊಂದಿಗೆ ಮತ್ತು ಅಂಶದೊಂದಿಗೆ ಸೇರಿಸುತ್ತೇವೆ. ಎರಡನೇ ಶಾಖೆಯ ಉದ್ದದ ಅಂದಾಜು ಯಾವ ನೋಡ್ಗೆ, ಮತ್ತು ಈಗ ಸಂಪರ್ಕಿತವಾಗಿದೆ ಎಂಬುದನ್ನು ಸೂಚಿಸೋಣ. ಅಲ್ಟ್ರಾಮೆಟ್ರಿಸಿಟಿ ನಿರ್ಬಂಧದಿಂದಾಗಿ, ಶಾಖೆಗಳು ಸೇರುವ ಅಥವಾ ಸೇರುವ, ಮತ್ತು ಸೇರುವ, ಮತ್ತು ಸಹ ಸಮಾನವಾಗಿರುತ್ತವೆ ಮತ್ತು ಈ ಕೆಳಗಿನ ಒಟ್ಟು ಉದ್ದವನ್ನು ಹೊಂದಿರುತ್ತವೆಃ ನಾವು ಕಾಣೆಯಾದ ಶಾಖೆಯ ಉದ್ದವನ್ನು ಕಂಡುಹಿಡಿಯುತ್ತೇವೆಃ (ಅಂತಿಮ ಡೆಂಡ್ರೋಗ್ರಾಮ್ ಅನ್ನು ನೋಡಿ) ಎರಡನೇ ದೂರ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ನವೀಕರಣ ನಾವು ನಂತರ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಅನ್ನು ಹೊಸ ದೂರ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಆಗಿ ನವೀಕರಿಸಲು ಮುಂದುವರಿಯುತ್ತೇವೆ (ಕೆಳಗೆ ನೋಡಿ), ಗಾತ್ರದಲ್ಲಿ ಎರಡು ಸಾಲುಗಳು ಮತ್ತು ಎರಡು ಕಾಲಮ್ಗಳಿಂದ ಕಡಿಮೆಯಾಗುತ್ತದೆ ಏಕೆಂದರೆ ಅದರೊಂದಿಗೆ ಮತ್ತು ಅದರೊಂದಿಗೆ ಕ್ಲಸ್ಟರಿಂಗ್ಃ ಅಂತಿಮ ಹಂತ ಅಂತಿಮ ಮ್ಯಾಟ್ರಿಕ್ಸ್ಃ ಆದ್ದರಿಂದ ನಾವು ಸಮೂಹಗಳನ್ನು ಸೇರುತ್ತೇವೆ ಮತ್ತು. ಈಗ ಸಂಪರ್ಕಗೊಂಡಿರುವ (ಮೂಲ) ನೋಡ್ ಅನ್ನು ಸೂಚಿಸೋಣ. ಶಾಖೆಗಳು ಸೇರುತ್ತವೆ ಮತ್ತು ನಂತರ ಉದ್ದವನ್ನು ಹೊಂದಿರುತ್ತವೆಃ ನಾವು ಉಳಿದ ಶಾಖೆಯ ಉದ್ದವನ್ನು ಊಹಿಸುತ್ತೇವೆಃ ಏಕ-ಸಂಪರ್ಕ ಡೆಂಡ್ರೋಗ್ರಾಮ್ ಡೆಂಡ್ರೋಗ್ರಾಮ್ ಈಗ ಪೂರ್ಣಗೊಂಡಿದೆ. ಇದು ಅಲ್ಟ್ರಾಮೆಟ್ರಿಕ್ ಆಗಿದೆ ಏಕೆಂದರೆ ಎಲ್ಲಾ ತುದಿಗಳು (,,,, ಮತ್ತು) ಇವುಗಳಿಂದ ಸಮಾನ ದೂರದಲ್ಲಿರುತ್ತವೆಃ ಆದ್ದರಿಂದ ಡೆಂಡ್ರೋಗ್ರಾಮ್ ಅದರ ಆಳವಾದ ನೋಡ್ನಿಂದ ಬೇರೂರಿದೆ. ಇತರ ಸಂಪರ್ಕಗಳು ಸಿಂಗಲ್ ಲಿಂಕೇಜ್ ಕ್ಲಸ್ಟರಿಂಗ್ಗಾಗಿ ನೈವ್ ಅಲ್ಗಾರಿದಮ್ ಮೂಲಭೂತವಾಗಿ ಕನಿಷ್ಠ ವಿಸ್ತಾರವಾದ ಮರಗಳಿಗೆ ಕ್ರುಸ್ಕಲ್ನ ಅಲ್ಗಾರಿದಮ್ನಂತೆಯೇ ಇರುತ್ತದೆ. ಆದಾಗ್ಯೂ, ಸಿಂಗಲ್ ಲಿಂಕೇಜ್ ಕ್ಲಸ್ಟರಿಂಗ್ನಲ್ಲಿ, ಸಮೂಹಗಳು ರೂಪುಗೊಳ್ಳುವ ಕ್ರಮವು ಮುಖ್ಯವಾಗಿದೆ, ಆದರೆ ಕನಿಷ್ಠ ವಿಸ್ತಾರವಾದ ಮರಗಳಿಗೆ ಮುಖ್ಯವಾದುದು ಅಲ್ಗಾರಿದಮ್ ಆಯ್ಕೆ ಮಾಡಿದ ದೂರವನ್ನು ರೂಪಿಸುವ ಜೋಡಿ ಬಿಂದುಗಳ ಗುಂಪಾಗಿದೆ. ಪರ್ಯಾಯ ಸಂಪರ್ಕ ಯೋಜನೆಗಳು ಸಂಪೂರ್ಣ ಸಂಪರ್ಕ ಕ್ಲಸ್ಟರಿಂಗ್, ಸರಾಸರಿ ಸಂಪರ್ಕ ಕ್ಲಸ್ಟರಿಂಗ್ (ಯುಪಿಜಿಎಂಎ ಮತ್ತು ಡಬ್ಲ್ಯುಪಿಜಿಎಂಎ) ಮತ್ತು ವಾರ್ಡ್ನ ವಿಧಾನವನ್ನು ಒಳಗೊಂಡಿವೆ. ಅಗ್ಲೋಮೆರೇಟಿವ್ ಕ್ಲಸ್ಟರಿಂಗ್ಗಾಗಿ ನೈವ್ ಅಲ್ಗಾರಿದಮ್ನಲ್ಲಿ, ಅಲ್ಗಾರಿದಮ್ನಲ್ಲಿನ ಅಂತರ-ಕ್ಲಸ್ಟರ್ ದೂರಗಳನ್ನು ಲೆಕ್ಕಹಾಕಲು ಬೇರೆ ಸೂತ್ರವನ್ನು ಬಳಸುವ ಮೂಲಕ ವಿಭಿನ್ನ ಸಂಪರ್ಕ ಯೋಜನೆಯನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸಬಹುದು. ಸರಿಹೊಂದಿಸಬೇಕಾದ ಸೂತ್ರವನ್ನು ಮೇಲಿನ ಅಲ್ಗಾರಿದಮ್ ವಿವರಣೆಯಲ್ಲಿ ದಪ್ಪ ಪಠ್ಯವನ್ನು ಬಳಸಿಕೊಂಡು ಹೈಲೈಟ್ ಮಾಡಲಾಗಿದೆ. ಆದಾಗ್ಯೂ, ಕೆಳಗೆ ವಿವರಿಸಿದಂತಹ ಹೆಚ್ಚು ಪರಿಣಾಮಕಾರಿ ಕ್ರಮಾವಳಿಗಳು ಎಲ್ಲಾ ಸಂಪರ್ಕ ಯೋಜನೆಗಳಿಗೆ ಒಂದೇ ರೀತಿಯಲ್ಲಿ ಸಾಮಾನ್ಯೀಕರಿಸುವುದಿಲ್ಲ. ಸಿಂಗಲ್-ಲಿಂಕೇಜ್ ಕ್ಲಸ್ಟರಿಂಗ್ಗಾಗಿ ನಿಷ್ಕಪಟ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಅರ್ಥಮಾಡಿಕೊಳ್ಳುವುದು ಸುಲಭ ಆದರೆ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯೊಂದಿಗೆ ನಿಧಾನವಾಗಿರುತ್ತದೆ. 1973ರಲ್ಲಿ, ಆರ್. ಸಿಬ್ಸನ್ ಅವರು ಸಮಯದ ಸಂಕೀರ್ಣತೆ ಮತ್ತು ಬಾಹ್ಯಾಕಾಶದ ಸಂಕೀರ್ಣತೆ (ಎರಡೂ ಸೂಕ್ತವಾದವು) ಹೊಂದಿರುವ ಒಂದು ಕ್ರಮಾವಳಿಯನ್ನು ಪ್ರಸ್ತಾಪಿಸಿದರು, ಇದನ್ನು ಸ್ಲಿಂಕ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಸ್ಲಿಂಕ್ ಅಲ್ಗಾರಿದಮ್ ಎರಡು ಕಾರ್ಯಗಳಿಂದ ಸಂಖ್ಯೆಯ ವಸ್ತುಗಳ ಗುಂಪಿನ ಮೇಲೆ ಕ್ಲಸ್ಟರಿಂಗ್ ಅನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ. ಐಟಂ ಮತ್ತು ಕನಿಷ್ಠ ಒಂದು ದೊಡ್ಡ ಸಂಖ್ಯೆಯ ಐಟಂ ಎರಡನ್ನೂ ಒಳಗೊಂಡಿರುವ ಚಿಕ್ಕ ಕ್ಲಸ್ಟರ್ ಅನ್ನು ಕಂಡುಹಿಡಿಯುವ ಮೂಲಕ ಈ ಕಾರ್ಯಗಳನ್ನು ನಿರ್ಧರಿಸಲಾಗುತ್ತದೆ. ಮೊದಲ ಕಾರ್ಯವು, ಕ್ಲಸ್ಟರ್ನಲ್ಲಿನ ಅತಿದೊಡ್ಡ ಸಂಖ್ಯೆಯ ವಸ್ತುವಿಗೆ ಐಟಂ ಅನ್ನು ನಕ್ಷೆ ಮಾಡುತ್ತದೆ. ಎರಡನೇ ಕಾರ್ಯವು, ಕ್ಲಸ್ಟರ್ ಸೃಷ್ಟಿಗೆ ಸಂಬಂಧಿಸಿದ ದೂರಕ್ಕೆ ಐಟಂ ಅನ್ನು ನಕ್ಷೆ ಮಾಡುತ್ತದೆ. ಪ್ರತಿ ಐಟಂ ಸಂಖ್ಯೆಯನ್ನು ಅದರ ಕಾರ್ಯ ಮೌಲ್ಯಕ್ಕೆ ಮ್ಯಾಪ್ ಮಾಡುವ ಎರಡು ಸರಣಿಗಳಲ್ಲಿ ಈ ಕಾರ್ಯಗಳನ್ನು ಸಂಗ್ರಹಿಸುವುದು ಸ್ಥಳವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ ಮತ್ತು ಕ್ಲಸ್ಟರಿಂಗ್ ಅನ್ನು ಸ್ವತಃ ನಿರ್ಧರಿಸಲು ಈ ಮಾಹಿತಿಯು ಸಾಕಾಗುತ್ತದೆ. ಸಿಬ್ಸನ್ ತೋರಿಸಿದಂತೆ, ವಸ್ತುಗಳ ಗುಂಪಿಗೆ ಹೊಸ ವಸ್ತುವನ್ನು ಸೇರಿಸಿದಾಗ, ವರ್ಧಿತ ಗುಂಪಿಗೆ ಹೊಸ ಏಕ-ಸಂಪರ್ಕ ಕ್ಲಸ್ಟರಿಂಗ್ ಅನ್ನು ಪ್ರತಿನಿಧಿಸುವ ನವೀಕರಿಸಿದ ಕಾರ್ಯಗಳನ್ನು, ಅದೇ ರೀತಿಯಲ್ಲಿ ಪ್ರತಿನಿಧಿಸಲಾಗುತ್ತದೆ, ಹಳೆಯ ಕ್ಲಸ್ಟರಿಂಗ್ನಿಂದ ಸಮಯಕ್ಕೆ ನಿರ್ಮಿಸಬಹುದು. ಸ್ಲಿಂಕ್ ಅಲ್ಗಾರಿದಮ್ ನಂತರ ವಸ್ತುಗಳ ಮೇಲೆ ಒಂದೊಂದಾಗಿ ಲೂಪ್ ಮಾಡುತ್ತದೆ, ಅವುಗಳನ್ನು ಕ್ಲಸ್ಟರಿಂಗ್ನ ಪ್ರಾತಿನಿಧ್ಯಕ್ಕೆ ಸೇರಿಸುತ್ತದೆ. ಒಂದೇ ಸೂಕ್ತವಾದ ಸಮಯ ಮತ್ತು ಸ್ಥಳದ ಮಿತಿಯಲ್ಲಿ ಚಾಲನೆಯಲ್ಲಿರುವ ಪರ್ಯಾಯ ಅಲ್ಗಾರಿದಮ್, ಕನಿಷ್ಠ ವಿಸ್ತಾರವಾದ ಮರಗಳಿಗೆ ನಿಷ್ಕಪಟ ಅಲ್ಗಾರಿದಮ್ ಮತ್ತು ಕ್ರುಸ್ಕಲ್ನ ಅಲ್ಗಾರಿದಮ್ನ ನಡುವಿನ ಸಮಾನತೆಯನ್ನು ಆಧರಿಸಿದೆ. ಕ್ರುಸ್ಕಲ್ನ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಬಳಸುವ ಬದಲು, ಪ್ರೈಮ್ನ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಬೈನರಿ ರಾಶಿಗಳಿಲ್ಲದ ವ್ಯತ್ಯಾಸದಲ್ಲಿ ಬಳಸಬಹುದು, ಇದು ನಿರ್ದಿಷ್ಟ ವಸ್ತುಗಳು ಮತ್ತು ದೂರಗಳ ಕನಿಷ್ಠ ಸ್ಪ್ಯಾನಿಂಗ್ ಟ್ರೀ ಅನ್ನು (ಆದರೆ ಕ್ಲಸ್ಟರಿಂಗ್ ಅಲ್ಲ) ನಿರ್ಮಿಸಲು ಸಮಯ ಮತ್ತು ಸ್ಥಳವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ. ನಂತರ, ಕನಿಷ್ಠ ವಿಸ್ತಾರವಾದ ಮರದ ಅಂಚುಗಳಿಂದ ರೂಪುಗೊಂಡ ವಿರಳ ಗ್ರಾಫ್ಗೆ ಕ್ರುಸ್ಕಲ್ನ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಅನ್ವಯಿಸುವುದರಿಂದ ಹೆಚ್ಚುವರಿ ಸಮಯ ಮತ್ತು ಜಾಗದಲ್ಲಿ ಕ್ಲಸ್ಟರಿಂಗ್ ಅನ್ನು ಉತ್ಪಾದಿಸುತ್ತದೆ. ಕ್ಲಸ್ಟರ್ ವಿಶ್ಲೇಷಣೆಯನ್ನು ಸಹ ನೋಡಿ ಕಂಪ್ಲೀಟ್-ಲಿಂಕೇಜ್ ಕ್ಲಸ್ಟರಿಂಗ್ ಕ್ರಮಾನುಗತ ಕ್ಲಸ್ಟರಿಂಗ್ ಆಣ್ವಿಕ ಗಡಿಯಾರ ನೆರೆಹೊರೆಯವರು-ಸೇರುವ ಯುಪಿಜಿಎಂಎ ಡಬ್ಲ್ಯುಪಿಜಿಎಂಎ ಉಲ್ಲೇಖಗಳು ಮ್ಯಾಟ್ಲ್ಯಾಬ್ ಕ್ಲಸ್ಟರ್ ವಿಶ್ಲೇಷಣೆ ಕ್ರಮಾವಳಿಗಳಲ್ಲಿ ಬಳಸುವ ಬಾಹ್ಯ ಕೊಂಡಿಗಳು